One-way functions and circuit complexity
type: Item
instance of: scholarly article
title: One-way functions and circuit complexity
zbMATH Open document ID: 0633.94015
DOI: 10.1016/0890-5401(87)90022-8
author: Ravi B. Boppana
author: Jeffrey C. Lagarias
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4031573
zbMATH Keywords: one-way functions
zbMATH Keywords: Turing machine complexity
zbMATH Keywords: one-wayness
zbMATH Keywords: circuit complexity
zbMATH Keywords: finite functions
zbMATH Keywords: polynomial-size circuits
zbMATH Keywords: satisfiability problem
reviewed by: Tao Renji
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90022-8
OpenAlex ID: W2060260518
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Relativized cryptography
cites work: Constant Depth Reducibility
cites work: Q4138187
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: One-way permutations in NC 0
cites work: Q3957950
cites work: One way functions and pseudorandom generators
cites work: On gamma-reducibility versus polynomial time many-one reducibility
cites work: Q3726006
cites work: Q4172915
cites work: Relative complexity of checking and evaluating
description: scientific article; zbMATH DE number 4031573