Paper 2025/778

Amplifying Randomized Encodings & Applications

Abstract

A randomized encoding for a promise problem is a randomized reduction whose outcome distribution on input $x$ can be simulated within some distance $d$, called privacy, using only one bit of information about $x$: whether it is a YES or NO instance. The encoding is one-sided if this property holds only for YES instances. Our main contribution is showing that (classical and quantum) one-sided randomized encodings have privacy and correctness amplification: any problem with a randomized encoding with privacy $1-1/poly(n)$ and error $1/2-1/poly(n)$, also has an encoding with negligible privacy and error. We then use this result to obtain the following statements: - We show that NISZK, the class of problems that have a non-interactive (statistical) zero-knowledge proof, has strong zero-knowledge amplification, i.e., every problem with a non-interactive zero-knowledge proof with zero-knowledge error $1-1/poly(n)$, also has a non-interactive zero-knowledge proof with negligible zero-knowledge error. This solves a problem open since the work of Goldreich, Sahai, and Vadhan (CRYPTO '99). - The worst-case hardness of a problem that has a perfect (i.e., zero error) one-sided encoding implies one-way functions (OWFs). And if the encoding is quantum, it implies one-way state generators (OWSGs). We then conclude that by removing the error from one-sided randomized encodings, the worst-case hardness of the complexity class SZK becomes sufficient for the existence of OWFs. - Weak and imperfect indistinguishability obfuscation (iO) implies OWFs assuming that the Polynomial Hierarchy does not collapse to its third level. Here, weakness means that the computational distance between the obfuscated circuit and the original circuit is $1-1/poly(n)$, and imperfectness means that the error is $1/2-1/poly(n)$. To achieve this privacy and correctness amplification, we study randomized encodings through the lens of lossy reductions (Ball et al. ITCS 2020). In particular, we introduce an extended and flexible notion of lossy reductions, and show that it is equivalent to randomized encodings. This equivalence serves as the base of our main results and might be of independent interest.

Note: Compared to the previous version, the content has been substantially modified. This includes the presentation of the techniques and ideas as well as the results. Most notably: - The main contribution is now rephrased in terms of the class of randomized encodings and a newly defined complexity class that corresponds to lossy reductions. - The result on the existence of OWFs and OWSGs is now rephrased in terms of the hardness of one-sided randomized encodings. The fine-grained analysis is omitted. - The core technical tools have been further developed. - An error in the bound for the reverse Pinsker's inequality has been fixed. - More applications have been added.