Razborov and Rudich's natural proofs barrier roughly says that it is computationally hard to certify that a uniformly random truth table has high circuit complexity. In this work, we show that the natural proofs barrier (specifically, Rudich's conjecture that there are no NP-constructive natural properties against $P/poly$) implies the following important consequences in derandomization, proof complexity, and cryptography.

- Derandomization: **Fortnow and Santhanam's Oracle Derandomization Hypothesis is false.** In particular, this means that one cannot use the hardness-versus-randomness paradigm to derandomize data structures, at least in the straightforward way. Our result is the first direct evidence that the Oracle Derandomization Hypothesis is false. As a corollary, we also get the first average-case hardness result for the Circuit Range Avoidance Problem (Avoid).

- Proof Complexity: **There is a single non-uniform proof complexity generator secure against all proof systems.** This is the first construction of such a proof complexity generator under any complexity assumption. Indeed, it was previously not clear whether such an object should exist.

- Cryptography: **In the non-uniform setting, zero-knowledge does not require interaction.** We construct a non-uniform, truly non-interactive prover and verifier where the verifier is perfectly sound and the prover has every ``falsifiable'' consequence of being zero-knowledge. Thus, in the non-uniform setting, we bypass a classical impossibility result of Goldreich and Oren that says zero-knowledge proofs require interaction. This is the first construction of such an object.