Interactive protocols

A two-party protocol $\Pi =(\mathsf{Setup},P_1,P_2)$ consists of:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{pp},$ a randomized algorithm generating public parameters,
• $P_1,P_2,$ two stateful interactive algorithms (the parties).

Each party $P_i$ has private inputs ${\mathbf{x}}_i$ and private random coins ${\rho }_i$. The parties exchange messages in sequence according to the protocol specification until both halt.

When $\mathsf{Setup}$ is trivial (no public parameters are needed), we write $\mathsf{pp}=1^{\lambda }$ and omit it.

Execution

The joint execution of $P_1$ with input ${\mathbf{x}}_1$ against $P_2$ with input ${\mathbf{x}}_2$ is written

$$⟨P_1(\mathsf{pp},{\mathbf{x}}_1),P_2(\mathsf{pp},{\mathbf{x}}_2)⟩\to ({\mathsf{out}}_1,{\mathsf{out}}_2),$$

where ${\mathsf{out}}_i$ is the output of $P_i$. When we wish to make randomness explicit, we write $P_i(\mathsf{pp},{\mathbf{x}}_i;{\rho }_i)$.

View

The view of party $P_i$ in an execution captures everything $P_i$ observed:

$${\mathsf{V}}_{P_i}=({\mathbf{x}}_i,{\rho }_i,{\mathbf{m}}_i),$$

where ${\mathbf{m}}_i=(m_i^{(1)},m_i^{(2)},\dots )$ is the ordered sequence of messages $P_i$ received. The view determines $P_i$‘s behavior completely: given ${\mathsf{V}}_{P_i}$, one can recompute all messages $P_i$ sent and its final output.

Transcript

The transcript of an execution is the ordered sequence of all messages exchanged by both parties. The views ${\mathsf{V}}_{P_1}$ and ${\mathsf{V}}_{P_2}$ together determine the transcript.

Adversary models

Security of a protocol is analyzed under one of two standard adversary models:

• Semi-honest (honest-but-curious): the adversary follows the protocol specification exactly but tries to learn additional information from its view alone.
• Malicious: the adversary may deviate from the protocol arbitrarily, sending any messages it chooses.

Security against malicious adversaries implies security against augmented semi-honest adversaries, which may substitute their input before the execution Gol04, but not in general against semi-honest adversaries: the malicious-model simulator may change the corrupted party’s input, which the semi-honest ideal model forbids — HL10.

Network models

A multi-party protocol runs in synchronous rounds among parties $P_1,\dots ,P_n$: a message sent in round $r$ is delivered before round $r+1$. The adversary is rushing, choosing the corrupted parties’ round-$r$ messages after seeing the honest parties’ round-$r$ messages.

Authenticated channels

Every pair of parties is joined by an authenticated point-to-point channel: the adversary reads every message, and cannot modify, drop or inject a message between two honest parties. There is no broadcast channel and no setup.

Secure channels

Point-to-point channels between every pair that are authenticated, as above, and also private: of a message between two honest parties the adversary learns only that it was sent, and its length. Unlike authenticated channels, secure channels do not exclude a broadcast channel: a result over secure channels states whether it also uses one.

Broadcast channel

A channel on which a party’s message reaches every party, every party knowing that all parties received the same message. Over authenticated channels without setup, a Byzantine broadcast protocol emulates it if and only if fewer than a third of the parties are corrupted — LSP82.

Correlated randomness

Before the inputs are chosen, a trusted dealer samples $(r_1,\dots ,r_n)$ from a distribution that the protocol specifies, which may depend on $n$, $\lambda$ and the functionality but not on the inputs, and hands $r_i$ to $P_i$ privately; this is the preprocessing model. Random OT correlations — Bea95 — and multiplication triples, sharings of $a$, $b$ and $ab$ for uniform $a,b$, as consumed by the online phases of BDOZ11 and DPSZ12, are examples. Triples descend from Beaver’s circuit randomization, in which the random gate values are prepared within a secret-sharing-based protocol rather than by a dealer — Bea91.

Participates in

Builds on Interactive protocol

• Authenticated channels ⇒ Broadcast against $t<n/3$ (Lamport–Shostak–Pease) (via Authenticated channels)
• Correlated randomness ⇒ UC MPC (BDOZ online phase) (via Correlated randomness)
• SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ) (via Correlated randomness)
• Secure channels ⇒ MPC with honest majority ($t<n/2$) (Rabin–Ben-Or) (via Secure channels)
• Secure channels ⇒ MPC with honest majority ($t<n/3$) (BGW) (via Secure channels)
• Secure channels ⇒ MPC with honest majority ($t<n/3$) with linear communication (Beerliová-Trubíniová–Hirt) (via Secure channels)
• Secure channels ⇒ MPC with honest majority ($t<n/3$) (Chaum–Crépeau–Damgård) (via Secure channels)
• Secure channels ⇒ MPC with honest majority ($t<n/3$) from linear secret sharing (Cramer–Damgård–Maurer) (via Secure channels)
• Secure channels ⇒ MPC with abort and honest majority ($t<n/2$) (CGH+18) (via Secure channels)
• Secure channels ⇒ Semi-honest MPC with honest majority ($t<n/2$) (BGW) (via Secure channels)

Barriers

• No reduction from authenticated channels to Byzantine broadcast (via Authenticated channels) — circumvented by Digital signatures ⇒ Byzantine broadcast (Dolev–Strong)
• No reduction from authenticated channels to fair coin flipping (via Authenticated channels)
• No reduction from authenticated channels to fair MPC (via Authenticated channels)
• No reduction from authenticated channels to UC MPC (via Authenticated channels) — circumvented by Enhanced TDP ⇒ UC MPC in the CRS model (CLOS), Ideal OT + PRG ⇒ UC MPC (IPS), Correlated randomness ⇒ UC MPC (BDOZ online phase)