Cryptography Reference
In-Depth Information
Hence, to use the identification scheme, a user, say
Alice
, whose identity is en-
coded by the string
α
, should first uniformly select a secret string
s
, compute
i
def
=
I
s
(
α
),
ask the trusted third party to place the record (
α,
i
) in the public file, and store the string
s
in a safe place. The viability condition asserts that
Alice
can convince
Bob
of her
identity by executing the identification protocol:
Alice
invokes the program
P
using
the stored string
s
as auxiliary input, and
Bob
uses the program
V
and makes sure that the
common input is the public record containing
α
(which is in the public file). Ignoring
for a moment the algorithm
B
and the random variable
T
n
, the security condition
implies that it is infeasible for a party to impersonate
Alice
if all that this party has
is the public record of
Alice
and some unrelated auxiliary information (represented
by the auxiliary input
z
). However, such a security condition may not suffice in many
applications, since a user wishing to impersonate
Alice
may ask her first to prove
her identity to him/her. The (full) security condition asserts that even if
Alice
has
proved her identity to
Carol
many times in the past, still it is infeasible for
Carol
to
impersonate
Alice
. We stress that
Carol
cannot impersonate
Alice
to
Bob
provided
that she cannot interact concurrently with both
Alice
and
Bob
. In case this condition
does not hold, nothing is guaranteed (and indeed
Carol
can easily impersonate
Alice
by referring
Bob
's questions to
Alice
and answering as
Alice
does).
4.7.5.2. Identification Schemes and Proofs of Knowledge
A natural way to determine a person's identity is to ask him/her to supply a proof of
knowledge of a fact that the person is supposed to know. Let us consider a specific (but
in fact quite generic) example.
Construction 4.7.9 (Identification Scheme Based on a One-Way Function):
Let f be a function. On input an identity
α
∈{
0
,
1
}
n
, the
information-generating
algorithm
uniformly selects a string s
∈{
0
,
1
}
n
and outputs
f
(
s
)
.
(The pair
(
.)
The
identification proto-
col
consists of a proof of knowledge of the inverse of the second element in the
public record. Namely, in order to prove its identity, user
α,
f
(
s
)) is the public record for the user named
α
α
proves that it knows a
string s such that f
(
s
)
r
)
is a record in the public file. (The proof
of knowledge in use is allowed to have negligible knowledge error.)
=
r , where
(
α,
Proposition 4.7.10:
If f is a one-way function and the proof of knowledge in use
is zero-knowledge, then Construction 4.7.9 constitutes an identification scheme.
Hence, identification schemes exist if one-way functions exist. Practical identification
schemes can be constructed based on specific intractability assumptions. For example,
assuming the intractability of factoring, the so-called Fiat-Shamir identification scheme,
which is actually a proof of knowledge of a modular square root, follows.
Construction 4.7.11 (The Fiat-Shamir Identification Scheme, Basic Version):
On input an identity
n
, the
information-generating algorithm
uniformly
selects a composite number N that is the product of two n-bit-long primes and
a residue s
mod
N , and it outputs the pair
(
N
,
s
2
α
∈{
0
,
1
}
mod
N
)
.
(The pair (
α,
(
N
,
s
2
