No fully-black-box reduction from iO + OWP to average-case-hard SZK

Unconditional · against fully-black-box reductions · BDV17

Statement

There is no fully-black-box construction, from a one-way permutation and iO for circuits that call the permutation, of a promise problem in SZK that no efficient algorithm decides on every instance — BDV17. BDV17 take the problem to be Statistical Difference on instances given by circuits that call the primitives, and give an oracle $\Psi$ implementing a one-way permutation and an obfuscator for circuits with permutation gates, together with an adversary $\mathcal{A}$ that decides Statistical Difference relative to $\Psi$ on every instance, such that the permutation and the obfuscator stay secure against efficient adversaries with oracle access to $\mathcal{A}$. An algorithm that decides a promise problem on every instance decides it under every distribution, so constructions of average-case-hard SZK problems are ruled out as well — standard. The same holds for every primitive with a fully-black-box construction from one-way permutations and iO for circuits that call the permutation, among them public-key encryption, oblivious transfer, deniable encryption and functional encryption — BDV17.

Notes

• For NP $\cap$ coNP, BDV17 prove the analogue with an injective one-way function in place of the permutation: there is no fully-black-box construction, from an injective one-way function and iO for circuits that call it, of a language in $\mathbf{NP}\cap \mathbf{coNP}$ that no efficient algorithm decides on every input, nor from any primitive with a fully-black-box construction from these, among them public-key encryption, oblivious transfer, deniable encryption and functional encryption — BDV17.
• That separation cannot be strengthened to one-way permutations: inverting a one-way permutation is in NP ∩ coNP — folklore — so one-way permutations give hard problems in $\mathbf{NP}\cap \mathbf{coNP}$, while even together with iO they give none in $\mathbf{SZK}$ by a fully-black-box construction — BDV17.
• Strongly homomorphic encryption does give hard problems in $\mathbf{SZK}$: for a public-key bit-encryption scheme with a strong homomorphic evaluator for a suitable function, statistical rerandomizability places distinguishing encryptions of $0$ from encryptions of $1$ in $\mathbf{SZK}$ — BL13.