<<

. 7
( 19)



>>

188 Craig Gentry

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
( 19)



>>