Primeless Factoring-Based Cryptography

Autor: Serge Vaudenay, Sonia Bogos, Ioana Boureanu
Rok vydání: 2013
Předmět:
Zdroj: Applied Cryptography and Network Security ISBN: 9783642389795
ACNS
DOI: 10.1007/978-3-642-38980-1_35
Popis: Factoring based 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. By developing on the correct choice of the parameters of SIS we align SIS's security guarantees (i.e. resistance to factoring of moduli etc.) to those of other well known factoring based cryptosystems. Taking into consideration different possibilities to implement the fundamental operations we explicitly compare and contrast the asymptotic complexity of well known public key cryptosystems (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 offers a generally lower asymptotic complexity than e.g. GM or even RSA (when scaling correctly the number of encrypted bits). This would yield most 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 e.g. EKE password based key exchange protocols.
Databáze: OpenAIRE
Externí odkaz: