Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Most of the known public-key cryptosystems have an overall complexity which is dominated by the key-production algorithm, which requires the generation of prime numbers. This is most inconvenient in settings where the key-generation is not an one-off process, e.g., secure delegation of computation or EKE password-based key exchange protocols. To this end, we extend the Goldwasser-Micali (GM) cryptosystem to a provably secure system, denoted SIS, where the generation of primes is bypassed. Using number-theoretic and linear optimisation techniques, we align the security guarantees (i.e., resistance to factoring of moduli, etc.) of SIS to those of other well-known cryptosystems based on modular arithmetics. %Taking into consideration different possibilities to implement the fundamental operations, We explicitly compare and contrast the asymptotic complexity of well-known public-key cryptosystems based on modular arithmetics (e.g., GM and/or RSA) with that of SIS's. The latter shows that once we are ready to accept an increase in the size of the moduli, SIS's offers significant speed-ups to applications like the aforementioned secure delegation of computation or protocols where a fresh key needs to be generated with every new session. We also developed an efficient extension of SIS to handle more than one bit at a time, using linear codes, which will be omitted herein due to space constraints.