One-way functions and circuit complexity

A finite function f is a mapping of {0, 1} n into {0, 1} m ⌣{#}, where “#” is a symbol to be thought of as “undefined. ” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f i (x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f i (x) = y. A family of functions f i (x) can be evaluated if some family of polynomial-size circuits with input x can compute f i (x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP ⋔ co-UP are equal. A family of functions f i is one-way for constant depth circuits if f i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f i −1 cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.

Authors

• R.B. Boppana
• J.C. Lagarias

Keywords

No keywords are indexed for this paper.