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.
Algorithm | Reference(s) |
---|---|
RSA encryption | [252] |
Rabin encryption | [246] |
Goldwasser–Micali encryption | [117] |
Blum–Goldwasser encryption | [27] |
ElGamal encryption | [84] |
Chor–Rivest encryption | [54] |
XTR encryption | [170, 172, 171, 173, 289, 297] |
NTRU encryption | [130] |
Identity-based encryption | [267, 34, 35] |
Diffie–Hellman key exchange | [78] |
Menezes–Qu–Vanstone key exchange | [161] |
RSA signature | [252] |
Rabin signature | [246] |
ElGamal signature | [84] |
Schnorr signature | [263] |
Nyberg–Rueppel signature | [223, 224] |
DSA | [220] |
ECDSA | [141] |
XTR signature | [170, 172, 171, 173, 289, 297] |
NTRUSign | [110, 111, 128, 129, 131, 217] |
Chaum blind signature | [48, 49, 50] |
Schnorr blind signature | [263, 202] |
Okamoto–Schnorr blind signature | [227, 236] |
Chaum–Van Antwerpen undeniable signature | [51, 52, 53] |
RSA undeniable signature | [109, 187, 102, 186] |
Signcryption | [310, 311, 312] |
Signcryption based on elliptic curves | [313, 314] |
Identity-based signcryption | [178, 185] |
Feige–Fiat–Shamir ZK protocol | [90, 91] |
Guillou–Quisquater ZK protocol | [122] |
Schnorr ZK protocol | [263] |
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:
Algorithm | Intractable problem |
---|---|
LUC [284, 285, 286] | RSA and ElGamal-like problems based on Lucas sequences |
Goldreich–Goldwasser–Halevi [115] | lattice-basis reduction |
Patarin’s hidden field equation | solving multivariate polynomial |
(HFE) [232] | equations |
EPOC/ESIGN [97, 228] | factorization of integers p2q |
McEliece encryption [190] | decoding of error-correcting codes |
Number field cryptography [38, 39] | discrete log problem in class groups of quadratic fields |
KLCHKP (Braid group cryptosystem) [148] | Braid conjugacy problem |
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!
3.142.250.203