main-content

Published in:

24-11-2021

# LWE from non-commutative group rings

Authors: Qi Cheng, Jun Zhang, Jincheng Zhuang

Published in: Designs, Codes and Cryptography | Issue 1/2022

## Abstract

The Learning-With-Errors (LWE) problem (and its variants including Ring-LWE and Module-LWE), whose security are based on hard ideal lattice problems, has proven to be a promising primitive with diverse applications in cryptography. For the sake of expanding sources for constructing LWE, we study the LWE problem on group rings in this work. One can regard the Ring-LWE on cyclotomic integers as a special case when the underlying group is cyclic, while our proposal utilizes non-commutative groups. In particular, we show how to build public key encryption schemes from dihedral group rings, while maintaining the efficiency of the Ring-LWE. We prove that the PKC system is semantically secure, by providing a reduction from the SIVP problem of group ring ideal lattice to the decisional group ring LWE problem. It turns out that irreducible representations of groups play important roles here. We believe that the introduction of the representation view point enriches the tool set for studying the Ring-LWE problem.
Literature
1.
Agrawal S., Boneh D., Boyen X.: Efficient lattice (H)IBE in the standard model. Adv. Cryptol. EUROCRYPT 2010, 553–572 (2010).
2.
Agrawal S., Boneh D., Boyen X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Adv. Cryptol. CRYPTO 2010, 98–115 (2010).
3.
Albrecht M.R., Deo A.: Large modulus Ring-LWE $$\ge$$ module-LWE. In: Advances in Cryptology—ASIACRYPT, Volume 10624 of Lecture Notes in Computer Science, pp. 267–296. Springer (2017)
4.
Alexei G., Myasnikov V.S., Alexander U.: American Mathematical Society, Non-commutative Cryptography and Complexity of Group-theoretic Problems (2011)
5.
Banaszczyk W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–636 (1993).
6.
Bootland C.,Castryck W., Vercauteren F.: On the security of the multivariate ring learning with errors problem. In: ANTS-XIV, Fourteenth Algorithmic Number Theory Symposium, Proceedings. MSP (2020)
7.
Brakerski Z., Vaikuntanathan V.: Efficient fully homomorphic encryption from (standard) LWE. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 97–106 (2011)
8.
Brakerski Z., Vaikuntanathan V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. Adv. Cryptol. CRYPTO 2011, 505–524 (2011).
9.
Brakerski Z., Gentry C., Vaikuntanathan V.: (Leveled) Fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science—ICTS, pp. 309–325 (2012)
10.
Cash D., Hofheinz D., Kiltz E., Peikert C.: Bonsai trees, or how to delegate a lattice basis. Adv. Cryptol. EUROCRYPT 2010, 523–552 (2010).
11.
Chen H., Lauter K.E., Stange K.E.: Attacks on search RLWE. In: Cryptology ePrint Archive, Report 2015/971 (2015)
12.
Chen H., Lauter K.E., Stange K.E.: Vulnerable Galois RLWE families and improved attacks. In: Cryptology ePrint Archive, Report 2016/193 (2016)
13.
Coppersmith D. Attacking non-commutative NTRU. In: IBM Research Report (1997)
14.
Cramer R., Ducas L., Peikert C., Regev O.: Recovering short generators of principal ideals in cyclotomic rings. Adv. Cryptol. EUROCRYPT 2016, 559–585 (2016).
15.
Cramer R., Ducas L., Wesolowski B.: Short stickelberger class relations and application to Ideal-SVP. In: Cryptology ePrint Archive, Report 2016/885 (2016)
16.
Eisenträger K., Hallgren S., Lauter K.E.: Weak instances of PLWE. Select. Areas Cryptogr. 2014, 183–194 (2014).
17.
Elias Y., Lauter K.E., Ozman E., Stange K.E.: Provably weak instances of Ring-LWE. Adv. Cryptol. CRYPTO 2015, 63–92 (2015).
18.
Fan J., Vercauteren F.: Somewhat practical fully homomorphic encryption. In: Cryptology ePrint Archive, Report 2012/144 (2012)
19.
Fisher J.L., Sehgal S.K.: Principal ideal group rings. Commun. Algebra 4(4), 319–325 (1976).
20.
Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp.197–206 (2008)
21.
Grover C., Ling C., Vehkalahti R.: Non-commutative ring learning with errors from cyclic algebras. In: Cryptology ePrint Archive, Report 2019/680 (2019)
22.
Jeffrey H., Jill P., Silverman Joseph H.: NTRU: A ring-based public key cryptosystem. In: Algorithmic Number Theory, Third International Symposium, ANTS-III, pp. 267–288 (1998).
23.
Langlois A., Stehlé D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565–599 (2015).
24.
Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. Top. Cryptol. CT-RSA 2011, 319–339 (2011).
25.
Lyubashevsky V., Peikert C., Regev O.: On ideal lattices and learning with errors over rings. In:Advances in Cryptology—EUROCRYPT, Volume 6110 of Lecture Notes in Computer Science, pp. 1–23. Springer (2010)
26.
Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. Adv. Cryptol. EUROCRYPT 2012, 700–718 (2012).
27.
Miklós A.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing—STOC, pp. 99–108 (1996)
28.
Pan Y., Xu J., Wadleigh N., Cheng Q.: On the ideal shortest vector problem over random rational primes. In: Advances in Cryptology—EUROCRYPT, Volume 12696 of Lecture Notes in Computer Science, pp. 559–583. Springer (2021)
29.
Pedrouzo-Ulloa A., Troncoso-Pastoriza J.R., Pérez-González, F.: Multivariate lattices for encrypted image processing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1707–1711. IEEE (2015)
30.
Pedrouzo-Ulloa A., Troncoso-Pastoriza J.R., Pérez-González, F.: On ring learning with errors over the tensor product of number fields. https://​arxiv.​org/​abs/​1607.​05244 (2016)
31.
Pedrouzo-Ulloa A., Troncoso-Pastoriza J.R., Pérez-González, F.: Multivariate cryptosystems for secure processing of multidimensional signals. In: CoRR abs/1712.00848 (2017)
32.
Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 333–342. ACM (2009)
33.
Peikert C., Pepin Z.: Algebraically structured LWE, revisited. In: Theory of Cryptography—TCC 2019, Proceedings, Part I, Volume 11891 of Lecture Notes in Computer Science, pp. 1–23. Springer (2019)
34.
Peikert C., Waters B.: Lossy trapdoor functions and their applications. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 187–196 (2008)
35.
Peikert C., Regev O., Stephens-Davidowitz N.: Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 461–473 (2017)
36.
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pp. 84–93. ACM, New York (2005)
37.
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34 (2009).
38.
Sehgal S.K.: Units in Integral Group Rings. Longman, London (1993). MATH
39.
Serre J.-P.: Linear Representations of Finite Groups. Springer, New York (1997).
40.
Shor P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science—FOCS, pp. 124–134 (1994)
41.
Stehlé D., Steinfeld R.: Making NTRU as secure as worst-case problems over ideal lattices. Adv. Cryptol. EUROCRYPT 2011, 27–47 (2011).
42.
Stehlé D., Steinfeld R., Tanaka K., Xagawa K.: Efficient public key encryption based on ideal lattices. In: Matsui M. (ed.) Advances in Cryptology–ASIACRYPT, Volume 5912 of Lecture Notes in Computer Science, pp. 617–635. Springer, New York (2009).
43.
Truman K.R.: Analysis and extension of non-commutative NTRU. PhD thesis, University of Maryland (2007)
44.
Wang Y., Wang M.: Module-LWE versus Ring-LWE, revisited. In: Cryptology ePrint Archive, Report 2019/930 (2019)
45.
Yasuda T., Dahan X., Sakurai K.: Characterizing NTRU-variants using group ring and evaluating their lattice security. In: Cryptology ePrint Archive, Report 2015/1170 (2015)
Title
LWE from non-commutative group rings
Authors
Qi Cheng
Jun Zhang
Jincheng Zhuang
Publication date
24-11-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00973-6

Go to the issue