Paper 2026/2817

From Degree Three to Degree Two: Statistical Randomized Encodings for All Functions

Abstract

A randomized encoding represents a function by a simpler randomized map whose output allows recovery of the function value while revealing essentially no further information about the input. Perfectly correct and perfectly private encodings of degree three over $\F_2$ are known for every Boolean function, but degree two cannot provide these guarantees for all functions (Ishai and Kushilevitz, FOCS 2000 and ICALP 2002). Whether degree two suffices when small statistical errors are allowed in both correctness and privacy has remained open. We construct quadratic randomized encodings of every Boolean function with exponentially small correctness and statistical privacy errors. The degree bound holds jointly in the input bits and independent uniform random bits, and the construction, encoder, decoder and simulator have complexity polynomial in the total size of mod-2 branching programs computing the function's output bits and in the security parameter. Our encodings also achieve decomposability and output locality three, meaning that each encoded bit depends on at most three input and random bits. These results resolve the degree-two and locality-three questions for statistical randomized encodings (Ishai, 2013). As an application, we obtain one-way functions of optimal output locality three from one-way functions in polynomial-time uniform $\mathrm{NC}^1$, improving the previous locality-four result under the same assumption (Applebaum, Ishai and Kushilevitz, FOCS 2004). We also obtain quadratic multiparty randomized encodings with negligible correctness and statistical privacy errors against semi-honest corruption of any coalition of parties. Previous general constructions for $k\ge4$ parties provided perfect correctness and privacy against at most $\lfloor 2k/3\rfloor$ corruptions (Applebaum, Ishai, Karni and Patra, CRYPTO 2022). Through known reductions, our encodings yield non-interactive reductions of every functionality to a fixed three-party functionality and three-round protocols in the two-round OT-hybrid model, with negligible correctness and statistical privacy errors against every coalition. They also yield non-interactive client--server protocols for every function whenever a majority of the servers is honest, even when corrupted servers collude with any set of clients. This server threshold is optimal in this model when privacy is required against arbitrary client coalitions.