Universally composable oblivious transfer from ideal lattice

Abstract

As a fundamental cryptographic primitive, oblivious transfer (OT) is developed for the sake of efficient usability and combinational feasibility. However, most OT protocols are built upon some quantum non-immune cryptosystems by assuming the hardness of discrete logarithm or factoring problem, whose security will break down directly in the quantum setting. Therefore, as a subarea of postquantum cryptography, lattice-based cryptography is viewed as a promising alternative and cornerstone to support for building post-quantum protocols since it enjoys some attractive properties, such as provable security against quantum adversaries and lower asymptotic complexity.

In this paper, we first build an efficient 1-out-of-2 OT protocol upon the hardness of ring learning with errors (RLWE) problem, which is at least as hard as some worst-case ideal lattice problems. We show that this 1-out-of-2 OT protocol can be universally composable and secure against static corruptions in the random oracle model. Then we extend it to a general case, i.e., 1-out-of-N OT with achieving the same level of security. Furthermore, on the basis of the above OT structure, we obtain two improved OT protocols using two improved lattice-based key exchange protocols (respectively relying on the RLWE problem and learning with errors (LWE) problem, and both achieving better efficiency by removing the Gaussian sampling for saving cost) as building blocks. To show that our proposed OT protocol indeed achieves comparable security and efficiency, we make a comparison with another two lattice-based OT protocols in the end of the paper.

With concerning on the potential threat from quantum computing and expecting on the practical use of OT with high efficiency, an efficient post-quantum OT protocol is pressing needed. As shown in this paper, our proposed OT protocols may be considered as post-quantumOT candidates since they can both preserve provable security relying on lattice problems and enjoy practical efficiency.

Keywords

oblivious transfer / universally composability / lattice-based cryptography / learning with errors / ring learning with errors / random oracle model

References

[1] Rabin M O. How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive, 2005, 2005: 187

[2] Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts. Communications of the ACM, 1985, 28(6): 637–647

[3] Kilian J. Founding crytpography on oblivious transfer. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 20–31

[4] Nielsen J B, Nordholt P S, Orlandi C, Burra S S. A new approach to practical active-secure two-party computation. In: Proceedings of the 32nd Annual International Cryptology Conference. 2012, 681–700

[5] Burra S S, Larraia E, Nielsen J B, Nordholt P S, Orlandi C, Orsini E, Scholl P, Smart N P. High performance multi-party computation for binary circuits based on oblivious transfer. IACR Cryptology ePrint Archive, 2015, 2015: 472

[6] Bellare M, Micali S. Non-interactive oblivious transfer and applications. In: Proceedings of the 9th CRYPTO Meeting. 1989, 547–557

[7] Naor M, Pinkas B. Efficient oblivious transfer protocols. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001, 448–457

[8] Damgård I, Nielsen J B, Orlandi C. Essentially optimal universally composable oblivious transfer. In: Proceedings of the 11th International Conference on Information Security and Cryptology. 2008, 318–335

[9] Lindell A Y. Efficient fully-simulatable oblivious transfer. In: Proceedings of the Cryptographers’ Track at the RSA Conference. 2008, 52–70

[10] Lindell Y. How to simulate it-a tutorial on the simulation proof technique. IACR Cryptology ePrint Archive, 2016, 2016: 46

[11] Canetti R. Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 2001, 136–145

[12] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303–332

[13] Bernstein D J. Post-quantum Cryptography. Encyclopedia of Cryptography and Security, Springer, Boston, MA, 2011, 949–950

[14] Micciancio D. Lattice-based Cryptography. Encyclopedia of Cryptography an Security. Springer, Boston, MA, 2011, 713–715

[15] Peikert C. Some recent progress in lattice-based cryptography. In: Proceedings of the 6th Theory of Cryptography Conference. 2009, 72

[16] Sendrier N. Code-based Cryptography. Encyclopedia of Cryptography and Security. Springer, Boston, MA, 2011, 215–216

[17] Zhang J, Zhang Z, Ding J, Snook M, Dagdelen Ö. Authenticated key exchange from ideal lattices. In: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2015, 719–751

[18] Krawczyk H. HMQV: a high-performance secure Diffie-Hellman protocol. In: Proceedings of the 25th Annual International Cryptology Conference. 2005, 546–566

[19] Chou T, Orlandi C. The simplest protocol for oblivious transfer. In: Proceedings of the 4th International Conference on Cryptology and Information Security. 2015, 40–58

[20] Ding J, Xie X, Lin X. A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive, 2012, 2012: 688

[21] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 2009, 56(6): 34

[22] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2010, 1–23

[23] Dowsley R, van de Graaf J, Müller-Quade J, Nascimento A C A. Oblivious transfer based on the McEliece assumptions. In: Proceedings of the 3rd International Conference on Information Theoretic Security. 2008, 107–117

[24] Kobara K, Morozov K, Overbeck R. Coding-based Oblivious Transfer. Mathematical Methods in Computer Science, Springer, Berlin, Heidelberg, 2008, 142–156

[25] David B M, Nascimento A C A, Nogueira R B. Oblivious transfer based on the mceliece assumptions with unconditional security for the sender. In: Proceedings of X Simposio Brasileiro de Segurança da Informaç ao e de Sistemas Computacionais. 2010

[26] Vasant S, Venkatesan S, Rangan C P. A code-based 1-out-of-N oblivious transfer based on mceliece assumptions. In: Proceedings of the 8th International Conference on Information Security Practice and Experience. 2012, 144–157

[27] David B M, Nascimento A C A, De Sousa R T. Efficient fully simulatable oblivious transfer from the mceliece assumptions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012, 95(11): 2059–2066

[28] McEliece R J. A public-key cryptosystem based on algebraic. Coding Thv, 1978, 4244: 114–116

[29] David B M, Nascimento A C A, Müller-Quade J. Universally composable oblivious transfer from lossy encryption and the mceliece assumptions. In: Proceedings of the 6th International Conference on Information Theoretic Security. 2012, 80–99

[30] Peikert C, Vaikuntanathan V, Waters B. A framework for efficient and composable oblivious transfer. In: Proceedings of the 28th Annual International Cryptology Conference. 2008, 554–571

[31] Lyubashevsky V, Palacio A, Segev G. Public-key cryptographic primitives provably as secure as subset sum. In: Proceedings of the 7th Theory of Cryptography Conference. 2010, 382–400

[32] Crépeau C, Kazmi R A. Oblivious transfer from weakly random selfreducible public-key cryptosystem. In: Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science. 2015, 261–273

[33] Zeng B, Tang X, Hsu C. A framework for fully-simulatable h-out-of-noblivious transfer. 2010, arXiv preprint arXiv:1005.0043

[34] Blazy O, Chevalier C. Generic construction of uc-secure oblivious transfer. In: Proceedings of the 13th International Conference on Applied Cryptography and Network Security. 2015, 65–86

[35] Peikert C. Lattice cryptography for the internet. In: Proceedings of the 6th International Workshop on Post-Quantum Cryptography. 2014, 197–219

[36] Bos J W, Costello C, Naehrig M, Stebila D. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: Proceedings of 2015 IEEE Symposium on Security and Privacy. 2015, 553–570

[37] Lyubashevsky V, Peikert C, Regev O. A toolkit for ring-LWE cryptography. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 35–54

[38] Nisan N, Zuckerman D. Randomness is linear in space. Journal of Computer and System Sciences, 1996, 52(1): 43–52

[39] Canetti R, Friege U, Goldreich O, Naor M. Adaptively secure multiparty computation. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 639–648

[40] Fluhrer S R. Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptology ePrint Archive, 2016, 2016: 85

[41] Ding J, Alsayigh S, Saraswathy R V, Fluhrer S. Leakage of signal function with reused keys in RLWE key exchange. IACR Cryptology ePrint Archive, 2016, 2016: 1176

[42] Alkim E, Ducas L, Pöppelmann T, Schwabe P. Post-quantum key exchange-a new hope. IACR Cryptology ePrint Archive, 2015, 2015: 1092

[43] Ding J, Alsayigh S, Lancrenon J, Saraswathy , R V, Snook M. Provably secure password authenticated key exchange based on RLWE for the post-quantum world. In: Proceedings of the Cryptographers’ Track at the RSA Conference. 2017, 183–204

[44] Pritzker P, Gallagher P D. SHA-3 standard: permutation-based hash and extendable-output functions. Information Tech Laboratory National Institute of Standards and Technology, 2014, 1–35

[45] Brakerski Z, Langlois A, Peikert C, Regev O, Stehlé D. Classical hard ness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 2013, 575–584

[46] Bos J, Costello C, Ducas L, Mironov I, Naehrig M, Nikolaenko V, Raghunathan A, Stebila D. Frodo: take off the ring! practical, quantum-secure key exchange from LWE. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1006–1018

[47] Garay J A, Wichs D, Zhou H S. Somewhat non-committing encryption and efficient adaptively secure oblivious transfer. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 505–523

[48] Farshim P, Orlandi C, Rosie R. Security of symmetric primitives under incorrect usage of keys. IACR Transactions on Symmetric Cryptology, 2017, 2017(1): 449–473

[49] Abdalla M, Bellare M, Neven G. Robust encryption. In: Proceedings of the 7th Theory of Cryptography Conference. 2010, 480–497

[50] Farshim P, Libert B, Paterson K G, Quaglia E A. Robust encryption, revisited. In: Proceedings of the 16th International Conference on Practice and Theory in Public-Key Cryptography. 2013, 352–368

[51] Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. In: Proceedings of the Cryptographers’ Track at the RSA Conference. 2011, 319–339

[52] Laarhoven T, Mosca M, Van De Pol J. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 2015, 77(2–3): 375–400

[53] Peikert C. An efficient and parallel Gaussian sampler for lattices. In: Proceddings of the 30th Annual Cryptology Conference. 2010, 80–97

[54] Albrecht M R, Player R, Scott S. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 2015, 9(3): 169–203

[55] Damgård I, Nielsen J B. Adaptive versus static security in the UC model. In: Proceedings of the 8th International Conference on Provable Security. 2014, 10–28

RIGHTS & PERMISSIONS

2018 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature