Classical Cryptographic Protocols in a Quantum World

Abstract

Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: what classical protocols remain secure against quantum attackers? Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.

Full version of an old paper in Crypto'11. Invited to IJQI. This is authors' copy with different formatting

References in corpus (9)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Unconditionally secure quantum bit commitment is impossible
• Is Quantum Bit Commitment Really Possible?
• Fully device independent quantum key distribution
• Memory effects in quantum channel discrimination
• Security and Composability of Randomness Expansion from Bell Inequalities
• On a measure of distance for quantum strategies

Cited by in corpus (2)

• Zero-knowledge proof systems for QMA
• Composable security in relativistic quantum cryptography