![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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, where The ordered pair (b1, b2) computed by Olga is certainly in the set 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 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 and where all arithmetic is performed in 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 Here is an example to illustrate the computation of 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 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |