Separation Results on the 'One-More' Computational Problems
| Autor: | Damien Vergnaud, Jean Monnerat, Emmanuel Bresson |
|---|---|
| Přispěvatelé: | Laboratoire des Technologies de l'Information (DCSSI/SDS/LTI), SGDN, Department of Computer Science and Engineering [San Diego] (CSE-UCSD), University of California [San Diego] (UC San Diego), University of California-University of California, Laboratoire d'informatique de l'école normale supérieure (LIENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), T. Malkin, Department of Computer Science and Engineering [Univ California San Diego] (CSE - UC San Diego), University of California (UC)-University of California (UC), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris) |
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: |
Discrete mathematics
Hierarchy Theoretical computer science business.industry Algebraic algorithms 020206 networking & telecommunications Cryptography 02 engineering and technology RSA problem Random oracle Random self-reducible problems [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Discrete logarithm 0202 electrical engineering electronic engineering information engineering Blind signature 020201 artificial intelligence & image processing Computational problem Algebraic number business Black-box reductions Mathematics Computer Science::Cryptography and Security One-more problems |
| Zdroj: | Topics in cryptology-CT-RSA 2008 Topics in cryptology-CT-RSA 2008, 2008, San Francisco, United States. pp.71-87, ⟨10.1007/978-3-540-79263-5_5⟩ Topics in Cryptology – CT-RSA 2008 ISBN: 9783540792628 CT-RSA Web of Science |
| DOI: | 10.1007/978-3-540-79263-5_5⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|