Verification of the private components of a public-key cryptographic system6952476Abstract A method of exchanging digital public-key verification data whereby a first computing entity (102) enables a second computing entity (104) to obtain probabilistic evidence that a given public-key number n is the product of exactly two odd primes p and q, not known to the second party, whose bit lengths (l(p), l(q)) differ by not more than d bits. The method provides an efficient proof of knowledge protocol for demonstrating Monte-Carlo evidence that a number n is the product of two odd primes of roughly equal size. The evidence is shown "in the dark", which means that the structure is verified without the prime factors of n disclosed. The cost of a proof amounts to 12klog2 n multiplications of integers of size of n where k is the number of the iterations in the proof and relates to an error probability bounded by max(½k, 24/n1/4). Claims 1. A method of exchanging digital public-key verification data whereby a first party enables a second party to obtain probabilistic evidence that a given public-key number n is the product of exactly two odd primes p and q, not known to the second party, whose bit lengths (l(p), l(q)) differ by not more than d bits; the method including the following steps, all operations being to mod P unless specified mod n, the method being halted should any check fail; Description TECHNICAL FIELD
It can be seen that the results of a Solovay-Strassen primality test are obtained on both p and q by steps f) of this method. Furthermore, the applicant has determined that the difficulty of finding p and q from knowledge of n, A and B of this test is at least as difficult as solving the decision problem on the membership of the Diffe-Hellman quadruples generated by g. (This is assumes that factorization of n and computing discrete logarithms to the base g are infeasible). Thus, if a verifier could be convinced that a prover has provided values for step f) which are properly related to p, q and the value of h (supplied by the verifier), the verifier would equally be confident of the Solovay-Strassen primality test using those values provide. The present invention is as claimed in the claims. SUMMARY OF THE INVENTION The present invention, in a first aspect, provides a method of exchanging digital public-key verification data whereby a first party enables a second party to obtain probabilistic evidence that a given public-key number n is the product of exactly two odd primes p and q, not known to the second party, whose bit lengths (l(p), l(q)) differ by not more than d bits. The method including the following steps, all operations being to mod P unless specified mod n, the method being halted should any check fail. Initial parameters are established by:
Thereafter:
The cost of a proof amounts to 12klog2 n multiplications of integers of size of n where k is the number of the iterations in the proof and relates to an error probability bounded by max(½k, 24/n1/4). To achieve cost and error similar to these, previous techniques require two additional conditions: (1) n is a Blum integer, and (2) a mutually trusted klog2n-bit long random source is accessible by the proving/verification participants. In failure of (1), k must be increased substantially in order to keep error probability comparably small (e.g., k should be increased to 3000 for an error probability to remain at the level of ½60). The present invention, in further aspects, encompasses computing entities and a communications system, a system of co-operating computing entities all for carrying out this protocol and a computer storage medium on which is stored instructions to enable general purpose computers to carry out the protocol. BRIEF DESCRIPTION OF THE DRAWINGS For a better understanding of the invention and to show how the same may be carried into effect, there will now be described, by way of example only, specific embodiments, methods and processes according to the present invention with reference to the accompanying drawings in which: FIG. 1 illustrates schematically transmission of encrypted data from a first to second computing entity; FIG. 2 illustrates schematically physical and logical resources of the computing entities illustrated in FIG. 1; FIG. 3 illustrates schematically data communications between the computing entities of FIGS. 1 and 2; FIGS. 4A to 4C illustrates schematically process steps carried out by the one of the computing entities of FIGS. 1 and 2; and FIGS. 5A to 5C illustrates schematically process steps carried out by the other of the computing entities of FIGS. 1 and 2. DETAILED DESCRIPTION OF THE BEST MODE FOR CARRYING OUT THE INVENTION There will now be described by way of example the best mode contemplated by the applicant for carrying out the invention. In the following description numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent however, to one skilled in the art, that the present invention may be practiced without limitation to these specific details. In other instances, well-known methods and structures have not been described in detail so as not to unnecessarily obscure the present invention. There will now be described with reference to FIGS. 1 to 4 herein a method and apparatus by which private components p,q of a public-key n may be verified according to a first specific implementation of the present invention. Referring to FIG. 1, there is illustrated schematically a pair of computing entities 102,104 configured for communicating electronic data with each other over a communications network, in this case the internet 106, by communicating data 108,110 to each other via the internet 106 in well known manner. Illustrated in FIG. 1 is first computing entity 102, herein after referred to as entity A and a second computing entity 104 herein referred to as entity B. In the example illustrated in FIG. 1, the first and second computing entities 102,104 are geographically remote from each other and whilst in the best mode herein, the communications network comprises the known internet 106, in other embodiments and implementations of the present invention the communications network could comprise any suitable means of transmitting digitized data between the computing entities. For example, a known Ethernet network, local area network, wide area network, virtual private circuit or public telecommunications network may form the basis of a communications medium between the computing entities 102,104. The computing entities 102 and 104 have been programmed by storing on memory programs read from computer program storage media 112,114, for example, a CD-ROM. Referring now to FIG. 2, there is illustrated schematically physical resources and logical resources of the computing entities A and B. Each computing entity comprises at least one data processing means 200,202, a memory area 203,205, a communications port 206,208, for communicating with other computing entities. There is an operating system 209,211, for example a known Unix operating system. One or more applications programs 212, 214 are configured for operating for receiving, transmitting and performing data processing on electronic data received from other computing entities, and transmitted to other computer entities in accordance with specific methods of the present invention. Optionally there is a user interface 215,217 which may comprise a visual display device, a pointing device, e.g. a mouse or track-ball device, a keypad, and a printer. Under control of the respective application program 212,214, each of the computing entities 102, 104 is configured to operate according to a first specific method of the present invention. Referring to FIG. 3 herein, there is illustrated schematically data communications passed between the first and second computing entities to effect verification by B of A's private components of a public-key according to the first specific implementation of the present invention. Applications programs 212,214 operate a set of algorithms that effect implementation of the verification protocol. The precise implementation of the algorithms is preferably made in a conventional prior art programming language, for example the language C, or C++ using conventional programming techniques which are known to those skilled in the art. For a better understanding of the implementation of the algorithms, the following presents a model, notation and explanation of the verification protocol. It will be understood by those skilled in the art that the algorithmic steps are used to control the logical and physical resources of the computing entities by being programmed into the applications in a conventional programming language. Referring now to FIGS. 3, 4 and 5, there will now be described the operation of two computing entities commonly referred to Alice and Bob which will be adopted here. The computing entity 102 and computing entity 104 by following the steps of FIGS. 4 and 5, respectively, exchanging signals representative of various data values as shown in Figure. First, the computing entities agree on a set of parameters as follows, where Alice 102 is the prover and Bob 104 is the verifier. Alice has constructed n=pq such that p and q are distinct odd primes with |l(p)-l(q)|≦d (i.e., the lengths of the two primes differ by at most d bits). The length of n is generally at least 512 to meet common security standards. d is preferably no greater than 2 but can be larger. The disadvantage of a larger d is that as d increases it will reach a threshold where the probability of p and q are primes when the test of the present invention is passed becomes dependent on n not k. A proof will be abandoned on Alice's instigation if any check she (i.e., the computing entity A) performs fails and will be rejected by Bob if any check he (ie the computing entity B) performs fails. First, Alice shall help Bob to set up a multiplicative group of order n. For her part, Alice only needs to generate a prime P with n|(P-1). This prime can be constructed by testing the primality of P=2a n+1 for a=1,2, . . . , until P is found to be prime. By the prime number theorem (general form due to Dirichlet, see e.g., p. 28 of [E. Kranakis. Primality and Cryptography, Wiley-Teubner Series in Computer Science, John Wiley & Sons, 1986]), for fixed n with P=2a n+1≦N, there are roughly ##EQU8## Such P's which are under N and are primes. Note that N≦2a n+1 and n>φ(2n). So ##EQU9## Since Alice's primality test procedure uses a=1,2, . . . , the above inequality indicates a non-trivial probability for two primes to show up upon a reaching 1n(2n 1n n). So one can be sure that a is small (likely to be bounded by 1n(2n 1n n)). It will be computationally easy for Alice to find the prime P (step 402). Once P is found to be prime, Alice sends the numbers n and P to Bob (step 404, data 302). Upon receipt of n and P (step 501), Bob tests the primality of P (step 502). If P is not a prime the proof is rejected (step 504). Upon passing of the test, Bob chooses a random element f<P (step 506), and sets
Upon receipt of g (step 406), Alice shall check OrdP(g)=n (step 408). If this does not hold, Alice may not be able to pass a proof later and so abandons the proof (step 410). Above we have reasoned that 2a=(P-1)/n is small (<<n). Thus, for n=pq, there can only be a few factors of P-1 which are less than n and are fully known to Alice. So it will be computationally easy for Alice to check OrdP(g)=n. Upon passing this simple checking, Alice shall set
Upon receipt of (A, B)(step 512), Bob shall check the following:
For clarity, we shall omit the trailing mod P operation in the following protocol specification which, for reference will be called Two—Prime—Product (n, g, A, B, P) The following steps are repeated k times
If c=0 and any of the checks of step 534 fails then Bob rejects the proof (step 536). Similarly, if c=1 and if the checks of step 538 fail, then Bob rejects the proof (step 536). If the checks at step 534 all pass, Bob decides if a primality check for a further value of n is required (step 540). If "Yes" Bob chooses another h(step 520) and another iteration is carried out; if "No" the protocol is ended (step 542). If the checks at step 538 all pass, Bob checks for Monte-Carlo evidence at step 539 and then determines if another iteration is to be carried out (step 540). Alice then determines if Bob wishes to go through a further iteration (step 434). If "Yes" it returns to step 420, if "No" the protocol ends. We shall see below that the two congruences checked in step 6.3 actually evaluate the Jacobi (Legendre) symbols ##EQU12## Using challenges of the negative Jacobi symbol has the virture of not disclosing the quadratic residue information of the challenges. In contrast, many square-root displaying protocols (e.g., [R. Gennaro, D. Miccianicio and T. Rabin. An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, In 5gh ACM Conference on Computer and Communications Security, October 1998, J. van de Graaf and R. Peralta. A simple and secure way to show the validity of your public-key, Advances in Cryptology—Proceedings of CRYPTO 87 (E. Pomerance, ed.), Lecture Notes in Computer Science, Springer-Verlag, 293 (1988), pp. 128-134]) disclose such information. The protocol allows for the two factors to have size differences satisfying |l(p)-l(q)|≦d. Larger size differences, if desirable, can be accommodated by adjusting the inequalities in steps 5.1 and 6.1. We analyze the security the protocol, which consists of the properties of completeness, soundness, and privacy. Completeness Theorem 1 If Alice follows the specification of Two—Prime—Product, a proof will be accepted. Proof We show that Bob will be satisfied by the checks performed in protocol step 5.1 through step 5.4. First, we show the inequalities in 5.1. Alice has set p and q such that pq=n Obviously Adding (1) to (2) yields Alice has chosen l(u)=l((p-1)/2). With p odd, (p-1)/2 is a whole number and l((p-1)/2)=l(p)-1. So when c=0 and When c=1 So for both cases, (3) will imply Analogously we can show In the following, we shall only examine the cases under c=1, since c=0 will render the congruences in 5.2 through 5.4 to hold trivially. In 5.2, noting that gp≡A (mod P) and the structures of U and r, it is easy to see that the first congruence will hold. The second congruence holds similarly. To see that the congruences in 5.3 will hold, observe ##EQU13## The first congruence in (4) is due to OrdP(B)=p|n. Then, since p is prime, the second congruence in (4) follows from Euler's criterion. Therefore, the first congruence in 5.3 (for c=1) is: ##EQU14## while the second congruence in 5.3 (for c=1) is, analogously, ##EQU15## The exponents of the both right-hand sides must take opposite signs since Jacobi symbols only take values ±1 and h has been chosen to satisfy ##EQU16## Therefore the congruences in 5.3 will hold. Finally, any h∈Zn* will satisfy With (p-1)/2, (q-1)/2 and (n-1)/2 being whole numbers, it is easy to rewrite the above into Therefore the congruence in 5.4 will hold. Soundness We now show that protocol Two—Prime—Product provides a Monte-Carlo method for testing the primality of the orders of A and B. We firstly note that all the numbers and variables to appear in this section are non-negative integers. In particular, logg(A) and logg(B) denote some positive integers p and q less than OrdP(g) satisfying A≡gp(mod P) and B≡gq(mod P). Lemma 1 Without the knowledge of the factorization of n, the element g fixed by Bob satisfies for any x divides n. Proof Without the knowledge of the factorization of n. Bob's procedure for fixing g is via g=f(P-1)/n mod P using f which is chosen at random from ZP*. Then gn≡1 (mod P) by Fermat's Theorem. In the cyclic group ZP* there are exactly n=Σd|nφ(d) elements of orders dividing n. Only these elements can be the candidates for g. For the same reason, for any x|n|P-1, there are exactly x=Σd|xφ(d) elements in ZP* of orders dividing x. The claimed probability is thus calculated as that of picking x objects from n. Lemma 2 Denote OrdP(B)=x and OrdP(A)=y. Upon acceptance of a proof on running Two—Prime—Product(n, g, A, B, P), Bob accepts that his random choice of h in the protocol run ((h, n)=1 and ##EQU17## satisfies ##EQU18## and the probability for failing this does not exceed ½k where k is the number of iterations used in the protocol. Proof The first congruence in 5.2 shows that Alice knows both logg(U) (shown when c=0) and logg(U A)=logg(U)+logg(A) (shown when c=1), and has added logg(A) to the response whenever c=1 is the case. Suppose Alice does not know logg(A). Then in each iteration she can only answer Bob's random challenge with at most ½ chance of correctness. Thus, after having verified k times of correct responses to his random challenges, Bob should agree that the probability for Alice not having used logg(A) in her response (when c=1) is at most ½k. The first congruence in 5.3 further shows that HU is generated from B with the use of an exponent which is in turn generated from Bob's randomly chosen challenge h. Since (h, n)=1, (hr mod n, n)=1. Therefore Clearly, the quantity logg(A) in 2r+1 (when c=1) amounts to (logg(A)-1)/2 in r. Therefore the first congruence in 5.3 shows that for h satisfying (h, n)=1: Analogously we can use the second congruence in 5.3 to establish that for the same h In the rest of this section we will continue denoting Following the Solovay-Strassen primality test technique [17] we define the following set Clearly, this set is a subgroup of Zx*. It is a variation of its counterpart used in the Solovay-Strassen primality test technique. There, Hx is defined such that the exponent a is (x-1)/2. In our "test in the dark" method., the verifier Bob is not given the modulus x, let alone does he know the relation between the exponent and the modulus. All the information Bob has is that the modulus is a factor of n, and that the exponent is a constant. (The result of Lemma 2 stipulates the constant be (logg(A)-1)/2.) Lemma 3 Let x, y and h be as in Lemma 2. Bob accepts that x and y are prime powers. The probability for failing this does not exceed ½k. Proof We prove the lemma by estimating the probability for x not being a prime power. A prime power can be written as pr with p prime and r≧1. Suppose x is not a prime power. Then let x=ξn with ξ>1, n>1 and (ξ, n)=1. Obviously, either Hx is a proper subgroup of Zx*, or Hx=Zx*. In the first case, #Hx is at most half of #Zx* (since the former must divide the latter), and thereby the probability for each h randomly picked from Zx* to fall in Hx cannot exceed ½, which amounts to ½k to bound the probability for k such h's to be so. Now we consider Hx=Zx*. We claim that Hx will only contain elements satisfying where a is the constant in (5). Suppose Hx=Zx* while (6) is not true for some element in Hx. Let h be such an element. So ha≡-1(mod x). Since ξ and n are relatively prime, by the Chinese remainder theorem, the system f≡1 (mod ξ), f≡h (mod n) has a solution f∈Zx*. Obviously, yielding So f∈Zx*\Hx, contradiction to Hx=Zx*. So now we must consider Hx=Zx* with all elements in Hx satisfying (6). This implies that for k randomly chosen h's with (h mod y, y)=1, hβ≡-1 (mod y) where β=(logg(B)-1)/2. Let z be a prime factor of y. Then we will also have (hβ mod z, z)=1 and Since z is prime, by Fermat's Theorem we know z-1|2β, i.e., β is a multiple of (z-1)/2. In Zz* there are exactly half the elements which are quadratic non-residues satisfying (7) (none of other elements can satisfy it). So the probability for this congruence to hold for k randomly chosen h's cannot exceed ½k. This value must also bound the probability for x not being a prime power. By symmetry, y is also a prime power. Lemma 4 Under the hypotheses of Lemma 3, (x, y)=1, and the probability for failing this does not exceed ½k. Proof Since x and y are both prime powers, if (x, y)>1, we can assume without loss of generality that x=pr|y. Using the result of Lemma 2 we can derive At the same time we have Thus, for all k instances of randomly-picked h with (h, p)=1. Since p is prime, the above is only possible if p-1 divides 2|a-β| but not divides |a-β|. So |a-β| is an odd multiple of (p-1)/2 which implies for all such h mod p. There are only half the elements in Zp* which are quadratic non-residues satisfying (8). Therefore the probability for (8) to hold for k time, i.e., for k random h's with h mod p being quadratic non-residues will not exceed ½k. Since the congruence in (8) is derived from the assumption (x, y)>1, the value ½k also bounds the probability for (x, y)>1. Lemma 5 Under the hypotheses of Lemma 2, there exists integers a and b satisfying Proof From the proof of Lemma 2 we know that A is generated from g. So its order y can only be reduced from OrdP(g) and thereby y|OrdP(g). We also know This means By symmetry, x|OrdP(g)|x logg (B). Then xy |OrdP(g) since (x, y)=1 (Lemma 4). Combining this with (9), we have x|logg(A). By symmetry we can also derive and y|logg(B). So we can write for some a and b. In protocol step 5.1. Bob has checked that in both challenge cases, the responses r and s satisfy Since when the challenge is c=1, l(logg(A))≦l(2r+1)=l(r)+1, This implies By symmetry, by=logg(B)≦8n1/2. Now we can prove the soundness of our protocol. Theorem 2 Upon acceptance of a proof Two—Prime—Product(n, g, A, B, P) with n≧244 and odd, Bob accepts that logg(A) and logg(B) are distinct odd primes. The probability for failing this does not exceed max(½k, 24/n1/4) where k is the number of iterations used in the proof. Proof We know x≠y since they axe relatively prime to each other. Both are odd since both divide an odd number n. By symmetry; we only need to prove the case for x=logg(A) to be a prime. We have already established ax=logg(A) (Lemma 5) and x=pr with p being prime (Lemma 3). So to prove this theorem we need only to show a=r=1. We shall establish the probability for Bob to accept the proof while assuming either r>1, or a>1. Using the method that we have used in the proof of Lemma 3, we shall reason that if any of these two cases is true, then either Hx (defined in (5)) should be a proper subgroup of Zx*, which will render ½k to bound the probability for Bob to accept a proof of k iterations, or another event of a negligibly small probability should has occurred. First, consider the case of r>1. There exists h∈Zp which yields So there exists λ satisfying This means pr-1 is relatively prime to pr, impossible with r>1. So Hx must be a proper subgroup of Zx*. The remaining case is a>1 and x prime. There exists h∈Zx* of full order x-1. If h is not in Hx then Hx is a proper subgroup and we have done. Now suppose h∈Hx. The first congruence in Lemma 2 implies which further implies x-1|ax-1=a(x-1)+a-1. So x-1|a-1. This is only possible if x≦a. From Lemma 5, ax≦8n1/2. So x2≦ax≦8n1/2, or x<3n1/4. Lemma 5 also requires logg(B)=by ≦8n1/2. These yield So, this case of logg(A) requires xby<24n3/4. From (10), Ordp(g)|xby. Also, OrdP(g)|n. So OrdP(g)|(xby, n)≦xby≦n(n≧244). Now we can apply Lemma 1 and obtain We have shown that if x is not a prime, or x≠logg(A), then the probabilities for Bob to accept the proof are bounded by either ½k, or 24/n1/4, whichever is larger. The latter value bounds the probability for Bob to have chosen g of such a small order. Remark In the proof of Theorem 2 and Lemma 3 we have used random elements in Zx*. We should point out that in the protocol Bob only picks h at random from Zn*, rather than from Zx*, since he does not know the factorization of n. Also h is chosen to have the negative Jacobi symbol mod n. However, the mapping from such h in Zn*, to h mod x in Zx* is onto (the mapping is accomplished by the double exponentiations checked in protocol step 5.3) and thereby results in uniformly distributed elements in Zx*. Theorem 3 Under the hypotheses of Theorem 2, n=logg(A)logg(B), and the probability for failing this does not exceed max(½k, 8/n1/4). Proof In Theorem 2 we have proved logg(A) logg(B)=xy=OrdP(g) |n where x and y are distinct primes. Suppose n=xyz for some integer z. We prove the theorem by estimating the probability for z>1. The congruence checked in protocol step 5.4 implies that each h that Bob chooses at random satisfies Define the following set as a subgroup of Zn*: Since x, y are distinct primes, there exists h∈Zn*, of order max(x-1, y-1). If h∉H then H is a proper subgroup of Zn* and #H cannot exceed the half of #Zn*. Thus, the probability for choosing k random elements from Zn* which also fall in H (to pass the congruence in step 5.4) will not exceed ½k. Now suppose h∈H. Without loss of generality, let x-1≧y-1. Then from (11) we can derive This is only possible if x≦z. Given y≦8n1/2, the maximum possible value for OrdP(g)=xy=n/z can only be resulted from the maximum possible value of x=z, which renders Applying Lemma 1 we know that the probability for Bob having chosen g of such a small order does not exceed 8/n1/4. Thus, we can use max(½k, 8/n1/4) to bound the probability for z>1. To this end we know that the two primes factors of n have roughly equal size since As a concluding remark for our soundness analysis, we emphasize the importance of verifying the congruences in the protocol step 5.3. Besides their roles in the soundness proof that we have seen, they also exclude x and y from being certain pseudo-primes such as Carmichael numbers (see e.g., p. 137 of [13]). Moreover, they prevent x and y from being methodically chosen in a cheating way that can pass a (flawed) protocol in [12] for proof of a required format for RSA moduli. (The required format is the same as what our protocol proves: n is the product of exactly two primes of roughly equal size.) That protocol first applies a square-root displaying protocol to prove that n is the product of two prime powers ([12] suggests to use the method of [9] for proof of Blum integers; we will discuss more on square-root displaying protocols in Section 4), and then verifies (equivalent to the congruence checked in our protocol step 5.4), plus checking the sizes of x and y. Below we reason that such verification does not suffice for proving the required format of n. Let n=xy with x, y being odd. It is easy to see that, as long as λ(n) (Carmichael function of n, which is the lowest order of all elements in Zn*) divides (x-1)(y-1)/2=(n-1)/2-[(x-1)+(y-1)]/2, the congruence above will always pass. Alice can thus cheat as follows. She sets x=pr with p prime and r>1 such that y=2pr-1+1 is prime and l(x)≈l(y). There are sufficiently many primes p such that 2pr-1+1 is also prime. So it will be easy for Alice to find p and y to satisfy what is required. Clearly, n is the product of two prime powers, and will therefore pass a Blum integer proof based on displaying square roots of challenges. The size checking on x and y will pass too. Moreover, and So it always holds Consequently, verification using hx+y≡hn+1(mod n) will pass for all h∈Zn*. But n is not the product of exactly two primes, and the sizes of its prime factors are not roughly equal (l(p)≈l(y)/r). Privacy In addition to n Alice has also made available the following two constants: Were these two constants not available, the prime factors of n are protected by the factorization problem. On the other hand, were n not available, given the two constants (A, B) to find (p, q) one faces the discrete logarithm problem. Our privacy analysis shall nevertheless identify whether finding p and q will still remain a hard problem given the availability of both n and (A, B). Clearly, we can no longer consider the problem to be those of pure factorization or pure discrete logarithm. To identify the exact difficulty for finding p, q from n and (A, B), suppose there exists an efficient algorithm A such that with input (g, A, B, n) it will output p and q in time bounded by a polynomial in the size of n. We should keep in mind that A works because the input values are related by Were the input values not related in any way then because to date there exists no polynomial-time algorithms to factor integers or to compute discrete logarithms, A should not have output logg(A), logg(B) in time bounded by any polynomial in the size of n. For any z with (z, n)=1, (12) is equivalent to So with input (g, Az, Bz Further notice that for any z<q, A′≡Az(mod P) forms a permutation in the subgroup generated by A. Analogously for any z′<p, B′≡Bz′(modP) forms a permutation in the subgroup generated by B. Thus, given an arbitrary quadruple (g, A′, B′, 1), A forms a decision procedure to answer whether (g, A′, B′, 1) is a member of the Diffie-Hellman quadruples generated by g. Theorem 4 Under the assumptions that factorization of n and computing discrete logarithms to the base g are infeasible, finding p, q, from the constants A, B and the modulus n is at least as difficult as solving a decision problem on the membership of the Diffie-Hellman quadruples generated by g. This membership decision problem is often referred to as Decision-Diffie-Hellman Problem ([15, 18]) and is widely regarded hard. Performance The operations in the protocol mainly involve exponentiations modulo big integers and evaluation of Jacobi symbols. Because the cost of the latter is trivial in comparison to that of the former, we shall focus our attention of estimating the cost of modulo exponentiations. We shall not consider the cost for Alice to generate n and the related prime P=2an+1 since these procedures are purely local to Alice (while a protocol involves communications). She can prepare these two numbers well in advance before running the protocol. However, the cost to Bob of testing the primality of P should be included in the cost for him to run the protocol. Testing the primality of P using a Monte-Carlo method needs k testing iterations to achieve ½k error probability (using k the same as that in the protocol to equalize the error probability). Each iteration mainly involves exponentiation mod P so for this part, Bob performs k exponentiations mod P. In the proof protocol, in each iteration Alice computes four exponentiations mod P and two of them mod n. Bob performs slightly more: four of them mod P and on average 2.5 of them mod n (2 for c=0 and 3 for c=1). Thus, with a proof of k iterations, Alice computes 4k exponentiations mod P and 2k of them mod n. For Bob's part adding the cost of testing the primality of P, he should perform in total 5k exponentiations mod P and 2.5 of them mod n. Notice the fact that P=2an+1 where a is small (at the level of 1n(2n 1n n), see Section 3.2). We have This means that the size of P may exceed that of n by only a few bits (for instance for any n of size less than 10,000 bits, log2[2 1n(2n 1n n)]<5, which is less than two percent of the size of n). Since the previous equation renders that the growth of the size difference between the two moduli is much slower than that of the moduli, we can claim that for n any size larger than 512 bits (recommended least size for today), the size of P will not exceed that of n by two percent (of the size of n), namely
For n of size larger than 512 bits, the computational cost of proving and verifying that n is the product of two primes of roughly equal size using protocol Two—Prime—Product is 12klog2n multiplications of integer of size of n. Both parties should perform this number of operations. Considering the fact that a Monte-Carlo primality test on non-secret number mainly involves modulo exponentiation, Bob's verification cost is equal to eight such tests on non-secret numbers of size n. We have constructed an efficient knowledge proof protocol for demonstrating an integer being the product of two prime factors of roughly equal size. The new protocol is the first of its kind that proves such a structure with efficiency comparable to that of a Monte-Carlo method for primality evidence "in the dark". Previous techniques for proving such a structure have a much higher cost for non-Blum integers (as will be discussed below). The improved efficiency for reasoning about non-Blum integers due to this work manifests a particular suitability for using the proposed protocol in the proof of valid RSA keys which are generated at uniformly random (e.g., for the protocol of Blackburn and Galbraith (S. R. Blackburn and S. D. Galbraith. Certification of secure RSA keys, University of Waterloo Centre for Applied Cryptographic Research, Technical Report CORR 90-44. The cost of a proof amounts to 12klog2n multiplications of integers of size of n where k is the number of the iterations in the proof and relates to an error probability bounded by max(½k, 24/n1/4). This is the first protocol that proves the two-prime-product structure of a number with the cost at the level of O(klog2n) multiplications and the error probability at the level of ½k (considering k=60, and n>2512, ½k>>24/n1/4) regardless of whether the number in question is a Blum integer [M. Blum. Coin flipping by telephone: a protocol for solving impossible problems, Proceedings of 24th IEEE Computer Conference (CompCon), 1982, pp. 133-137].
|
Same subclass Same class Consider this |
||||||||||