Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
The Schnorr Scheme was designed to be very fast and efficient, both from a computational point of view and in the amount of information that needs to be exchanged in the protocol. It is also designed to minimize the amount of computation performed by Alice. This is desirable because in many practical applications, Alices computations will be performed by a smart card with low computing power, while Bobs computations will be performed by a more powerful computer.
For the purpose of discussion, lets assume that ID (Alice) is a 512-bit string. v also comprises 512 bits, and s will be 320 bits if the DSS is used as a signature scheme. The total size of the certificate C(Alice) (which needs to be stored on Alices smart card) is then 1344 bits.
Let us consider Alices computations: step 1 requires a modular exponentiation to be performed; step 5 comprises one modular addition and one modular multiplication. It is the modular exponentiation that is computationally intensive, but this can be precomputed offline, if desired. The online computations to be performed by Alice are very modest.
It is also a simple matter to calculate the number of bits that are communicated during the protocol. We can depict the information that is communicated in the form of a diagram:
Alice gives Bob 1344 + 512 = 1856 bits of information in step 2; Bob gives Alice 40 bits in step 4; and Alice gives Bob 140 bits in step 6. So the communication requirements are quite modest, as well.
Figure 9.4 Issuing a certificate to Alice
In this section, we present a modification of the Schnorr Scheme due to Okamoto. This modification can be proved secure, assuming the intractibility of computing a particular discrete logarithm in .
To set up the scheme, the TA chooses p and q as in the Schnorr Scheme. The TA also chooses two elements both having order q. The value is kept secret from all the participants, including Alice. We will assume that it is infeasible for anyone (even a coalition of Alice and Olga, say) to compute the value c. As before, the TA chooses a signature scheme and hash function. The certificate issued to Alice by the TA is constructed as described in Figure 9.4. The Okamoto Identification Scheme is presented in Figure 9.5.
Here is an example of the Okamoto Scheme.
Example 9.4
As in previous examples, we will take p = 88667, q = 1031, and t = 10. Suppose α1 = 58902 and α2 = 73611 (both α1 and α2 have order q in ). Now, suppose α1 = 846 and α2 = 515; then v = 13078.
Figure 9.5 The Okamoto identification scheme
Suppose Alice chooses k1 = 899 and k2 = 16; then γ = 14574. If Bob issues the challenge r = 489 then Alice will respond with y1 = 131 and y2 = 287. Bob will verify that
So Bob will accept Alices proof of identity.
The proof that the protocol is complete (i.e., that Bob will accept Alices proof of identity) is straightforward. The main difference between Okamotos and Schnorrs scheme is that we can prove that the Okamoto Scheme is secure provided that the computation of the discrete logarithm is intractible.
The proof of security is quite subtle. Here is the general idea: As before, Alice identifies herself to Olga polynomially many times by executing the protocol. We then suppose (hoping to obtain a contradiction) that Olga is able to learn some information about the values of Alices secret exponents α1 and α2. If this is so, then we will show that (with high probability) Alice and Olga together will be able to compute the discrete logarithm c in polynomial time. This contradicts the assumption made above, and proves that Olga must be unable to obtain any information about Alices exponents by taking part in the protocol.
The first part of this procedure is similar to the soundness proof for the Schnorr Scheme.
THEOREM 9.2
Suppose Olga knows a value γ for which she has probability ∈ ≥ 1/2t-1 of successfully impersonating Alice in the verification protocol. Then, in polynomial time, Olga can compute values b1 and b2 such that
PROOF For a fraction ∈ of the 2t possible challenges r, Olga can compute values y1, y2, z1, z2, r and s with r ≠ s and
Define
b1 = (y1 - z1)(r - s)-1 mod q
and
b2 = (y2 - z2)(r - s)-1 mod q.
Then it is easy to check that
as desired.
We now proceed to show how Alice and Olga can together compute the value of c.
THEOREM 9.3
Suppose Olga knows a value γ for which she has probability ∈ ≥ 1/2t-1 of successfully impersonating Alice in the verification protocol. Then, with probability 1 - 1/q, Alice and Olga can together compute in polynomial time.
PROOF By Theorem 9.2, Olga is able to determine values b1 and b2 such that
Now suppose that Alice reveals the values α1 and α2 to Olga. Of course
so it must be the case that
Suppose that (a1, a2) ≠ (b1, b2). Then (a2 - b2)-1 mod q exists, and the discrete log
can be computed in polynomial time.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC