Cryptography Reference
In-Depth Information
interaction between the honest prover and the same verifier. Therefore the verifier gets
no important advantage in playing with the prover: he can just play with the simulator.
(The complexity factor is about 2
k
because of the potential failures.)
In order to prove the soundness, we first notice that if the dishonest prover can
answer to two different questions
e
e
k
) and
e
=
(
e
1
,...,
e
k
) for the same
=
(
e
1
,...,
commitment
x
, then he can produce
y
and
y
such that
e
1
1
e
k
k
e
1
1
e
k
k
y
2
(
y
)
2
x
≡±
v
...v
≡±
v
...v
(mod
n
)
thus he can solve
e
1
−
e
1
1
e
k
−
e
k
k
y
)
2
±
(
y
/
≡
v
...v
(mod
n
)
.
Since this does not necessarily require the full knowledge of the secret key, we just say
that we consider the scheme as broken if one can express a product of the
v
i
's with
z
2
mod
n
way. We have
thus proven that provided that this problem is hard, no dishonest prover can answer to
two different challenges.
powers 0,
+
1, or
−
1 (with at least one nonzero power) in a
±
Let us now assume that one prover can pass the protocol with probability 2
−
kt
+
ε
.
1
ε
We can prove that after
iterations of the protocol there is a fair amount of chance
that the prover is able to answer to at least two different challenges in a single round.
Therefore an extractor can break the above problem.
11.2
Secret Sharing
Sometimes, it is necessary to be really paranoid for access control. A typical example
is nuclear weapon access. We must not provide access to this dangerous power to
anyone who may be the victim of a human failure such as death, insanity, bribery,
blackmail, etc. Fiction literature is quite inventive on this issue. For this we thus need
to have independent control and backup solutions. Let us say, for example, that access
is provided only if one of the following conditions are met
the president and the head of the parliament agree
the president and the chief of the army agree
the vice president, the head of the parliament, and the chief of the army agree
and others.
This list of conditions actually defines an
access structure
.
Cryptography formalizes this problem as follows: there is an access control secret
key
S
which is
shared
among several participants (each participant has a
share
), and
Search WWH ::
Custom Search