Signature Schemes

  • 1988. M. Bellare, S. Micali. "How to Sign Given any Trapdoor Functions" (STOC 1988)
    • TOWPからEUF-CMA安全な署名を構成?
  • 1989. M. Naor, M. Yung. "Universal One-Way Hash FUnctions and Their Cryptographic Applications" (STOC 1989)
    • OWPからUOWHFを構成. また, UOWHFからEUF-CMA安全な署名を構成.
    • ただ出来てる署名はなんか変な気がする. あとで調べる.
  • 1990. J. Rompel. "One-Way Functions are Necessary and Sufficient for Secure Signatures"
    • OWFからUOWHFを構成. 結果, Naor and Yung 1989と同様にEUF-CMA安全な署名を構成.
  • 2005. J. Katz, C. Koo. "On Constructing Universal One-Way Hash Functions from Arbitrary One-Way Functions" (Cryptology ePrint Archive 2005/328)
    • Rompel90のFull Versionが無い.
    • Romepl90だと間違いが多いので正しく証明を付けた.

ZK for NP

  • 1996. O. Goldreich, Kahan. "How to construct constant-round zero-knowledge proof systems for NP" (J. of Cryptology 9(2), 1996)
  • 1998. M. Naor, R. Ostrovsky, R. Venkatesan, M. Yung. "Perfect zero-knowledge arguments for NP using any one-way permutation" (J. of Cryptology 11(2), 1998) (CRYPTO 1992)
  • 2006. M. Nguyen, S. Vadhan. "Zero knowledge with efficient provers" (STOC 2006)

String Commitment

  • 1993. Damgaard, Pedersen, Pfitzmann. "On the existence of statistically-hiding bit commitment and fail-stop signatures" (CRYPTO 1993)
    • CRHFsからstatistically hiding string commitmentを構成
    • 1998?
  • 1996. Halevi, Micali. "Practical and Provably-secure Commitment Schemes from Collision-Free Hashing" (CRYPTO 1996)
    • CRHFからstatistically hiding string commitmentを構成