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

Area of Science:

• Lattice-based cryptography
• Algebraic number theory
• Post-quantum cryptography

Background:

• Existing research characterizes weak instances of the Ring-LWE problem using algebraic structures.
• These weak instances are not covered by worst-case hardness theorems.
• Expanding ring instantiations broadens applications and diversifies security assumptions.

Purpose of the Study:

• To extend the Ring-LWE problem to algebraic lattices via twisted embeddings.
• To define and analyze the security of the proposed Twisted Ring-LWE problem.
• To explore the implications for cryptographic applications and number field usage.

Main Methods:

• Definition of Twisted Ring-LWE using extended embeddings.
• Security reduction proofs from Ring-LWE to Twisted Ring-LWE (search and decision forms).
• Analysis of twist factor's impact on worst-case to average-case reductions.
• Expansion of spherical Gaussian distribution sampling to new lattice classes.

Main Results:

• Twisted Ring-LWE is proven secure via reduction from Ring-LWE.
• The twist factor does not negatively impact hardness guarantees.
• The scope of algebraic lattices for cryptography is significantly increased.
• Direct sampling from spherical Gaussian distributions is achieved in number fields.

Conclusions:

• Twisted Ring-LWE offers a secure and practical extension of Ring-LWE.
• This work enhances the flexibility and applicability of lattice-based cryptography.
• The findings support the use of a wider range of algebraic structures in cryptographic designs.