Cryptography Reference
In-Depth Information
.)
The
identification protocol
consists
of a proof of knowledge of the corresponding modular square root. Namely, in
order to prove its identity, user
mod
N
)) is the public record for user
α
α
proves that it knows a modular square root of
r
def
=
s
2
mod
N , where
(
α,
(
r
,
N
))
is a record in the public file. (Again, negligible
knowledge error is allowed.)
The proof of knowledge of modular square roots is analogous to the proof system
for Graph Isomorphism presented in Construction 4.3.8. Namely, in order to prove
knowledge of a square root of
r
s
2
≡
(mod
N
), the prover repeats the following steps
sufficiently many times:
Construction 4.7.12 (Atomic Proof of Knowledge of Modular Square Root):
This refers to the common input
(
r
,
N
)
, where the prescribed prover has auxiliary
input s such that r
≡
s
2
(mod
N
):
def
=
g
2
The prover randomly selects a residue g
modulo
N and sends h
mod
Nto
the verifier.
The verifier uniformly selects
σ
∈{
0
,
1
}
and sends it to the prover.
Motivation:
In case
σ
=
0
, the verifier asks for a square root of h
mod
N , whereas
σ
=
·
in case
1
the verifier asks for a square root of h
r
mod
N . In the sequel, we
assume, without loss of generality, that
σ
∈{
0
,
1
}
.
def
=
s
σ
mod
N.
The prover replies with a
g
·
The verifier accepts if and only if the messages h and a sent by the prover satisfy
a
2
r
σ
mod
N.
≡
h
·
When Construction 4.7.12 is repeated
k
times, either sequentially or in parallel, the
resulting protocol constitutes a proof of knowledge of a modular square root, with
knowledge error 2
−
k
(see Exercise 27). In case these repetitions are conducted sequen-
tially, the resulting protocol is zero-knowledge. Yet, for use in Construction 4.7.11, it
suffices that the proof of knowledge be
witness-hiding
under the relevant distribution
(see Definition 4.6.5), even when polynomially many executions take place concur-
rently (in an asynchronous manner). Hence the resulting identification scheme has
constant-round complexity. We remark that for identification purposes it suffices to
perform Construction 4.7.12 super-logarithmically many times. Furthermore, fewer
repetitions can also be of value: When applying Construction 4.7.12 for
k
=
O
(log
n
)
times and using the resulting protocol in Construction 4.7.11, we get a scheme (for
identification) in which impersonation can occur with probability at most 2
−
k
.
4.7.5.3. Identification Schemes and Proofs of Ability
As hinted earlier, a proof of knowledge of a string (i.e., the ability to output the string)
is a special case of a proof of ability to do something. It turns out that identification
schemes can also be based on the more general concept of proofs of ability. We avoid
defining this concept and confine ourself to two “natural” examples of using a proof of
ability as a basis for identification.
It is everyday practice to identify people by their ability to produce their signatures.
This practice can be carried into the digital setting. Specifically, the public record of
273
