ńňđ. 7 |

where we use to denote the probability that the choice of in Step

4 of VallĂ©eâ€™s algorithm will map to the line

Remark 2. So that the above terminology works when (or

lies in the chest or feet, we can pretend that these points lie on a single

â€śline.â€ť

Focusing on the first summand in the expression above, the simulator can

compute each of the two probabilities in this term efficiently. First, the simu-

lator computes the number of integers in denoting this number by

is simply Next, for the second probability, suppose

that is the approximation used in Step 4 of VallĂ©eâ€™s algorithm derived

from her lower bounds (namely, for the legs, and

that is her approximation for the number

of points on (Warning: our notation collides here with VallĂ©eâ€™s definition

of and Then, In a similar

fashion, the simulator can compute the necessary probabilities for

thereby obtaining a perfectly uniform drawing algorithm.

VallĂ©e was presumably content with finding a quasi-uniform drawing al-

gorithm, since a uniform algorithm would not have improved her result of a

provable factoring algorithm by a significant

amount. However, as described below, our uniform drawing algorithm has a

significant practical impact on Coronâ€™s partial-domain hash variant of Rabinâ€™s

signature scheme.

4.2 Improving Coronâ€™s Results for Rabin-PDH

Coron [16] provided a random-oracle security proof for a partial-domain hash

Rabin signature scheme (Rabin-PDH), in which the signature is a modular

square root (up to a fudge factor) of where H is a partial-

domain hash with output space for is a possibly

constant function, and is a constant. In Rabin signing, a common fudge factor

is to accept the signature if for any

when N = pq for and In this case,

is an integer in for and if is positive,

or for and if is negative. Coronâ€™s proof requires

that be very small in magnitude (e.g., 16 or 256) [16], so that

is sufficiently small. One reason that Rabin-PDH was an interesting problem

for Coron to analyze was that partial-domain hashes were already being used by

standardized encoding schemes. For example, ISO 9796-2 defined the encoding

As mentioned above, Coron provides a proof of security for Rabin-PDH when

is at least but this can be quite large in practice.

Coronâ€™s security proof relies completely on his algorithm for drawing integers

from with a distribution whose distance from uniform is at most

This statistical distance must be very small, so that an adversary cannot distin-

guish a real attack from a simulated attack, in which the simulator uses Coronâ€™s

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 189

drawing algorithm to respond to hash queries. For the statistical distance to be at

most we must have that which implies that

This implies that is at least When

for example, must be at least This means that,

for Coronâ€™s technique does not reduce the minimum output size of the

hash function at all, until N is at least 3 Â· 364 = 1092 bits!

We get a better, and much more practical, provable security result by using

our perfectly uniform drawing algorithm. In particular, since our algorithm al-

lows us to draw uniformly for we can prove

a reduction from factoring to Rabin-PDH when is only

over 300 bits less than Coronâ€™s result for Moreover, the proof of security

is tighter than Coronâ€™s proof for two reasons: 1) the adversary cannot possi-

bly distinguish the simulated distribution from uniform; and 2) Coronâ€™s proof,

which adapts his proof for RSA-FDH [15], does not provide a tight reduction

from factoring (cf. Bernstein [6]).

For completeness, we prove the security of a specific variant of our improved

Rabin-PDH, though it should be clear that our drawing algorithm can work

with essentially any variant. We pick the one (succintly) described below for

its simplicity. Other variants may have advantages; e.g., Bernsteinâ€™s [6] security

reduction is tighter by a small constant, and Bellare and Rogaway [3] describe

an encoding scheme that allows (at least partial) recovery of the message being

signed.

Let N be the public key, with N = pq for and

Let be the unique number modulo N that satisfies and

Let be the partial-domain hash function

with and be a keyed

hash function, with the key known only to the signer. To sign M, the signer first

computes and then:

1. Sets if else, sets

2. Sends mod

To verify, the recipient checks that either or

This scheme can be easily modified, Ă la Bernstein [6], to avoid

the computation of Jacobi symbols.

In Appendix A, we prove the following theorem.

Theorem 5. Assume that there is a chosen-message attack adversary that

breaks our Rabin-PDH scheme for modulus N in time with probability Then,

in the random oracle model, there is an algorithm that factors N in time

with probability where and

5 The Compression Algorithms

In the previous section, we reduced the permissible output size of the hash

function in Rabin-PDH to about but Rabin-PDH signatures are

TEAM LinG

Craig Gentry

190

still log N bits. In this section, we describe compression algorithms that allow

us to compress not only Rabin-PDH signatures, but also Rabin ciphertexts (not

to mention aggregate signatures, ring signatures, signcryptions, and so on).

A prerequisite of any compression algorithm is to understand the distribu-

tion of what is being compressed. VallĂ©e gives a constructive characterization

of the distribution, in of integers in we leverage her character-

ization to construct a lossless compression algorithms. Roughly speaking, we

associate to strings of about bits that specify the

Farey interval and its â€śaddressâ€ť (according to VallĂ©eâ€™s rough

enumeration) within that interval. For a B-element in a wider Farey interval,

we use fewer bits of the bit string to specify the Farey interval and more bits to

specify its address; on balance, it evens out.

Our compression algorithms involve two nondeterministic quasi-bijections,

(used in the signature schemes) and

(used in the encryption scheme), for

small nonnegative constants and These mappings are not actual bijections;

we call them â€śnondeterministic quasi-bijectionsâ€ť since the image of an element

under each mapping or its inverse has a small constant cardinality; formally:

Definition 7 (Nondeterministic Quasi-bijection). For sets and

constants we say is an

if:

1. For all the cardinality of is in

2. For all the cardinality of with is in

Above, is an auxiliary set â€“ e.g., it may be used as a source of (a small number

of) random dummy bits if one wishes to make randomized. The purpose of

is simply to make an actual â€śmapping,â€ť with a single output for a given input

(even though for a single there may be multiple outputs). Notice that an

actual bijection is a (1,1,1,1)-quasi-bijection.

Roughly speaking, our signature scheme uses to compress, without loss,

a Rabin-PDH signature (an element of to a short bit string. Since the

â€śentropyâ€ť of the hash output in Rabin-PDH is about one may hope

that a Rabin-PDH signature can also be this short; in fact, within a few bits, this

is precisely the case. To verify the compressed signature, it is decompressed to

recover the ordinary Rabin-PDH signature, which is then verified in the normal

fashion. Our encryption scheme uses to map encoded bit strings to integers in

which are then squared to create short ciphertexts. Both and are

efficiently computable and efficiently invertible â€“ i.e., it is easy to recover from

or from â€“ without any trapdoor information.

Why donâ€™t we just replace with Indeed, we could if were a bijec-

tion, but (unfortunately) maps each to possibly several short

strings; if we used to map short encoded messages to mul-

tiple plaintexts would correspond to the same ciphertext, which we wish to avoid.

Thus, although the only real difference between and is that we reduce the

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 191

size of domain to ensure that it is an injection, we find it convenient to keep

the notation separate.

Mapping B-Elements to Short Strings (The Quasi-bijection)

5.1

Below, we give one approach to the quasi-bijection. Roughly speaking,

re-expresses a according to its Farey interval and its â€śaddressâ€ť

(using VallĂ©eâ€™s lattice) within the Farey interval. For example, a â€śnaiveâ€ť way to

re-express is as where defines Farey interval, is the

index of the quasi-horizontal line that contains the lattice point associated to

and represents the lattice pointâ€™s position on the line. In this format, has at

most two representations, one corresponding to each Farey interval that contains

the only effect of is to pick one of these representations. We describe a

different format below that has tighter compression and does not suffer from the

parsing problems of the naive approach.

The quasi-bijection below maps to a short string in

where is a parameter whose value will be calibrated later.

Computing

1. Determine for which is in

2. Compute the smallest integer in with in

and the largest integer in with in

3. Compute the number of lattice points in the chest and feet of

and an upper bound for the number of points in the legs.

4. Using VallĂ©eâ€™s enumeration, select one integer in (there may

be several) that corresponds to the lattice point that is associated to

More specifically:

If is the point in the chest or feet, set

Otherwise, let be VallĂ©eâ€™s upper bound for the number of leg lattice

points on quasi-horizontal lines with index at most Compute the index

of the line containing Let be the actual number of lattice points

on the line with index and let be VallĂ©eâ€™s upper-bound

estimate. Suppose that is the lattice point on the line. Pick an integer

Pick an integer Set

Although not mentioned explicitly in the algorithm description above, VallĂ©eâ€™s

quasi-enumeration, and the steps that use this quasi-enumeration, depend on

the values of and (which we assume to be public, and which could be

most conveniently be set to 0 and Shortly, we will calibrate so that

is larger than (but within a constant of) In computing

is used â€“ either deterministically or as a source of random bits â€“ to

pick the values of and Given one can recover the value of as

follows:

TEAM LinG

192 Craig Gentry

Computing

1. Determine for which is in

2. Compute the smallest integer in with in

and the largest integer in with in

3. Compute the number of lattice points in the chest and feet of

and an upper bound for the number of points in the legs.

4. Compute From and compute the value of If

let be the point in the chest or feet. Otherwise, compute

the index such that as well as the value of

(defined as above), and let be the point on the quasi-horizontal

line with index

5. Set

Now, we calibrate to be as small as possible while still allowing the prop-

erty that at least one bit string in is uniquely associated to each

element. We can ensure this property if, for every interval,

â€“ i.e., the number of bit strings associated to is at least the

number of points in

Since and are separated by a distance greater than the

width of we get that where the latter term

is the half of the diameter of thus, we get

for which

To determine an we use an upper bound

proven by VallĂ©e [33]: Thus, if

As long as the estimate is an integer, this

then

implies that as desired. So, we can set

For this value of the mapping compresses to within 3 bits

of the theoretical minimum. The reader can verify that outputs an answer for

and that has exactly one possible output for each

every (i.e.,

(i.e.,

Mapping Short Strings to B-Elements (The Quasi-bijection)

5.2

Like the quasi-bijection maps short strings to However,

we would like to map short strings (e.g., plaintext strings) into injec-

tively (e.g., to allow correct decryption); thus, the set of short strings is smaller

than the set of (rather than the reverse). For that reason,

uses VallĂ©eâ€™s lower bounds (unlike Since is otherwise similar to we

relegate a precise description of to Appendix B.

In terms of performance, all steps of the and quasi-bijections and their

inverses are except (possibly) the determination of the Farey interval,

which uses continued fractions. However, even the continued fraction step can

be computed in time â€“ e.g., using adaptations of techniques from [14].

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 193

6 Compressed Rabin-PDH Signing

and Compressed Rabin-OAEP+ Encryption

In this section, we describe how to use the and quasi-permutations to achieve

a 33% reduction in the size of Rabin signatures and Rabin ciphertexts.

The signature case is easy to describe. Recall that, in Section 4.2, we de-

scribed how to construct a Rabin-PDH signature that satisfies either

or for where

For simplicity, letâ€™s assume that the

other cases can be handled similarly. In this case, we simply set the compressed

Rabin-PDH signature to be â€“ i.e., the quasi-permutationâ€™s com-

pression of for modulus N and parameters and To verify the compressed

Rabin-PDH signature, the verifier simply recovers from and then

verifies in the normal fashion. Note that anybody can create a compressed

Rabin-PDH signature from a (non-compressed) Rabin-PDH signature, and vice

versa, without needing trapdoor information â€“ i.e., the compression algorithm is

completely separate from the signing process.

The proof of security for compressed Rabin-PDH follows easily from the proof

of security for (non-compressed) Rabin-PDH. Specifically, let be a chosen-

message attack adversary against Compressed Rabin-PDH, and let be chosen-

message attack adversary against Rabin-PDH that interacts both with a â€śchal-

lengerâ€ť and with To respond to signature query on M, queries the

challenger regarding M, receives back Rabin-PDH signature and sends to

where Eventually, aborts or sends a forgery on a

message M* that it has never queried. aborts or computes

and sends to the challenger as its forgery.

The encryption case is more complicated, because the compression algorithm

cannot be separated from the encryption process. Unfortunately, this fact â€“

together with the fact the encryption scheme is not quite a one-way permutation

as required by OAEP+, but rather a quasi-bijection â€“ requires us redo the entire

OAEP+ security proof, albeit with relatively minor modifications. At a high

level, encryption and decryption proceed as follows:

Encryption:

Compute an encoding of M.

1.

Compute

2.

Compute

3.

Output as the ciphertext.

4.

Decryption:

1. Recover from and

2. Compute each such that

3. For each compute the values of

4. For each undo the message encoding, and confirm that the message M is

encoded correctly.

5. If an is encoded correctly, output the decryption; otherwise, indicate de-

cryption failure.

TEAM LinG

194 Craig Gentry

For VallĂ©eâ€™s parameters, for a given there are at most two values of in Step

3 â€“ i.e., â€“ so the encoding of at most 4 values of must be checked.

As mentioned in section 5 and further discussed in Appendix B, our preferred

parameters are and

Although we could use any of a variety of encoding schemes, we prove that

Compressed Rabin-OAEP+ has a tight reduction to factoring. The OAEP+

encoding scheme uses three hash functions:

and

where are security parameters. The quantities and should

be negligible. Let To encode message

the sender:

1. Picks a random

2. Sets and

3. Sets an integer.

In Step 4 of Decryption, the recipient decodes by parsing each candidate into

for and and then parsing into for for

and For each the recipient computes

and and tests whether If there is a unique

for which the condition is satisfied, the recipient outputs as the correct

plaintext; otherwise, it indicates a decryption failure. For technical reasons in

the security proof, we require that â€“ i.e., that the encrypter use as the

random bits in the computation of â€“ and that the decrypter indicate

a decryption failure if this is not done. For compressed Rabin-OAEP+, we prove

the following theorem in Appendix C.

Theorem 6. Let be an IND-CCA2 adversary that breaks Compressed Rabin-

OAEP+ in time with advantage for modulus N. Then

where is the success probability that a particular

algorithm can factor, and

is the complexity of encryption.

7 Extensions

In the full version of the paper, we describe compressed signcryption, aggregate

signature and ring signature schemes, in which we achieve a 33% bandwidth

reduction in comparison to Rabin-variants of the schemes in [24], [23] and [29].

We also note that our compression algorithms can be applied to allow shorter

identity-based secret and public keys for the Fiat-Shamir signature scheme and

Cocksâ€™ identity-based encryption scheme.

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 195

References

1. T.M. Apostol, Modular Functions and Dirichlet Series in Number Theory,

Springer-Verlag (1976).

K. Barr and Energy Aware Lossless Data Compression, in Proc. of

2.

MobiSys 2003.

3. M. Bellare and P. Rogaway, The Exact Security of Digital Signatures â€“ How to

Sign with RSA and Rabin, in Proc. of Eurocrypt 1996, LNCS 1070, pages 399â€“416.

Springer-Verlag, 1996.

4. M. Bellare and P. Rogaway, Optimal Asymmetric Encryption â€“ How to Encrypt

with RSA, in Proc. of Eurocrypt 1994, LNCS 950, pages 92â€“111. Springer-Verlag,

1994.

5. D.J. Bernstein, A Secure Public-Key Signature System with Extremely Fast Veri-

fication, 2000. Available at http://cr.yp.to/djb.html.

6. D.J. Bernstein, Proving Tight Security for Standard Rabin-Williams Signatures,

2003. Available at http://cr.yp.to/djb.html.

7. D.J. Bernstein, Reducing Lattice Bases to Find Small-Height Values of Univariate

Polynomials, 2003. Available at http://cr.yp.to/djb.html.

8. D. Bleichenbacher, Compressed Rabin Signatures, in Proc. of CT-RSA 2004.

9. D. Boneh, Simplified OAEP for the RSA and Rabin Functions, in Proc. of Crypto

2001, LNCS 2139, pages 275â€“291. Springer-Verlag, 2001.

10. D. Boneh, C. Gentry, B. Lynn, and H. Shacham, Aggregate and Verifiably Encrypted

Signatures from Bilinear Maps, in Proc. of Eurocrypt 2003, LNCS 2656, pages 416-

432. Springer-Verlag, 2003.

11. D. Boneh, G. Durfee, and N. Howgrave-Graham, Factoring for Large

in Proc. of Crypto 1999, LNCS 1666, pages 326â€“337. Springer-Verlag, 1999.

12. D. Boneh and R. Venkatesan, Breaking RSA May Not Be Equivalent to Factoring,

in Proc. of Eurocrypt 1998, LNCS 1233, pages 59â€“71. Springer-Verlag, 1998.

13. C. Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, in

Proc. of Cryptography and Coding 2001, LNCS 2260, Springer (2001). Available

at http://www.cesg.gov.uk/technology/id-pkc/media/ciren.pdf.

14. H. Cohen, A Course in Computational Algebraic Number Theory, 4th ed., Graduate

Texts in Mathematics, Springer, 2000.

15. J.S. Coron, On the Exact Security of Full Domain Hash, in Proc. of Crypto 2000,

LNCS 1880, pages 229-235. Springer-Verlag, 2000.

16. J.-S. Coron, Security Proof for Partial-Domain Hash Signature Schemes, In Proc.

of Crypto 2002, LNCS 2442, pages 613â€“626. Springer-Verlag, 2002.

17. D. Coppersmith, Finding a Small Root of a Univariate Modular Equation, in Proc.

of Eurocrypt 1996, LNCS 1070, pages 155-165. Springer-Verlag, 1996.

18. U. Feige, A. Fiat, A. Shamir, Zero-Knowledge Proofs of Identity, in Jour, of Cryp-

tology (1), pp. 77â€“94 (1988).

19. A. Fiat, A. Shamir, How to Prove Yourself: Practical Solutions to Identification

and Signature Problems, in Proc. of Crypto 1986, LNCS 263, pp. 186-194. Springer

(1986).

20. G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford

Science Publications edition).

21. J. Jonsson, A OAEP Variant with a Tight Security Proof, 2003. Available at

http://www.math.kth.se/Ëśjakobj/crypto.html.

22. A.K. Lenstra and E.R. Verheul, The XTR Public Key System, In Proc. of Crypto

2000, LNCS 1880, pages 1â€“20. Springer-Verlag, 2000.

TEAM LinG

Craig Gentry

196

23. A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham, Sequential Aggregate Sig-

natures from Trapdoor Homomorphic Permutations, in Proc. of Eurocrypt 2004,

LNCS 3027, pages 74â€“90. Springer-Verlag, 2004.

24. J. Malone-Lee and W. Mao, Two Birds One Stone: Signcryption Using RSA, 2002.

Available at http://www.hpl.hp.com/techreports/2002/HPL-2002-293.html.

25. A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography,

CRC Press, 1996.

26. S. Micali, A. Shamir, An Improvement of the Fiat-Shamir Identification and Sig-

nature Scheme, in Proc. of Crypto 1988, LNCS 403, pp. 244â€“247. Springer-Verlag

(1990).

27. H. Ong, C.P. Schnorr, Fast Signature Generation with a Fiat Shamir - Like Scheme,

in Proc. of Eurocrypt 1990, LNCS 473, pp. 432â€“440. Springer-Verlag (1990).

28. M.O. Rabin, Digitalized Signatures and Public-Key Functions as Intractable as

Factorization, MIT/LCS/TR-212, MIT Laboratory for Computer Science, 1979.

29. R.L. Rivest, A. Shamir, and Y. Tauman, How to Leak a Secret, in Proc. of Asiacrypt

2001, LNCS 2248, pages 552â€“565. Springer-Verlag, 2001.

30. K. Rubin and A. Silverberg, Torus-based Cryptography, in Proc. of Crypto 2003,

LNCS 2729, pages 349â€“365. Springer-Verlag, 2003.

31. V. Shoup, OAEP Reconsidered, in Proc. of Crypto 2001, LNCS 2139, pages 239-

259. Springer-Verlag, 2001.

32. A.K. Lenstra, A. Shamir, J. Tomlinson and E. Tromer, Analysis of Bernsteinâ€™s

Factorization Circuit, in Proc. of Asiacrypt 2002, LNCS 2501, pages 1â€“26. Springer-

Verlag, 2002.

33. B. VallĂ©e, Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic

Residues, In Proc. of STOC 1989, pages 98â€“106.

34. B. VallĂ©e, Generation of Elements with Small Modular Squares and Provably Fast

Integer Factoring Algorithms, Mathematics of Computation, vol. 56, no. 194, pages

823â€“849, 1991.

A Security Proof for Improved Rabin-PDH

To prove our scheme secure against existential forgery under chosen-message

attacks, we construct the following game:

Setup: gives the public key N, retaining for use as a random oracle.

Hash Queries: can make a query to the at any time. If

has received an identical query before, it responds as it did before. Other-

wise, responds by first generating a random value with

uniform distribution. It then generates a number with uni-

form distribution and sets It logs into its

(When there is a small complication â€“ namely, must be cho-

sen s.t. not only but also

The simulator can accomplish this easily

simply by discarding the sampled that donâ€™t satisfy the latter inequality

(50% of them for

Signature Queries: can make a query to the at any time.

responds by using to recover from its it then sends

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 197

Forgery: Eventually, the adversary either aborts or outputs a signature on a

message M for which it has not made a signature query.

One can easily confirm that responses, as well as its signature

responses, are indistinguishable from uniform; in fact, they are perfectly uniform.

Any forgery that manages to generate for message M must satisfy

or If made no at M,

then its probability of success is at most If did make an at M,

then recovers the value associated to M from its With probability

gives a nontrivial factor of N. Thus, and

B Details of the Quasi-bijection

Let where is a parameter whose value will be calibrated later.

The quasi-permutations sends to an element of as follows.

Computing

1. Compute and determine for which the result is in

2. Compute the smallest integer in with in

and the largest integer in with in

3. Compute the number of lattice points in the chest and feet of

and a lower bound for the number of points in the legs.

4. Using VallĂ©eâ€™s enumeration, select one lattice point (there may be

several) that corresponds to More specifically:

Pick an integer in

If pick the lattice point that has enumeration in the

chest or feet.

Otherwise, let be VallĂ©eâ€™s lower-bound for the number of leg lattice

points on quasi-horizontal lines with index at most Compute such that

Let be the number of lattice points on the line

with index and let be VallĂ©eâ€™s lower-bound estimate. Pick an integer

and set to be the point

in on the line.

5. Set where Output

We omit the description of since it should be clear from the above. Now,

we mention some of the properties of the quasi-permutation.

Choosing the parameters such that â€“ i.e.,

such that the lower bound on the number of points in is greater than

the number of bit strings associated to â€“ ensures that is at least 1,

since one can always find a value for in the computation of Notice that

where the latter term is the diameter of

This implies that Now, consider the parameters used

by VallĂ©e. VallĂ©e considered the case â€” so that

TEAM LinG

198 Craig Gentry

For this value of VallĂ©e proved a lower bound of

(see [33]). Thus, if then As long

as the estimate is an integer, this implies that as

desired. To ensure that is never zero, we want that

where the latter is the diameter of the narrowest

Farey interval. So, we can set to be anything between and

values closer to the latter involve less ciphertext expansion.

On the other hand, we would like and to be small positive constants.

This ensures that picking (and uniformly and outputting is a quasi-

uniform drawing algorithm for (this helps get a tight security proof for

the encryption scheme). The computation of outputs up to two values

of exactly one for each Farey interval that contains thus We

use VallĂ©eâ€™s upper bounds to bound Specifically, VallĂ©eâ€™s computations allow

to be upper bounded by

allowing us to upper bound the number of possible values of by 4, for Also,

there are at most (see VallĂ©eâ€™s Leg Theorem) possible values of so

is at most 4 Ă— 4 = 16. Accordingly, for and one

gets a (1,16,1, 2) quasi-bijection.

C Security Proof for Compressed Rabin-OAEP+

Recall the standard definition of security against adaptive chosen-ciphertext at-

tack. An algorithm â€śbreaksâ€ť the encryption scheme if, in the following game,

it outputs the correct value of in the final stage with more than negligible

advantage:

Setup: The challenger generates a Rabin modulus N and hash functions G,

and H, defined as above. It sends to

Phase 1: requests the challenger to decrypt ciphertexts of choosing.

Challenge: chooses two plaintexts and and sends them to the chal-

lenger. The challenger randomly chooses bit encrypts and sends

the ciphertext to

Phase 2: again requests the challenger to decrypt ciphertexts of choosing,

other than the Challenge ciphertext.

Output: Finally, outputs a bit

We define advantage as:

In the game above, algorithm plays the part of the challenger, using its

its control over the random oracles G, and H to respond to decryption

queries. We say that the system is if no attacker

limited to time to decryption queries, to G-queries, to

and to H-queries, has advantage more than Now, we define aspects of the

game more precisely.

Hash queries: can query G, or H at any time. In responding to these

queries, maintains a G-list, and H-list logging queries and responses. If

TEAM LinG

How to Compress Rabin Ciphertexts and Signatures (and More) 199

makes a query that is contained in one of lists, responds the same way

it did before. Otherwise, for G, it generates a random string with uniform

distribution, sends this to as its G-query response, and logs G-query and

its response on its G-list. It responds similarly to and H-queries. We

use the convention that before makes an on it makes a

G-query on and an H-query on

Challenge: At some point, produces two plaintexts on

which it wishes to be challenged. picks a random and encrypts

in the usual way. Let be the resulting ciphertext, and let and

M* denote the values corresponding to that would be obtained through the

decryption process.

Decryption Queries and Probability Analysis: can make decryption

queries at any time, subject to the constraint that it cannot query the Challenge

ciphertext in Phase 2. Our treatment of decryption queries closely tracks Shoupâ€™s

analysis for trapdoor permutations encoded using OAEP+. Shoupâ€™s analysis con-

sists of a sequence of games for each game a slight modification

of the previous one, where represents the attack on the encryption scheme,

and is a certain attack in which an adversary obviously has no advantage.

Shoup bounds for where is an adversaryâ€™s

probability of success in game thereby bounding an adversaryâ€™s advantage

in To reduce space, our proof draws heavily from Shoupâ€™s proof.

In game the decryption oracle decrypts ciphertext as usual, recovering

and in the process. The decryption oracle is identical to (e.g.,

it can find modular square roots) except that the decryption oracle in rejects

whenever is not on its G-list. Let be the event that a ciphertext rejected in

would not have been rejected in Consider a ciphertext submitted

to the decryption oracle. If and then since there is only a

single legitimate ciphertext generated from and M* (recall that we use

as the random bits in the quasi-bijection), would also have rejected. Our

analysis of the case of or is identical to Shoupâ€™s, leading to

the conclusion that

In game the decryption oracle is identical to that of except it rejects

when is not on its .H-list. Let be the event that a ciphertext rejected in

would not have been rejected in For ciphertext with not on the

H-list, we consider two cases:

Case 1: Now, and implies (again because we

made deterministic given Shoupâ€™s remaining analysis of this case also works

for our situation.

Case 2: Our analysis here is again identical.

Like Shoup, we obtain

In game the decryption oracle does not have access to a trapdoor, but

instead maintains a ciphertext-list. After receiving an it com-

putes all possible values of and It

logs these ciphertexts in its ciphertext-list. Shoupâ€™s probability analysis applies

to our case: His time-complexity analysis also applies: over the

TEAM LinG

200 Craig Gentry

course of the decryption oracleâ€™s complexity is

where is the complexity of the encryption function.

Game in which Shoup replaces the original random oracles with different

but identically distribute variables, also works in our case. (See [31] for details

of Note the new encryption oracle in is identically distributed to the old

one, even though is not a permutation in our case, since Shoupâ€™s changes

only affect input, not itself.

Game is the same as (we skipped describing except that the

encryption oracle chooses random strings and and

it uses these values in the computation of the ciphertext, as described in [31].

Since is only used to mask M*, Like Shoup, we also obtain in

our case that where is the event that queries

G at However, our proofs finally diverge significantly at this point. Shoup

describes an auxiliary game in which the encryption oracle is modified again

to simply output a random number in the ciphertext space (in our case,

and then he uses the fact that, for a permutation, comes

from a distribution identical to We cannot do this, since the quasi-bijection

chooses from â€“ and thus from the ciphertext space â€“ only quasi-

uniformly.

Instead, we define our as for chosen randomly with

uniform distribution, and (as always) and are defined with respect to this

ciphertext. Then, for reasons analogous to those used by Shoup, if we define

to be the event that queries G at in game we have

Letting be the event that queries H at in game we have that

Now, we claim that, if is an quasi-bijection, then

â€“ i.e., the probability

For brevity, denote the probability

and occur given the value for as chosen above â€“ by

where will be treated as a random variable. Notice that, for any

there exists a such that and is a nontrivial

factor of N; in fact, we can â€śpair offâ€ť the numbers in so that each

corresponds to exactly one Suppose that and

correspond to If queries and (which occurs

with probability then can use to find a nontrivial factor of N

by taking every pair queried by deriving the corresponding computing

and checking whether is a nontrivial factor.

Overall, we have that This proba-

bilility is less than by quasi-uniformity, where each

is paired off with a that gives a nontrivial factor. However, the probability

is less than probability of success, which proves

the claim.

For the same reason as in [31], Thus, we get

Collecting all of the results, we get the time and complexity

stated in the theorem.

TEAM LinG

On the Bounded Sum-of-Digits Discrete

Logarithm Problem in Finite Fields*

Qi Cheng

School of Computer Science

The University of Oklahoma

Norman, OK 73019, USA

qcheng@cs.ou.edu

Abstract. In this paper, we study the bounded sum-of-digits discrete

logarithm problem in finite fields. Our results concern primarily with

fields where The fields are called kummer extensions of

It is known that we can efficiently construct an element with order

greater than in the fields. Let be the function from integers

to the sum of digits in their expansions. We first present an algo-

rithm that given finds in random polynomial time,

provided that We then show that the problem is solvable in

random polynomial time for most of the exponent with

by exploring an interesting connection between the discrete logarithm

problem and the problem of list decoding of Reed-Solomon codes, and

applying the Guruswami-Sudan algorithm. As a side result, we obtain a

sharper lower bound on the number of congruent polynomials generated

by linear factors than the one based on Stothers-Mason ABC-theorem.

We also prove that in the field the bounded sum-of-digits dis-

crete logarithm with respect to can be computed in random time

where is a subexponential function and is the

bound on the sum-of-digits of the exponent, hence the problem is

fixed parameter tractable. These results are shown to be generalized to

Artin-Schreier extension where is a prime. Since every finite field

has an extension of reasonable degree which is a Kummer extension, our

result reveals an unexpected property of the discrete logarithm problem,

namely, the bounded sum-of-digits discrete logarithm problem in any

given finite field becomes polynomial time solvable in certain low degree

extensions.

1 Introduction and Motivations

Most of practical public key cryptosystems base their security on the hardness

of solving the integer factorization problem or the discrete logarithm problem

in finite fields. Both of the problems admit subexponential algorithms, thus we

have to use long parameters, which make the encryption/decryption costly if

the parameters are randomly chosen. Parameters of low Hamming weight, or

more generally, of small sum-of-digits, offer some remedy. Using them speeds

This research is partially supported by NSF Career Award CCR-0237845.

*

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 201â€“212, 2004.

Â© International Association for Cryptologic Research 2004

TEAM LinG

202 Qi Cheng

up the system while seeming to keep the security intact. In particular, in the

cryptosystem based on the discrete logarithm problem in finite fields of small

characteristic, using small sum-of-digits exponents is very attractive, due to the

existence of normal bases [1]. It is proposed and implemented for smart cards and

mobile devices, where the computing power is severely limited. Although attacks

exploring the specialty were proposed [14], none of them have polynomial time

complexity.

Let be a finite field. For if form a linear

basis of over we call them a normal basis. It is known that a normal

basis exists for every pair of prime power and a positive integer [11, Page

29]. Every element in can be represented as

where for The power of is a linear operation, thus

Hence to compute the power, we only need to shift the digits, which can be

done very fast, possibly on the hardware level. Let be an integer with

expansion

The sum-of-digits of in the expansion is defined as

When the sum-of-digits becomes the famous Hamming weight. To com-

pute we only need to do shiftings and at most many of multiplications.

Furthermore, the exponentiation algorithm can be parallelized, which is a prop-

erty not enjoyed by the large characteristic fields. For details, see [16].

1.1 Related Work

The discrete logarithm problem in finite field is to compute an integer such

that given a generator of a subgroup of and in the subgroup.

The general purpose algorithms to solve the discrete logarithm problem are the

number field sieve and the function field sieve (for a survey see [13]). They have

time complexity

for some constant when is small, or is small.

Suppose we want to compute the discrete logarithm of with respect to

base in the finite field If we know that the Hamming weight of is equal

to there is an algorithm proposed by Coppersmith (described in [14]), which

works well if is very small. It is a clever adaption of the baby-step giant-

step idea, and runs in random time It is proved in [14] that

the average-case complexity achieves only a constant factor speed-up over the

worst case. It is not clear how his idea can be generalized when the exponent

has small sum-of-digits in the base However, we can consider the very

TEAM LinG

On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 203

special case where for and

Recall that are the digits of in the expansion. It can be verified

that Coppersmithâ€™s algorithm can be applied in this case. The time complexity

becomes If it is much worse than the time complexity

of the function field sieve on a general exponent.

If the sum-of-digits of the exponent is bounded by is there an algo-

rithm which runs in time and solves the discrete logarithm problem

in for some function and a constant A similar problem has been raised

from the parametric point of view by Fellows and Koblitz [10], where they con-

sider the prime finite fields and the bounded Hamming weight exponents. Their

problem is listed among the most important open problems in the theory of

parameterized complexity [9]. From the above discussions, it is certainly more

relevant to cryptography to treat the finite fields with small characteristic and

exponents with bounded sum-of-digits.

Unlike the case of the integer factorization, where a lot of special purpose

algorithms exist, the discrete logarithm problem is considered more intractable

in general. As an example, one should not use a RSA modulus of about 1000 bits

with one prime factor of 160 bits. It would be vulnerable to the elliptic curve

factorization algorithm. However, in the Digital Signature Standard, adopted by

the U.S. government, the finite field has cardinality about or larger, while

the encryption/decryption is done in a subgroup of cardinality about As

another example, one should search for a secret prime as random as possible in

RSA, while in the case of the discrete logarithm problem, one may use a finite

field of small characteristic, hence the group of very special order. It is believed

that no trapdoor can be placed in the group order, as long as it has a large

prime factor (see the panel report on this issue in the Proceeding of Eurocrypt

1992). In order to have an efficient algorithm to solve the discrete logarithm,

we need that every prime factor of the group order is bounded by a polynomial

function on the logarithm of the cardinality of the field. Given the current state

of analytic number theory, it is very hard, if not impossible, to decide whether

there exists infinitely many finite fields of even (or constant) characteristic, where

the discrete logarithm can be solved in polynomial time.

In summary, there are several common perceptions about the discrete loga-

rithm problem in finite fields:

1. As long as the group order has a big prime factor, the discrete logarithm

problem is hard. We may use exponents with small sum-of-digits, since the

discrete logarithm problem in that case seems to be fixed parameter in-

tractable. We gain advantage in speed by using bounded sum-of-digits ex-

ponents, and at the same time keep the problem as infeasible as using the

general exponents.

2. If computing discrete logarithm is difficult, it should be difficult for any

generator of the group. The discrete logarithm problem with respect to one

generator can be reduced to the discrete logarithm problem with respect

to any generator. Even though in the small sum-of-digits case, a reduction

is not available, it is not known that changing the generator of the group

affects the hardness of the discrete logarithm problem.

TEAM LinG

204 Qi Cheng

1.2 Our Results

In this paper, we show that those assumptions taken in combination are incor-

rect. We study the discrete logarithm problem in large multiplicative subgroups

of the Kummer and Artin-Schreier extensions with a prescribed base, and prove

that the bounded sum-of-digits discrete logarithm are easy in those groups. More

precisely we prove constructively:

Theorem 1. (Main) There exists a random algorithm to find the integer given

and in in time polynomial in under the conditions:

1.

2. and

3. where and

Moreover, there does not exist an integer satisfying that

and

The theorem leads directly to a parameterized complexity result concerning

the bounded sum-of-digits discrete logarithm, which answers an important open

question for special, yet non-negligibly many, cases.

Corollary 1. There exists an element of order greater than in such

that the discrete logarithm problem with respect to the generator can be solved

in time where is a subexponential function and is the bound

of the sum-of-digits of the exponent in expansion.

A few comments are in order:

For a finite field if then there exists satisfying the

condition in the theorem, in the other words, there exists an irreducible

polynomial of form over if there exists such that

and then

As a comparison, Coppersmithâ€™s algorithm runs in exponential time in the

case where for and while our

algorithm runs in polynomial time in that case. On the other hand, Copper-

smithâ€™s algorithm works for every finite field, while our algorithm works in

Kummer extensions. Our result has an indirect affect on an arbitrary finite

field though, since every finite field has extensions of degree close to a given

number, which are Kummer extensions. As an example, suppose we want

to find such an extension of with degree about We first pick a

random close to such that Let be the order of in Z/nZ.

The field is a Kummer extension of and an extension of Ac-

cording to Theorem 1, there is a polynomial time algorithm which computes

the discrete logarithm to some element in provided that the sum-

of-digits of the exponent in the expansion is less than Hence our

result reveals an unexpected property of the discrete logarithm problem in

finite fields: the difficulty of bounded sum-of-digits discrete logarithm prob-

lem drops dramatically if we move up to extensions and increase the base of

the exponent accordingly.

TEAM LinG

On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 205

Numerical evidences suggest that the order of is often equal to the group

order and is close to the group order otherwise. However, it seems

hard to prove it. In fact, this is one of the main obstacles in improving the

efficiency of AKS-style primality testing algorithm [2]. We make the following

conjecture.

Conjecture 1. Suppose that a finite field and an element in the field

satisfy the conditions in Theorem 1. In addition, The order of

is greater than for an absolute constant

Even though we can not prove that the largest prime factor of the order of

is very big, it seems, as supported by numerical evidences, that the order of

which is a factor of bigger than is rarely smooth. For instance,

in the any generates the whole group The order

contains a prime factor of 749 bits. One should not attempt to apply

the Silver-Pohlig-Hellman algorithm here.

A natural question arises: can the restriction on the sum-of-digits in Theo-

rem 1 be relaxed? Clearly if we can solve the problem under condition

in polynomial time, then the discrete logarithm problem in subgroup

generated by is broken. If is a generator of then the discrete logarithm

problem in and any of its subfields to any base are broken. We find a sur-

prising relationship between the relaxed problem and the list decoding problem

of Reed-Solomon codes. We are able to prove:

Theorem 2. Suppose is chosen randomly from the set

There exists an algorithm given and in to find in time polynomial in

with probability greater than for some constant greater than

1, under the conditions:

1.

2. where and

Given a polynomial ring it is an important problem to deter-

mine the size of multiplicative subgroup generated by

where is a list of distinct elements in and for all

The lower bound of the order directly affects the time complex-

ity of AKS-style primality proving algorithm. In that context, we usually have

deg Assume that deg For a list of integers

we denote

by One can estimate the number of distinct congruent polynomi-

als of form modulo for E in certain set. It is obvious that if

then all the polynomials are in

different congruent classes. This gives a lower bound of Through a clever

TEAM LinG

206 Qi Cheng

use of Stothers-Mason ABC-theorem, Voloch [15] and Berstein [5] proved that

if then at most 4 such polynomials can fall in the same congruent

class, hence obtained a lower bound of We improve their result and

obtain a lower bound of

Theorem 3. Use the above notations. Let C be

If there exist pairwise different element such that

then Note that

By allowing negative exponents, Voloch [15] obtained a bound of Our

bound is smaller than his. However, starting from our method

gives better bounds. Details are left in the full paper. A distinct feature of our

bound is that it relates to the list decoding algorithm of Reed-Solomon codes.

If a better list decoding algorithm is found, then our bound can be improved

accordingly.

1.3 Organization of the Paper

The paper is organized as follows. In Section 2, we list some results of counting

numbers with small sum-of-digits. In Section 3, we present the basic idea and

the algorithm, and prove Theorem 1 and Corollary 1. In Section 4, we prove

Theorem 2 and Theorem 3. In Section 5, we extend the results to Artin-Schreier

extensions. We conclude our paper with discussions of open problems.

2 Numbers with Small Sum-of-Digits

Suppose that the expansion of a positive integer is

where for all How many nonnegative integers less

than satisfy Denote the number by Then

equals the number of nonnegative integral solutions of

under the conditions that for all The generating

function for is

If then the conditions can be removed, we have that

It is easy to see that if we have that

In the later section, we will need to estimate where is times

a small constant less than 2. Since

TEAM LinG

On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 207

Hence if

3 The Basic Ideas and the Algorithm

The basic idea of our algorithm is adopted from the index calculus algorithm. Let

be a Kummer extension of namely, Assume that where

is the characteristic. The field is usually given as where

is an irreducible polynomial of degree dn over If satisfies the condition in

Theorem 1, then must be an irreducible polynomial over Denote

by To implement our algorithm, it is necessary that we work in another

model of namely, Fortunately the isomorphism

can be efficiently computed. To compute where is a polynomial

of degree at most dn â€“ 1 over all we have to do is to factor over

and to evaluate at one of the roots. Factoring polynomials

over finite fields is a well-studied problem in computational number theory, we

refer to [3] for a complete survey of results. The random algorithm runs in

expected time and the deterministic algorithm

runs in time From now on we assume the model

Consider the subgroup generated by in recall

that and The generator has order greater than

[8], and has a very nice property as follows. Denote by we have

and more generally

In other words, we obtain a set of relations: for

This corresponds to the precomputation stage of the index calculus.

TEAM LinG

208 Qi Cheng

The difference is that, in our case, the stage finishes in polynomial time, while

generally it requires subexponential time. For a general exponent

If is an element in where is a polynomial of degree less

than and and then due to unique factorization

in can be completely split into the product of linear factors over

We can read the discrete logarithm from the factorizations, after the coefficients

are normalized. The algorithm is described as follows.

Algorithm 1 Input: in satisfying the conditions in

Theorem 1.

Output:

1. Define an order in (for example, use the lexicographic order). Compute

and sort the list

2. Suppose that is represented by where has degree less

than Factoring over let where

are in

3. (Normalization) Normalize the coefficients and reorder the factors of

such that their constant coefficients are and

where

4. Output

The step 1 takes time The

most time-consuming part is to factor a polynomial over with degree at most

The random algorithm runs in expected time and

the deterministic algorithm runs in time

Normalization and reordering can be done in time since we have

a sorted list of Thus the algorithm can be finished in

random time and in deterministic time

This concludes the proof of the main theorem.

Now we are ready to prove Corollary 1. Any where

is congruent to a product of at most linear factors

modulo If we have an algorithm running in time

according to Theorem 1. So we only need to consider the case when

The general purpose algorithm will run in random time where

is a subexponential function. Theorem 1 follows from the fact that

4 The Application of the List Decoding Algorithm

of Reed-Solomon Codes

A natural question arises: can we relax the bound on the sum-of-digits and

still get a polynomial time algorithm? Solving the problem under the condition

TEAM LinG

On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 209

basically renders the discrete logarithm problems in and

any of its subfields easy. Suppose that where has degree

less than Using the same notations as in the previous section, we have

Hence there exists a polynomial with degree such that

If the cardinality of is greater than then the curve will pass

at least points in the set

To find all the polynomials of degree which pass at least

points in a given set of points, is an instance of the list decoding problem of

Reed-Solomon codes. It turns out that there are only a few of such polynomials,

and they can be found efficiently as long as

Proposition 1. (Guruswami-Sudan [12] ) Given distinct elements

values and a natural number there are

at most many univariate polynomials of degree at most

such that for at least many points. Moreover, these polynomials

can be found in random polynomial time.

For each we use the Cantor-Zassenhaus algorithm to factor

There must exist a such that the polynomial can

be completely factored into a product of linear factors in

and is computed as a consequence.

4.1 The Proof of Theorem 2

In this section, we consider the case when If there are at least

number of nonzero then we can apply the Guruswami-

Sudan algorithm to find all the In order to prove Theorem 2, it remains to

show:

Lemma 1. Define as

and for

and as

We have

for some constant when is sufficiently large.

TEAM LinG

210 Qi Cheng

Proof. The cardinality of is

The cardinality of is less than The summands

maximize at if Hence we have

This proves the lemma with

4.2 The Proof of Theorem 3

Proof. Let be a positive real number less than 1. Define

Given if there exists such that

(mod there must exist a polynomial such that

and is a solution for the list decoding problem with input

According to Propostion 1, there are at most solutions. Thus the

number of congruent classes modulo that has is

greater than We have

It takes the maximum value at

5 Artin-Schreier Extensions

Let be a prime. The Artin-Schreier extension of a finite field is It is

easy to show that is an irreducible polynomial in for any

So we may take Let

For any we have

and similarly

TEAM LinG

On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 211

Hence the results for Kummer extensions can be adopted to Artin-Schreier ex-

tensions. For the subgroup generated by we have a polynomial algorithm

to solve the discrete logarithm if the exponent has sum-of-digits less than

Note that may be 0 in this case.

Theorem 4. There exists an algorithm to find the integer given and in

in time polynomial in under the conditions:

1. and

2. where and

Moreover, there does not exist an integer satisfying that

and

Theorem 5. There exists an element of order greater than in such

that the discrete logarithm problem with respect to can be solved in time

where is a subexponential function and is the bound of

the sum-of-digits of the exponent in the expansion.

Theorem 6. Suppose that where and

Suppose is chosen in random from the set

There exists an algorithm given and in to find in time polynomial in

with probability greater than for some constant greater than 1.

6 Concluding Remarks

A novel idea in the celebrated AKS primality testing algorithm, is to construct a

subgroup of large cardinality through linear elements in finite fields. The subse-

quent improvements [6,7,4] rely on constructing a single element of large order.

It is speculated that these ideas will be useful in attacking the integer factor-

ization problem. In this paper, we show that they do affect the discrete loga-

rithm problem in finite fields. We give an efficient algorithm which computes

the bounded sum-of-digits discrete logarithm with respect to prescribed bases

in Kummer extensions. We believe that this is more than a result which deals

with only special cases, as every finite field has extensions of reasonable degrees

which are Kummer extensions. For instance, if we need to compute the discrete

logarithm of in base we can construct a suitable Kummer extention

and try to solve the discrete logarithms of and with respect to a selected base

in the extension. This approach is worth studying. Another interesting problems

is to further relax the restriction on the sum-of-digits of the exponent. It is also

important to prove or disprove Conjecture 1. If that conjecture is true, the AKS-

style primality proving can be made compatible or even better than ECPP or

the cyclotomic testing in practice.

TEAM LinG

Qi Cheng

212

Acknowledgments

We thank Professor Pedro Berrizbeitia for very helpful discussions.

References

1. G. B. Agnew, R. C. Mullin, I. M. Onyszchuk, and S. A. Vanstone. An implemen-

tation for a fast public-key cryptosystem. Journal of Cryptology, 3:63-79, 1991.

2. M. Agrawal, N. Kayal, and N. Saxena. Primes is in P.

http://www.cse.iitk.ac.in/news/primality.pdf, 2002.

3. Eric Bach and Jeffrey Shallit. Algorithmic Number theory, volume I. The MIT

Press, 1996.

4. D. J. Bernstein. Proving primality in essentially quartic random time.

http://cr.yp.to/papers/quartic.pdf, 2003.

5. D. J. Bernstein. Sharper ABC-based bounds for congruent polynomials.

http://cr.yp.to/, 2003.

6. Pedro Berrizbeitia. Sharpening â€śprimes is in pâ€ť for a large family of numbers.

http://lanl.arxiv.org/abs/math.NT/0211334, 2002.

7. Qi Cheng. Primality proving via one round in ECPP and one iteration in AKS. In

Dan Boneh, editor, Proc. of the 23rd Annual International Cryptology Conference

(CRYPTO), volume 2729 of Lecture Notes in Computer Science, Santa Barbara,

2003. Springer-Verlag.

8. Qi Cheng. Constructing finite field extensions with large order elements. In ACM-

SIAM Symposium on Discrete Algorithms (SODA), 2004.

9. R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag,

1999.

10. M. Fellows and N. Koblitz. Fixed-parameter complexity and cryptography. In Pro-

ceedings of the Tenth International Symposium on Applied Algebra, Algebraic Al-

gorithms and Error-Correcting Codes (AAECCâ€™93), volume 673 of Lecture Notes

in Computer Science. Springer-Verlag, 1993.

11. Shuhong Gao. Normal Bases over Finite Fields. PhD thesis, The University of

Waterloo, 1993.

12. Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon

and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):

1757â€“1767, 1999.

13. A. M. Odlyzko. Discrete logarithms: The past and the future. Designs, Codes, and

Cryptography, 19:129â€“145, 2000.

14. D. R. Stinson. Some baby-step giant-step algorithms for the low Hamming weight

discrete logarithm problem. Math. Comp., 71:379â€“391, 2002.

15. J. F. Voloch. On some subgroups of the multiplicative group of finite rings.

http://www.ma.utexas.edu/users/voloch/preprint.html, 2003.

16. Joachim von zur Gathen. Efficient exponentiation in finite fields. In Proc. 32nd

IEEE Symp. on Foundations of Comp. Science, 1991.

TEAM LinG

Computing the RSA Secret Key Is Deterministic

Polynomial Time Equivalent to Factoring

Alexander May

Faculty of Computer Science, Electrical Engineering and Mathematics

University of Paderborn

33102 Paderborn, Germany

alexx@uni-paderborn.de

Abstract. We address one of the most fundamental problems concern-

ing the RSA cryptoscheme: Does the knowledge of the RSA public key/

secret key pair yield the factorization of N = pq in polynomial

time? It is well-known that there is a probabilistic polynomial time algo-

rithm that on input outputs the factors and We present the

first deterministic polynomial time algorithm that factors N provided

that and that the factors are of the same bit-size. Our

approach is an application of Coppersmithâ€™s technique for finding small

roots of bivariate integer polynomials.

Keywords: RSA, Coppersmithâ€™s method

1 Introduction

One of the most important tasks in public key cryptography is to establish the

polynomial time equivalence of

the problem of computing the secret key from the public information to

a well-known hard problem P that is believed to be computational infeasible.

This reduction establishes the security of the secret key under the assumption

that the problem P is computational infeasible. On the other hand, such a re-

duction does not provide any security for a public key system itself, since there

might be ways to break a system without computing the secret key.

Now let us look at the RSA scheme. We briefly define the RSA parameters:

Let N = pq be a product of two primes of the same bit-size. Furthermore, let

be integers such that where is Eulerâ€™s totient function.

For the RSA scheme, we know that there exists a probabilistic polynomial

time equivalence between the secret key computation and the problem of fac-

toring the modulus N. The proof is given in the original RSA paper by Rivest,

Shamir and Adleman [9] and is based on a work by Miller [8].

In this paper, we present a deterministic polynomial time algorithm that on

input outputs the factors provided that and are of the same

bit-size and that

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 213â€“219, 2004.

Â© International Association for Cryptologic Research 2004

TEAM LinG

214 Alexander May

In the normal RSA-case we have since axe defined modulo

This implies that as required. Thus, our algorithm establishes the

deterministic polynomial time equivalence between the secret key computation

and the factorization problem in the most common RSA case. We reduce the

problem of factoring N to the problem of computing the reduction in the

opposite direction is trivial.

Our approach is an application of Coppersmithâ€™s method [4] for finding small

roots of bivariate integer polynomials. We want to point out that some crypt-

analytic results [1,2] are based on Coppersmithâ€™s technique for solving modular

bivariate polynomial equations. In contrast to these, we make use of Copper-

smithâ€™s algorithm for bivariate polynomials with a small root over the integers.

Therefore, our result does not depend on the usual heuristic for modular multi-

variate polynomial equations but is rigorous.

To the best of our knowledge, the only known application of Coppersmithâ€™s

method for bivariate polynomials with a root over the integers is the so-called

â€śfactoring with high bits knownâ€ť [4]: Given half of the most significant bits of

one can factor N in polynomial time. Howgrave-Graham [6] showed that this

problem can be solved alternatively using an univariate modular approach (see

also [5]).

Since our approach directly uses Coppersmithâ€™s method for bivariate integer

polynomials, the proof of our reduction is brief and simple.

The paper is organized as follows. First, we present in Sect. 2 a deterministic

polynomial time algorithm that factors N on input provided that

This more restricted result is interesting, since RSA is frequently used with

small in practice. Additionally, we need only elementary arithmetic in order to

prove the result. As a consequence, the underlying algorithm has running time

Second, we show in Sect. 3 how to improve the previous result to the desired

bound by applying Coppersmithâ€™s method for solving bivariate integer

polynomials. We conclude by giving experimental results in Sect. 4.

An Algorithm for

2

In this work, we always assume that N is a product of two different prime factors

of the same bitsize, wlog This implies

We obtain the following useful estimates:

Let us denote by the smallest integer greater or equal to Furthermore, we

denote by the ring of invertible integers modulo

TEAM LinG

Computing the RSA Secret Key 215

In the following theorem, we present a very efficient algorithm that on input

outputs the factors of N provided that

Theorem 1 Let N = pq be an RSA-modulus, where and are of the same

bit-size. Suppose we know integers with ed > 1,

Then N can be factored in time

Proof: Since we know that

Next, we show that can be computed up to a small constant for our choice of

and Therefore, let us define as an underestimate of We observe

that

Using the inequalities and we conclude that

Since we know that Thus, one of the six values

must be equal to We test these six candidates successively. For

the right choice we can compute

From the value we can easily find the factorization of N.

Our approach uses only elementary arithmetic on integers of size log (N).

Thus, the running time is which concludes the proof of the theorem.

3 The Main Result

In this section, we present a polynomial time algorithm that on input

outputs the factorization of N provided that This improves upon the

result of Theorem 1. However, the algorithm is less efficient, especially when we

get close to the bound

Our approach makes use of the following result of Coppersmith [4] for finding

small roots of bivariate integer polynomials.

TEAM LinG

216 Alexander May

Theorem 2 (Coppersmith) Let be an irreducible polynomial in two

variables over of maximum degree in each variable separately. Let X, Y be

bounds on the desired solution Let W be the absolute value of the largest

entry in the coefficient vector of If

then in time polynomial in log W and we can find all integer pairs

with and

Now, let us prove our main theorem.

Theorem 3 Let N = pq be an RSA-modulus, where and are of the same

bit-size. Suppose we know integers with ed > 1,

Then N can be factored in time polynomial in the bit-size of N.

Proof: Let us start with the equation

Analogous to the proof of Theorem 1, we define the underestimate of

Using (1), we know that

Let us denote Therefore, we have an approximation for the unknown

parameter in (2) up to an additive error of

Next, we also want to find an approximation for the second unknown param-

eter in (2). Note that

That is, lies in the interval We can easily guess an estimate

of with additive error at most by doing a brute-force search on the

most significant bits of

More precisely, we divide the interval into 6 sub-interval of

For the correct choice of

length with centers

we have

Let denote the term for the right choice of That is, we know

for some unknown with

Plugging our approximations for and in (2) leads to

TEAM LinG

Computing the RSA Secret Key 217

Let us round and to the next integers. Here we omit the rounding brackets

for ease of simplicity. Notice that the effect of this rounding on the

bounds of the estimation errors and can be neglected becomes even

smaller). Thus, we assume in the following that are integers. Therefore, we

can define the following bivariate integer polynomial

with a root over the integers.

In order to apply Coppersmithâ€™s theorem (Theorem 2), we have to bound

the size of the root We define and Then,

and

Let W denote the of the coefficient vector of We have

By Coppersmithâ€™s theorem, we have to satisfy the condition Using

our bounds, we obtain

Thus, we can find the root in time polynomial in the bit-size of W using

Coppersmithâ€™s method. Note that the running time is also polynomial in the

bit-size of N since Finally, the term yields

the factorization of N. This concludes the proof of the theorem.

We want to point out that Theorem 3 can be easily generalized to the case,

where I.e., we do not necessarily need that and are

of the same bit-size. All that we have to require is that they are balanced up to

some polylogarithmic factor in N.

The following theorem is a direct consequence of Theorem 3. It establishes

the polynomial time equivalence of computing and factoring N in the common

RSA case, where

Theorem 4 Let N = pq be an RSA-modulus, where and are of the same

be an RSA public exponent.

bit-size. Furthermore, let

Suppose we have an algorithm that on input outputs in deterministic

polynomial time the RSA secret exponent satisfying

Then N can be factored in deterministic polynomial time.

4 Experiments

We want to provide some experimental results. We implemented the algorithm

introduced in the previous section on an 1GHz Linux-PC. Our implementation

of Coppersmithâ€™s method follows the description given by Coron [4].

reduction [7] is done using Shoupâ€™s NTL library [10].

TEAM LinG

218 Alexander May

We choose randomly. Therefore, in every experiment the product

ed is very close to the bound Notice that in Theorem 3, we have to do a

small brute-force search on the most significant bits of in order to prove

the desired bound. The polynomial time algorithm of Coppersmith given by

Theorem 2 requires a similar brute-force search on the most significant bits.

In Table 1, we added a column that states the total number of bits that one

has to guess in order to find a sufficiently small lattice vector. Thus, we have to

multiply the running time of the lattice reduction algorithm by a factor of

As the results indicate, the number heavily depends on the lattice dimension.

Coppersmithâ€™s technique yields a polynomial time algorithm when the lattice

dimension is of size However, we only tested our algorithm for lattices

of small fixed dimensions 16, 25 and 36.

Our experiments compare well to the experimental results of Coron [3]: One

cannot come close to the bounds of Coppersmithâ€™s theorem without reducing

lattices of large dimension. Notice that we have to guess a large number of bits.

In contrast, by the proof of Coppersmithâ€™s theorem (see [4]) the number of bits

that one has to guess for lattice dimension is a small constant. However,

it is a non-trivial task to handle lattices of these dimensions in practice.

TEAM LinG

Computing the RSA Secret Key 219

One might conclude that our method is of purely theoretical interest. But let

us point out that we have a worst case for our approach when the product ed is

very close to the bound In Table 2, we provide some more practical results

for the case

References

1. D. Boneh, G. Durfee, â€śCryptanalysis of RSA with private key less than

IEEE Trans. on Information Theory, Vol. 46(4), pp. 1339â€“1349, 2000

2. J. BlĂ¶mer, A. May, â€śNew Partial Key Exposure Attacks on RSAâ€ť, Advances in

Cryptology â€“ Crypto 2003, Lecture Notes in Computer Science Vol. 2729, pp. 27â€“

43, Springer-Verlag, 2003

3. Jean-SĂ©bastien Coron, â€śFinding Small Roots of Bivariate Integer Polynomial Equa-

tions Revisitedâ€ť, Advances in Cryptology â€“ Eurocrypt â€™04, Lecture Notes in Com-

puter Science Vol. 3027, pp. 492â€“505, Springer-Verlag, 2004

4. D. Coppersmith, â€śSmall solutions to polynomial equations and low exponent vul-

nerabilitiesâ€ť, Journal of Cryptology, Vol. 10(4), pp. 223â€“260, 1997.

5. D. Coppersmith, â€śFinding Small Solutions to Small Degree Polynomialsâ€ť, Cryp-

tography and Lattice Conference (CaLC 2001), Lecture Notes in Computer Science

Volume 2146, Springer-Verlag, pp. 20â€“31, 2001.

6. N. Howgrave-Graham, â€śFinding small roots of univariate modular equations re-

visitedâ€ť, Proceedings of Cryptography and Coding, Lecture Notes in Computer

Science Vol. 1355, Springer-Verlag, pp. 131â€“142, 1997

7. A. K. Lenstra, H. W. Lenstra, and L. LovĂˇsz, â€śFactoring polynomials with rational

coefficients,â€ť Mathematische Annalen, Vol. 261, pp. 513â€“534, 1982

8. G. L. Miller, â€śRiemannâ€™s hypothesis and tests for primalityâ€ť, Seventh Annual ACM

Symposium on the Theory of Computing, pp. 234â€“239, 1975

9. R. Rivest, A. Shamir and L. Adleman, â€śA Method for Obtaining Digital Signatures

and Public-Key Cryptosystemsâ€ť, Communications of the ACM, Vol. 21(2), pp. 120â€“

126, 1978

10. V. Shoup, NTL: A Library for doing Number Theory, online available at

http://www.shoup.net/ntl/index.html

TEAM LinG

Multi-trapdoor Commitments and Their

Applications to Proofs of Knowledge Secure

Under Concurrent Man-in-the-Middle Attacks*

ńňđ. 7 |