Pseudorandom Correlation Functions from Variable-Density LPN, Revisited
Pseudorandom correlation functions (PCF), introduced in the work of (Boyle et al., FOCS 2020), allow two parties to locally generate, from short correlated keys, a near-unbounded amount of pseudorandom samples from a target correlation. PCF is an extremely appealing primitive in secure computation, where they allow to confine all preprocessing phases of all future computations two parties could want to execute to a single short interaction with low communication and computation, followed solely by offline computations. Beyond introducing the notion, Boyle et al. gave a candidate construction, using a new variable-density} variant of the learning parity with noise (LPN) assumption. Then, to provide support for this new assumption, the authors showed that it provably resists a large class of linear attacks, which captures in particular all known attacks on LPN. In this work, we revisit the analysis of the VDLPN assumption. We make two key contributions: - First, we observe that the analysis of Boyle et al is purely asymptotic: they do not lead to any concrete and efficient PCF instantiation within the bounds that offer security guarantees. To improve this state of affairs, we combine a new variant of a VDLPN assumption with an entirely new, much tighter security analysis, which we further tighten using extensive computer simulations to optimize parameters. This way, we manage to obtain for the first time a set of provable usable parameters (under a simple combinatorial conjecture which is easy to verify experimentally), leading to a concretely efficient PCF resisting all linear tests. - Second, we identify a flaw in the security analysis of Boyle et al., which invalidates their proof that VDLPN resists linear attacks. Using several new non-trivial arguments, we repair the proof and fully demonstrate that VDLPN resists linear attack; our new analysis is more involved than the original (flawed) analysis. Our parameters set leads to PCFs with keys around 3MB allowing ~ 500 evaluations per second on one core of a standard laptop for 110 bits of security; these numbers can be improved to 360kB keys and ~ 3800 evaluations/s using a more aggressive all-prefix variant. All numbers are quite tight: only within a factor 3 of the best bounds one could heuristically hope for.
Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding
Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle et al. (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computation, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). Furthermore, programmable PCGs can be used similarly to generate multiparty correlated randomness to be used in silent secure N-party protocols. Previous works constructed very efficient (non-programmable) PCGs for correlations such as random oblivious transfer. However, the situation is less satisfying for the case of random oblivious linear evaluation (OLE), which generalize oblivious transfers over large field, and are a core resource for secure computation of arithmetic circuits. The state-of-the-art work of (Boyle et al., Crypto 2020) constructed programmable PCGs for OLE, but their work suffers from two important downsides: (1) it only generates OLEs over large fields, and (2) it relies on a relatively new ``splittable'' ring-LPN assumption, which lacks strong security foundations. In this work, we construct new programmable PCGs for the OLE correlation, that overcome both limitations. To this end, we introduce the Quasi-Abelian Syndrome Decoding problem (QASD), a family of assumption which generalizes the well-established Quasi-Cyclic Syndrome Decoding assumption. Building upon QASD, we construct new programmable PCGs for OLEs over any field Fq with q > 2. Furthermore, we provide strong security foundations for QASD, showing that it resists all attacks from the linear test framework (Couteau et al., Crypto 2021) and admits a search-to-decision reduction. In particular, our analysis also sheds light on the security of the ring-LPN assumption used in Boyle et al., Crypto 2020). Using our new PCGs, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over Fq for any q > 2.