Impossibility Results

• Oracle separation
  • [scholar]Limits on the provable consequences of one-way permutations (Russell Impagliazzo and Steven Rudich, STOC 1989)
  • [scholar]Finding collisions on a one-way street: Can secure hash functions be based on general assumptions (Dan Simon, Eurocrypt 1998)
  • [scholar]Lower bounds on the efficiency of generic cryptographic constructions (Rosario Gennaro and Luca Trevisan, FOCS 2000)
  • [scholar]On the impossibility of basing trapdoor functions on trapdoor predicates (Yael Gertner, Tal Malkin, and Omer Reingold, FOCS 2001)
  • [scholar]On the imposibilities of basing one-way permutations on central cryptographic primitives (Yan-Cheng Chang, Chun-Yun Hsiao, and Chi-Jen Lu, Asiacrypt 2002)
  • [scholar]Notions of reducibility between cryptographic primitives (Omer Reingold, Luca Trevisan, and Salil Vadhan, TCC 2004)
  • [scholar]Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins? (Chun-Yuan Hsiao and Leonid Reyzin, Crypto 2004)
  • [scholar]On the Generic Insecurity of the Full Domain Hash (Yevgeniy Dodis, Roberto Oliveira and Krzysztof Pietrzak, Crypto 2005)
  • [scholar]Does secure time-stamping imply collision-free hash functions? (Ahto Buldas and Aivo Jürgenson, ProvSec 2007)
  • [scholar]Possibility and Impossibility Results for Selective Decommitments (Dennis Hofheinz, JoC 2008)
  • [scholar]Can We Construct Unbounded Time-Stamping Schemes from Collision-Free Hash Functions? (Ahto Buldas and Margus Niitsoo, Provsec 2008)
  • [scholar]On the Security of Padding-Based Encryption Schemes – or – Why We Cannot Prove OAEP Secure in the Standard Model (Eike Kiltz and Krzysztof Piertzak, Eurocrypt 2009)
  • [scholar]Oracle Separation in the Non-uniform Model (Ahto Buldas, Sven Laur and Margus Niitsoo, ProvSec 2009)
  • [scholar]On Black-Box Separations among Injective One-Way Functions (Takahiro Matsuda and Kanta Matsuura, TCC 2011)
  • [scholar]On the Impossibility of Instantiating PSS in the Standard Model (Rishiraj Bhattacharyya and Avradip Mandal, PKC 2011)

  ---

  
  
  Cryptology Pointers by Helger Lipmaa
  Got any suggestions or additional links? Mail to <helger.lipmaa>gmail.com
  NB! If you find any broken links, please be kind and report them to me together with their current location!
  
  (C) Helger Lipmaa 1997-2009.