If P \(\neq\) NP then some strongly noninvertible functions are invertible

DOI10.1016/j.tcs.2006.05.022zbMath1100.68038MaRDI QIDQ2508963

Hemaspaandra, Lane A., Jörg Rothe, Kari Pasanen

Publication date: 20 October 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.022

zbMATH Keywords

computational complexity; cryptography; associativity; one-way functions; strong noninvertibility

Mathematics Subject Classification ID

94A60: Cryptography

68P25: Data encryption (aspects in computer science)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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

Related Items

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

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
• Is the data encryption standard a group? (Results of cycling experiments on DES)
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• Complexity Measures for Public-Key Cryptosystems
• A survey of one-way functions in complexity theory
• P-Printable Sets
• Theoretical Computer Science