Description
We present new classical and quantum algorithms for solving random hard instances of the subset-sum problem, in which we are given n integers on n bits and try to find a subset of them that sums to a given target. This classical NP-complete problem has several applications in cryptography and underlies the security of some proposed post-quantum cryptosystems.<br/> At EUROCRYPT 2010, Howgrave-Graham and Joux (HGJ) introduced the representation technique and presented an algorithm running in time $\bigOt{2^{0.337 n}}$. This asymptotic time was improved by Becker, Coron, Joux (BCJ) at EUROCRYPT 2011. We show how to improve this further.<br/> We then move to the context of quantum algorithms. The two previous quantum speedups in the literature are given by Bernstein, Jeffery, Lange and Meurer (PQCRYPTO 2013) and Helm and May (TQC 2018), which are respectively quantum versions of HGJ and BCJ. They both rely on the framework of quantum walks, use exponential quantum memory with quantum random-access and require an unproven conjecture on quantum walk updates. We devise a new algorithm, using quantum search only, that achieves the first quantum speedup in the model of \emph{classical} memory with quantum random access. Next, we study improvements for the quantum walks. We show how to avoid the quantum walk conjecture and give a better quantum walk time complexity for subset-sum.<br/> lien: http://desktop.visio.renater.fr/scopia?ID=725403***3883&autojoin
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
-