Secure and efficient computation of the Diffie-hellman protocol using Montogomery curves over prime order fields/ Kaushik Nath

Thesis (Ph.D.) - Indian Statistical Institute, 2021

Includes bibliographical references

1 Introduction and Overview -- 2 Background and RelatedWork -- 3 Constant Time Montgomery Ladder -- I New Techniques for Efficient Implementations -- 4 Efficient Arithmetic in (Pseudo-)Mersenne Prime Order Fields -- 5 Reduction Modulo 2 to the power 448 - 2 to the power 224 - 1 -- 6 Efficient Field Arithmetic Using 4-way Vector Instructions -- 7 Efficient 4-way Vectorizations of the Montgomery Ladder -- II New Curves and Security/Efficiency Trade-off -- 8 Security and Efficiency Trade-off of ECDH over Prime Order Fields -- 9 Conclusion

Guided by Prof. Palash Sarkar

Public-key cryptography came into light in 1976 through the seminal work New Directions in Cryptography [DH76] by Whitfield Diffie and Martin Hellman. The work introduced the first one-way function which gave birth to the famous Diffie-Hellman(DH)
key agreement protocol. The function simply exponentiates a positive integer modulo
a pre-defined prime number. The inverse of the function is called the discrete logarithm
and the corresponding problem is known as the Discrete Logarithm Problem (DLP). The
discrete logarithm problem can also be defined over certain other cryptographically relevant algebraic groups where the problem is believed to be computationally hard. Some
of these groups are multiplicative subgroups of finite fields, group of points on elliptic
curves [Kob87, Mil85], divisor class groups of degree 0 on hyper-elliptic curves [Kob89].
In 1977, Ron Rivest, Adi Shamir and Leonard Adleman proposed the RSA cryptosystem which is based on the hardness of the integer factorization problem. The DH protocol
was further extended by ElGamal in 1984 to define public-key encryption and signature
schemes. The area of work of this thesis is the Diffie-Hellman protocol.