Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
From MaRDI portal
Publication:935140
DOI10.1016/j.tcs.2008.03.014zbMath1146.68036OpenAlexW2082976544MaRDI QIDQ935140
Jörg Rothe, Amitabh Saxena, Hemaspaandra, Lane A.
Publication date: 31 July 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.014
computational complexityassociativitycommutativitystrong noninvertibilityworst-case one-way functions
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An observation on associative one-way functions in complexity theory
- Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
- 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
- Inverting onto functions.
- Characterizing the existence of one-way permutations
- On characterizing the existence of partial one-way permutations
- One-way permutations and self-witnessing languages
- If P \(\neq\) NP then some strongly noninvertible functions are invertible
- One-way functions and the nonisomorphism of NP-complete sets
- Complexity Measures for Public-Key Cryptosystems
- A survey of one-way functions in complexity theory
- A note on the complexity of cryptography (Corresp.)
- Foundations of Cryptography
- P-Printable Sets
- Theoretical Computer Science
- The complexity theory companion
