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
Key generation
- 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)
generate quadratic residues h,x ∈ QRn - generate an (l+1)-bit prime e' and
- define pk=(n,h,x,e') and sk=(p,q)
for a hash function H with l-bit outputs set x=H(m) - choose (l+1)-bit number e
- choose y ∈ QRn
- choose x' where (y')e = x' hH(m)
- compute y where ye=xhH(x')
- define σ = (e,y,y')
check whether e is a (l+1)-bit integer and e≠ e' - compute x'=(y')e' h-H(m)
- check x= ye h-H(x')
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
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
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
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
pick an RSA modulus N, pick h ← Zn* pick a pseudo-random function Fk:{0,1}* → {0,1}l- pick a random c ← {0,1}l
- define Hk,c(z)=Fk(i||z) ⊕ c, where i is smallest number s.t. Hk,c(z) is an odd prime
- output pk=(N,h,c,k), sk=(c,k,p,q)
Signing
let m(i) be defined as the first i bits of m - define ei=Hk,c(m(i)) (thus, given a message we generate n prime numbers)
- define σ = h∏ e_i-1
compute ei=Hk,c(m(i)) - check σ∏ e_i = h
Suppose we guess this position, then we know what the (m*)(j) is, and can then fix c s.t. H on
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.
ReplyDeleteThe 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.
ReplyDeleteSo 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)
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.
ReplyDeleteIn 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.