International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lova: Lattice-Based Folding Scheme from Unstructured Lattices

Authors:
Giacomo Fenzi , EPFL
Christian Knabenhans , EPFL
Ngoc Khanh Nguyen , King's College London
Duc Tu Pham , ENS Paris
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: Folding schemes (Kothapalli et al., CRYPTO 2022) are a conceptually simple, yet powerful cryptographic primitive that can be used as a building block to realise incrementally verifiable computation (IVC) with low recursive overhead without general-purpose non-interactive succinct arguments of knowledge (SNARK). Most folding schemes known rely on the hardness of the discrete logarithm problem, and thus are both not quantum-resistant and operate over large prime fields. Existing post-quantum folding schemes (Boneh, Chen, ePrint 2024/257) based on lattice assumptions instead are secure under structured lattice assumptions, such as the Module Short Integer Solution Assumption (MSIS), which also binds them to relatively complex arithmetic. In contrast, we construct Lova, the first folding scheme whose security relies on the (unstructured) SIS assumption. We provide a Rust implementation of Lova, which makes only use of arithmetic in hardware-friendly power-of-two moduli. Crucially, this avoids the need of implementing and performing any finite field arithmetic. At the core of our results lies a new exact Euclidean norm proof which might be of independent interest
BibTeX
@inproceedings{asiacrypt-2024-34705,
  title={Lova: Lattice-Based Folding Scheme from Unstructured Lattices},
  publisher={Springer-Verlag},
  author={Giacomo Fenzi and Christian Knabenhans and Ngoc Khanh Nguyen and Duc Tu Pham},
  year=2024
}