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
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
4.2 Improving Coronâ€™s Results for Rabin-PDH
Coron  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) , 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
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 , does not provide a tight reduction
from factoring (cf. Bernstein ).
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  security
reduction is tighter by a small constant, and Bellare and Rogaway  describe
an encoding scheme that allows (at least partial) recovery of the message being
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 , 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
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
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
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)
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.
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
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
192 Craig Gentry
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
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
To determine an we use an upper bound
proven by VallĂ©e : Thus, if
As long as the estimate is an integer, this
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
Mapping Short Strings to B-Elements (The Quasi-bijection)
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 .
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:
Compute an encoding of M.
Output as the ciphertext.
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
5. If an is encoded correctly, output the decryption; otherwise, indicate de-
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:
where are security parameters. The quantities and should
be negligible. Let To encode message
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.
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 ,  and .
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.
How to Compress Rabin Ciphertexts and Signatures (and More) 195
1. T.M. Apostol, Modular Functions and Dirichlet Series in Number Theory,
K. Barr and Energy Aware Lossless Data Compression, in Proc. of
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.
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,
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
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
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
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.
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
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-
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
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
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.
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
198 Craig Gentry
For this value of VallĂ©e proved a lower bound of
(see ). 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
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
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 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
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  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 .
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-
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
For the same reason as in , Thus, we get
Collecting all of the results, we get the time and complexity
stated in the theorem.
On the Bounded Sum-of-Digits Discrete
Logarithm Problem in Finite Fields*
School of Computer Science
The University of Oklahoma
Norman, OK 73019, USA
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
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
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 . 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 , none of them have polynomial time
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
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 .
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 ). They have
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 ), 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  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
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 , 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 . 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
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.
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:
3. where and
Moreover, there does not exist an integer satisfying that
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
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.
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 . We make the following
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:
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
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
206 Qi Cheng
use of Stothers-Mason ABC-theorem, Voloch  and Berstein  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  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
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
On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields 207
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  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
, 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.
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
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
3. (Normalization) Normalize the coefficients and reorder the factors of
such that their constant coefficients are and
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
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  ) 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
Lemma 1. Define as
for some constant when is sufficiently large.
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
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:
2. where and
Moreover, there does not exist an integer satisfying that
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.
We thank Professor Pedro Berrizbeitia for very helpful discussions.
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.
3. Eric Bach and Jeffrey Shallit. Algorithmic Number theory, volume I. The MIT
4. D. J. Bernstein. Proving primality in essentially quartic random time.
5. D. J. Bernstein. Sharper ABC-based bounds for congruent polynomials.
6. Pedro Berrizbeitia. Sharpening â€śprimes is in pâ€ť for a large family of numbers.
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,
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,
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
12. Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon
and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):
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.
16. Joachim von zur Gathen. Efficient exponentiation in finite fields. In Proc. 32nd
IEEE Symp. on Foundations of Comp. Science, 1991.
Computing the RSA Secret Key Is Deterministic
Polynomial Time Equivalent to Factoring
Faculty of Computer Science, Electrical Engineering and Mathematics
University of Paderborn
33102 Paderborn, Germany
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
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  and is based on a work by Miller .
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
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  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â€ť : Given half of the most significant bits of
one can factor N in polynomial time. Howgrave-Graham  showed that this
problem can be solved alternatively using an univariate modular approach (see
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
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
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
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  for finding
small roots of bivariate integer polynomials.
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
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
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
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,
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.
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 .
reduction  is done using Shoupâ€™s NTL library .
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 : 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 ) 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.
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
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â€“
10. V. Shoup, NTL: A Library for doing Number Theory, online available at
Multi-trapdoor Commitments and Their
Applications to Proofs of Knowledge Secure
Under Concurrent Man-in-the-Middle Attacks*