Description
This survey addresses the problems of factoring and inverting the RSA function. We define practically relevant relaxed instances of these problems that can be solved in polynomial time. These problem instances are modelled by polynomial equations with small roots. In order to recover the roots, we make use of a method due to Coppersmith which is in turn based on the famous LLL lattice reduction.<br/> As new applications of the method we present an improved Hastad attack on RSA in the case of several RSA encryptions of the same underlying message, and an algorithm for factoring N=pq given 70% of the bits of p in any positions.
Prochains exposés
-
Oblivious Transfer from Zero-Knowledge Proofs (or how to achieve round-optimal quantum Oblivious Transfer without structure)
Orateur : Léo Colisson - Université Grenoble Alpes
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable oblivious transfer (OT) protocol (the protocol itself involving quantum interactions), mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely[…]-
Cryptography
-