×

Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency. (English) Zbl 1469.94114

Summary: Middle-product learning with errors \((\mathsf{MP} \text{- }\mathsf{LWE})\) is a variant of the \(\mathsf{LWE}\) problem introduced by M. Roşca et al. [Lect. Notes Comput. Sci. 10403, 283–297 (2017; Zbl 1406.94078)]. Asymptotically, the theoretical results of Rosca et al. [loc. cit.] suggest that \(\mathsf{MP} \text{- }\mathsf{LWE}\) gives lattice-based public-key cryptosystems offering a ‘security-risk vs. efficiency’ trade-off: higher performance than cryptosystems based on unstructured lattices \((\mathsf{LWE}\) problem) and lower risk than cryptosystems based on structured lattices (Polynomial/Ring \(\mathsf{LWE}\) problem). However, although promising in theory, Rosca et al. [loc. cit.] left the practical implications of \(\mathsf{MP} \text{- }\mathsf{LWE}\) for lattice-based cryptography unclear. In this paper, we show how to build practical public-key cryptosystems with strong security guarantees based on \(\mathsf{MP} \text{- }\mathsf{LWE}\). On the implementation side, we present optimised fast algorithms for computing the middle-product operation over polynomial rings \({\mathbb{Z}}_q[x]\), the dominant computation for \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based cryptosystems. On the security side, we show how to obtain a nearly tight security proof for \(\mathsf{MP} \text{- }\mathsf{LWE}\) from the hardest Polynomial LWE problem over a large family of rings, improving on the loose reduction of Rosca et al. [loc. cit.]. We also show and analyze an optimised cryptanalysis of \(\mathsf{MP} \text{- }\mathsf{LWE}\) that narrows the complexity gap between best known attacks on \(\mathsf{MP} \text{- }\mathsf{LWE}\) and Polynomial \(\mathsf{LWE}\). To evaluate the practicality of \(\mathsf{MP} \text{- }\mathsf{LWE}\), we apply our results to construct, implement and optimise parameters for a practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based public-key cryptosystem, \(\mathsf{Titanium}\), and compare its benchmarks to other lattice-based systems. Our results show that \(\mathsf{MP} \text{- }\mathsf{LWE}\) offers a new ‘security-risk vs. efficiency’ trade-off in lattice-based cryptography in practice, not only asymptotically in theory.

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1406.94078

Software:

FrodoKEM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albrecht, Martin R.; Deo, Amit, Large Modulus Ring-LWE \[\ge \] ≥ Module-LWE, 267-296 (2017), Cham · Zbl 1420.94033 · doi:10.1007/978-3-319-70694-8_10
[2] Albrecht, Martin R.; Fitzpatrick, Robert; Göpfert, Florian, On the Efficacy of Solving LWE by Reduction to Unique-SVP, 293-310 (2014), Cham · Zbl 1368.94082
[3] Alkim E., Ducas L., Pöppelmann T., Schwabe P.: Post-quantum key exchange—a new hope. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, 10-12 August 2016, pp. 327-343 (2016).
[4] Alkim E., Bos JW., Ducas L., Longa P., Mironov I., Naehrig M., Nikolaenko V., Peikert C., Raghunathan A., Stebila D., Easterbrook K., LaMacchia B.: FrodoKEM learning with errors key encapsulation. https://frodokem.org/files/FrodoKEM-specification-20171130.pdf (2017).
[5] Bernstein D.J., Chuengsatiansup C., Lange T., van Vredendaal C.: NTRU Prime. Cryptology ePrint Archive. http://eprint.iacr.org/2016/461 (2016).
[6] Bos J.W., 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, Vienna, Austria, 24-28 Oct 2016, pp. 1006-1018 (2016).
[7] Bos J.W., Ducas L., Kiltz E., Lepoint T., Lyubashevsky V., Schanck J.M., Schwabe P., Stehlé D.: CRYSTALS—kyber: a cca-secure module-lattice-based KEM. IACR Cryptology ePrint Archive 2017, 634 (2017).
[8] Boucheron S., Lugosi G., Massart P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013). · Zbl 1337.60003 · doi:10.1093/acprof:oso/9780199535255.001.0001
[9] Brakerski, Z.; Vaikuntanathan, V., Efficient fully homomorphic encryption from (standard) LWE, 97-106 (2011), Washington, DC · Zbl 1292.94038
[10] Castryck, W.; Iliashenko, I.; Vercauteren, F., Provably weak instances of Ring-LWE revisited, 147-167 (2016), Berlin · Zbl 1347.94025
[11] Cramer R., Ducas L., Wesolowski B.: Short Stickelberger class relations and application to Ideal-SVP. Cryptology ePrint Archive. https://eprint.iacr.org/2016/885 (2016). · Zbl 1411.94057
[12] Cramer, R.; Ducas, L.; Peikert, C.; Regev, O., Recovering short generators of principal ideals in cyclotomic rings (2016), Berlin · Zbl 1371.94630
[13] D’Anvers J-P., Karmakar A., Roy S.S., Vercauteren F.: SABER: Mod-LWR based KEM. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/SABER.zip (2017). · Zbl 1423.94065
[14] Dodis Y., Ostrovsky R., Reyzin L., Smith A.D.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97-139 (2008). · Zbl 1165.94326 · doi:10.1137/060651380
[15] Eisenträger, K.; Hallgren, S.; Lauter, K., Weak instances of PLWE (2014), Berlin · Zbl 1336.94045
[16] Elias, Y.; Lauter, KE; Ozman, E.; Stange, KE, Provably weak instances of Ring-LWE (2015), Berlin · Zbl 1336.94046
[17] Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: Advances in Cryptology-CRYPTO’99, 19th Annual International Cryptology Conference, Santa Barbara, CA, USA, 15-19 August, 1999, pp. 537-554 (1999). · Zbl 0942.94019
[18] Hanrot G., Quercia M., Zimmermann P.: The middle product algorithm I. Appl. Algebra Eng. Commun. Comput. 14(6), 415-438 (2004). · Zbl 1064.68094 · doi:10.1007/s00200-003-0144-2
[19] Harvey D.: Faster arithmetic for number-theoretic transforms. J. Symb. Comput. 60, 113-119 (2014). · Zbl 1284.65195 · doi:10.1016/j.jsc.2013.09.002
[20] Hofheinz D., Hövelmanns K., Kiltz E.: A modular analysis of the Fujisaki-Okamoto transformation. Cryptology ePrint Archive, Report 2017/604 (2017). http://eprint.iacr.org/2017/604. · Zbl 1410.94082
[21] Kannan R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415-440 (1987). · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[22] Laarhoven T., Mosca M., van de Pol J.: Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr. 77(2), 375-400 (2015). · Zbl 1356.94069 · doi:10.1007/s10623-015-0067-5
[23] Langlois A., Stehlé D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565-599 (2015). · Zbl 1361.94043 · doi:10.1007/s10623-014-9938-4
[24] Lyubashevsky, V., Digital signatures based on the hardness of ideal lattice problems in all rings, 196-214 (2016), Berlin · Zbl 1407.94141
[25] Lyubashevsky, V.; Micciancio, D., Generalized compact knapsacks are collision resistant, 144-155 (2006), Berlin · Zbl 1133.68353
[26] Lyubashevsky, V.; Peikert, C.; Regev, O., On ideal lattices and learning with errors over rings, 1-23 (2010), Berlin · Zbl 1279.94099
[27] NIST. NIST post-quantum competition. http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/call-for-proposals-final-dec-2016.pdf. Accessed 13 June 2017.
[28] NIST. SHA-3 standard: Permutation-based hash and extendable-output functions. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf. Accessed 29 Sept 2017.
[29] Peikert, Chris, Lattice Cryptography for the Internet, 197-219 (2014), Cham · Zbl 1383.94037 · doi:10.1007/978-3-319-11659-4_12
[30] Peikert, C., How not to instantiate Ring-LWE, No. 9841, 411-430 (2016), Berlin · Zbl 1421.94066
[31] Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC, pp. 84-93 (2005). · Zbl 1192.94106
[32] Regev O.: On lattices, learning with errors, random linear codes, and cryptography. JACM 56, 34 (2009). · Zbl 1325.68101 · doi:10.1145/1568318.1568324
[33] Roşca, M.; Sakzad, A.; Stehlé, D.; Steinfeld, R., Middle-product learning with errors, 283-297 (2017), Berlin · Zbl 1406.94078 · doi:10.1007/978-3-319-63697-9_10
[34] Rosca, M.; Stehlé, D.; Wallet, A., On the ring-lwe and polynomial-lwe problems, No. 2018, 146-173 (2018), Berlin · Zbl 1421.94069
[35] Schnorr C.P.: Lattice Reduction by Random Sampling and Birthday Methods, pp. 145-156. Springer, Berlin (2003). · Zbl 1035.68113
[36] Seiler G.: Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography. https://eprint.iacr.org/2018/039.pdf (2018).
[37] Sorensen H.V., Burrus C.S.: Efficient computation of the DFT with only a subset of input or output points. IEEE Trans. Signal Process. 41(3), 1184-1200 (1993). · Zbl 0775.65019 · doi:10.1109/78.205723
[38] Stehlé, D.; Steinfeld, R.; Tanaka, K.; Xagawa, K., Efficient public key encryption based on ideal lattices, 617-635 (2009), Berlin · Zbl 1267.94132
[39] Steinfeld R., Sakzad A., Zhao R.K.: Titanium: post-quantum public-key encryption and Kem algorithms. http://users.monash.edu.au/ rste/Titanium.html. Accessed 1 May 2018.
[40] Steinfeld R., Sakzad A., Zhao R.K.: Titanium: post-quantum public-key encryption and Kem algorithms. NIST PQC Standardisation Process submission. Accessed 1 May 2018.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.