Advertisement
Published in:
2008 | OriginalPaper | Chapter
Separation Results on the “One-More” Computational Problems
Authors : Emmanuel Bresson, Jean Monnerat, Damien Vergnaud
Published in: Topics in Cryptology – CT-RSA 2008
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 2001, Bellare, Namprempre, Pointcheval and Semanko introduced the notion of
“one-more” computational problems
. Since their introduction, these problems have found numerous applications in cryptography. For instance, Bellare
et al.
showed how they lead to a proof of security for Chaum’s
RSA
-based blind signature scheme in the random oracle model.
In this paper, we provide separation results for the computational hierarchy of a large class of algebraic “one-more” computational problems (
e.g.
the one-more discrete logarithm problem, the one-more
RSA
problem and the one-more static Computational Diffie-Hellman problem in a bilinear setting). We also give some cryptographic implications of these results and, in particular, we prove that it is very unlikely, that one will ever be able to prove the unforgeability of Chaum’s
RSA
-based blind signature scheme under the sole
RSA
assumption.