One-way functions and circuit complexity (Q1096587): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:28, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | One-way functions and circuit complexity |
scientific article |
Statements
One-way functions and circuit complexity (English)
0 references
1987
0 references
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.
0 references
one-way functions
0 references
Turing machine complexity
0 references
one-wayness
0 references
circuit complexity
0 references
finite functions
0 references
polynomial-size circuits
0 references
satisfiability problem
0 references