TY - JOUR
T1 - Classical cryptographic protocols in a quantum world
AU - Hallgren, Sean
AU - Smith, Adam
AU - Song, Fang
N1 - Funding Information:
We would like to thank anonymous reviewers for valuable comments. This work was informed by insightful discussions with many colleagues, notably Michael Ben-Or, Daniel Gottesman, Claude Crépeau, Ivan Damgård and Scott Aaronson. Several of the results were obtained while A.S. was at the Institute for Pure and Applied Mathematics (IPAM) at UCLA in the fall of 2006. He gratefully acknowledges Ra¯ Ostrovksy and the IPAM sta® for making his stay there pleasant and productive. Sean Hallgren partially supported by National Science Foundation award CCF-0747274 and by the National Security Agency (NSA) under Army Research O±ce (ARO) Contract No. W911NF-08-1-0298. Adam Smith partially supported by National Science Foundation award CCF-0747294. Fang Song partially supported by Cryptoworks21, NSERC, ORF and US ARO. Most work was conducted while at the Pennsylvania State University.
Publisher Copyright:
© 2015 World Scientific Publishing Company.
PY - 2015/6/26
Y1 - 2015/6/26
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84932644623&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84932644623&partnerID=8YFLogxK
U2 - 10.1142/S0219749915500288
DO - 10.1142/S0219749915500288
M3 - Article
AN - SCOPUS:84932644623
SN - 0219-7499
VL - 13
JO - International Journal of Quantum Information
JF - International Journal of Quantum Information
IS - 4
M1 - 1550028
ER -