One-way functions and circuit complexity

DOI10.1016/0890-5401(87)90022-8zbMath0633.94015OpenAlexW2060260518MaRDI QIDQ1096587

Ravi B. Boppana, Jeffrey C. Lagarias

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90022-8

zbMATH Keywords

satisfiability problemTuring machine complexitycircuit complexityone-way functionspolynomial-size circuitsfinite functionsone-wayness

Mathematics Subject Classification ID

Related Items (6)

Normal numbers and sources for BPP ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ One-way permutations, computational asymmetry and distortion. ⋮ A lower bound for primality ⋮ Fine-grained cryptography revisited ⋮ Cryptography with constant input locality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• One way functions and pseudorandom generators
• One-way permutations in NC 0
• On gamma-reducibility versus polynomial time many-one reducibility
• Relative complexity of checking and evaluating
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Relativized cryptography

This page was built for publication: One-way functions and circuit complexity