Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
From MaRDI portal
Publication:596322
DOI10.1016/j.jcss.2003.10.004zbMath1069.68052OpenAlexW2036373002MaRDI QIDQ596322
Publication date: 10 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.10.004
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
ON THE CIRCUIT-SIZE OF INVERSES ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ If P \(\neq\) NP then some strongly noninvertible functions are invertible
Cites Work
- Unnamed Item
- An observation on associative one-way functions in complexity theory
- On some natural complete operators
- On hardness of one-way functions
- Relative complexity of checking and evaluating
- Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
- Complexity Measures for Public-Key Cryptosystems
- The Complexity of Enumeration and Reliability Problems
- A survey of one-way functions in complexity theory
- P-Printable Sets
This page was built for publication: Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
