Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 1/2022

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

Login to get access
share
SHARE

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.
go back to reference Agrawal S., Boneh D., Boyen X.: Efficient lattice (H)IBE in the standard model. Adv. Cryptol. EUROCRYPT 2010, 553–572 (2010). MathSciNetMATH Agrawal S., Boneh D., Boyen X.: Efficient lattice (H)IBE in the standard model. Adv. Cryptol. EUROCRYPT 2010, 553–572 (2010). MathSciNetMATH
2.
go back to reference Agrawal S., Boneh D., Boyen X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Adv. Cryptol. CRYPTO 2010, 98–115 (2010). MathSciNetMATH Agrawal S., Boneh D., Boyen X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Adv. Cryptol. CRYPTO 2010, 98–115 (2010). MathSciNetMATH
3.
go back to reference 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) 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.
go back to reference Alexei G., Myasnikov V.S., Alexander U.: American Mathematical Society, Non-commutative Cryptography and Complexity of Group-theoretic Problems (2011) Alexei G., Myasnikov V.S., Alexander U.: American Mathematical Society, Non-commutative Cryptography and Complexity of Group-theoretic Problems (2011)
5.
go back to reference Banaszczyk W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–636 (1993). MathSciNetCrossRef Banaszczyk W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–636 (1993). MathSciNetCrossRef
6.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Brakerski Z., Vaikuntanathan V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. Adv. Cryptol. CRYPTO 2011, 505–524 (2011). MathSciNetMATH Brakerski Z., Vaikuntanathan V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. Adv. Cryptol. CRYPTO 2011, 505–524 (2011). MathSciNetMATH
9.
go back to reference Brakerski Z., Gentry C., Vaikuntanathan V.: (Leveled) Fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science—ICTS, pp. 309–325 (2012) Brakerski Z., Gentry C., Vaikuntanathan V.: (Leveled) Fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science—ICTS, pp. 309–325 (2012)
10.
go back to reference Cash D., Hofheinz D., Kiltz E., Peikert C.: Bonsai trees, or how to delegate a lattice basis. Adv. Cryptol. EUROCRYPT 2010, 523–552 (2010). MathSciNetMATH Cash D., Hofheinz D., Kiltz E., Peikert C.: Bonsai trees, or how to delegate a lattice basis. Adv. Cryptol. EUROCRYPT 2010, 523–552 (2010). MathSciNetMATH
11.
go back to reference Chen H., Lauter K.E., Stange K.E.: Attacks on search RLWE. In: Cryptology ePrint Archive, Report 2015/971 (2015) Chen H., Lauter K.E., Stange K.E.: Attacks on search RLWE. In: Cryptology ePrint Archive, Report 2015/971 (2015)
12.
go back to reference Chen H., Lauter K.E., Stange K.E.: Vulnerable Galois RLWE families and improved attacks. In: Cryptology ePrint Archive, Report 2016/193 (2016) Chen H., Lauter K.E., Stange K.E.: Vulnerable Galois RLWE families and improved attacks. In: Cryptology ePrint Archive, Report 2016/193 (2016)
13.
go back to reference Coppersmith D. Attacking non-commutative NTRU. In: IBM Research Report (1997) Coppersmith D. Attacking non-commutative NTRU. In: IBM Research Report (1997)
14.
go back to reference Cramer R., Ducas L., Peikert C., Regev O.: Recovering short generators of principal ideals in cyclotomic rings. Adv. Cryptol. EUROCRYPT 2016, 559–585 (2016). MathSciNetMATH Cramer R., Ducas L., Peikert C., Regev O.: Recovering short generators of principal ideals in cyclotomic rings. Adv. Cryptol. EUROCRYPT 2016, 559–585 (2016). MathSciNetMATH
15.
go back to reference Cramer R., Ducas L., Wesolowski B.: Short stickelberger class relations and application to Ideal-SVP. In: Cryptology ePrint Archive, Report 2016/885 (2016) Cramer R., Ducas L., Wesolowski B.: Short stickelberger class relations and application to Ideal-SVP. In: Cryptology ePrint Archive, Report 2016/885 (2016)
16.
go back to reference Eisenträger K., Hallgren S., Lauter K.E.: Weak instances of PLWE. Select. Areas Cryptogr. 2014, 183–194 (2014). MathSciNetMATH Eisenträger K., Hallgren S., Lauter K.E.: Weak instances of PLWE. Select. Areas Cryptogr. 2014, 183–194 (2014). MathSciNetMATH
17.
go back to reference Elias Y., Lauter K.E., Ozman E., Stange K.E.: Provably weak instances of Ring-LWE. Adv. Cryptol. CRYPTO 2015, 63–92 (2015). MathSciNetMATH Elias Y., Lauter K.E., Ozman E., Stange K.E.: Provably weak instances of Ring-LWE. Adv. Cryptol. CRYPTO 2015, 63–92 (2015). MathSciNetMATH
18.
go back to reference Fan J., Vercauteren F.: Somewhat practical fully homomorphic encryption. In: Cryptology ePrint Archive, Report 2012/144 (2012) Fan J., Vercauteren F.: Somewhat practical fully homomorphic encryption. In: Cryptology ePrint Archive, Report 2012/144 (2012)
20.
go back to reference 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) 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.
go back to reference Grover C., Ling C., Vehkalahti R.: Non-commutative ring learning with errors from cyclic algebras. In: Cryptology ePrint Archive, Report 2019/680 (2019) Grover C., Ling C., Vehkalahti R.: Non-commutative ring learning with errors from cyclic algebras. In: Cryptology ePrint Archive, Report 2019/680 (2019)
22.
go back to reference 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). 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.
go back to reference Langlois A., Stehlé D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565–599 (2015). MathSciNetCrossRef Langlois A., Stehlé D.: Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75(3), 565–599 (2015). MathSciNetCrossRef
24.
go back to reference Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. Top. Cryptol. CT-RSA 2011, 319–339 (2011). MathSciNetMATH Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. Top. Cryptol. CT-RSA 2011, 319–339 (2011). MathSciNetMATH
25.
go back to reference 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) 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.
go back to reference Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. Adv. Cryptol. EUROCRYPT 2012, 700–718 (2012). MathSciNetMATH Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. Adv. Cryptol. EUROCRYPT 2012, 700–718 (2012). MathSciNetMATH
27.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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)
31.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
38.
go back to reference Sehgal S.K.: Units in Integral Group Rings. Longman, London (1993). MATH Sehgal S.K.: Units in Integral Group Rings. Longman, London (1993). MATH
39.
go back to reference Serre J.-P.: Linear Representations of Finite Groups. Springer, New York (1997). Serre J.-P.: Linear Representations of Finite Groups. Springer, New York (1997).
40.
go back to reference 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) 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.
go back to reference Stehlé D., Steinfeld R.: Making NTRU as secure as worst-case problems over ideal lattices. Adv. Cryptol. EUROCRYPT 2011, 27–47 (2011). MathSciNetMATH Stehlé D., Steinfeld R.: Making NTRU as secure as worst-case problems over ideal lattices. Adv. Cryptol. EUROCRYPT 2011, 27–47 (2011). MathSciNetMATH
42.
go back to reference 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). 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.
go back to reference Truman K.R.: Analysis and extension of non-commutative NTRU. PhD thesis, University of Maryland (2007) Truman K.R.: Analysis and extension of non-commutative NTRU. PhD thesis, University of Maryland (2007)
44.
go back to reference Wang Y., Wang M.: Module-LWE versus Ring-LWE, revisited. In: Cryptology ePrint Archive, Report 2019/930 (2019) Wang Y., Wang M.: Module-LWE versus Ring-LWE, revisited. In: Cryptology ePrint Archive, Report 2019/930 (2019)
45.
go back to reference 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) 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)
Metadata
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

Other articles of this Issue 1/2022

Designs, Codes and Cryptography 1/2022 Go to the issue

Premium Partner