Paper 2026/1355

Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography

Abstract

We revisit the question of securely compressing multiparty correlations using only symmetric cryptography. A *linear correlation* ${\cal C}$, defined by a linear subspace $C\subseteq \mathbb F^n$, samples a secret random ${\bf c}\in C$ and assigns to each party a fixed subset of the entries of ${\bf c}$. Gilboa and Ishai (Crypto 1999) and Cramer, Damgård and Ishai (TCC 2005) provide a general technique for securely compressing many independent samples from $\cal C$ by replicating independent keys of a pseudorandom function (PRF) among the parties. This implies a *pseudorandom correlation function* (PCF) for $\cal C$ from any PRF, where the PCF key size scales with the number of minimal-support codewords in $C$. We observe that the above generalizes to other types of useful target correlations ${\cal C}_T$ by using a *secret* replication pattern obtained via a random secret assignment of parties in $\cal C$ to parties in ${\cal C}_T$. We present several corollaries of this general blueprint. These include a re-derivation of two-party PCF constructions for VOLE and subfield-VOLE over small domains (Roy, Crypto 2022) as well as new multiparty PCFs for small-domain VOLE-style correlations, including scalar-vector multiplication triples and their authenticated variants. Finally, we discuss applications to secure computation.