Fiat-Shamir_Transformation

Fiat-Shamir_Transformation

ランダムオラクルモデルでの安全性について

  • Fiat, Shamir. "How to Prove Yourself: Practical Solution to Identification and Signature Problems" (CRYPTO 1986)
  • D. Pointcheval, J. Stern "Security Proofs for Signature Schemes" (CRYPTO 1996)
    • さまざまなZero-Knowledge Identificationからの構成.
      • Forking Lemmaはこれが最初?
    • 具体的には, Fiat-Shamirの平方剰余の話とModified ElGamal署名の安全性の話.
    • コメント:The same results are true for every signature scheme which comes from the transformation of a honest verifier zero-knowledge identification protocol.
  • K. Ohta, T. Okamoto "On Concrete Security Treatment of Signatures Derived from Identification" (CRYPTO 1998)
    • Honest-Verifier Public-Coin Zero-Knowledge Identificationからの構成?
    • ID Lemma, Heavy Row Lemma
      • Forking Lemmaよりも帰着の効率がよくなるらしい.
  • M. Abdalla, J. An, M. Bellare, C. Namprempre "From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security" (EUROCRYPT 2002)
    • 一般的な認証方式からの構成
    • Forward-Secureも構成可能? これまでのForward-Secureな署名の構成方法の一般化らしいが.
  • 2004. M. Bellare, C. Namprempre, G. Neven "Security Proofs for Identity-Based Identification and Signature Schemes" (EUROCRYPT 2004)
    • これから読むかも.
  • 2007. M. Bellare, S. Shoup. "" (PKC 2007)
    • 認証方式がss-concurrentの意味で安全ならば, CRHFsで変形したときに, Two-Tier Signatureが構成可能.
      • 応用1:EUF-CMA安全な署名をsEUF-CMA安全な署名に持ち上げる.
      • 応用2:One-time Signatureとして使用.

ROMと現実世界との乖離

  • Canetti, Goldreich, and Halevi (1998?)
    • これ以外にもいろいろあったと思う
    • MicaliのCS-proofを活用. non black-box reductionなんだっけか? 解説したけど1年前だから忘れた.
  • S. Goldwasser, Y. Tauman Kalai "On the (In)security of the Fiat-Shamir Paradigm" (FOCS 2003, ECCC 2003)
    • 具体的な認証方式の構成: Fiat-Shamir変換を掛けたときに, ROMで安全だけど現実世界で安全でないような認証方式の構成.
    • Barakのnon black-box reductionを活用しているらしい.

関係あるかも?

  • Pointcheval, Stern "Security arguments for digital signatures and blind signatures" (J. Crypt. 2000)
  • Stern, Pointcheval, Malone-Lee, Smart "Flaws in applying proof methodologies to signature schemes" (CRYPTO 2002)
  • Kurosawa, Heng "From digital signature to ID-based identification/signature" (PKC 2004)