As an undergraduate, I took Introduction to Algorithms from Ron Rivest. One of the topics he taught was the RSA public-key cryptosystem which he had created with Adi Shamir and Leonard Adleman. At the time, RSA was only about a decade old, yet already one of the banner creations of computer science. Today many of us rely on it routinely for the security of banking transactions. The internet would not be the same without it and its successors (such as elliptic curve cryptography, ECC). However, as you may have heard, quantum computation spells change for cryptography. Today I’ll tell a little of this story and talk about prospects for the future.

Ron Rivest

What is public-key cryptography (PKC)? The basic notion is due to Ralph Merkle in 1974 and (in a stronger form) to Whitfield Diffie and Martin Hellman in 1976. Their remarkable proposal was that two parties, “Alice” and “Bob”, could cooperate in cryptographic protocols, even if they had never met before. All prior cryptography, from the ancients up through and after the cryptographic adventures of WWII, had relied on the cooperating parties sharing in advance some “secret key” that gave them an edge over any eavesdropper “Eve”.
Continue reading →