The Ring-LWE Problem in Lattice-Based Cryptography: The Case of Twisted Embeddings

Author(s)

Ortiz, Jheyne N. ^[1] ; de Araujo, Robson R. ^[2] ; Aranha, Diego F. ^[3] ; Costa, Sueli I. R. ^[4] ; Dahab, Ricardo ^[1]

Affiliation

^[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas - Brazil

^[2] Fed Inst Sao Paulo, BR-11533160 Cubatao - Brazil

^[3] Aarhus Univ, Dept Comp Sci, DK-8200 Aarhus - Denmark

^[4] Univ Estadual Campinas, Inst Math Stat & Comp Sci, BR-13083859 Campinas - Brazil

• Document type: Journal article
• Source: Entropy; v. 23, n. 9 SEP 2021.
• Web of Science Citations: 0

Abstract

Several works have characterized weak instances of the Ring-LWE problem by exploring vulnerabilities arising from the use of algebraic structures. Although these weak instances are not addressed by worst-case hardness theorems, enabling other ring instantiations enlarges the scope of possible applications and favors the diversification of security assumptions. In this work, we extend the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. By doing so, we allow the Ring-LWE problem to be used over maximal real subfields of cyclotomic number fields. We prove that Twisted Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the twist factor does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. As a result, sampling from a spherical Gaussian distribution can be done directly in the respective number field while maintaining its format and standard deviation when seen in R-n via twisted embeddings. (AU)

• FAPESP's process: 13/25977-7 - Security and reliability of Information: theory and practice
• Grantee: Marcelo Firer
• Support Opportunities: Research Projects - Thematic Grants