Quantum security analysis of a lattice-based oblivious transfer protocol

Abstract

Because of the concise functionality of oblivious transfer (OT)protocols, they have been widely used as building blocks in securemultiparty computation and high-level protocols. The security of OTprotocols built upon classical number theoretic problems, such asthe discrete logarithm and factoring, however, is threatened as aresult of the huge progress in quantum computing. Therefore, post-quantumcryptography is needed for protocols based on classical problems,and several proposals for post-quantum OT protocols exist. However,most post-quantum cryptosystems present their security proof onlyin the context of classical adversaries, not in the quantum setting.In this paper, we close this gap and prove the security of the lattice-basedOT protocol proposed by Peikert et al. (CRYPTO, 2008), which is universally composably secure under theassumption of learning with errors hardness, in the quantum setting.We apply three general quantum security analysis frameworks. First,we apply the quantum lifting theorem proposed by Unruh (EUROCRYPT,2010) to prove that the security of the lattice-based OT protocolcan be lifted into the quantum world. Then, we apply two more securityanalysis frameworks specified for post-quantum cryptographic primitives,i.e., simple hybrid arguments (CRYPTO, 2011) and game-preserving reduction(PQCrypto, 2014).

Keywords

Oblivious transfer / Post-quantum / Lattice-based / Learning with errors / Universally composable

References

[1] Bernstein , D.J., Buchamann , J., Dahmen , E., 2009. Post-QuantumCryptography. Springer, Berlin. https://doi.org/10.1007/978-3-540-88702-7

[2] Canetti , R., 2001. Universally composable security: anew paradigm for cryptographic protocols. Proc. 42nd IEEE Symp. on Foundations of Computer Science, p.136–145. https://doi.org/10.1109/SFCS.2001.959888

[3] Damgård , I., Funder , J., Nielsen , J.B., , 2014. Superposition attacks on cryptographic protocols. LNCS, 8317:142–161. https://doi.org/10.1007/978-3-319-04268-8_9

[4] Even , S., Goldreich , O., Lempel , A., 1985. A randomizedprotocol for signing contracts. Commun. ACM, 28(6):637–647. https://doi.org/10.1145/3812.3818

[5] Fehr , S., Katz , J., Song , F., , 2013. Feasibilityand completeness of cryptographic tasks in the quantum world. LNCS, 7785:281–296. https://doi.org/10.1007/978-3-642-36594-2_16

[6] Gentry , C., Peikert , C., Vaikuntanathan ,V., 2008. Trapdoors for hard lattices and new cryptographic constructions. Proc. 40th Annual ACM Symp. on Theory of Computing, p.197–206. https://doi.org/10.1145/1374376.1374407

[7] Gilboa , N., 1999. Two party RSA key generation. LNCS, 1666:116–129. https://doi.org/10.1007/3-540-48405-1_8

[8] Hallgren , S., Smith , A., Song , F., 2011. Classical cryptographicprotocols in a quantum world. LNCS, 6841:411–428. https://doi.org/10.1007/978-3-642-22792-9_23

[9] Hallgren , S., Smith , A., Song , F., 2015. Classical cryptographicprotocols in a quantum world. CryptologyePrint Archive, 2015/687. http://eprint.iacr.org/2015/687

[10] Ishai , Y., Kilian , J., Nissim , K., , 2003. Extendingoblivious transfers efficiently.LNCS, 2729:145–161. https://doi.org/10.1007/978-3-540-45146-4_9

[11] Lai , R.W.F., Cheung , H.K.F., Chow , S.S.M., 2014. Trapdoorsfor ideal lattices with applications. LNCS, 8957:239–256. https://doi.org/10.1007/978-3-319-16745-9_14

[12] Lyubashevsky , V., Peikert , C., Regev , O., 2013. On ideallattices and learning with errors over rings. J. ACM, 60(6):43. https://doi.org/10.1145/2535925

[13] Micciancio , D., Regev , O., 2009. Lattice-based cryptography.In: Bernstein, D.J., Buchmann, J., Dahmen, E. (Eds.), Post-Quantum Cryptography. Springer, Berlin, p.147–191. https://doi.org/10.1007/978-3-540-88702-7_5

[14] Nielsen , M.A., Chuang , I.L., 2010. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge.

[15] Peikert , C., 2009. Some recent progress in lattice-basedcryptography. LNCS, 5444:72. https://doi.org/10.1007/978-3-642-00457-5_5

[16] Peikert , C., Vaikuntanathan , V., Waters , B., 2008. A frameworkfor efficient and composable oblivious transfer. LNCS, 5157:554–571. https://doi.org/10.1007/978-3-540-85174-5_31

[17] Rabin , M.O., 1981. How to Exchange Secrets with ObliviousTransfer. Technical Report No. TR-81, AikenComputation Lab, Harvard University, Cambridge, MA.http://eprint.iacr.org/2005/187

[18] Regev , O., 2005. On lattices, learning with errors,random linear codes, and cryptography. Proc.37th Annual ACM Symp. on Theory of Computing, p.84–93. https://doi.org/10.1145/1060590.1060603

[19] Sendrier , N., 2011. Code-based cryptography.In: van Tilborg, H.C.A., Jajodia, S. (Eds.), Encyclopedia of Cryptography and Security.Springer, New York, p.215–216. https://doi.org/10.1007/978-1-4419-5906-5_378

[20] Shor , P.W., 1997. Polynomial-time algorithms for primefactorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509. https://doi.org/10.1137/S0097539795293172

[21] Song , F., 2014. A note on quantum security for post-quantumcryptography. LNCS, 8772:246–265. https://doi.org/10.1007/978-3-319-11659-4_15

[22] Unruh , D., 2010. Universally composable quantum multipartycomputation. LNCS, 6110:486–505. https://doi.org/10.1007/978-3-642-13190-5_25

[23] Unruh , D., 2012. Quantum proofs of knowledge. LNCS, 7237:135–152. https://doi.org/10.1007/978-3-642-29011-4_10

[24] Watrous , J., 2009. Zero-knowledge against quantum attacks. SIAM J. Comput., 39(1):25–58. https://doi.org/10.1137/060670997

[25] Zhandry , M., 2012. How to construct quantum random functions. IEEE 53rd Annual Symp. on Foundations of ComputerScience, p.679–687. https://doi.org/10.1109/FOCS.2012.37

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbHGermany