We may believe SAT does not have small Boolean circuits.
But is it possible that some language with small circuits
looks indistiguishable from SAT to every polynomial-time
bounded adversary? We rule out this possibility. More
precisely, assuming SAT does not have small circuits, we
show that for every language $A$ with small circuits,
there exists a probabilistic polynomial-time algorithm
that makes black-box queries to $A$, and produces, for a
given input length, a Boolean formula on which $A$
differs from SAT. A key step for obtaining this result is
a new proof of the main result by Gutfreund, Shaltiel,
and Ta-Shma reducing average-case hardness to worst-case
hardness via uniform adversaries \emph{that know the
algorithm they fool}. The new adversary we construct has
the feature of being black-box on the algorithm it fools,
so it makes sense in the non-uniform setting as well. Our
proof makes use of a refined analysis of the learning
algorithm of Bshouty et al..