現代暗号史

現代暗号史

まず大雑把に時代を分ける。

参考資料はWeb上の資料を基本に。GoldreichのFoundations of Cryptographyに歴史載ってたかなぁ。Simon Singhの暗号解読の方が楽?

DBLPと英語版Wikipediaで色々と漁って纏める。

  • 現代暗号史_署名?

中世

1900年以降

1950年以降

  • One time pad

1970年以降

  • 1970年代, イギリスの軍事組織だったかどこだかで公開鍵暗号による通信に関する論文があった筈. ただし情報が公開されたのは90年代だったか?
  • 1976, Whitfield Diffie and Martin E. HellmanによるDH鍵交換 (安全性の証明なし. この問題自体を基盤としてしまうという逆転の発想がElGamalから生まれる)
  • 1978, Ronald Rivest and Adi Shamir and Leonard AdlemanによるRSA暗号 (安全性の証明なし. これも後々RSAのOW性を基盤として使うようになる.)
  • 1979, Michael O. RabinによるRabin暗号 (安全性の証明あり. 平方剰余を経由して素因数分解同値)
  • 1982, Taher ElgamalによるElGamal暗号 (安全性の証明あり)
    • DH鍵交換+共有した鍵で平文をマスク.
  • 楕円曲線
  • MOV
  • Cramer-Shoup暗号 (RO無しでIND-CCA2を証明)
    • DH鍵交換+共有した鍵で平文をマスク+署名.
    • 後に一般化されていた筈.
  • Gap-DH仮定, Pairing (流行中)

格子について

  • 詳しくは現代格子史, 現代暗号史_格子を参照のこと.
  • 1980代にLLLの登場
  • 1996, Ajtaiの"Generating Hard Instances of Lattice Problems"
  • 1997, Ajtaiの"The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions"
  • 1998, Ajtai-Dwork暗号 (帰着はa/w)
    • 1998, GGHによるエラーレスバージョン
    • 1999, Nguyen-Sternによる攻撃
  • 1999, GGH暗号 (安全性証明無し)
  • 1998, Cai-Cusick暗号 (安全性証明はない) 実はAjtai-Dwork暗号+Knapsack暗号
  • 2003, Regev暗号 (帰着はa/w)
  • 2005, Ajati暗号 (帰着がa/wでない)
  • 2005, Regev暗号 (帰着がquantum)
  • Jin-Yi Cai "Some Recent Progress on the Complexity of Lattice Problems"やNguyen and Stern "The Two Faces of Lattices in Cryptology"を読むと良い
  • NTRU
    • 方向性が違うので個人的には格子ベースと言わない方が良いと思う

安全性について

  • Goldwasser-Micali "Provable Secure" (Semantic Secureを定義した)
    • しかしこのgoalはCPAの設定でのみ有効となる
    • 後にIraqだったかIranの学生がCCA1, CCA2版を作っていた筈
  • INDはどこが発祥だっけ←上のGoldwasser-Micaliの中で定義されてます.
  • NMもどこだっけ
    • Dolve, Dwork, Naor の Non-malleable Cryptography (STOC91)が発祥かと. NMの定義の流儀については Bellare, Sahai の Non-malleable Encryption:Equivalence between Two Notions, and Indistinguishability Based Characterisation (CRYPTO99) を参照. SNM, CNM, PNM の3つが等価であることをいっている. 下のNMの定義はCNM.
  • M.Bellare A,Desai D.Pointcheval P.Rogway "Relations Among Notions of Security for Public-key Encryption Schemes"
    • (IND|NM)-(CPA|CCA1|CCA2)についての議論. 定義は, これが一番分かり易い。

その他関連

  • 署名とその応用だとChaumの一連の結果
  • Zero-Knowledge Goldwasser-Rackoffと誰だっけ
  • CRSは誰だっけ
    • CRSと明記されてないけど DamgardのConcurrent Zero Knowledge with Auxiliary Strings になるのかなあ(あやふや)
RO (Random Oracle)
  • 明言されていないが初出はFiat-Shamirヒューリスティック
  • 1993, M. Bellare, P. Rogaway (ACM CCS 1993)で定式化.
  • 1998, R. Canetti, O. Goldreich, S. Halevi. "Random Oracle Methodology, Revisited"
    • ROMだと安全だけどStandard Modelで安全じゃないCMA安全な署名とIND-CCA2安全な暗号の構成.
    • ROMと現実の世界のギャップを示したと. 他にも応用があるらしい. S. MicaliのCS-Proofが効果的に使われている.
  • 2003, FOCS, Goldwasser-Kalai, On the (In)security of the Fiat-Shamir Paradigm
    • secure 3 move public coin identification を変換して得られた SIGRO モデルだと安全だが, hash に置き換えた場合, 安全でなくなるケースが存在する.
UC (Universal Composability) 現代暗号史_UC
  • 2001, Ran Canetti and Marc Fischlin "Universally Composable Commitments"
  • 以後, それなりに流行している筈.
  • MPC (Multi Party Computation) の定義と相性が良い. 真の関数を相手にしているか, MPCプロトコルを相手にしているか当てられないという雰囲気で定義.
    • MPC文脈では, 良いのがあるらしい→CPT course home pageのCramer, Damgard "Lecture notes on multiparty computation".
  • 仮定無しだとビット・コミットメントやゼロ知識証明が無理. 巻き戻し(Rewiding)が出来ない所為か? CRSモデルにして解決 (個人的意見:それはどうだろう?).
    • 環境Zの性質上, 巻き戻しが不可. CRSモデルで全てが解決するが, bbsim もCRSはあまりよくないと思っている. 最近はCRSより弱い仮定で実現する方向がチラホラ. 他には Angel という方向がある.
  • 最近だと書き換え系と相性が良いらしい (岡本先生談 2006/05/18 ISEC講演会)