2006 | OriginalPaper | Chapter
A Practical and Tightly Secure Signature Scheme Without Hash Function
Authors : Benoît Chevallier-Mames, Marc Joye
Published in: Topics in Cryptology – CT-RSA 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.