安全多方计算

Defining MPC

There are $n$ parties $P_1,\cdots,P_n$ with private inputs $x_1,\cdots,x_n$ that want to jointly compute a function $y=f(x_1,\cdots,x_n),$ but not leak their own input to the other parties.

If $n=2$, then we call that secure two-party computation (2PC). If $n\geq 3$, we call that secure multiparty computation (MPC).

Security

The adversary corrupts a subset of the parties and makes them collude to break security of the protocol. Many security goals of MPC:

1. Privacy: Parties only learn the output of $f$.
2. Correctness: If a party receives $y$, then $y=f(x_1,\cdots,x_n)$.
3. Input independence: Corrupt parties' inputs can't depend on honest parties' inputs.
4. Fairness: If the adversary learns the output, so do the honest parties.

Some Results

For Fairness, only possible if there is an honest majority. Therefor, fair 2PC is impossible!

For Privacy, Correctness and Input independence,

• Information-theoretic security if more than $\frac{2}{3}n$ parties are honest. (Veritable secret sharing + Error correcting codes)
• Computational security if at least one party is honest.
  • "Classical" approach:
    • Parties commit to their inputs
    • In each step, parties prove in zero-knowledge that they followed the protocol ( e.g. [GMW87])
  • "Modern" approach: compute on shares of authenticated data (e.g. [DPSZ11])

References

Stanford CS335 Lecture

[GMW87] Goldreich, Oded, S. Micali and A. Wigderson. “How to play ANY mental game.” STOC '87 (1987).

[DPSZ11] Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. "Multiparty computation from somewhat homomorphic encryption". CRYPTO 2012.

本文标题: 安全多方计算
本文作者: 云中雨雾
本文链接: https://weiviming.github.io/16092286702660.html
本站文章采用 知识共享署名4.0 国际许可协议进行许可
除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间: 2020-12-29T15:57:50+08:00