Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2019, Vol. 13 Issue (4) : 879-906    https://doi.org/10.1007/s11704-018-6507-4
RESEARCH ARTICLE
Universally composable oblivious transfer from ideal lattice
Momeng LIU(), Yupu HU
State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 710071, China
 Download: PDF(811 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Momeng LIU   
Just Accepted Date: 25 September 2017   Online First Date: 22 October 2018    Issue Date: 29 May 2019
 Cite this article:   
Momeng LIU,Yupu HU. Universally composable oblivious transfer from ideal lattice[J]. Front. Comput. Sci., 2019, 13(4): 879-906.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-6507-4
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I4/879
1 M ORabin. How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive, 2005, 2005: 187
2 SEven, O Goldreich, ALempel. A randomized protocol for signing contracts. Communications of the ACM, 1985, 28(6): 637–647
https://doi.org/10.1145/3812.3818
3 JKilian. Founding crytpography on oblivious transfer. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 20–31
https://doi.org/10.1145/62212.62215
4 J BNielsen, P S Nordholt, COrlandi, S SBurra. A new approach to practical active-secure two-party computation. In: Proceedings of the 32nd Annual International Cryptology Conference. 2012, 681–700
https://doi.org/10.1007/978-3-642-32009-5_40
5 S SBurra, E Larraia, J BNielsen, P SNordholt, C Orlandi, EOrsini, PScholl, N PSmart. High performance multi-party computation for binary circuits based on oblivious transfer. IACR Cryptology ePrint Archive, 2015, 2015: 472
6 MBellare, SMicali. Non-interactive oblivious transfer and applications. In: Proceedings of the 9th CRYPTO Meeting. 1989, 547–557
7 MNaor, BPinkas. Efficient oblivious transfer protocols. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001, 448–457
8 IDamgård, J B Nielsen, COrlandi. Essentially optimal universally composable oblivious transfer. In: Proceedings of the 11th International Conference on Information Security and Cryptology. 2008, 318–335
9 A YLindell. Efficient fully-simulatable oblivious transfer. In: Proceedings of the Cryptographers’ Track at the RSA Conference. 2008, 52–70
10 YLindell. How to simulate it-a tutorial on the simulation proof technique. IACR Cryptology ePrint Archive, 2016, 2016: 46
11 RCanetti. Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 2001, 136–145
https://doi.org/10.1109/SFCS.2001.959888
12 P WShor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999, 41(2): 303–332
https://doi.org/10.1137/S0036144598347011
13 D JBernstein. Post-quantum Cryptography. Encyclopedia of Cryptography and Security, Springer, Boston, MA, 2011, 949–950
14 DMicciancio. Lattice-based Cryptography. Encyclopedia of Cryptography an Security. Springer, Boston, MA, 2011, 713–715
15 CPeikert. Some recent progress in lattice-based cryptography. In: Proceedings of the 6th Theory of Cryptography Conference. 2009, 72
https://doi.org/10.1007/978-3-642-00457-5_5
16 NSendrier. Code-based Cryptography. Encyclopedia of Cryptography and Security. Springer, Boston, MA, 2011, 215–216
17 JZhang, ZZhang, JDing, M Snook, Ö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
https://doi.org/10.1007/978-3-662-46803-6_24
18 HKrawczyk. HMQV: a high-performance secure Diffie-Hellman protocol. In: Proceedings of the 25th Annual International Cryptology Conference. 2005, 546–566
https://doi.org/10.1007/11535218_33
19 TChou, C Orlandi. The simplest protocol for oblivious transfer. In: Proceedings of the 4th International Conference on Cryptology and Information Security. 2015, 40–58
https://doi.org/10.1007/978-3-319-22174-8_3
20 JDing, XXie, XLin. A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive, 2012, 2012: 688
21 ORegev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 2009, 56(6): 34
https://doi.org/10.1145/1568318.1568324
22 VLyubashevsky, C Peikert, ORegev. 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
https://doi.org/10.1007/978-3-642-13190-5_1
23 RDowsley, J van de Graaf, JMüller-Quade, A C ANascimento. Oblivious transfer based on the McEliece assumptions. In: Proceedings of the 3rd International Conference on Information Theoretic Security. 2008, 107–117
https://doi.org/10.1007/978-3-540-85093-9_11
24 KKobara, K Morozov, ROverbeck. Coding-based Oblivious Transfer. Mathematical Methods in Computer Science, Springer, Berlin, Heidelberg, 2008, 142–156
https://doi.org/10.1007/978-3-540-89994-5_12
25 B MDavid, A C A Nascimento, R BNogueira. 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 SVasant, S Venkatesan, C PRangan. 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 B MDavid, A C A Nascimento, R TDe Sousa. Efficient fully simulatable oblivious transfer from the mceliece assumptions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012, 95(11): 2059–2066
https://doi.org/10.1587/transfun.E95.A.2059
28 R JMcEliece. A public-key cryptosystem based on algebraic. Coding Thv, 1978, 4244: 114–116
29 B MDavid, A C A Nascimento, JMüller-Quade. 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
https://doi.org/10.1007/978-3-642-32284-6_5
30 CPeikert, V Vaikuntanathan, BWaters. A framework for efficient and composable oblivious transfer. In: Proceedings of the 28th Annual International Cryptology Conference. 2008, 554–571
https://doi.org/10.1007/978-3-540-85174-5_31
31 VLyubashevsky, A Palacio, GSegev. Public-key cryptographic primitives provably as secure as subset sum. In: Proceedings of the 7th Theory of Cryptography Conference. 2010, 382–400
https://doi.org/10.1007/978-3-642-11799-2_23
32 CCrépeau, R A Kazmi. 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 BZeng, XTang, CHsu. A framework for fully-simulatable h-out-of-noblivious transfer. 2010, arXiv preprint arXiv:1005.0043
34 OBlazy, C Chevalier. Generic construction of uc-secure oblivious transfer. In: Proceedings of the 13th International Conference on Applied Cryptography and Network Security. 2015, 65–86
https://doi.org/10.1007/978-3-319-28166-7_4
35 CPeikert. Lattice cryptography for the internet. In: Proceedings of the 6th International Workshop on Post-Quantum Cryptography. 2014, 197–219
https://doi.org/10.1007/978-3-319-11659-4_12
36 J WBos, C Costello, MNaehrig, DStebila. 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
https://doi.org/10.1109/SP.2015.40
37 VLyubashevsky, C Peikert, ORegev. 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
https://doi.org/10.1007/978-3-642-38348-9_3
38 NNisan, D Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 1996, 52(1): 43–52
https://doi.org/10.1006/jcss.1996.0004
39 RCanetti, UFriege, OGoldreich, M Naor. Adaptively secure multiparty computation. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 639–648
40 S RFluhrer. Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptology ePrint Archive, 2016, 2016: 85
41 JDing, S Alsayigh, R VSaraswathy, SFluhrer. Leakage of signal function with reused keys in RLWE key exchange. IACR Cryptology ePrint Archive, 2016, 2016: 1176
42 EAlkim, LDucas, TPöppelmann, PSchwabe. Post-quantum key exchange-a new hope. IACR Cryptology ePrint Archive, 2015, 2015: 1092
43 JDing, S Alsayigh, JLancrenon, , R VSaraswathy, M Snook. 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 PPritzker, P D Gallagher. SHA-3 standard: permutation-based hash and extendable-output functions. Information Tech Laboratory National Institute of Standards and Technology, 2014, 1–35
45 ZBrakerski, A Langlois, CPeikert, ORegev, D Stehlé. Classical hard ness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 2013, 575–584
46 JBos, C Costello, LDucas, IMironov, M Naehrig, VNikolaenko, ARaghunathan, D Stebila. 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
https://doi.org/10.1145/2976749.2978425
47 J AGaray, DWichs, H SZhou. Somewhat non-committing encryption and efficient adaptively secure oblivious transfer. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 505–523
https://doi.org/10.1007/978-3-642-03356-8_30
48 PFarshim, C Orlandi, RRosie. Security of symmetric primitives under incorrect usage of keys. IACR Transactions on Symmetric Cryptology, 2017, 2017(1): 449–473
49 MAbdalla, M Bellare, GNeven. Robust encryption. In: Proceedings of the 7th Theory of Cryptography Conference. 2010, 480–497
https://doi.org/10.1007/978-3-642-11799-2_28
50 PFarshim, BLibert, K GPaterson, E AQuaglia. Robust encryption, revisited. In: Proceedings of the 16th International Conference on Practice and Theory in Public-Key Cryptography. 2013, 352–368
https://doi.org/10.1007/978-3-642-36362-7_22
51 RLindner, C Peikert. Better key sizes (and attacks) for LWE-based encryption. In: Proceedings of the Cryptographers’ Track at the RSA Conference. 2011, 319–339
52 TLaarhoven, MMosca, JVan De Pol. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 2015, 77(2–3): 375–400
https://doi.org/10.1007/s10623-015-0067-5
53 CPeikert. An efficient and parallel Gaussian sampler for lattices. In: Proceddings of the 30th Annual Cryptology Conference. 2010, 80–97
https://doi.org/10.1007/978-3-642-14623-7_5
54 M RAlbrecht, RPlayer, SScott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 2015, 9(3): 169–203
https://doi.org/10.1515/jmc-2015-0016
55 IDamgård, J B Nielsen. Adaptive versus static security in the UC model. In: Proceedings of the 8th International Conference on Provable Security. 2014, 10–28
https://doi.org/10.1007/978-3-319-12475-9_2
[1] Wei GAO, Guilin WANG, Kefei CHEN, Xueli WANG. Efficient identity-based threshold decryption scheme from bilinear pairings[J]. Front. Comput. Sci., 2018, 12(1): 177-189.
[2] Mingming JIANG,Yupu HU,Hao LEI,Baocang WANG,Qiqi LAI. Lattice-based certificateless encryption scheme[J]. Front. Comput. Sci., 2014, 8(5): 828-836.
[3] Xiuhua LU,Qiaoyan WEN,Zhengping JIN,Licheng WANG,Chunli YANG. A lattice-based signcryption scheme without random oracles[J]. Front. Comput. Sci., 2014, 8(4): 667-675.
[4] Wenbo SHI,Neeraj KUMAR,Peng GONG,Zezhong ZHANG. Cryptanalysis and improvement of a certificateless signcryption scheme without bilinear pairing[J]. Front. Comput. Sci., 2014, 8(4): 656-666.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed