New Lattice-Based Cryptographic Constructions Using Fourier Analysis

Title: New Lattice-Based Cryptographic Constructions Using Fourier Analysis

Abstract: This research introduces the use of Fourier analysis on lattices as an integral part of lattice-based cryptographic constructions. The main result is a reduction from the O(n1.5)-unique shortest vector problem (uSVP) to the problem of distinguishing between two types of distributions on the segment [0, 1). This theorem can have further applications and seems to be a powerful tool in the field of lattice-based cryptography.

Using the main theorem, the authors present three results. The main outcome is a new public key cryptosystem based on the hardness of O(n1.5)-uSVP. This is a significant improvement over the 1996 cryptosystem, providing a stronger security guarantee. The second result is a family of collision resistant hash functions with improved security and based on the same principles. Both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1).

The paper also discusses open problems and potential future applications of the developed methodology. Overall, the research contributes a new approach to lattice-based cryptographic constructions, offering stronger security guarantees and opening up possibilities for further advancements in the field.

Link to Article: https://arxiv.org/abs/0309051v1 Authors: arXiv ID: 0309051v1