Tuesday, October 18, 2011

Study group: RSA-based standard model signatures

Nigel and Ming-Feng presented the results of 4 papers on provably secure digital signatures in the standard model. Ming-Feng started with Cramer and Shoup's seminal paper from 2000 [ps], and then discussed reductions of the signature length by Fischlin (PKC 2003) [pdf]. Nigel then mentioned the first (stateful) scheme based on the RSA assumption by Hohenberger and Waters [pdf], and dedicated a more thorough presentation to their follow-up work at CRYPTO 2009 [pdf], which is a stateless scheme.

Cramer-Shoup signature scheme was the first to have a standard-model proof of security against adaptive chosen-message attack. It is stateless (which is now the standard for digital signatures, meaning the signer need not keep any state information) and based on the strong RSA assumption. The RSA assumption is, given an RSA modulus n (which is the product of two large primes) and r, z ∈ Zn*, it is hard to find y ∈ Zn* s.t. yr≡z (mod n). For the strong RSA assumption, the adversary has more flexibility: given n and z, she has to find both r>1 and y ∈ Zn* s.t. yr≡z (mod n).

Note that while the latter assumption is stronger than the former, the best known attack against both of them is to factor the modulus n.

A signature scheme SIG=(KG,Sign,Ver) consists of algorithms for key generation, signing and verification, which can be sketched as follows (pk is the public key and sk is the signing key):
  • 1k → KG → (sk,pk)
  • (sk,m) → Sign → σ
  • (pk,m,σ) → Ver → 1/0

A scheme is secure against chosen-message attacks if an adversary getting the public key and a signing oracle that returns signatures on messages of its choice cannot output a message it has never queried and a valid signature on it.

Note that the "text-book" RSA signature (where a signature is simply md mod n) scheme is not secure under chosen-message attack, since signing is homomorphic. "Hashed RSA" is secure in the random-oracle model.

Cramer and Shoup proposed the first scheme that is provably secure against chosen-message attacks in the standard model. The scheme has 2 parameters l and l' with l+1<l'. Typical assignments are l=160, l'=512.

Key generation

  1. generate an RSA modulus n=pq where p=2p'+1 and q=2q'+1 for p' and q' large primes (such p and q are called strong primes)
  2. generate quadratic residues h,x ∈ QRn
  3. generate an (l+1)-bit prime e' and
  4. define pk=(n,h,x,e') and sk=(p,q)
  1. for a hash function H with l-bit outputs set x=H(m)
  2. choose (l+1)-bit number e
  3. choose y ∈ QRn
  4. choose x' where (y')e = x' hH(m)
  5. compute y where ye=xhH(x')
  6. define σ = (e,y,y')
  1. check whether e is a (l+1)-bit integer and e≠ e'
  2. compute x'=(y')e' h-H(m)
  3. check x= ye h-H(x')
The proof distinguishes different kinds of forgers, depending on whether their forgery reuses the e' of a signature it obtained from a signing query or it reuses the x' or both. While forgeries that reuse parts can be reduced to the standard RSA assumptions, for forgeries with a new e we need to resort to the strong RSA assumption.

In his PKC '03 paper, Fischlin gives a variant of Cramer-Shoup signatures (also provably secure under the strong RSA assumption) which has shorter signatures: instead of |σ| = 2|n|+l+1, we now have σ=|n|+2l+1, but the public keys are longer.

While the CS signature scheme was state of the art, it requires the strong RSA assumption. The reason being that every signature requires its own value e, therefore in the security reduction, in order to simulate the signing oracle, we allow the simulator (who does not know the factorisation of n) to somehow "cheat" by creating new e's.

It thus seems the that we cannot get around this stronger assumption for RSA-based signatures. However, at EUROCRYPT 2009, Hohenberger and Waters presented a scheme that was proven secure under the RSA assumption. The caveat being that it was a stateful scheme, meaning that the signer had to store a counter, which it had to increase every time it issues a signature; else all bets are off. Their signatures were short and looked like standard hash&sign signature à la
H(M)d mod n.

At CRYPTO the same year, they then extended their ideas to define a stateless signature scheme, based on RSA. They start with defining a scheme that only satisfies security against weak chosen-message attacks, where the adversary has to give the challenger all messages it would like to have signed before it gets to see the public key.

Then they transform their scheme into a fully secure scheme by using a known trick: Chameleon hash functions. These are functions that have input a message and some randomness: H(m,r) → y. Now, given a trapdoor τ one can for any y and m efficiently compute r s.t.

The good news is that there exists a chameleon hash function based on the RSA assumption. Given a weekly (not daily) secure scheme and a Chameleon hash function, one can generically construct a fully secure scheme as follows.

Add to the public and private key the description of the hash function. To sign
pick a random r and sign x=H(m,r): σ'=S(sk,x). The signature is then defined as σ=(σ',r). To verify it, just recompute the hash and verify σ' on it.

Now given this transformation, all that needs to be done is construct a weakly secure scheme, which is done as follows (remember, a simulator's goal is given N,e and y to compute y1/y mod n):

Key generation
  1. pick an RSA modulus N, pick h ← Zn*
  2. pick a pseudo-random function Fk:{0,1}* → {0,1}l
  3. pick a random c ← {0,1}l
  4. define Hk,c(z)=Fk(i||z) ⊕ c, where i is smallest number s.t. Hk,c(z) is an odd prime
  5. output pk=(N,h,c,k), sk=(c,k,p,q)
(Whereas in the EUROCRYPT paper, the state i is responsible for choosing the primes, now the picked prime depends on the input, not on the index of the signature.)

  1. let m(i) be defined as the first i bits of m
  2. define ei=Hk,c(m(i)) (thus, given a message we generate n prime numbers)
  3. define σ = h∏ e_i-1
  1. compute ei=Hk,c(m(i))
  2. check σ∏ e_i = h
The proof idea is the following. First, after the adversary outputs m1, ..., mn, we fix pk. Since the output m* is a forgery, it must be different from all mi, so there has to be a j s.t.
(m*)(j) is different from all mi(j).

Suppose we guess this position, then we know what the (m*)(j) is, and can then fix c s.t. H on
(m*)(j) returns e, the target from the RSA challenge. To simulate signatures on the queried messages mi, we raise y to the power of all primes ei,j = Hk,c(mi(j)) and set it as h. Now we can take ei,j-th roots of h. (This is similar to how Boneh and Boyen transform a challenge for the strong Diffie-Hellman assumption into signatures in their scheme.)


  1. Excellent post! I'm really curious how efficient these would be in practice. Not because it's a big deal (the authors cheerfully admit that all the prime-finding is a killer), but because I think it's interesting to know what the options are if you want to stick with RSA.

  2. The killer is the fact that you need, when signing an m bit message, to apply the "hash function" m times. Each invocation of the hash function requires invoking a PRF an expected t times where 1/t is the probability of getting a prime number of the requisite size.

    So if signing a 160 bit hash (which is what would happen in practice), then CPU time is going to be roughly 160*t times slower than standard RSA (at least)

  3. The bottleneck of the signing algorithm in {CS, Fischlin, HW, ...} is the (deterministic or randomized) generation of the primes. As Nigel points out, generating a 160-bit prime takes considerably more CPU time than one standard RSA exponentiation.

    In our papers from Crypto 08 and Asiacrypt 11 we show techniques to decrease the size of the primes from 160 to 80 bits or less. In that case the signing algorithm of our strong RSA schemes is almost as efficient as that of RSA-FDH, with the price of a large public key. Our RSA schemes are still less efficient.

    I'm also curious to find out how efficient these schemes really are.