Memo_UC

Memo_UC

UCについてのメモを残すよ. ある種サーベイ.

概要

歴史

定義

現実世界のプロトコルπが理想世界の関数Fを使うプロトコルφをエミュレート出来るかどうか. simulation-based definitionに馴染めないと, 何故これで安全かが納得できないと思った. エミュレートさせるために理想関数Fに色々細工してあるし.

環境Zと敵Aとプロトコルπと関数FとシミュレータSが登場.

\{EXEC_{\pi,A,Z}(k,z)\}_{k\in \Nset, z \in \{0,1\}^*}が現実世界, \{EXEC_{\phi,S,Z}(k,z)\}_{k\in \Nset, z \in \{0,1\}^*}が理想世界.

πがφをUC-emurateする

∀PPT adv A ∃ PPT sim. S s.t. ∀Z, |\{EXEC_{\pi,A,Z}(k,z)\}_{k\in \Nset, z \in \{0,1\}^*} \{EXEC_{\phi,S,Z}(k,z)\}_{k\in \Nset, z \in \{0,1\}^*}| < \epsilon

UC formulations of some computational models Sec.6 [C05]

デルUCのFunctionalityとして定義できる.

認証済み通信路 F_{AUTH}.

Functionality F_{AUTH}.
  1. Upon receiving an input (Send, sid, m) from party S, do: If sid=(S, sid') from some R, then generate a public delayed output (Sent, sid,m) to R and halt. Else ignore the input.
  2. Upon receiving (Corrupt-sender, sid, m') from the adversary, and if the (Sent sid, m) output is not yet deliverd to R, then output (Sent, sid, m') to R and halt.

[C04] There exist no useful protocols that UC-realize F_{AUTH} in the bare model.

登録

Functionality F_{REG}.
  1. Upon receiving input (Register, sid, v) verify that sid=(P, sid'). If sid is not of that form, or this is not the first input form P, then ignore this input. Else, send (Registered, sid, v) to the adversary and record the value v.
  2. Upon receiving input (Retrieve, sid) from party P', send a delayed output (Retriever, sid, v) to P'. (If no value v is recorded then set v=⊥.)

[C04] If there exist signature schemes secure against chosen message attacks then there exists an F_{REG}-hybrid protocol that UC-realizes F_{AUTH}.

安全な通信路

Functionality F_{SMT}^{l}

l:{0,1}^{*} \to {0,1}^{*} : leakage function.

  1. Upon receiving an input (Send, sid, m) from party S, do: If sid=(S, R, sid') for some R then send (Sent, sid, l(m)) to the adversary, generate a private delayed output (Sent, sid, m) to R and halt. Else ignore the input.
  2. Upon receiving (Corrupt, sid, P) from the adversary, where P \in {S, R}, disclose m to the adversary. Next, if the adversary provides a value m', and P=S, and no output has been yet written to R, then output (Sent, sid, m') to R and halt.

同期通信

Functionality F_{SYN}

省略

Non-concurrent Security

Functionality F_{NC}
  1. When receiving message (Start, sid, \hat{A}) from the adversary, where \hat{A} is the code of an ITM (representing an adversary), invoke \hat{A} and change state to running.
  2. When receiving input (Send, sid, m, Q) from party P, and if the state is running, activate \hat{A} with incoming message (m, Q) from party P. Then:
    1. If \hat{A} instructs to deliver a message (m', P') to party Q' then output (sid, m', P') to Q'.
    2. If \hat{A} halts without delivering a message to any party then send the current state of \hat{A} to the adversary and halt.

この定義でいいの?

CRS

Functionality F_{CRS}
  1. When receiving input (CRS, sid) from party P, first verify that sid=(\PP,sid') where \PP is a set of identities, and that P \in \PP; else ignore the input. Next, if there is no value r recorded then choose and record a value r \gets_{R} D. Finally, send a public delayed output (CRS, sid, r) to P.

Key Set-Up

Fuctionality F_{KS}^{f}

given function f and security parameter k. At the first activation a set R of string is initialized to be empty.

Registration
When receiving input (Register, sid) from a party P, verify that sid=(P, sid') for some set \PP of identities and that P \in \PP; else ignore the input. Next, send (Register, sid, P) to the adversary, and receive a value p' from the adversary. Then, if p' \in R then let p \gets p'. Else, choose r \gets_R {0,1}^{k}, let p \gets f(r), and add p to R. Finally, record (P,p) and return (sid, p) to P and to the adversary.
Registration by a corrupted party
When receiving input (Register, sid, r) from a corrupted party P \in \PP, record (P, f(r)). In this case, f(r) is not added to R.
Retrieval
When receiving a message (Retrieve, sid, P) from party P' \in \PP, send (Retrieve, sid, P, P') to the adversary and obtain a value p in return. If (P, p) is recorded then return (sid, P, p) to P'. Else, return (sid, P, ⊥) to P'.

Claim 26. The above F_{CRS}^{D}-hybrid protocol UC-realizes F_{KS}^{f].

問題点

今後の発展

Formal Method (だっけか?)

Split Functionality

Non-malleable commitmentやPassword-based authenticated key exchangeや敵が過半数を超える状況下でのMPCを扱えるようにできるらしい.

CRYPTO2005の読んだ. Split Functionalityの定義は上手い. プロトコル開始時に全員が全員に検証鍵を送って, その検証鍵に署名を行って送り返す. するとシミュレータがシミュレート出来ない状況では敵が署名を破っていることになる. そこにPassのn-bounded concurrent MPCを組み合わせると色々出来るという話.