Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries

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 polynomialtime bounded adversary? We rule out this possibility. More precisely, assuming SAT does not have small circuits, we show that for every languageAwith small circuits, there exists a probabilistic polynomial-time algorithm that makes black-box queries toA, and produces, for a given input length, a Boolean formula on whichAdiffers 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 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..