If P NP then some strongly noninvertible functions are invertible

DOI10.1016/J.TCS.2006.05.022MaRDI QIDQ2508963zbMATH OpenOpenAlexFDO

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

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

associativitycomputational complexitycryptographyone-way functionsstrong noninvertibility

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 1839441
• On the circuit-size of inverses
• Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
• On basing one-way functions on NP-hardness
• Theoretical Computer Science

Cites work

• A survey of one-way functions in complexity theory
• An observation on associative one-way functions in complexity theory
• Complexity Measures for Public-Key Cryptosystems
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• Is the data encryption standard a group? (Results of cycling experiments on DES)
• On some natural complete operators
• P-Printable Sets
• Theoretical Computer Science
• Tight lower bounds on the ambiguity of strong, total, associative, one-way functions

Cited in

(5)

• Quantum one-way permutation over the finite field of two elements
• All superlinear inverse schemes are coNP-hard
• On the circuit-size of inverses
• scientific article; zbMATH DE number 1839441 (Why is no real title available?)
• Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions

This page was built for publication: If P \(\neq\) NP then some strongly noninvertible functions are invertible

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