ABSTRACT

The Diffie-Hellman key exchange protocol (DH) [8] and the Rivest-Shamir-Adleman cryptosystem (RSA) [36] are among the very first public key cryptosystems. DH was originally instantiated over multiplicative groups of finite fields, and one works with a group of integers modulo a large composite integer in RSA. In 1985, elliptic curve groups were introduced for cryptographic applications [26, 21], and their large scale deployment started in the early 2000s. As of today, elliptic curve groups are known to yield more efficient public key cryptosystems, as compared to the use of360 multiplicative groups, for the same classical security level. In both cases, though, group operations dominate the run time of these systems.