Fast Scramblers: from Black Holes to Computation on Encrypted Data

Tue, Nov 16, 2021, 12:30 pm
Joseph Henry Room

We examine the scrambling speed of random reversible classical circuits with long-range gates. In particular, we ask the following question: how short can a classical reversible circuit be and still represent ciphers that cannot be distinguished from a random permutation with a polynomial number of queries. To address this question, we cast encryption via classical ciphers in terms of operator spreading in a dual space of Pauli strings, a formulation which allows us to characterize classical ciphers by using tools well known in the analysis of quantum many-body systems. We connect plaintext and ciphertext attacks to out-of-time order correlators (OTOCs) and quantify the quality of ciphers using measures of delocalization in string space such as participation ratios and corresponding entropies obtained from the wave function amplitudes in string space. These results carry over to random quantum circuits and inform us on the structure required in order that such circuits scramble as fast as a Black Hole. More interesting from a practical point of view is that such short ciphers enable an efficient (polynomial) scheme for computing directly on encrypted data, a physics-inspired alternative to homomorphic encryption.