Can PPAD hardness be based on standard cryptographic assumptions?

DOI10.1007/s00145-020-09369-6zbMath1460.94064OpenAlexW2769677883WikidataQ114692955 ScholiaQ114692955MaRDI QIDQ5925502

Alon Rosen, Gil Segev, Ido Shahaf

Publication date: 7 April 2021

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-020-09369-6

zbMATH Keywords

average-case complexitytotal search problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Related Items

On the Complexity of Equilibrium Computation in First-Price Auctions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for finding Brouwer fixed points
• On the complexity of the parity argument and other inefficient proofs of existence
• A tight relationship between generic oracles and type-2 complexity theory
• Perfect Structure on the Edge of Chaos
• On Constructing One-Way Permutations from Indistinguishability Obfuscation
• Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
• Cryptanalysis of the New CLT Multilinear Map over the Integers
• Cryptanalysis of GGH Map
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
• Cryptanalysis of the Multilinear Map over the Integers
• An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero
• On Security Preserving Reductions – Revised Terminology
• Limits on the Power of Indistinguishability Obfuscation and Functional Encryption
• Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
• Settling the complexity of computing two-player Nash equilibria
• Zeroizing Without Low-Level Zeroes: New MMAP Attacks and their Limitations
• Foundations of Cryptography
• The Journey from NP to TFNP Hardness
• The Complexity of Computing a Nash Equilibrium
• Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
• How to use indistinguishability obfuscation
• On the (im)possibility of obfuscating programs
• Theory of Cryptography