Special Issue: Recent Highlights in Quantum Computer ScienceNo Access

Classical cryptographic protocols in a quantum world

Sean Hallgren

Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA

Search for more papers by this author

Adam Smith

Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA

Search for more papers by this author

, and

Fang Song

Department of Combinatorics & Optimization and Institute for Quantum Computing, University of Waterloo, Canada

Search for more papers by this author

https://doi.org/10.1142/S0219749915500288Cited by:8 (Source: Crossref)

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.

A preliminary version of this work appeared in Advances in Cryptology — CRYPTO 2011.

Keywords:

References

S. Goldwasser , S. Micali and C. Rackoff , SIAM J. Comput. 18 , 186 ( 1989 ) . Crossref, Web of Science, Google Scholar
O. Goldreich , S. Micali and A. Wigderson , J. ACM 38 , 691 ( 1991 ) . Crossref, Web of Science, Google Scholar
P. W. Shor , SIAM J. Comput. 26 , 1484 ( 1997 ) . Crossref, Web of Science, Google Scholar
S. Hallgren , J. ACM 54 , 1 ( 2007 ) . Crossref, Web of Science, Google Scholar
C. Crépeauet al., Two provers in isolation, Advances in Cryptology–ASIACRYPT 2011 (Springer, 2011) pp. 407–430. Google Scholar
J. Watrous, SIAM J. Comput. 39 (2009) 25, Preliminary version in STOC 2006 . Google Scholar
I. Damgård and C. Lunemann, Quantum-secure coin-flipping and applications, ASIACRYPT5912, Lecture Notes in Computer Science, ed. M. Matsui (Springer, 2009) pp. 52–69. Google Scholar
S. Hallgrenet al., Making classical honest verifier zero knowledge protocols secure against quantum attacks, ICALP (2)5126, Lecture Notes in Computer Science, eds. L. Acetoet al. (Springer, 2008) pp. 592–603. Google Scholar
C. Crépeau, D Gottesman and A. Smith, Secure multi-party quantum computation, STOC (ACM, 2002) pp. 643–652. Google Scholar
M. Ben-Oret al., Secure multiparty quantum computation with (only) a strict honest majority, FOCS (IEEE Computer Society, 2006) pp. 249–260. Google Scholar
S. Fehr and C. Schaffner, Composing quantum protocols in a classical environment, TCC5444, Lecture Notes in Computer Science, ed. O. Reingold (Springer, 2009) pp. 350–367. Google Scholar
D. Unruh, Universally composable quantum multi-party computation, EUROCRYPT6110, Lecture Notes in Computer Science, ed. H. Gilbert (Springer, 2010) pp. 486–505. Google Scholar
C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Proc. IEEE Int. Conf. Computers, Systems and Signal Processing (New York, 1984) pp. 175–179. Google Scholar
O. Regev, J. ACM 56 (2009), 34 pp. Preliminary version in STOC 2005 . Google Scholar
C. Crépeauet al., Computational collapse of quantum state with application to oblivious transfer, TCC2951, Lecture Notes in Computer Science, ed. M. Naor (Springer, 2004) pp. 374–393. Google Scholar
I. Damgårdet al., Improving the security of quantum protocols via commit-and-open, CRYPTO5677, Lecture Notes in Computer Science, ed. S. Halevi (Springer, 2009) pp. 408–427. Google Scholar
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, FOCS (IEEE Computer Society, 2001) pp. 136–145. Google Scholar
R. Canetti , J. Cryptology 13 , 143 ( 2000 ) . Crossref, Web of Science, Google Scholar
Y. Lindell , J. Cryptology 16 , 143 ( 2003 ) . Crossref, Web of Science, Google Scholar
D. Unruh, Quantum proofs of knowledge, in Eurocrypt 2012, Volume 7237 of LNCS (Springer, April 2012), pp. 135–152, Preprint on IACR ePrint 2010/212 . Google Scholar
R. Canettiet al., Universally composable two-party and multi-party secure computation, STOC (ACM, 2002) pp. 494–503. Google Scholar
S. Fehret al., Theory of Cryptography (Springer, 2013) pp. 281–296. Crossref, Google Scholar
O. Goldreich, S. Micali and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, STOC, ed. A. V. Aho (ACM, 1987) pp. 218–229. Google Scholar
C. Lunemann and J. B. Nielsen, Fully simulatable quantum-secure coin-flipping and applications, AFRICACRYPT6737, Lecture Notes in Computer Science, eds. A. Nitaj and D. Pointcheval (Springer, 2011) pp. 21–40. Google Scholar
M. Ben-Or and D. Mayers, General security definition and composability for quantum and classical protocols, September 2004 , arXiv:quant-ph/0409062v2 . Google Scholar
D. Unruh, Simulatable security for quantum protocols (2004) , arXiv:quant-ph/0409125v2. . Google Scholar
M. Ben-Oret al., The universal composable security of quantum key distribution, TCC3378, Lecture Notes in Computer Science, ed. J. Kilian (Springer, 2005) pp. 386–406. Google Scholar
U. Maurer and R. Renner , Innovations in Computer Science ( Tsinghua University Press , 2011 ) . Google Scholar
V. Dunjkoet al., Composable security of delegated quantum computation, Advances in Cryptology–ASIACRYPT 2014 (Springer, 2014) pp. 406–425. Google Scholar
D. Mayers , J. ACM 48 , 351 ( 2001 ) . Crossref, Web of Science, Google Scholar
H.-K. Lo and H. F. Chau , Science 283 , 2050 ( 1999 ) . Crossref, Web of Science, Google Scholar
P. W. Shor and J. Preskill , Phys. Rev. Lett. 85 , 441 ( 2000 ) . Crossref, Web of Science, Google Scholar
D. Beaver, On deniability in quantum key exchange, EUROCRYPT2332, Lecture Notes in Computer Science, ed. L. R. Knudsen (Springer, 2002) pp. 352–367. Google Scholar
G. Brassard and C. Crépeau, Quantum bit commitment and coin tossing protocols, CRYPTO537, Lecture Notes in Computer Science, eds. A. Menezes and S. A. Vanstone (Springer, 1990) pp. 49–61. Google Scholar
C. H. Bennettet al., Practical quantum oblivious transfer, CRYPTO576, Lecture Notes in Computer Science, ed. J. Feigenbaum (Springer, 1991) pp. 351–366. Google Scholar
P. Dumais, D. Mayers and L. Salvail, Perfectly concealing quantum bit commitment from any quantum one-way permutation, EUROCRYPT1807, Lecture Notes in Computer Science, ed. B. Preneel (2000) pp. 300–315. Google Scholar
C. Crépeau, D. Gottesman and A. Smith, Approximate quantum error-correcting codes and secret sharing schemes, EUROCRYPT3494, Lecture Notes in Computer Science, ed. R. Cramer (Springer, 2005) pp. 285–301. Google Scholar
F. Dupuis, J. B. Nielsen and L. Salvail, Secure two-party quantum evaluation of unitaries against specious adversaries, Advances in Cryptology–CRYPTO 2010 (Springer, 2010) pp. 685–706. Google Scholar
F. Dupuis, J. B. Nielsen and L. Salvail, Actively secure two-party evaluation of any quantum operation, Advances in Cryptology–CRYPTO 2012 (Springer, 2012) pp. 794–811. Google Scholar
I. Damgård et al. , SIAM J. Comput. 37 , 1865 ( 2008 ) . Crossref, Web of Science, Google Scholar
I. Damgårdet al., Secure identification and qkd in the bounded-quantum-storage model, CRYPTO4622, Lecture Notes in Computer Science, ed. A. Menezes (Springer, 2007) pp. 342–359. Google Scholar
D. Unruh, Concurrent composition in the bounded quantum storage model, EUROCRYPT6632, Lecture Notes in Computer Science, ed. K. G. Paterson (Springer, 2011) pp. 467–486. Google Scholar
S. Fehr , R. Gelles and C. Schaffner , Phys. Rev. A 87 , 012335 ( 2013 ) . Crossref, Web of Science, Google Scholar
U. Vazirani and T. Vidick , Phys. Rev. Lett. 113 , 140501 ( 2014 ) . Crossref, Web of Science, Google Scholar
C. A. Miller and Y. Shi, Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices, Proc. 46th Annual ACM Symp. Theory of Computing (ACM, 2014) pp. 417–426. Google Scholar
K.-M. Chung, Y. Shi and X. Wu, Physical randomness extractors: Generating random numbers with minimal assumptions (2014), [quant-ph]. Presented at QIP'14 , arXiv:1402.4797 . Google Scholar
E. Kushilevitz , Y. Lindell and T. Rabin , SIAM J. Comput. 39 , 2090 ( 2010 ) . Crossref, Web of Science, Google Scholar
M. Bellare and P. Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, EUROCRYPT4004, Lecture Notes in Computer Science, ed. S. Vaudenay (Springer, 2006) pp. 409–426. Google Scholar
R. Canettiet al., Universally composable security with global setup, TCC4392, Lecture Notes in Computer Science, ed. S. P. Vadhan (Springer, 2007) pp. 61–85. Google Scholar
D. Beaver, S. Micali and P. Rogaway, The round complexity of secure protocols (extended abstract), STOC, ed. H. Ortiz (ACM, 1990) pp. 503–513. Google Scholar
R. Pass, Simulation in quasi-polynomial time, and its application to protocol composition, EUROCRYPT2656, Lecture Notes in Computer Science, ed. E. Biham (Springer, 2003) pp. 160–176. Google Scholar
M. Prabhakaran and A. Sahai, New notions of security: Achieving universal composability without trusted setup, STOC, ed. L. Babai (ACM, 2004) pp. 242–251. Google Scholar
B. Barak and A. Sahai, How to play almost any mental game over the net — concurrent composition via super-polynomial simulation, FOCS (IEEE Computer Society, 2005) pp. 543–552. Google Scholar
U. Feige and A. Shamir, Zero knowledge proofs of knowledge in two rounds, CRYPTO435, Lecture Notes in Computer Science, ed. G. Brassard (Springer, 1989) pp. 526–544. Google Scholar
M. A. Nielsen and I. L. Chuang , Quantum Computation and Quantum Information ( Cambridge University Press , 2000 ) . Google Scholar
A. C.-C. Yao, FOCS (IEEE Computer Society, 1993) pp. 352–361. Google Scholar
G. Gutoski and J. Watrous, Toward a general theory of quantum games, Proc. Thirty-Ninth Annual ACM Symp. Theory of Computing, STOC '07 (ACM, New York, NY, USA, 2007) pp. 565–574. Google Scholar
G. Gutoski , J. Math. Phys. 53 , 032202 ( 2012 ) . Crossref, Web of Science, Google Scholar
G. Chiribella , G. M. D'Ariano and P. Perinotti , Phys. Rev. Lett. 101 , 180501 ( 2008 ) . Crossref, Web of Science, Google Scholar
R. Cleve, Limits on the security of coin flips when half the processors are faulty, Proc. Eighteenth Annual ACM Symp. Theory of Computing (ACM, 1986) pp. 364–369. Google Scholar
J. Katz, On achieving the best of both worlds in secure multiparty computation, Proc. Thirty-Ninth Annual ACM Symp. Theory of Computing (ACM, 2007) pp. 11–20. Google Scholar
T. Moran, M. Naor and G. Segev, Theory of Cryptography (Springer, 2009) pp. 1–18. Crossref, Google Scholar
S. D. Gordon et al. , J. ACM (JACM) 58 , 24 ( 2011 ) . Crossref, Web of Science, Google Scholar
H. K. Lo and H. F. Chau , Phys. Rev. Lett. 78 , 3410 ( 1997 ) . Crossref, Web of Science, Google Scholar
D. Mayers , Phys. Rev. Lett. 78 , 3414 ( 1997 ) . Crossref, Web of Science, Google Scholar
G. Gutoski, Personal communication (2013), See also http://pirsa.org/12120028/ . Google Scholar
D. Hofheinz and D. Unruh, Simulatable security and polynomially bounded concurrent composability, IEEE Symp. Security and Privacy (IEEE Computer Society, 2006) pp. 169–183. Google Scholar
Y. Lindell , J. Cryptology 22 , 395 ( 2009 ) . Crossref, Web of Science, Google Scholar
M. Naor , J. Cryptology 4 , 151 ( 1991 ) . Crossref, Google Scholar
O. Goldreich , Foundations of Cryptography 2 ( Cambridge University Press , 2009 ) . Google Scholar
R. Canetti and M. Fischlin, Universally composable commitments, Advances in Cryptology—Crypto 2001 (Springer, 2001) pp. 19–40. Google Scholar
U. Feige and A. Shamir, Witness indistinguishable and witness hiding protocols, Proc. Twenty-Second Annual ACM Symp. Theory of Computing (ACM, 1990) pp. 416–426. Google Scholar
M. Blum, How to prove a theorem so no one else can claim it, Proc. Int. Congress of Mathematicians (American Mathematical Society, 1986) p. 2. Google Scholar