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 ∈ Z_n^*, it is hard to find y ∈ Z_n^* s.t. y^r≡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 ∈ Z_n^* s.t. y^r≡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):

• 1^k → 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 m^d 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 ∈ QR_n
3. generate an (l+1)-bit prime e' and
4. define pk=(n,h,x,e') and sk=(p,q)
   

Signing

1. for a hash function H with l-bit outputs set x=H(m)
2. choose (l+1)-bit number e
3. choose y ∈ QR_n
4. choose x' where (y')^e = x' h^H(m)
5. compute y where y^e=xh^H(x')
6. define σ = (e,y,y')
   

Verification

1. check whether e is a (l+1)-bit integer and e≠ e'
2. compute x'=(y')^e' h^-H(m)
3. check x= y^e 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. H(m,r)=y.

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 y^1/y mod n):

Key generation

1. pick an RSA modulus N, pick h ← Z_n^*
2. pick a pseudo-random function F_k:{0,1}^* → {0,1}^l
3. pick a random c ← {0,1}^l
4. define H_k,c(z)=F_k(i||z) ⊕ c, where i is smallest number s.t. H_k,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.)

Signing

1. let m⁽ⁱ⁾ be defined as the first i bits of m
2. define e_i=H_k,c(m⁽ⁱ⁾) (thus, given a message we generate n prime numbers)
3. define σ = h^{∏ e_i-1}
   

Verification

1. compute e_i=H_k,c(m⁽ⁱ⁾)
2. check σ^{∏ e_i} = h
   

The proof idea is the following. First, after the adversary outputs m₁, ..., m_n, we fix pk. Since the output m* is a forgery, it must be different from all m_i, so there has to be a j s.t. (m^*)^(j) is different from all m_i^(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 m_i, we raise y to the power of all primes e_i,j = H_k,c(m_i^(j)) and set it as h. Now we can take e_i,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.)