Description
We initiate the study of a novel class of group-theoretic intractability problems. Inspired by the theory of learning in presence of errors [Regev, STOC'05] we ask if noise in the exponent amplifies intractability. We put forth the notion of Learning with Errors in the Exponent (LWEE) and rather surprisingly show that various attractive properties known to ex- clusively hold for lattices carry over. Most notably are worst-case hardness and post-quantum resistance. In fact, LWEE's "diprosopus" is due to the reducibility to two seemingly orthogonal assumptions: Learning with errors and the representation problem [Brands, Crypto'93]. For suitable parameter choices one obtains double-hard assumptions superposing properties from each individual assumption. The argument holds in the classical and quantum model of computation, and makes LWEE an appealing provisioner of strong security and robustness guarantees. We give the very first construction of a semantically secure public-key encryption system in the standard model. The heart of our construction is an "error recovery" technique to tame the crucial propagation of noise in the exponent which is of independent interest.
Next sessions
-
Dual attacks in code-based (and lattice-based) cryptography
Speaker : Charles Meyer-Hilfiger - Inria Rennes
The hardness of the decoding problem and its generalization, the learning with errors problem, are respectively at the heart of the security of the Post-Quantum code-based scheme HQC and the lattice-based scheme Kyber. Both schemes are to be/now NIST standards. These problems have been actively studied for decades, and the complexity of the state-of-the-art algorithms to solve them is crucially[…]-
Cryptography
-
-
Lie algebras and the security of cryptosystems based on classical varieties in disguise
Speaker : Mingjie Chen - KU Leuven
In 2006, de Graaf et al. proposed a strategy based on Lie algebras for finding a linear transformation in the projective linear group that connects two linearly equivalent projective varieties defined over the rational numbers. Their method succeeds for several families of “classical” varieties, such as Veronese varieties, which are known to have large automorphism groups. In this talk, we[…]-
Cryptography
-