Cryptographic Protocols - Codes: The Guide to Secrecy from Ancient to Modern Times - page 204

Therefore, Eve can find a square root of t A , namely, r 2 r − 1 (mod n ). In other
words, if she can successfullyimpersonate Alice, Eve must know the prover's
secret. Hence, the protocol is in possession of the soundness property.
The above being said, the probabilityof 1 / 2 is still too high for a cheater
such as Eve. Thus, the parameter a , if set suKcientlyhigh, can reduce this
probabilityto negligible levels. In other words, for a> 1, the probabilityis
reduced to 2 − a , which for suKcientlyhigh a means that Eve has near zero
chance of success. Also, in order to maintain securityin the protocol, Alice
must respond to at most one challenge for a given witness; she should never
reuse a given witness.
Since Alice has communicated only that she has knowledge of a square root
of t A , then the protocol has the zero-knowledge property , which means that the
verifier, Bob, learns nothing from the prover, Alice, that could not have been
learned without Alice's participation. The zero-knowledge propertyensures that
interacting with Alice, as described in the protocol, does not leak information
that can be used to impersonate her.
We conclude the analysis with a discussion of types of protocols to show how
the above protocol fits in. Arbitrated protocols are those protocols relying on a
trusted third party, such as Trent, who will not render preferential treatment to
anyof the participants. Trent has no allegiances to anyof the participants and
no particular reason to complete the protocol. Thus, Trent maybe considered
to be playing the role of a disinterested lawyer. Hence, all participating entities
are assured that what is done in the protocol is correct, and that their partic-
ular portion of the protocol is complete. The Feige-Fiat-Shamir protocol is an
arbitrated protocol.
The above discussion motivates us to complete the discussion of protocol
types, of which there are two. A variation of the arbitrated protocol is the
adjudicated protocol . This requires the introduction of our next character in
the cryptographic play, Judy the adjudicator . Judyis brought into the protocol
onlyif cheating byparticipants is suspected. In that case, she comes into the
playand analyzes the dispute, rendering a ruling to determine who is right and
determining the punishment for the entitywho is in the wrong. An example is a
scenario where Bob agrees to sell his house to Alice, who gives him a cheque for
it. If the cheque is fraudulent, or the keys are fake, they go before Judy to present
their case. Judyrules on the evidence presented and the entitywho cheated
is fined or imprisoned. There is, however, a third kind of protocol involving
no third party. A self-enforcing protocol is designed to make cheating a virtual
impossibility. Cheaters gain no advantage by not following the protocol. In
Section 5.4, we will encounter an example of such a protocol, coin flipping by
telephone .
We close this section with an alternative to the Feige-Fiat-Shamir scheme.
The following is based upon the intractabilityof the DLP (see page 164, es-
peciallyEquation (4.2)). We will require the notion of a certificate , which is
a quantityof information that has been signed bya trusted authoritysuch as
Trent. One type of certificate pertinent to the following, and protocols to be
considered later in the text, is an identification certificate , which contains iden-