Pseudorandom correlation generator

A pseudorandom correlation generator (PCG) for a target correlation $\mathcal{C}$ samples a pair of seeds $(k_0,k_1)$ that the two parties expand locally into outputs $(R_0,R_1)$, such that the pair is indistinguishable from a sample of $\mathcal{C}$ and each seed reveals nothing about the other party’s output beyond what $\mathcal{C}$ itself reveals — BCG+19.

Syntax

A correlation generator $\mathcal{C}$ is a $\mathrm{PPT}$ algorithm that on input $1^{\lambda }$ outputs a pair $(R_0,R_1)$. A PCG for $\mathcal{C}$ is a pair of efficient algorithms $(\mathsf{Gen},\mathsf{Eval})$:

• $\mathsf{Gen}(1^{\lambda })\to (k_0,k_1)$, a randomized algorithm outputting a pair of seeds.
• $\mathsf{Eval}(\sigma ,k_{\sigma })\to R_{\sigma }$, a deterministic algorithm taking a party index $\sigma \in \{0,1\}$ and the seed $k_{\sigma }$, outputting party $\sigma$‘s output $R_{\sigma }$.

$\mathsf{Eval}$ is called Expand in BCG+19.

Properties

Correctness

The pair $(\mathsf{Eval}(0,k_0),\mathsf{Eval}(1,k_1))$ for $(k_0,k_1)\leftarrow \mathsf{Gen}(1^{\lambda })$ is computationally indistinguishable from $\mathcal{C}(1^{\lambda })$ — BCG+19.

TODO: game.

Security

$\mathcal{C}$ is required to be reverse-sampleable: an efficient algorithm, given $\sigma$ and an output $R_{1-\sigma }$ of one party, samples an $R_{\sigma }$ such that the resulting pair is computationally indistinguishable from $\mathcal{C}(1^{\lambda })$. A PCG is secure if for each $\sigma \in \{0,1\}$, $(k_{1-\sigma },\mathsf{Eval}(\sigma ,k_{\sigma }))$ is computationally indistinguishable from $(k_{1-\sigma },R_{\sigma })$, where $R_{\sigma }$ is reverse-sampled from $R_{1-\sigma }=\mathsf{Eval}(1-\sigma ,k_{1-\sigma })$ — BCG+19.

TODO: game.

Participates in

Produces Pseudorandom correlation generator

• Sparse Ring-LPN ⇒ PCG
• Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG)