Strong RSA + CRHF ⇒ DS

Fully-black-box reduction · standard model · CS99 · security loss: factor $O(q_S)$ for $q_S$ signing queries, from guessing which signing prime a forgery reuses, plus the collision-finding advantage

Statement

If strong RSA is hard and the hash function is collision resistant, the Cramer–Shoup signature scheme is EUF-CMA-unforgeable in the standard model: it signs each message under a fresh random prime exponent, and any forger yields a strong-RSA solution or a hash collision — CS99.

Sketch

Each signature is an $e$-th root, for a fresh random prime $e$, of a value determined by the public key and the message. The reduction plants the strong-RSA challenge $z$ in the public key as $z$ raised to the product of the primes it will use to answer signing queries, so it signs without computing roots; a forgery under a new prime $e^{\ast }$ gives $y^{e^{\ast }}=z^a$ with $\gcd (e^{\ast },a)=1$, and Bézout coefficients yield $z^{1/e^{\ast }}$ (Shamir’s trick). A forgery that reuses a signing prime $e_j$ is handled by guessing $j$ in advance and embedding $z$ so that the forgery yields a root of $z$ or a hash collision.

Notes

• Concurrently and independently, a hash-and-sign scheme from strong RSA together with a division-intractable hash function — GHR99.
• A variant with signatures of roughly half the size and faster signing and verification, still under strong RSA — Fis03.