Niv Yehuda Gilboa

Pseudorandom correlation generators (PCGs) have emerged as a powerful tool for concretely efficient secure computation, allowing parties to generate vast amounts of correlated randomness by expanding short, local seeds. In the dishonest-majority setting, two primary correlations have been used as tools for achieving malicious security:Authenticated multiplication triples (AMT), used in SPDZ-style protocols, have efficient PCGs. However, the expanded AMT correlations themselves are highly redundant, up to σ× larger than the underlying (unauthenticated) multiplication triples, where σ is a statistical security parameter.Batch-authenticated multiplication triples (BAMT), based on fully linear interactive oracle proofs (FLIOP), have only a sublinear additive overhead on top of the underlying unauthenticated triples. However, the only known PCGs for BAMT have a slow seed generation, requiring more time than generating the entire expanded correlation. Authenticated multiplication triples (AMT), used in SPDZ-style protocols, have efficient PCGs. However, the expanded AMT correlations themselves are highly redundant, up to σ× larger than the underlying (unauthenticated) multiplication triples, where σ is a statistical security parameter. Batch-authenticated multiplication triples (BAMT), based on fully linear interactive oracle proofs (FLIOP), have only a sublinear additive overhead on top of the underlying unauthenticated triples. However, the only known PCGs for BAMT have a slow seed generation, requiring more time than generating the entire expanded correlation. Using existing LPN-style assumptions, we obtain the first fast PCG for BAMT, where the PCG seed size and generation time both scale sublinearly with the number of triples n. Concretely, for any ϵ>0, the seeds can be generated in time O(n^ϵ) with O(n^1-ϵ) batch-authentication size. We further demonstrate the concrete efficiency of the above PCG. For example, for n=2·10⁸ binary triples, we can obtain essentially the same seed size and expansion time as the current best PCGs for AMT, but with a 32× smaller correlation size.