A Practical and Tightly Secure Signature Scheme Without Hash Function

In 1999, two signature schemes based on the flexible

RSA

problem (a.k.a. strong

RSA

problem) were independently introduced: the Gennaro-Halevi-Rabin (

GHR

) signature scheme and the Cramer-Shoup (

CS

) signature scheme. Remarkably, these schemes meet the highest security notion in the

standard model

. They however differ in their implementation. The

CS

scheme and its subsequent variants and extensions proposed so far feature a loose security reduction, which, in turn, implies larger security parameters. The security of the

GHR

scheme and of its twinning-based variant are shown to be tightly based on the flexible

RSA

problem but additionally (i) either assumes the existence of

division-intractable

hash functions, or (ii) requires an

injective

mapping into the prime numbers in both the signing

and

verification algorithms.

In this paper, we revisit the

GHR

signature scheme and completely remove the extra assumption made on the hash functions without relying on injective prime mappings. As a result, we obtain a

practical

signature scheme (and an on-line/off-line variant thereof) whose security is

solely

and

tightly

related to the strong

RSA

assumption.