Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions

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

zbMATH Keywords

computational complexityassociativitycommutativitystrong noninvertibilityworst-case one-way functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

ON THE CIRCUIT-SIZE OF INVERSES

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