# 1/12: MPC Definitions / Problems Collection

- chapter 23 of https://toc.cryptobook.us/book.pdf
- the book https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf

thanks to cryptohack discord for sending me resources below
- https://nigelsmart.github.io/SCALE/
- https://github.com/rdragos/awesome-mpc

## 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
- BDOZ (https://eprint.iacr.org/2010/514.pdf)
- SPDZ (https://eprint.iacr.org/2011/535.pdf)
- https://eprint.iacr.org/2012/642.pdf
- https://eprint.iacr.org/2015/523.pdf
- https://eprint.iacr.org/2017/1230.pdf
- https://eprint.iacr.org/2018/482.pdf
- https://eprint.iacr.org/2019/599.pdf
- https://eprint.iacr.org/2020/521.pdf

### Yao's Millionare Problem

This one aims to simply compare two inputs.
- https://eprint.iacr.org/2005/043.pdf
- https://www.win.tue.nl/~berry/papers/pkc07intcomp.pdf
- https://iacr.org/archive/pkc2007/44500343/44500343.pdf
- https://eprint.iacr.org/2016/544.pdf
- https://eprint.iacr.org/2020/1002.pdf

### 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.

- https://dl.acm.org/doi/pdf/10.1145/301250.301312
- https://link.springer.com/content/pdf/10.1007/3-540-45664-3_11.pdf
- https://ir.nctu.edu.tw/bitstream/11536/27052/1/000188196400010.pdf
- https://eprint.iacr.org/2013/552.pdf
- https://eprint.iacr.org/2015/267.pdf
- https://eprint.iacr.org/2016/799.pdf
- https://eprint.iacr.org/2016/933.pdf
- https://eprint.iacr.org/2019/414.pdf
- https://dl.acm.org/doi/pdf/10.1145/3503045

### Private Set Intersection

Two participants have a set, wish to compute intersection.

- https://eprint.iacr.org/2015/634.pdf
- https://eprint.iacr.org/2016/930.pdf
- https://eprint.iacr.org/2017/299.pdf
- https://eprint.iacr.org/2017/1064.pdf
- https://eprint.iacr.org/2018/120.pdf
- https://eprint.iacr.org/2019/634.pdf
- https://eprint.iacr.org/2020/729.pdf
- https://eprint.iacr.org/2021/122.pdf

### Multiparty ECDSA / Schnorr

Compute a signature via multiparty signature with each party having key shares
- https://eprint.iacr.org/2019/114.pdf
- https://eprint.iacr.org/2020/540.pdf
- https://eprint.iacr.org/2021/060.pdf
- https://eprint.iacr.org/2022/374.pdf

### MPC-in-the-head

MPC related ideas to ZKP, signatures, and etc.
- https://web.cs.ucla.edu/~rafail/PUBLIC/77.pdf
- https://eprint.iacr.org/2016/687.pdf
- https://eprint.iacr.org/2018/475.pdf
- https://eprint.iacr.org/2019/532.pdf
- https://eprint.iacr.org/2021/068.pdf
- https://eprint.iacr.org/2021/692.pdf
- https://eprint.iacr.org/2022/588.pdf

### Others (TBD)

Private Information Retrieval, Private Function Evaluation, etc