Average-case-hard CZK ⇒ CZK ⊄ BPP

Fully-black-box reduction · standard model · folklore · security loss: none: a BPP decider for the language succeeds with probability at least 2/3 under every distribution

Statement

If CZK is hard on average, witnessed by $L\in \mathbf{CZK}$ and a PPT sampler $D$, then $L\notin \mathbf{BPP}$, so CZK ⊄ BPP: a PPT algorithm deciding $L$ with probability at least $2/3$ on every input does so under $D(1^n)$, and $2/3>1/2+\mathrm{negl}(n)$ for all sufficiently large $n$ — folklore.