現代暗号史_UC

現代暗号史_UC

UCの定義

Universal Composability (通称 UC)とは

暗号の安全性を解析するためのフレームワークである.

UC での安全性を考える利点は主に二つ.

  • 従来定式化されてきたどの安全性概念よりもの強い安全性を保証する. すなわち単体として保証された安全性がいかなる結合/利用環境においても保持される.
  • すべての暗号機能 (公開鍵暗号, ディジタル署名, ゼロ知識証明など) の安全性を統一的に定式化できる.

UCにおける計算は interactive Turing machine (ITM) によってモデル化される.

以下にUCにおける特別な参加者を定義する.

adversary {\cal A}
現実世界においてプロトコルをattackしたり, プロトコルの参加者をcorruptしたりすることにより妨害することを目的とした敵をモデル化したもの.
simulator {\cal s}
ideal worldにおけるadversaryであり, environmentが現実世界と理想世界を区別できないように働くsimulator.
environment {\cal Z}
システム内で動作している他の全てのプロトコルや敵をモデル化したもの, すなわち入力を与えたり, 出力を読み取ったりする存在である. 現実世界と理想世界を区別しようとする識別器(distinguisher). それぞれの世界にinteractiveにアクセスできる.
functionality {\cal F}
理想機能. 暗号機能が達成すべき理想的な性質を書き出したもの.

以上はすべてprobabilistic polynomial-time (PPT) ITMである.

次に以下の二つの世界を考える

Real world
現実の暗号プロトコル \piとadversary {\cal A} が動作する現時世界
Ideal world
ideal functionality {\cal F} と simulator {\cal s} が動作する理想世界

UCフレームワークでは,単体の機能として実現したプリミティブ/プロトコルが, どのような組合せの中で部品として使われても単体のときの安全性/機能が保存される.

protocol emulation

\pi\phiをPPTプロトコルとする. 任意のPPT adversary Aに対してPPT adversary Sが存在して, どのようなPPT environment Zに対しても,次がなりたつとき\pi\phiUC-emulateするという.

EXEC_{\phi,{\cal S},{\cal Z}} \approx EXEC_{\pi,{\cal A},{\cal Z}}

Composition Operation (結合処理)

プロトコルに対するoperatorの観点でcomposition operationを表現する. このoperatorを universal composition operator UC()と呼び,次のように定義する. プロトコル,\phi, \pi, \rho が与えられたとき, 組み合わせたプロトコル\pi^{\rho / \phi}=UC(\pi, \rho, \phi)は以下の修正を加えて, プロトコル \pi と同一である.

  • \pi が入力 x を \phi に渡す命令を含んでいるとき, \pi^{\rho / \phi}は代わりに入力 x を ρ に渡す命令を含んでいる.
  • 組み合わせたプロトコル\pi^{\rho / \phi}\rho から出力を受け取ったとき, \pi\rho から出力を受け取ったときと同様に動作する.

プロトコル \phi がある functionality F に対する ideal protocol, IDEAL_{\cal F}であったとき, 組み合わせたプロトコル\pi^{\rho / {\cal F}}とかく.

hybrid protocol
Universal Composition Theorem (UC定理)
\pi, \rho, \phiをPPT multi party protocolとし, \rho\phiUC-emulateするとする. このときプロトコル\pi^{\rho/\phi}プロトコル\piUC-emulateする.

どのような敵に対しても, あるシミュレータが存在して,どのような環境も

現時世界なのか理想世界なのか区別できないとき, プロトコル\piは理想機能FをUC-realizeするという.

\forall {\cal A}, \exists {\cal S}, \forall {\cal Z}

 REAL_{\pi,{\cal A},{\cal Z}} \approx IDEAL_{{\cal F},{\cal S},{\cal Z}

既存の結果

UCは非常に強い意味での安全性をもつので, 従来定義されてきた安全性ではUC安全性を満たさない可能性がある. しかしごく一部は従来の安全性と等価であることが示されている.

UC PKE
IND-CCA2 PKEと等価
UC SIG
EUF-CMA SIGと等価
UC KEM
IND-CCA2 KEM と等価

これらは Key Generation Algorithm を有するので, 以上の結果は厳密にはplain modelではないことに注意.

two party protocol
set-up assumptionなしでは実現不可能.

この直感的な理由は 相反する two party の要求を同時に満たすような functionality は, 片方の party が corrupt された場合には, simulator がシミュレートしきれないからである. 例えば commitment に関していえば, sender は何とかして秘密を守るためにextract を防ぎたいが, receiver は何とかして中身を変更されないために equivocate を防ぎたい, という二人の完全に相反する要求を同時に実現するのは不可能なのである. 同様に, group signature は anonymity と tracability を満たさなければならないが, 相反する要求なので実現不可能である. (TCC'06 の Datta, et al の考察による)

歴史

  • FOCS'01, Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols.
    • UC の始まり.
  • CRYPTO'01, Canetti-Fischlin, Universally Composable Commitment.
    • plain model で UC commitment の実現は不可能. CRS モデルで実現. それを利用して UC ZK も実現 (BlumのZK for Hamilton Cycleに適用する)
  • Euro'02, Canetti-Krawczyk, UC Key Exchange
    • UC secure な Key Exchangeが SK-secure KE と等価であることを示す.(Non Information Oracleを使う)
  • STOC'02, Canetti-Lindell-Ostrovsky-Sahai, Universally Composable Two and Multi Party Protocols
    • CRS モデルで任意の UC two (and multi) party protocol を実現. Goldreich-Micali-Wigderson のコンパイラを利用.
  • CRYPTO'02, Damgrad-Nielsen
    • 改良されたUC COM を提案.
  • Euro'03, Canetti-Kushilevitz-Lindell
    • UC two party protocolの不可能性. かなり大きいクラスの関数UC実現不可能であることを示す.
  • STOC'03 Damgard-Groth
    • UC COM の改良
  • CRYPTO'03, Canetti-Rabin, Joint State
    • multi instanceの扱い
  • FOCS'03, Lindell, General Composition and Univerall Composable Security
    • UC定義の最適性. concurrent general composition や specialized simulatorとの関係.
  • TCC'04, Hofheinz-MullerQuade,
    • ランダムオラクルを用いたUC COMの構成。
  • CSFW'04, Canetti,
  • STOC'04, Prabhakaran-Sahai,
    • CRSなしでUC定理を実現する方法. Angelを利用. oracle assumptionであるため, うけは良くない.
  • STOC'04, Barak-Canetti-Nielsen-Pass, with relaxed Set-Up Assumptions
    • CRS 仮定でない,より弱い仮定の下, UC COM and UC ZK を構成
  • CRYPTO'05, Barak-Canetti-Lindell-Pass-Rabin secure computation without authentication,
    • split functionality
  • TCC'05, Nagao-Manabe-Okamoto UC secure channel based on KEM-DEM
    • Euro'02とは異なる構成の UC secure channel.
  • TCC'06, Datta et al,
    • どのようにF_COMを定義してもplain model では実現不可能. process calculusの利用. formal method 的なアプローチ.
  • TCC'06 Canetti-Herzog, Symbolic Analysis
    • Dolve-Yao型の Symbolic Analysis と UC の関連. これも formal method 絡み.

Backes-Pfitzmann-Waidnerもreactive systemというUCと非常によくに概念を導入したが、残念ながらUCのほうにイニシアチブをとられた形になった. 正直 BPW の reactive system はとっつきにくい.