On the power of nonuniformity in proofs of security

Abstract

Nonuniform proofs of security are common in cryptography, but traditional black-box separations consider only uniform security reductions. In this paper, we initiate a formal study of the power and limits of nonuniform black-box proofs of security. We first show that a known protocol (based on the existence of one-way permutations) that uses a nonuniform proof of security, and it cannot be proven secure through a uniform security reduction. Therefore, nonuniform proofs of security are indeed provably more powerful than uniform ones. We complement this result by showing that many known black-box separations in the uniform regime actually do extend to the nonuniform regime. We prove our results by providing general techniques for extending certain types of black-box separations to handle nonuniformity.