Cryptography Reference
In-Depth Information
11
Cryptographic Protocols
Content
Zero-knowledge:
Fiat-Shamir, Feige-Fiat-Shamir
Secret sharing:
threshold scheme, perfect schemes
Special purpose signatures:
undeniable signatures
In this chapter we review other particular cryptographic protocols. Although they
have a minor practical relevance when compared to encryption or signature, they beau-
tifully illustrate how cryptography can be a fun and a highly technical science.
11.1
Zero-Knowledge
All access control protocols that we have seen so far leak some information (which is
not necessarily useful). For instance, password access controls require to disclose the
password. Challenge-response protocols aim at proving the knowledge of a password,
but require to disclose responses for some given challenges. Complexity theory can
however show that it is possible to make access control without disclosing any informa-
tion through the puzzling notion of
zero-knowledge
proof of knowledge. This is made
possible by the power of interaction.
This puzzling concept was first introduced by Shafi Goldwasser, Silvio Micali, and
Charles Rackoff in the eighties (see Ref. [78]). The concept of power of interaction was
further extended by Adi Shamir who proved that all languages which can be accepted
by an interactive proof are actually all languages which can be accepted by a Turing
machine limited by a polynomially bounded memory space. This result was stated
by the equation IP=PSPACE (for “Interactive Proof ” and “Polynomial space”; see
Ref. [166]).
11.1.1
Notion of Zero-Knowledge
In an interactive proof of knowledge, a
prover
aims at convincing a
verifier
that he
knows some secret key, by his ability to solve some equations. For instance, he proves
that he knows
p
and
q
such that
N
pq
by his ability to compute square roots modulo
N
. This can be used, for instance, for identification schemes: assuming that the knowl-
edge of
p
and
q
such that
N
=
pq
is associated to some identity
I
N
, the prover can
prove that he is
I
N
. The interactive proof of knowledge is defined as follows.
=
Search WWH ::
Custom Search