Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF

Original paper: Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF. Yaxi Yang, Xiaojian Liang, Xiangfu Song, Ye Dong, Linting Huang, Hongyu Ren, Changyu Dong, and Jianying Zhou. 2024

Problem

Existing Circuit-PSI protocols only semi-honest secure
Cannot convert to malicious: consistency issue
- Parties can't guarantee inputs to function $f$ stay unchanged from PSI output
- Malicious party could alter secret-shared intersection before sending to circuit

Solution: $\Pi_{mcPSI}$ Protocol

Key Innovation: DDOPRF (Distributed Dual-key Oblivious PRF)

SPDZ-compatible OPRF using Dodis-Yampolskiy PRF: $F(k,x) = g^{1/(k+x)}$
Computes PRF on secret-shared inputs with MAC authentication
"Dual-key" mechanism ($k$ and $k_s$) enables fairness

Four-Phase Protocol

Phase 1: Secret Shared Shuffle
- Inputs: $\mathbf{x}$ ($P_0$), $\mathbf{y}$ ($P_1$)
- Create ASS: $\langle \mathbf{x} \rangle$, $\langle \mathbf{y} \rangle$
- Shuffle with random unknown permutations: $\langle \mathbf{x}' \rangle = \langle \pi(\mathbf{x}) \rangle$, $\langle \mathbf{y}' \rangle = \langle \rho(\mathbf{y}) \rangle$
Phase 2: DDOPRF
- $P_0$ computes: $F(k, x'_i) = g^{1/(k+x'_i)}$
- $P_1$ computes: $F(k, k_s, y'_j) = g^{k_s/(k+y'_j)}$
- Secondary key $k_s$ keeps $P_1$'s values random until revealed
Phase 3: Fair Comparison
- Bit-decompose $\langle k_s \rangle$ into $\ell$ bits
- Open bits one-by-one (with MAC checks)
- Both parties reconstruct $k_s$ simultaneously
- $P_0$ computes $(g^{1/(k+x'_i)})^{k_s}$ to compare with $P_1$'s values
- Match $\Rightarrow x'_i = y'_j$ in intersection
Phase 4: Function Computation
- Collect matching shares: $\langle \mathbf{x} \cap \mathbf{y} \rangle$
- Send to $\mathcal{F}_{2PC}$ to compute $f(\mathbf{x} \cap \mathbf{y})$
- MAC checks ensure shares weren't tampered
- Similar bit-decomposition trick for fair output revelation

Technical Details

Secret Sharing Notation

$⟨ x ⟩ : Linear Secret Sharing (LSS) - unauthenticated
- $P_i$ holds $\langle x \rangle_i \in \mathbb{F}_p$ where $\sum \langle x \rangle_i = x$
$\langle x \rangle$: Authenticated Secret Sharing (ASS) - with MACs
- $\langle x \rangle = (\langle x \rangle, \langle \gamma(x) \rangle)$ where $\gamma(x) = \xi \cdot x$
- MAC key $\langle \xi \rangle$ shared between parties
- $P_i$ holds $\langle x \rangle_i = (\langle x \rangle_i, \langle \gamma(x) \rangle_i) \in \mathbb{F}_p^2$

Beaver Triple Multiplication

Precompute random triple: $(\langle a \rangle, \langle b \rangle, \langle c \rangle)$ where $c = a \cdot b$
To compute $\langle x \cdot y \rangle$:
1. Mask: $\langle e \rangle = \langle x \rangle - \langle a \rangle$, $\langle f \rangle = \langle y \rangle - \langle b \rangle$
2. Open $e, f$ (safe because masked by random $a,b$)
3. Compute: $\langle z \rangle = \langle c \rangle + f \cdot \langle a \rangle + e \cdot \langle b \rangle + e \cdot f$
Result: $z = x \cdot y$

MAC Check Protocol

To open $\langle x \rangle$ with integrity check:

Each $P_i$ reveals $\langle x \rangle_i$
Reconstruct $x' = \sum \langle x \rangle_i$
Each $P_i$ computes: $\langle d \rangle_i = \langle \gamma(x) \rangle_i - x' \cdot \langle \xi \rangle_i$
Commit, then open $d = \sum \langle d \rangle_i$
Check $d = 0$ (fails if $x' \neq x$ with probability $\approx 1$)

Group Shares (MSS/AMSS)

$([x])$: Multiplicative Secret Sharing over group $\mathbb{G}$
- $\prod ([x])_i = g^x$ (secret in exponent)
- Operations: $([x]) \cdot ([y]) = ([x+y])$, $([x])^c = ([c \cdot x])$
$\langle [x] \rangle$: Authenticated MSS $= (([x]), ([\gamma(x)]))$
Convert ASS$→$AMSS: $([x])_i = g^{\langle x \rangle_i}$ (non-interactive!)

DDOPRF Protocol Detail

Input: $\langle x \rangle$, $\langle k \rangle$, optional $\langle k_s \rangle$

$\langle r \rangle \leftarrow$ random (for masking)
$\langle d \rangle \leftarrow \langle r \rangle \cdot (\langle k \rangle + \langle x \rangle)$ [via Beaver triple]
Open $d$ with MAC check $\to d = r \cdot (k+x)$
$\langle e \rangle \leftarrow d^{-1} \cdot \langle r \rangle \to e = 1/(k+x)$
If $k_s$ provided: $\langle e \rangle \leftarrow \langle e \rangle \cdot \langle k_s \rangle$ [another Beaver triple]
$\langle [e] \rangle \leftarrow \text{Convert}(\langle e \rangle)$ [ASS to AMSS]
Open $g^e$ with MAC check

Output: $g^{1/(k+x)}$ or $g^{k_s/(k+x)}$

References

Yaxi Yang, Xiaojian Liang, Xiangfu Song, Ye Dong, Linting Huang, Hongyu Ren, Changyu Dong, and Jianying Zhou. 2024. “Maliciously Secure Circuit Private Set Intersection via SPDZ-Compatible Oblivious PRF.” https://eprint.iacr.org/2024/789.