Description
The GGH Graded Encoding Scheme (of Garg, Gentry and Halevi), based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis the authors provided, the scheme requires very large parameters to provide security for its underlying encoding re-randomization process. Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. We apply these results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the drowning step of re-randomization, in which we apply the Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from Omega(n log n) to 2, where n is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from O(lambda^5 log lambda) for the GGH scheme to O(lambda log^2 lambda)$ in GGHLite, with respect to the security parameter lambda for a constant multilinearity parameter.
Prochains exposés
-
Key Attack on the ACDGV Matrix Encryption Scheme
Orateur : Anmoal Porwal - Technical University of Munich
I will present our key-recovery attack on the ACDGV public-key encryption scheme proposed at ASIACRYPT 2024 by Aragon, Couvreur, Dyseryn, Gaborit, and Vinçotte. The secret key is a Gabidulin code hidden by appending random rows and columns and by left- and right-multiplication with invertible matrices. Our attack exploits the resulting algebraic structure to recover an equivalent secret key. It[…]-
Cryptography
-
Asymmetric primitive
-
-
Module Learning With Errors and Structured Extrapolated Dihedral Cosets
Orateur : Jinwei Zheng - Télécom Paris
The Module Learning With Errors (MLWE) problem is the fundamental hardness assumption underlying the key encapsulation and signature schemes ML-KEM and ML-DSA, which have been selected by NIST for post-quantum cryptography standardization. Understanding its quantum hardness is crucial for assessing the security of these standardized schemes. Inspired by the equivalence between LWE and[…]-
Cryptography
-