Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
There remains to be considered the possibility that (a1, a2) = (b1, b2). If this happens, then the value of c cannot be computed as described above. However, we will argue that (a1, a2) = (b1, b2) will happen only with very small probability 1/q, so the procedure whereby Alice and Olga compute c will almost surely succeed.
Define
That is, consists of all the possible ordered pairs that could be Alices secret exponents. Observe that
where . Thus consist of q ordered pairs.
The ordered pair (b1, b2) computed by Olga is certainly in the set . We will argue that the value of the pair (b1, b2) is independent of the value of the pair (a1, a2) that comprises Alices secret exponents. Since (a1, a2) was originally chosen at random by Alice, it must be the case that the probability that (a1, a2) = (b1, b2) is 1/q.
So, we need to say what we mean by (b1, b2) being independent of (a1, a2). The idea is that Alices pair (a1, a2) is one of the q possible ordered pairs in the set , and no information about which is the correct ordered pair is revealed by Alice identifying herself to Olga. (Stated informally, Olga knows that an ordered pair from comprises Alices exponents, but she has no way of telling which one.)
Lets look at the information that is exchanged during the identification protocol. Basically, in each execution of the protocol, Alice chooses a γ; Olga chooses an r; and Alice reveals y1 and y2 such that
Recall that Alice computes
and
where
But note that k1 and k2 are not revealed (nor are a1 and a2).
The particular quadruple (γ, r, y1, y2) that is generated during one execution of the protocol appears to depend on Alices ordered pair (a1, a2), since y1 and y2 are defined in terms of a1 and a2. But we will show that each such quadruple could equally well be generated from any other ordered pair . To see this, suppose and where 0 ≤ θ ≤ q - 1. We can express y1 and y2 as follows:
and
where all arithmetic is performed in . That is, the quadruple (γ,r,y1,y2) is also consistent with the ordered pair using the random choices and to produce (the same) γ. We have already noted that the values of k1 and k2 are not revealed by Alice, so the quadruple (γ,r,y1,y2) yields no information regarding which ordered pair in Alice is actually using for her secret exponents. This completes the proof.
This security proof is certainly quite elegant and subtle. It would perhaps be useful to recap the features of the protocol that lead to the proof of security. The basic idea involves having Alice choose two secret exponents rather than one. There are a total of q pairs in the set that are equivalent to Alices pair (a1, a2). The fact that leads to the ultimate contradiction is that knowledge of two different pairs in provides an efficient method of computing the discrete logarithm c. Alice, of course, knows one pair in ; and we proved that if Olga can impersonate Alice, then Olga is able to compute a pair in which (with high probability) is different from Alices pair. Thus Alice and Olga together can find two pairs in and compute c, which provides the desired contradiction.
Here is an example to illustrate the computation of by Alice and Olga.
Example 9.5
As in Example 9.4, we will take p = 88667, q = 1031 and t = 10, and assume that v = 13078.
Suppose Olga has determined that
Then she can compute
b1 = (131 - 890)(489 - 199)-1 mod 1031 = 456
and
b2 = (287 - 303)(489 - 199)-1 mod 1031 = 519.
Now, using the values of a1 and a2 supplied by Alice, the value
c = (846 - 456)(519 - 515)-1 mod 1031 = 613
is computed. This value c is in fact as can be verified by calculating
58902613 mod 88667 = 73611.
Finally, we should emphasize that, although there is no known proof that the Schnorr Scheme is secure (even assuming that the discrete logarithm problem is intractible), neither is there any known weakness in the scheme. Actually, the Schnorr Scheme might be preferred in practice to the Okamoto Scheme simply because it is somewhat faster.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC