Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

DOI10.1007/978-3-662-53008-5_20zbMath1391.94752OpenAlexW2466495210MaRDI QIDQ2829231

Omkant Pandey, Sanjam Garg, Akshayaram Srinivasan

Publication date: 27 October 2016

Published in: Advances in Cryptology – CRYPTO 2016 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53008-5_20

Mathematics Subject Classification ID

Game theory (91A99) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (36)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ TFNP: An Update ⋮ The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO ⋮ Succinct garbling schemes from functional encryption through a local simulation paradigm ⋮ FE and iO for Turing machines from minimal assumptions ⋮ The Journey from NP to TFNP Hardness ⋮ From Cryptomania to Obfustopia Through Secret-Key Functional Encryption ⋮ Single-Key to Multi-Key Functional Encryption with Polynomial Loss ⋮ From cryptomania to obfustopia through secret-key functional encryption ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ From FE combiners to secure MPC and back ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Broadcast, trace and revoke with optimal parameters from polynomial hardness ⋮ Unique end of potential line ⋮ Collusion-resistant functional encryption for RAMs ⋮ Non-interactive universal arguments ⋮ Constrained (Verifiable) Pseudorandom Function from Functional Encryption ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Streaming functional encryption ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Robust Transforming Combiners from Indistinguishability Obfuscation to Functional Encryption ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ Constrained pseudorandom functions from functional encryption ⋮ Combiners for functional encryption, unconditionally ⋮ Continuous verifiable delay functions ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Unique End of Potential Line ⋮ Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium ⋮ Amplifying the security of functional encryption, unconditionally ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness ⋮ Pseudorandom Functions: Three Decades Later ⋮ Breaking the Sub-Exponential Barrier in Obfustopia

Cites Work

• Unnamed Item
• On total functions, existence theorems and computational complexity
• On the complexity of the parity argument and other inefficient proofs of existence
• Non-cooperative games
• Indistinguishability Obfuscation: From Approximate to Exact
• Functional Encryption Without Obfuscation
• Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Constrained Pseudorandom Functions and Their Applications
• Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
• The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
• How to Obfuscate Programs Directly
• Functional Encryption: Definitions and Challenges
• Settling the complexity of computing two-player Nash equilibria
• From Selective to Adaptive Security in Functional Encryption
• Indistinguishability Obfuscation from Compact Functional Encryption
• Candidate Multilinear Maps from Ideal Lattices
• How to use indistinguishability obfuscation
• Obfuscating Circuits via Composite-Order Graded Encoding
• Breaking the Sub-Exponential Barrier in Obfustopia
• On the (im)possibility of obfuscating programs
• Functional Signatures and Pseudorandom Functions
• Protecting Obfuscation against Algebraic Attacks
• Advances in Cryptology - CRYPTO 2003
• Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
• Can PPAD hardness be based on standard cryptographic assumptions?

This page was built for publication: Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium