aiqbench analysis
This research establishes that both classical and quantum one-sided randomized encodings support privacy and correctness amplification, effectively reducing statistical errors to negligible levels. The findings resolve a long-standing open problem regarding non-interactive zero-knowledge proofs and demonstrate that worst-case hardness of these quantum encodings is sufficient for constructing one-way functions and state generators. By linking lossy reductions to randomized encodings, the work bridges theoretical complexity classes with practical cryptographic primitives in the quantum regime.
Amplifying Randomized Encodings & Applications
arXiv:2505.21442v3 Announce Type: replace-cross 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 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 an encoding with privacy $1-1/poly(n)$ and error $1/2-1/poly(n)$ also has one with negligible privacy and error. We use this result to show: - NISZK, the class of problems with non-interactive (statistical) zero-knowledge proofs, has strong zero-knowledge amplification: every problem with such a proof with zero-knowledge error $1-1/poly(n)$ also has one with negligible zero-knowledge error. This solves a problem open since Goldreich, Sahai, and Vadhan (CRYPTO '99). - The worst-case hardness of a problem with a perfect (zero-error) one-sided encoding implies one-way functions (OWFs), and, if the encoding is quantum, one-way state generators (OWSGs). We then conclude that removing the error from one-sided randomized encodings would make the worst-case hardness of SZK sufficient for OWFs. - Weak and imperfect indistinguishability obfuscation (iO) implies OWFs assuming the Polynomial Hierarchy does not collapse to its third level. Here, weak means the computational distance between the obfuscated and original circuits is $1-1/poly(n)$, and imperfect means the error is $1/2-1/poly(n)$. To achieve this amplification, we study randomized encodings through the lens of lossy reductions (Ball et al. ITCS 2020): we introduce an extended, flexible notion of lossy reductions and show it is equivalent to randomized encodings. This equivalence underlies our main results and may be of independent interest.
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 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 an encoding with privacy $1-1/poly(n)$ and error $1/2-1/poly(n)$ also has one with negligible privacy and error. We use this result to show: - NISZK, the class of problems with non-interactive (statistical) zero-knowledge proofs, has strong zero-knowledge amplification: every problem with such a proof with zero-knowledge error $1-1/poly(n)$ also has one with negligible zero-knowledge error. This solves a problem open since Goldreich, Sahai, and Vadhan (CRYPTO '99). - The worst-case hardness of a problem with a perfect (zero-error) one-sided encoding implies one-way functions (OWFs), and, if the encoding is quantum, one-way state generators (OWSGs). We then conclude that removing the error from one-sided randomized encodings would make the worst-case hardness of SZK sufficient for OWFs. - Weak and imperfect indistinguishability obfuscation (iO) implies OWFs assuming the Polynomial Hierarchy does not collapse to its third level. Here, weak means the computational distance between the obfuscated and original circuits is $1-1/poly(n)$, and imperfect means the error is $1/2-1/poly(n)$. To achieve this amplification, we study randomized encodings through the lens of lossy reductions (Ball et al. ITCS 2020): we introduce an extended, flexible notion of lossy reductions and show it is equivalent to randomized encodings. This equivalence underlies our main results and may be of independent interest.
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
Cryptography and Security (cs.CR); Quantum Physics (quant-ph)
arXiv:2505.21442 [cs.CR]
(or arXiv:2505.21442v3 [cs.CR] for this version)
Full text under the publisher's open licence · 316 words
Related coverage
News
Quantum Computing Report · Jun 7, 2026
NISQ, What Noisy Intermediate-Scale Quantum Means
Quantum Zeitgeist · Aug 30, 2026
Quantum chip predicts time series with a feedback loop
Quantum Zeitgeist · Sep 27, 2026
WiMi Releases Resource - Efficient Quantum Convolutional Neural Network Based on QRAM , Accelerating the Practical Implementation of Large - Scale Image Classification Applications
manilatimes.net · Jul 20, 2026