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




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


\{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\}^*}が理想世界.


∀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]


認証済み通信路 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.



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.

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.
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を組み合わせると色々出来るという話.