ABSTRACT
This chapter provides an overview of the public-key cryptography. The chapter starts with the discrete logarithm and its related assumptions. The next part of the chapter provides the details about the Diffie-Hellman key exchange protocol since the key exchange is important in the public-key cryptosystems. The public-key encryption scheme is then defined as a triple of probabilistic polynomial-time algorithms for key generation, encryption, and decryption. Intuitively, a key-exchange protocol is secure if the key output by two communicating parties, Alice and Bob, is completely unguessable by an eavesdropping adversary. The Diffie-Hellman protocol serves as the first demonstration that asymmetric techniques could be used to alleviate the problems of key distribution in cryptography. Furthermore, to make the Diffie-Hellman protocol resilient to man-in-the-middle attacks, people adopt the station-to-station protocol which is in wide use today. In private-key encryptions, encryption is made on bit string. Public-key encryption, however, people usually encode strings as group elements on which encryption is made.
