An infinitely-often one-way function based on an average-case assumption

DOI10.1090/S1061-0022-10-01103-9MaRDI QIDQ3586759zbMATH OpenFDO

Authors Edward A. Hirsch, Dmitry Itsykson

Publication date 1 September 2010

Published in St. Petersburg Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/S1061-0022-10-01103-9

zbMATH Keywords

average-case complexityone-way function

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• An Infinitely-Often One-Way Function Based on an Average-Case Assumption
• On basing one-way functions on NP-hardness
• On building fine-grained one-way functions from strong average-case hardness
• Absolute results concerning one-way functions and their applications
• scientific article; zbMATH DE number 4125016

Cites work

• Average Case Complete Problems
• Average-Case Complexity
• Foundations of Cryptography
• On the theory of average case complexity
• The tale of one-way functions

Cited in

(4)

• On building fine-grained one-way functions from strong average-case hardness
• An Infinitely-Often One-Way Function Based on an Average-Case Assumption
• Coin flipping of any constant bias implies one-way functions
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

This page was built for publication: An infinitely-often one-way function based on an average-case assumption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586759)