From low-distortion embeddings to information locking


Hayden, P. (2010). From low-distortion embeddings to information locking. Perimeter Institute. https://pirsa.org/10110074


Hayden, Patrick. From low-distortion embeddings to information locking. Perimeter Institute, Nov. 24, 2010, https://pirsa.org/10110074


          @misc{ pirsa_10110074,
            doi = {10.48660/10110074},
            url = {https://pirsa.org/10110074},
            author = {Hayden, Patrick},
            keywords = {Quantum Information},
            language = {en},
            title = {From low-distortion embeddings to information locking},
            publisher = {Perimeter Institute},
            year = {2010},
            month = {nov},
            note = {PIRSA:10110074 see, \url{https://pirsa.org}}

Patrick Hayden Stanford University


I'll describe a connection between uncertainty relations, information locking and low-distortion embeddings of L2 into L1. Exploiting this connection leads to the first explicit construction of entropic uncertainty relations for a number of measurements that is polylogarithmic in the dimension d while achieving an average measurement entropy of (1-e) log d for arbitrarily small e. From there, it is straightforward to obtain the first strong information locking scheme that is efficiently computable using a quantum computer. This locking scheme can be interpreted as a method for encrypting classical messages using a key of size much smaller than the message length. Other applications include efficient encodings for amortized quantum identification over classical channels and new string commitment protocols.