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 (and vice versa, up to each party’s private randomness and inputs).

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.

Note: A protocol secure against malicious parties implies security against semi-honest parties.