RSA ⇒ DS (Hohenberger–Waters, short and stateless)

Standard model · HW09

Statement

If RSA is hard, there is a stateless signature scheme that is EUF-CMA in the standard model and whose signatures consist of one element of ${\mathbb{Z}}_N^{\ast }$ and one integer — HW09. The scheme is first shown weakly secure, by a technique in which the simulator predicts a prefix of the message the adversary will forge on, and then made fully secure with a chameleon hash — HW09.

Notes

• Efficiency: the public key is the modulus $N$, one element of ${\mathbb{Z}}_N^{\ast }$, one integer and one PRF seed. Earlier short standard-model signatures in the RSA setting needed a stronger assumption such as strong RSA, or a stateful signer — HW09.