|
|
Universally composable oblivious transfer from ideal lattice |
Momeng LIU( ), Yupu HU |
State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 710071, China |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|