Small pseudo-random families of matrices: Derandomizing approximate quantum encryption

DOI10.1007/978-3-540-27821-4_23MaRDI QIDQ5313028zbMATH OpenOpenAlexFDO

Authors Andris Ambainis, Adam Smith

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0404075

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Quantum computation (81P68) Cryptography (94A60)

Abstract: A quantum encryption scheme (also called private quantum channel, or state randomization protocol) is a one-time pad for quantum messages. If two parties share a classical random string, one of them can transmit a quantum state to the other so that an eavesdropper gets little or no information about the state being transmitted. Perfect encryption schemes leak no information at all about the message. Approximate encryption schemes leak a non-zero (though small) amount of information but require a shorter shared random key. Approximate schemes with short keys have been shown to have a number of applications in quantum cryptography and information theory. This paper provides the first deterministic, polynomial-time constructions of quantum approximate encryption schemes with short keys. Previous constructions (quant-ph/0307104) are probabilistic--that is, they show that if the operators used for encryption are chosen at random, then with high probability the resulting protocol will be a secure encryption scheme. Moreover, the resulting protocol descriptions are exponentially long. Our protocols use keys of the same length as (or better length than) the probabilistic constructions; to encrypt $n$ qubits approximately, one needs $n+o(n)$ bits of shared key. An additional contribution of this paper is a connection between classical combinatorial derandomization and constructions of pseudo-random matrix families in a continuous space.

Recommendations

• Approximate Randomization of Quantum States With Fewer Bits of Key
• On the Power of Quantum Encryption Keys
• Randomizing quantum states: constructions and applications
• On the optimality of quantum encryption schemes
• Cryptography from pseudorandom quantum states

Cited in

(19)

• Entropic security in quantum cryptography
• Random quantum circuits are approximate 2-designs
• Randomizing quantum states: constructions and applications
• On the mixed-unitary rank of quantum channels
• Quantum encryption and generalized Shannon impossibility
• Counterexamples to the maximal \(p\)-norm multiplicativity conjecture for all \(p>1\)
• On the optimality of quantum encryption schemes
• On the Power of Quantum Encryption Keys
• Nonmalleable encryption of quantum information
• Symmetric quantum fully homomorphic encryption with perfect security
• Approximate Randomization of Quantum States With Fewer Bits of Key
• Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker
• Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Entropically secure encryption with faster key expansion
• A note on quantum expanders
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Quantum expanders and quantifier reduction for tracial von Neumann algebras
• Secure sequential transmission of quantum information
• On almost randomizing channels with a short Kraus decomposition

This page was built for publication: Small pseudo-random families of matrices: Derandomizing approximate quantum encryption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5313028)