Cryptography: Theory and Practice:Identification Schemes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

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, Alice’s computations will be performed by a smart card with low computing power, while Bob’s computations will be performed by a more powerful computer.

For the purpose of discussion, let’s 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 Alice’s smart card) is then 1344 bits.

Let us consider Alice’s 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

9.3 The Okamoto Identification Scheme

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 α₁ = 58902 and α₂ = 73611 (both α₁ and α₂ have order q in ). Now, suppose α₁ = 846 and α₂ = 515; then v = 13078.

Figure 9.5 The Okamoto identification scheme

Suppose Alice chooses k₁ = 899 and k₂ = 16; then γ = 14574. If Bob issues the challenge r = 489 then Alice will respond with y₁ = 131 and y₂ = 287. Bob will verify that

So Bob will accept Alice’s proof of identity.

The proof that the protocol is complete (i.e., that Bob will accept Alice’s proof of identity) is straightforward. The main difference between Okamoto’s and Schnorr’s 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 Alice’s secret exponents α₁ and α₂. 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 Alice’s 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/2^t-1 of successfully impersonating Alice in the verification protocol. Then, in polynomial time, Olga can compute values b₁ and b₂ such that

PROOF For a fraction ∈ of the 2^t possible challenges r, Olga can compute values y₁, y₂, z₁, z₂, r and s with r ≠ s and

Define

b₁ = (y₁ - z₁)(r - s)^-1 mod q

and

b₂ = (y₂ - z₂)(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/2^t-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 b₁ and b₂ such that

Now suppose that Alice reveals the values α₁ and α₂ to Olga. Of course

so it must be the case that

Suppose that (a₁, a₂) ≠ (b₁, b₂). Then (a₂ - b₂)^-1 mod q exists, and the discrete log

can be computed in polynomial time.

Table of Contents