Characterizing the existence of one-way permutations

DOI10.1016/S0304-3975(00)00014-1zbMath0945.68053MaRDI QIDQ1575721

Jörg Rothe, Hemaspaandra, Lane A.

Publication date: 21 August 2000

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

zbMATH Keywords

computational complexityrankingone-way functionsone-way permutationsworst-case cryptography

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data encryption (aspects in computer science) (68P25)

Related Items (5)

One-way permutations and self-witnessing languages ⋮ ON THE CIRCUIT-SIZE OF INVERSES ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ Characterizing the existence of one-way permutations ⋮ On characterizing the existence of partial one-way permutations

Cites Work

• Unnamed Item
• On the complexity of ranking
• Polynomial-time compression
• Relative complexity of checking and evaluating
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• Easy sets and hard certificate schemes
• Characterizing the existence of one-way permutations
• Complexity Measures for Public-Key Cryptosystems
• Compression and Ranking
• A survey of one-way functions in complexity theory
• A Pseudorandom Generator from any One-way Function

This page was built for publication: Characterizing the existence of one-way permutations