Cryptography Reference
In-Depth Information
and proceeds by executing his role in the protocol. It is required that
Alice
always be
able to convince
Bob
(that she is indeed
Alice
), whereas nobody else can fool
Bob
into
believing that she/he is
Alice
. Furthermore,
Carol
should not be able to impersonate
Alice
even after receiving polynomially many proofs of identity from
Alice
.
The identification information is generated by
Alice
using a randomized algorithm.
Clearly, if the identification information is to be of any use, then
Alice
must keep secret
the random coins she used to generate her record. Furthermore,
Alice
must use these
stored coins during the execution of the identification protocol, but this must be done
in a way that will not allow anyone else to impersonate her later.
Conventions.
In the following definition, we adopt the formalism and notations of
interactive machines with auxiliary input (presented in Definition 4.2.10). We recall
that when
M
is an interactive machine, we denote by
M
(
y
) the machine that results
by fixing
y
to be the auxiliary input of machine
M
. In the following definition,
n
is
the security parameter, and we assume with little loss of generality that the names
(i.e., identities) of the users are encoded by strings of length
n
.If
A
is a probabilistic
algorithm and
x
,
r
∈{
0
,
1
}
∗
, then
A
r
(
x
) denotes the output of algorithm
A
on input
x
and random coins
r
.
Motivation.
Algorithm
I
in the following definition corresponds to the procedure used
to generate identification information, and (
P
V
) corresponds to the identification
protocol itself. The interactive machines
B
and
B
represent two components of the
adversary behavior (i.e., interacting with the user in order to extract its secrets and later
trying to impersonate it). On a first reading, the reader can ignore algorithm
B
and
the random variable
T
n
(in the security condition). Doing so, however, yields a weaker
condition that typically is unsatisfactory.
,
Definition 4.7.8 (Identification Scheme):
An
identification scheme
consists of a
pair
(
I
,
)
, where I is a probabilistic polynomial-time algorithm and
=
(
P
,
V
)
is a pair of probabilistic polynomial-time interactive machines satisfying the
following conditions:
n
, and every s
poly(
n
)
,
Viability:
For every n
∈ N
, every
α
∈{
0
,
1
}
∈{
0
,
1
}
Pr
[
P
(
s
)
,
V
(
α,
I
s
(
α
))
=
1]
=
1
Security:
For every pair of probabilistic polynomial-time interactive machines B
and B
, every polynomial p
(
n
, and
·
)
, all sufficiently large n
∈ N
, every
α
∈{
0
,
1
}
every z,
Pr
α,
)
=
1
<
1
p
(
n
)
B
(
z
,
T
n
)
,
V
I
S
n
(
α
where S
n
is a random variable uniformly distributed over
poly(
n
)
and T
n
is a
random variable describing the output of B
(
z
)
after interacting with P
(
S
n
)
,on
common input
(
{
0
,
1
}
))
, for polynomially many times.
Algorithm I is called the
information-generating algorithm
, and the pair
(
P
α,
I
S
n
(
α
,
V
)
is called the
identification protocol
.
