Adaptive One-Way Functions and Applications

[kaydoubleu]

by Omkant Pandey (UCLA), Rafael Pass (Cornell), and Vinod Vaikuntanathan (MIT)
at Crypto 2008

Keywords

• Cryptographic Assumptions
• Non-malleable Commitment
• Non-malleable Zero-knowledge

Abstract

We introduce new and general complexity theoretic hard-
ness assumptions. These assumptions abstract out concrete properties of
a random oracle and are significantly stronger than traditional crypto-
graphic hardness assumptions; however, assuming their validity we can
resolve a number of long-standing open problems in cryptography.

Headlines

1. Introduction
   a. Adaptive Hardness Assumptions
   b. Our Results
2. New Assumptions and Definitions
   a. Adaptive One-Way Functions
   b. Adaptive Pseudorandom Generator
   c. Adaptively Secure Commitment Schemes
3. Non-malleable Commitment Schemes
4. Four-round Non-malleable Zero-knowledge
   a. An Adaptively Secure WI Proof of Knowledge
   b. The Non-malleable Zero-Knowledge Argument System
5. CCA-2 Secure Encryption Scheme

Links

• IACR: https://www.iacr.org/cryptodb/data/paper.php?pubkey=23887
  • DOI
• Springer: https://rd.springer.com/content/pdf/10.1007%2F978-3-540-85174-5_4.pdf
• Cornell University: https://www.cs.cornell.edu/~rafael/papers/adaptiveowf.pdf