Paper 2026/255

On Compressing Linearly Shared Correlations

Abstract

Compressing correlated randomness is a key component of secure computation protocols in the silent preprocessing model and has received significant attention in recent years. Most existing constructions target additive correlations, where the parties receive additive shares of a relation. Beyond additive correlations, much less is known: more general linear correlations can be compressed using pseudorandom secret sharing, generic constructions for richer linear-output correlations can be obtained by combining LWE-based multiparty HSS with share conversion, in regimes where the share-conversion overhead is efficient, and general correlations can be compressed using indistinguishability obfuscation. In this work, we advance the study of compression for useful forms of correlated randomness beyond additive output sharing (concretely, linear-output correlations, together with a constrained variant capturing random permutations), without resorting to $iO$, introducing new techniques, new feasibility results, and relying on more diverse assumptions. We provide several constructions for pseudorandom correlation generators and functions using direct HSS- and LPN/MQ-based techniques. Concretely, we focus on two types of correlations in this work. First, we introduce pseudorandom permutation functions, where each party obtains a portion of a pseudorandom permutation $\pi$ over the set $\set{1,\dots, n}$, such that a single party learns nothing about the full permutation beyond its own output. We give a three-party construction of a pseudorandom correlation function (PCF) for permutations from homomorphic secret sharing satisfying a special share programmability property. This construction can be instantiated from a variety of standard assumptions and can even be concretely efficient (generating pseudorandom permutations in a fraction of a second). We describe two applications of pseudorandom permutation functions: one in anonymous broadcast and the other in single secret leader election. Second, we introduce pseudorandom correlation generators for classical correlations (such as Beaver triples) where additive secret sharing is replaced with threshold secret sharing. We obtain pseudorandom correlation functions for degree-$1$ Shamir shares of $\mathsf{NC}^1$ correlations from a variety of standard assumptions. We also introduce two new PCG constructions for threshold-shared constant-degree correlations in the regimes where either the privacy threshold $t$ or $n-t$ is a constant. These constructions rely on the conjunction of the LPN and MQ assumptions.