![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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.
9.3 The Okamoto Identification SchemeIn 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 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
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 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 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.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |