One-way functions and circuit complexity (Q1096587)

Several distinct definitions of one-way functions have been proposed based on Turing machine complexity. This paper defines one-wayness based on circuit complexity: A family of finite functions is one-way iff it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. It is shown that 1. There exists a one-way family of functions iff the satisfiability problem SAT does not have polynomial-size circuits; 2. There exists a one-way family of one-to-one functions iff \(PSIZE\neq UPSIZE;\) 3. There exists a one-way family of one- to-one and onto functions iff \(PSIZE\neq UPSIZE\cap co-UPSIZE.\) This paper then deals with similar questions concerning the relative complexity of checking versus evaluating and gives three complexity results for the checking versus evaluating problem parallel to the above results. Finally, this paper gives two examples of provably one-way permutations for constant depth circuits.