Suggestions for Further Reading

Public-key cryptography was born from the seminal works of Diffie and Hellman [78] and Rivest, Shamir and Adleman [252]. Though still young, this area has induced much research in the last three decades. In this chapter, we have made an attempt to summarize some important cryptographic algorithms proposed in the literature. The original papers where these techniques have been introduced are listed below. We don’t plan to be exhaustive, but mention only the most relevant resources.

The Handbook of Applied Cryptography [194] is a single resource where most of the above algorithms have been discussed in good details. See Chapter 8 of this book for encryption algorithms, Chapter 11 for digital signatures and Chapter 10 for identification schemes.

There are several other (allegedly) intractable mathematical problems based on which cryptographic protocols can be built. Some of the promising candidates that we left out in the text are summarized below:

The Internet site http://www.tcs.hut.fi/~helger/crypto/link/public/index.html is a good place to start, for more information on these (and some other) cryptosystems. Also visit http://www.kisa.or.kr/technology/sub1/index-PKC.htm.

The obvious question that crops up now is that, given so many different cryptographic schemes, which one a user should go for.^[5] There is no clear-cut answer to this question. One has to study the relative merits and demerits of the systems. If computational efficiency is what matters, we advocate users to go for NTRU schemes. Having said that, we must also add that the NTRU scheme is relatively new and has not yet withstood sufficient cryptanalytic attacks. Various attacks on NSS and NTRUSign cast doubt about the practical safety of applying such young schemes in serious applications.

^[5] It is worthwhile to issue a warning to the readers. Many cryptographic algorithms (and also the idea of public-key cryptography) are/were patented. In order to implement these algorithms (in particular, for commercial purposes), one should take care of the relevant legal issues. We summarize here some of the important patents in this area. The list is far from exhaustive.

Patent No.	Covers	Patent holder	Date of issue
US 4,200,770	Diffie–Hellman key exchange (includes ElGamal encryption)	Stanford University	Apr 29, 1980
US 4,218,582	Public-key cryptography	Stanford University	Aug 19, 1980
US 4,405,829	RSA	MIT	Sep 20, 1983
US 5,231,668	DSA	USA, Secretary of Commerce	Jul 27, 1993
US 5,351,298	LUC	P. J. Smith	Sep 27, 1994
US 5,790,675	HFE	CP8 Transac (France)	Aug 4, 1998
EP 0963635A1 / WO 09836526	XTR	Citibank (North America)	Dec 15, 1999 Aug 20, 1998
US 6,081,597	NTRU	NTRU Cryptosystems, Inc.	Jun 27, 2000
—	EPOC/ESIGN	Nippon Telegraph and Telephone Corporation	Apr 17, 2001

Our mathematical trapdoors are not provably secure and this is where the problems begin. We have to rely on historical evidences that should not be collected too hastily. Slow as it is, RSA has stood the test of time, and has successfully survived more than twenty years of cryptanalytic attacks [29]. The risks attached to the fact that an unforeseen attack will break the system tomorrow, appear much less with RSA, compared to newer schemes that have enjoyed only little cryptanalytic studies. The hidden monomial system proposed by Imai and Matsumoto [188] was broken by Patarin [231]. As a by-product, Patarin came up with the idea of cryptosystems based on hidden field equations (HFE) [232]. No serious attacks on HFE are known till date, but as we mentioned earlier, only time will show whether HFE is going to survive.

Bruce Schneier asserts in his Crypto-gram news-letter (15 March 1999, http://www.counterpane.com/crypto-gram.html): No one can duplicate the confidence that RSA offers after 20 years of cryptanalytic review. A standard security review, even by competent cryptographers, can only prove insecurity; it can never prove security. By following the pack you can leverage the cryptanalytic expertise of the worldwide community, not just a handful of hours of a consultant’s time.

Twenty-odd years is definitely not a wide span of time in the history of evolution of our knowledge, but public-key cryptography is only as old as RSA is!