2. Description of GPS 2.1. Identification Schemes Based on the Discrete Logarithm Problem In 1989 Schnorr [42] proposed a nice proof of knowledge of a discrete logarithm in groups of known prime order. This proof is a more efficient version of previous pro- posals of Chaum et al. [11], [10] and Beth [4]. Such a proof can be used as an iden- tification scheme, and also converted into a signature scheme using the Fiat–Shamir paradigm [17]. In these schemes the size of the data is short, and the computation load is quite acceptable. Towards a more precise description, we let p be a prime number. We denote by Z∗ the set of invertible elements modulo p. Let q be a large prime divisor of p − 1 and let g be an element of Z∗ of order q , i.e. such that gq = 1 mod p but g = 1. The prover knows a secret element s in Zq and he wants to prove that he knows the discrete logarithm of I = g−s mod p in base g. We first notice that any verifier can immediately check that p is prime, q is a prime divisor of p − 1, g is of order q and that I belongs to the subgroup of Z∗ generated by g. This last verification just consists in checking that I q = 1 mod p. In order to prove knowledge of s , the prover first generates r ∈ Z∗ at random and sends the commitment x = gr mod p to the verifier who answers a challenge c randomly chosen in the interval [0, B − 1], where B is a publicly known system parameter. Next, the prover computes y = r + sc mod q and sends y to the verifier who checks the equation x = g y I c mod p. This elementary round can be repeated sequentially; we denote by the number of repetitions. The security analysis of the scheme shows that a prover accepted with probability substantially greater than 1/ B must know the discrete logarithm of I , i.e. the secret s ; the proof is sound. Furthermore, even a dishonest verifier cannot learn any additional information about the secret, whatever the number of authentications may be, if B and are polynomial in a security parameter, i.e. asymptotically “not too large”; the proof is perfectly zero-knowledge. Many modifications of the Schnorr scheme, that achieve additional properties, have been proposed. Firstly, one can use a composite modulus instead of a prime modulus and keep the factorization of the modulus secret. As a consequence, the order of the multiplicative group in which the computations are performed may remain secret. Furthermore, the order of the publicly known base g can also be public or private. In the Schnorr scheme, both the order p − 1 of the group and the order q of g are known. We will see that in the GPS scheme, both of those parameters can remain unknown to provers and verifiers. Other schemes, classified in Fig. 1, achieve different combinations. We now briefly review those protocols. The Okamoto scheme. The Schnorr scheme is known to be perfectly zero-knowledge if the parameters B and remain polynomial in a security parameter. The one-round ( = 1) variant remains sound if B is super-polynomial, but, as a consequence, this variant is perfectly zero-knowledge only with respect to an honest verifier, i.e. a verifier who randomly chooses the challenges. However, it is unknown how to prove the zero- knowledge property if the verifier can bias the distribution of his challenges. This means that, for large challenges, we can only prove the security of Schnorr identification against passive adversaries who just observe regular authentications. Exactly the same remark applies to the GPS scheme. A solution proposed by Okamoto [36] consists in using two bases g1 and g2 and to prove the knowledge of a “representation” (s1, s2) such that I = g11 g22 mod p. While this protocol is not proven to be zero-knowledge, it nonetheless is witness indistinguish- able [16]. As a consequence, provided the computation of the discrete logarithm of g1 in base g2 modulo p is intractable, the scheme is provably secure against active adversaries, even for large challenges (note that so is GPS, as explained in Section 3). The Brickell–McCurley scheme. In the protocol proposed in [7], the computations are still done modulo a prime number p but instead of using a base g of publicly known prime order q , the parameters are chosen such that p − 1 is divisible by the product q × w of two secret prime numbers. The rest of the scheme is similar to the Schnorr protocol; it uses a base g of order q but the answer y is equal to r + sc mod p − 1 in order not to reveal information about q . The main advantage of this variant is to base the security on the intractability of the discrete logarithm problem modulo p or on the factorization of p − 1. This means that it is secure if at least one of those two problems is difficult. The Girault scheme. The idea of [20] is to choose a composite modulus n = (2 f p + 1) × (2 fq + 1) where 2 f p + 1, 2 fq + 1, p, q and f are prime. The integer f is public, the base g has order f and the answer y is computed modulo f . A public key of a prover of identity ID is obtained with the formula I = ID1/e gs mod n where the eth root of ID is computed by an authority who knows the factorization of n and s is a secret key chosen by the prover. In this setting, an identification, in spirit, is a Schnorr proof of knowledge of the discrete logarithm (e × s ) of I e /ID mod n in base g. The GPS scheme. A way of improving the Schnorr protocol efficiency is to eliminate modular reductions during identification or signature. Exponentiation modulo p can be performed off-line by the user’s device or precomputed by an authority in a use & throw coupons [33] setting. Therefore, in order to reduce the on-line computation further to a very simple operation, it is natural to eliminate the second modulus q by performing the operations y = r + sc in Z. This was first proposed by Girault in [21] and analysed in [40] and [38]. The security analysis of this protocol is precisely the subject of the present 468 M. Girault, G. Poupard, and J. Stern paper in a more general setting. Note that in [23], the on-line operation is reduced to a single, but much longer, addition. Other schemes. A variant of GPS, called RDSA, has been proposed in [5] and analyzed in [18]. We can also note that the scheme described in [41] is based on the intractability of the factorization problem, but it can be seen as a proof of knowledge of a discrete logarithm where the order of the group and the order of the base are secrets owned by the prover. More recently, another factorization-based scheme has been proposed, in which the key pair is an RSA key pair [24]. 2.2. GPS Identification Scheme We now describe precisely the GPS identification scheme. The security analysis appears in the next section. Choice of the underlying mathematical structure. The GPS identification scheme is defined on a generic group G and uses a specific element, namely the base g ∈ G . In the theoretical security analysis of the next section, we only assume the intractability of computing discrete logarithms in the group G , in base g, for exponents in the range [0, S − 1] where S is a public parameter of the scheme. More precisely, we assume the existence of a randomized algorithm PP (ωpp , k ) that generates public parameters G and g according to a security parameter k using a random tape ωpp . In practice, several mathematical structures can be used; the most interesting choices for G are listed below: – G = Z∗ with p a prime number such that p − 1 has a large prime factor q ; the order of the base g should be q . We obtain a variant of the Schnorr identification scheme in which on-line computation is twice as fast for the same security. – The set G = Z∗ of invertible elements modulo an RSA modulus n, i.e. a composite integer with typically two prime factors of almost the same size. Note that the factors of n are no longer required so they can be discarded after the generation of n. Then g can be randomly chosen. It should ne noted that there exist parameters for which the computation of “short” exponents, typically of 160 bits, can be done very easily using partial Pohlig–Hellman techniques [45] if the order of g is known and if it has many small prime factors. Accordingly, we advise the use of modulus n which is the product of two strong primes, i.e. primes p such that ( p − 1)/2 is also prime. We also advise the use of the base g = 2 for efficiency reasons. – G can also be derived from an elliptic curve. Analogs of GPS in the elliptic curve setting can be defined in a straightforward manner; see for example [12]. – Much more sophisticated mathematical structures can also be used; the only con- straint is the intractability of the discrete logarithm with short exponent problem in such groups. An example of such an approach is proposed in [5]. Other public parameters. Besides the upper bound S for the secret keys, additional parameters of the GPS scheme are the number of elementary rounds and two integer bounds A and B , defined below. The relations between those parameters are analyzed inSection 3. We just summarize some facts about these parameters in order to make their meaning more explicit: – the probability of impersonation is 1/ B , – the computation of discrete logarithms in base g in the group G must be intractable for exponents in the interval [0, S − 1], – A must be significantly larger than S × B since it defines the size of some random data used to mask the secret. Public/private keys. The private keys s are integers chosen in the range [0, S − 1] and the related public keys I are computed in the group G by the relation I = gs . Protocol (see Fig. 2). We let = ( B − 1)( S − 1). A round of identification consists for the prover in randomly choosing an integer r in [0, A −1], and computing the commitment x = gr . Next, he sends x to the verifier, who answers a challenge c randomly chosen in [0, B − 1]. The prover checks c ∈ [0, B − 1] and computes the integer y = r + c × s . He sends y to the verifier who checks g y = x × I c and y ∈ [0, A + − 1]. A complete identification consists in repeating the elementary round times. The theoretical analysis shows that should be super-logarithmic in the security parameter in order to be able to prove the security of the scheme against active adversaries, as in the Schnorr scheme. However, in many practical applications, will often be equal to = 1. As usual in this kind of scheme, many straightforward variants can be designed, such as choosing I = g−s and/or y = r − c × s , with some trivial impact on the rest of the protocol. 2.3. GPS Signature Scheme We can turn the identification scheme into a signature scheme by following the technique originally proposed by Fiat and Shamir [17], and used by Schnorr [42] and many others: challenges c are no longer randomly chosen by a verifier but computed by means of a 470 M. Girault, G. Poupard, and J. Stern hash function h with output range [0, B − 1], with B larger than in the identification scheme. The signature of a message m is computed by taking a random r in [0, A − 1] and computing x = gr , c = h (m , x ) and y = r + cs . This produces the signature (x , c, y ) that may be checked by anybody using the equations c = h (m , x ), y ∈ [0, A + ( B − 1) × ( S − 1) − 1] and g y = x I c . Furthermore, well known optimizations, described in Section 5.2, such as reducing the signature to the pair (c, y ) can be applied. This leads to the following signature scheme: Input: – public parameters (G , g, A, B, S), – hash function h (•), with output range [0, B − 1], – signer’s private key s , – message encoded as an integer m . Operations: signature (c, y ) shall be computed by the following sequence of steps: 1. Randomly generate an integer r from the range [0, A − 1]. 2. Compute x = gr . 3. Compute c = h (m , x ). 4. Compute y = r + c × s . 5. Output (c, y ). A signature is verified using the following scheme: Input: – public parameters (G , g, S, A, B ), – hash functions h (•), – signer’s public key I , – message encoded as an integer m , – signature to be verified (c, y ), a pair of integers. Output: “valid” if m and (c, y ) are consistent given the public key; “invalid” otherwise. Operations: output shall be computed by the following sequence of steps: 1. If c is not in [0, B − 1] or y is not in [0, A + ( B − 1) × ( S − 1) − 1] output “invalid” and stop. 2. Compute x = g y / I c . 3. Compute c = h (m , x ). 4. If c = c then output “valid” else output “invalid”.
Posted on: Mon, 01 Jul 2013 08:53:15 +0000
Trending Topics
Recently Viewed Topics
© 2015