Cryptography Reference
In-Depth Information
keys; the parties agree upon the key by collectively executing a decentralized
protocol.
Public key cryptography plays an important role in key agreement proto-
cols. Another use of public key systems is in digital signatures. Such signature
schemes often use what we call a hash function
h : {0,1}
∗
→{0,1}
n
,
that takes as input a message m of arbitrary length and produces a hash or
message digest h(m) of a fixed size n. In a public key cryptosystem, digital
certificates are used to authenticate the public keys. A Public Key Infrastruc-
ture or PKI [1] is a secure system that is used for managing and controlling
these certificates. Identity-Based Encryption or IBE [54,161] is an alternative
to PKI, that removes the need for certificates by generating the public key
of a user by applying a public hash function on the user's identity string (for
example, an email ID).
Unlike private key cryptosystems, public key cryptosystems do not require
prior communication of the secret key between the sender and the receiver.
However, the performance of public key cryptosystems is in general slower
than that of private key cryptosystems. In 1985, Koblitz and Miller proposed
a new domain of public key cryptosystem called Elliptic Curve Cryptography
or ECC [90, 121] based on the arithmetic on elliptic curves. ECC is usually
much faster than other traditional public key systems (see [64] for details).
The security of all public key systems relies on the di
culty of solving certain
problems for which no e
cient polynomial time algorithm is known. For
example, the security of RSA depends on the hardness of factoring a large
integer that is formed by multiplying two large primes (called the integer
factorization problem), the security of the ElGamal scheme depends on the
di
culty of computing the logarithm of an integer modulo a prime (called the
discrete log problem), and that of ECC relies on a variant of the discrete log
problem in the domain of elliptic curves.
So far we have discussed issues based on the classical (i.e., Turing) model
of computation. In 1982, a new era in computer science began when Richard
Feynman asserted that a quantum system can be used to do computations [49].
In 1985, this idea was formalized by David Deutsch [36], that initiated a new
field of study called Quantum Computation. In 1984, Charles Bennett and
Gilles Brassard demonstrated the use of Quantum Cryptography for the first
time, by using quantum mechanical effects to perform key distribution [11].
The topics [24,129] contain comprehensive treatises on quantum computation
and quantum cryptography.
In 1994, Peter Shor published his revolutionary paper [166,167] that proved
that integer factorization and discrete log problems can be solved e
ciently
(i.e., in polynomial time) using the quantum computation model. So far, the
quantum computer has mostly remained a theoretical concept and very little
development has been made toward the actual implementation. If, however,
scientists are successful in manufacturing a quantum computer, then the tra-
