Cryptography Reference
In-Depth Information
complement other authentication technologies and mechanisms). More recently, for
example, people have started to think about the possibility to use and take advantage
of the information that is available in cellular phone networks to complement user
authentication. Needless to say that there are some nontrivial privacy concerns that
must be addressed before such a technology may become feasible.
17.3
ZERO-KNOWLEDGE AUTHENTICATION PROTOCOLS
Most entity authentication protocols in use today implement a proof by knowledge,
but leak some (partial) information about the secret information known and used
by the claimant. If, for example, a DSS is used to digitally sign randomly chosen
challenges, then the corresponding authentication protocol leaks digital signatures
for the values that serve as challenges. Whether this poses a problem depends on
the application context. If, for example, the claimant uses the same signing key to
digitally sign challenges and electronic documents, then the verifier can challenge
the claimant with the hash value of a document he or she wants the claimant to sign.
The claimant then thinks to digitally sign a challenge, whereas in reality he or she
digitally signs the document.
3
If one wants to make sure that an authentication protocol does not leak
any information, then one must consider the use of
zero-knowledge proofs
and
corresponding
zero-knowledge authentication protocols
. This field of study was
pioneered by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s
[20]. After the discovery of public key cryptography in the 1970s, the development
of zero-knowledge proofs and zero-knowledge authentication protocols was the next
fundamental step in modern cryptography. Loosely speaking, a zero-knowledge
proof is a proof that yields nothing but the validity of the assertion. That is, a verifier
obtaining such a proof only gains conviction in the validity of the assertion. This
can be formulated by saying that anything that is feasibly computable from a zero-
knowledge proof is also feasibly computable from the valid assertion alone. This
formulation automatically leads to the simulation paradigm discussed later. Let's
begin with some preliminary remarks about proofs and proof systems.
17.3.1
Preliminary Remarks
Formally speaking, a statement is a finite sequence of symbols (i.e., a string) taken
from a finite alphabet. There are syntactic rules that specify how statements can be
formed, and there are semantic rules that specify whether a given statement is true.
3
Obviously, this problem can be addressed by using separate public key pairs for authentication and
digital signatures. Sometimes, it is even recommended to use a third public key pair for encryption.
