1/12: MPC Definitions / Problems Collection

thanks to cryptohack discord for sending me resources below

Key Definitions

The intuitive setting - is that there are \(n\) parties each with input \(x_1, x_2, \cdots, x_n\) and a public function \(f\). These \(n\) parties want to work together to compute \(y = f(x_1, \cdots, x_n)\), but they want to reveal nothing about their inputs \(x_i\) except the information that is trivially revealed due to the output \(y\). In this scenario, there's some desirable properties we can define.

Properties

  • privacy: as mentioned, other parties do not know anything about \(x_i\) except the information directly revealed by the output \(y\) (e.g. consider \(f(x_1, x_2) = x_1 + x_2\))
  • soundness: honest parties compute correct outputs
  • input independence: all parties choose their inputs independent from other inputs
  • guaranteed output delievery: honest parties are guaranteed to obtain output
  • fairness: if any party obtains an output, all honest parties do

where the latter two are a bit more optional than the previous three.

Communication

Such protocols need to deal with communications between parties.

  • Synchronous: message between honest parties will be delivered in a fixed amount of time
  • Asynchronous: messages may be arbitrarily delayed
  • Secure point-to-point communication channels are used (authenticated encryption)

Attack/Corruption Models

  • malicious security: corrupt parties behave arbitrarily adversarily
    • static: corrupted parties are fixed at the very beginning
    • adaptive: adversaries use an adaptive strategy
  • honest-but-curious adversaries: faithfully follow the protocol, but leak their internal state
    • also called "semi-honest security"

Formal Security

The precise definition of MPC is quite difficult - so more or less should be looked a bit later after studying some problems and constructions first - but some keywords.

  • Real/Ideal Paradigm
    • ideal world is where a trusted party is used - so each party, honest or corrupt, submits the input to the trusted party, and the protocol is ran by the trusted party
    • so a protocol is secure when an attack on the "real world" also works on the "ideal world" - and we prove this similar to the ZK-ness proof, by providing a simulator on the "ideal world" that provides the views of the "real world adversary", in a manner in which the two distributions are computationally indistinguishable
  • Universal Composability

For a concrete look into the definitions, Chapter 23.5 of the big book works as an intro.
The Chapter 2 of the pragmatic MPC book also has some nice explanations as well.

Problems to Look

General Purpose MPC

This is the most general format: we aim to do MPC for general function \(f\).

The current reading list looks as follows. First, the fundamentals.

  • Beaver's Protocol
  • Garbled Circuits and their extensions/improvements

from both books seems to be must-read.

Then, there are more "recent" papers

Yao's Millionare Problem

This one aims to simply compare two inputs.

Oblivious Transfer

The first participant has \(x_1, \cdots, x_n\), the other has the index \(k\), and the output is \(x_k\), but the first participant should not know the index \(k\). There is 1-out-of-\(n\), \(k\)-out-of-\(n\) and such.

Private Set Intersection

Two participants have a set, wish to compute intersection.

Multiparty ECDSA / Schnorr

Compute a signature via multiparty signature with each party having key shares

MPC-in-the-head

MPC related ideas to ZKP, signatures, and etc.

Others (TBD)

Private Information Retrieval, Private Function Evaluation, etc

Select a repo