Evaluation of Security Level of Cryptography:
ACE Signature Scheme
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang
Certicom ResearchContact: amenezes@certicom.com
January 15, 2001

2

Protocol specification

1

SummaryPage 1

The ACE signature scheme is an RSA-based signature scheme that has some attractive proofs ofsecurity. It has been proven existentially unforgeable against chosen-message attacks assumingthat the strong RSA problem is hard and that the UOWHF is universally collision-resistant. It
has also been proven existentially unforgeable against chosen-message attacks assuming thatthe RSA problem is hard and that the UOWHF is a random function. While the RSA and strong
RSA problems are known to be no harder than the integer factorization problem, it is not known
whether the RSA and strong RSA problems are as hard as the integer factorization problem. In
fact, the only evidence to date suggests that the RSA problem may in fact be easier than theinteger factorization problem.

2

Protocol specification

2.1 ACE key pairs
The signature scheme defined in the submission employs two key types, whose representationconsists of the following tuples:
ACE Signature public key: N  h  x  e  k  s  .
ACE Signature private key: p  q  a  .
For a given parameter m, with 1024  m  16384, the components are as follows.
p:  m 2 -bit prime with p

1  2 also a prime.

q:  m 2 -bit prime with q

1  2 also a prime.

Npq, and has either m or m

1 bits.

h  x are quadratic residue modulo N.

e is a 161-bit prime number.
a is an element of  0  p1 q1 41 .

k  is an element of B184, that is, k  is a concatenation of 184 elements from B, where B is
the set of all 256 bytes.
s is an element of B32 .

In the following, we will use the following notations:2

Protocol specification

Page 2



L M  denotes the length of the binary string M.

Lb m  denotes the length of the binary representation of m, where m is an integer.
LB m   8 m 8 , where m is an integer.

2.2 ACE signature generation
A signature of the ACE signature scheme has the form d  w y y  k̃  and is encoded as a bytestring. (For a description of the encoding method, please see the submission.)
Input: A public key N  h  x  e k   s  , the corresponding private key p  q  a  , and a byte string
M  B  , 0  L M   264 .
Output: A byte string encoded signature σ  B  of M.
1. Perform the following steps to hash the input data:
1.1. Generate a hash key k̃  B20m 64 at random, such thatm  Lb L M  8  64 
1.2. Compute mh Z UOWHash   k̃  M   , whereIW

1.2.1. W is the set of words.
Z is a conversion operator from W  to integers.
1.2.2. IW
1.2.3. UOWHash   is a universal one-way hash function.
2. Select ỹ 

1   N

3. Compute x 

1  at random, and compute y  ỹ2 mod N.

y  e hmh mod N.

4. Generate a random prime e, 2160
details see the submission).

e2161, and its certificate of correctness w d  (for5. Set r  UOWHash    k   LB N  x  k̃   Z, note that 0  r  2160, where UOWHash    is a
special-purpose hash function.
6. Compute y 

hb mod N, whereb

and p p

1  2, q qe 1 ar  mod p q 1  2.

7. Encode the signature N  d  w y y   k̃  as a byte-string σ.
8. Output the signature σ.

3

Security level of cryptographic techniques

Page 3

2.3 Signature verification
Input: A public key: N  h  x  e  k  s  , a signature σ  B  , and a message M  B  .
Output: If σ is a valid signature on M under the given public key, then outputs “Accept”;
otherwise outputs “Reject”.
1. Decode the signature σ into tuple: d  w y y   k̃ 
1.1. If L M 

264 then stop processing and signal “Reject”.

1.2. If L σ 85  2LB N  then stop processing and signal “Reject”.

1.3. Compute the tuple d  w y y  k̃  .
2. Set e VerCertPrime s  d  w  (see the submission).

3. If e  “Reject”, return “Reject”.
4. If e  e , return “Reject”.
5. If y  0 or y

N or y  0 or yN then return “Reject”.

6. Perform the following steps to hash the input data:
6.1. If L k̃   20m  64, where m  Lb
6.2. Compute mh 
7. Compute x 
8. Set r 

L M   8  64  , then return “Reject”.

Z UOWHash   k̃  M   .
IWy  e hmh mod N.

UOWHash   k   LB N  x  k̃   Z, note that 0  r  2160.

9. If x   yehr mod N  then return “Reject”.
10. Return “Accept”.

3

Security level of cryptographic techniques

The security objective of any signature scheme is to be existentially unforgeable against achosen-message attack. The goal of an adversary who launches such an attack against a legitimate entity A is to obtain a valid signature on a single message m, after having obtained A’s
signature on a collection of messages (not including m) of the adversary’s choice.
The security of the ACE signature scheme is based on the strong RSA assumption. The strong
RSA problem is as follows: Given a randomly generated RSA modulus N, and a randomly

4

Security level of cryptographic primitive functions

Page 4

generated integer z, find y and r 1 such that yr z mod N  . The strong RSA assumption
says that there is no efficient algorithm for solving the strong RSA problem.
Chosen-message attacks. It is proven in [4] that the ACE signature scheme is secure against
adaptive chosen-message attacks if the strong RSA assumption holds, and if UOWHF is universally collision-resistant (see 4.1).
Random oracle and chosen-message attacks. The RSA problem is the following: Given arandomly generated RSA modulus N, an exponent r, and a random z, find y such that y r z
mod N  . The RSA assumption says that there is no efficient algorithm for solving the RSAproblem. It is shown in [4] that the ACE signature scheme is secure against adaptive chosenmessage attacks in the random oracle model if the RSA assumption holds. The proof guarantees
resistance to attacks that do not use specific properties of the hash function, assuming only that
the RSA problem is intractable.
Comparison of assumptions. On the one hand, the first proof leads to stronger assurances than
the second proof because collision resistance of the UOWHF is a much weaker assumption thatthe random oracle assumption. On the other hand, the second proof leads to stronger assurances
than the first proof because the RSA assumption is a weaker assumption than the strong RSA
assumption. The difficulty of the RSA and strong RSA problems is considered further in 5.
4

Security level of cryptographic primitive functions

4.1 Attacks on the universal one-way hash function
D EFINITION. A universal one-way hash function is a keyed hash function that maps bit stringsof arbitrary lengths to bit strings of a fixed length t such that:
1. For every K, HK can be computed efficiently;
2. (universal collision resistance) If an adversary chooses a message x, and then a key K ischosen at random and given to the adversary, it is hard for the adversary to find a different
message x   x such that HK x   HK x  .
H ASH F UNCTION S ECURITY R EQUIREMENTS. The following explains how attacks on ACE
can be successfully launched if the universal hash function is not secure.
1. If for some K the hash function HK is not collision resistant, then an entity A may beable to repudiate signatures as follows. A first generates two messages m and m  such thatHK m   HK m  ; such a pair of messages is called a collision for HK . She then signs m,and later claims to have signed m (note that every signature for m is also a signature form ).

5Security level of cryptographic primitive problems

Page 52. If the hash function H is not universal collision resistant, then an entity B may be able
to forge signatures as follows. B generates a message m, obtains the signature σ of mfrom A. Assume that A has signed m with HK , then B finds another message m such thatHK m   HK m  . Now σ is also a signature of m .
I DEAL S ECURITY. A t-bit universal hash function is said to be have ideal security if both:(i) given a hash output HK x  , producing a preimage requires approximately 2t operations; and(ii) for any given K, producing two messages m and m  such that HK m   HK m  requires
approximately 2t 2 operations. The universal hash function in ACE is a 160-bit hash function
and is required to have ideal security. The fastest method known for existentially forgery attacks
on ACE by exploiting properties of universal hash functions is to find a universal collision.
Since this is believed to take 2160 steps, attacking ACE in this way is computationally infeasible.
The fastest method known for repudiation attacks on ACE by exploiting properties of a universal
hash function is to find a K, and then find two messages m and m  with HK m   HK m  . Since
this is believed to take 280 steps, attacking ACE in this way is computationally infeasible. Note,however, that this attack imposes an upper bound of 2160 (or 280 for repudiation attacks) on thesecurity level of ACE, regardless of the size of the primary security parameter n.

5Security level of cryptographic primitive problems: the RSAand strong RSA problems

The strong RSA assumption was first introduced in [1], and has subsequently been used in
the analysis of several cryptographic schemes (see, e.g., [5, 6]). This is a potentially stronger
assumption than the RSA assumption, but not much work has been published on either problem.
At present, the only known method for solving either the RSA problem or the strong RSA
problem is to solve the integer factorization problem.
The only result ever proved on the relationship between the RSA problem and the integer factorization problem is a negative one: Boneh and Venkatesan [3] proved that any polynomial-time
reduction algorithm from the integer factorization problem to the RSA problem (with smallencryption exponent e) that uses only algebraic operations can be efficiently converted to apolynomial-time algorithm for integer factorization (which doesn’t make use of the hypothetical oracle for the RSA problem). This provides some evidence that the RSA problem (andconsequently also the strong RSA problem) may in fact be easier than the integer factorization
problem.
Now, if an adversary can succeed in computing A’s private key p  q  from A’s public keyn  e  k  , then the adversary can subsequently forge A’s signature on any message of its choice.
The following summarizes the state-of-the-art in our knowledge for integer factorization.
Problem Definition. The integer factorization problem is the following: given an integer n,5Security level of cryptographic primitive problems

Page 6determine the factorization of n into primes.

Known algorithm for integer factorization
This subsection overviews the algorithms known for factoring and discusses how they can beavoided in practice.
1. Trial division. Once it is established that an integer is composite, before expending vast
amount of time with more powerful techniques, the first thing that should be attempted
is trial division by all “small” primes. Here “small” is determined as a function of thesize of n. As an extreme case, trial division can be attempted by all primes up to n. If
this is done, trial division will completely factor n but the procedure will take roughly ndivisions in the worst case when n is a product of two primes of the same size.
2. Pollard’s rho factoring algorithm. Pollard’s rho algorithm is a special-purpose factoringalgorithm for finding small factors of a composite integer. Let f : SS be a randomfunction, where S is a finite set of cardinality m. Let x0 be a random element of S, andconsider the sequence x0  x1  defined by xi  1  f xi  for i 0. Since S is finite, thesequence must eventually cycle, and consists of a tail of expected length nπ 8 followedby an endless repeating cycle of expected length nπ 8. A problem that arises in thefactorization problem is of finding distinct indices i and j such that x i  x j . The expected
time for finding such a collision is O p  where p is a prime factor of n.


3. Pollard’s p-1 factoring algorithm. Pollard’s p 1 factoring algorithm is a specialpurpose factoring algorithm that can be used to efficiently find any prime factors p ofa composite integer n for which p 1 is smooth with respect to some relatively smallB. Let n be an integer having a prime factor p such that p 1 is B-smooth. The running time of Pollard’s p 1 algorithm for finding the factor p is O B ln n lnB  modularmultiplication.
4. Elliptic curve factoring. The elliptic curve factoring method (ECM) has an expectedrunning time of O exp
2  o 1   ln p  1 2 ln ln p  1 2   to find a prime factor p of n. It
is the fastest factoring algorithm known when the running time is measured in terms of
the smallest prime factor of n, and is thus useful for finding factors of n in some situations
when n has a prime factor that is significantly smaller than the other prime factors of n.
5. Quadratic sieve factoring. The quadratic sieve factoring algorithm has the same expected running time as the elliptic curve factoring algorithm in the special case when n is
the product of two primes of equal size. However, for such numbers, the quadratic sieve
is superior in practice.
6. Number field sieve (NFS) factoring. The general version of the number field sieve factoring algorithm has an expected running time of O expc  o 1   ln n  1 3 ln ln n  2 3  6Recommended parameters

Page 7

to factor n, where c is approximately 1  923. This is asymptotically superior to thequadratic sieve factoring method. This superiority has also been validated by numerous
researchers through extensive experimentation.
7. Factoring n  pr q. Boneh, et al. [2] presented an algorithm for factoring n  pr q withlarge r using the LLL algorithm. Their algorithm, however, is only effective for the casewhere r is large (at least log p  1 2). If r is constant or small, the running time of theiralgorithm is exponential in the bitsize of n. For n  p2q, their algorithm is less efficientthan the ECM and NFS methods.
Summary: For carefully chosen n, the integer factorization problem is widely believed to beintractable. In particular, the integer n specified in the ACE signature scheme avoid all known
existing factoring attacks.

6

Recommended parameters

In Table 1, the security levels of the ACE with these parameters are compared with othersubmitted schemes, with RSA, and with symmetric schemes (e.g., the Advanced Encryption
Standard–AES). Some of the comparisons among symmetric key cryptography, RSA security,and ECDSA security are adapted from Lenstra and Verheul [7].

Symmetric
Key Size
40
48
76
80
(SKIPJACK)112(Triple-DES)
128(128-bit AES)
192
(192-bit AES)
256
(256-bit AES)

Table 1: Rough Comparison of Security Levels
RSAESIGN
ACE
ECDSA
Modulus
Modulus
ModulusKey Size
Size
Size
Size

MY-ELLTY
Key Size
160
192

960

960

960

152

1024

1024

1024

160

2048

2048

2048

224

3072

30723072

2567680

7680

7680

384

15360

15360

15360

512

References

7Page 8Performance comparison

Table 1 presented comparable key lengths of several schemes. Generally, the ESIGN signaturescheme is faster than both ECDSA and RSA signature schemes with comparable key lengths.
ACE, RSA, and ESIGN have roughly the same public key size for comparable security level.
ACE and RSA have roughly the same private key size for comparable security level. ESIGN’s
private key size is roughly 2 3 of the ACE (or RSA) private key size for comparable securitylevel. ECDSA and MY-ELLTY have smaller key size for comparable security level. However,
the hash function used in MY-ELLTY is not collision resistant, thus it is not secure against
attacks on the hash function.

References[1] N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes
without trees. In: Advances in Cryptology, Eurorypt 97, pages 480–494, 1997.
[2] D. Boneh, G. Durfee, and N. Howgrave-Graham. Factoring N in Cryptology, Crypto 99, LNCS 1666, pages 326–337, 1999.

p r q for large r. Advances[3] D. Boneh and R. Venkatesan, Breaking RSA may not be equivalent to factoring, Advancesin Cryptology, Eurocrypt 98, LNCS 1403, pages 59–71, 1998.
Advances in Cryptology, Crypto 99, LNCS 1666, pages 326–337, 1999.
[4] R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption. In: 6th
ACM Conf. on Computer and Communication Security, 1999.
[5] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In: Advances in Cryptology, Crypto 99, 1999.
[6] R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random
oracle. In: Advances in Cryptology, Crypto 99, pages 123–139, 1999.
[7] A. Lenstra and E. Verheul. Selecting cryptographic key sizes. Distributed in the 3rd workshop on Elliptic Curve Cryptography (ECC 99). Available from http://www.cryptosavvy.
com/[8] A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC
Press, 1997.