Abstract A wiretap coding scheme (Wyner in Bell Syst Tech J 54(8):1355–1387, 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel $$\textsf{ChB}$$ ChB , while at the same time hiding m from Eve who receives c over another noisy channel $$\textsf{ChE}$$ ChE . Wiretap coding is clearly impossible when $$\textsf{ChB}$$ ChB is a degraded version of $$\textsf{ChE}$$ ChE , in the sense that the output of $$\textsf{ChB}$$ ChB can be simulated using only the output of $$\textsf{ChE}$$ ChE . A classic work of Csiszár and Korner (IEEE Trans Inf Theory 24(3):339–348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $$(\textsf{ChB},\textsf{ChE})$$ ( ChB , ChE ) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if $$\textsf{ChB}$$ ChB is not a degraded version of $$\textsf{ChE}$$ ChE . Our construction assumes the existence of virtual black-box obfuscation of specific classes of “evasive” functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on $$\textsf{ChB}$$ ChB and not on $$\textsf{ChE}$$ ChE .

The existence of “unstructured” hard languages in NP ∩ coNP is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether P is separated from NP ∩ coNP relative to a random oracle, a question that remained open ever since. While a hard language in NP ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation.