*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

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 ∈ QR _{n}- 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 ∈ QR
_{n} - choose x' where (y')
^{e}= x' h^{H(m)} - compute y where y
^{e}=xh^{H(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= y
^{e}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

^{d}mod n.

*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

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

pick an RSA modulus N, pick h ← Z _{n}^{*} pick a pseudo-random function F_{k}:{0,1}^{*}→ {0,1}^{l}- pick a random c ← {0,1}
^{l} - 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 - 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 e
_{i}=H_{k,c}(m^{(i)}) (thus, given a message we generate n prime numbers) - define σ = h
^{∏ e_i-1}

compute e _{i}=H_{k,c}(m^{(i)})- check σ
^{∏ e_i}= h

_{1}, ..., 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.

^{*})

^{(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

^{*})

^{(j)}

_{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.)

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.