Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
From MaRDI portal
Publication:2829231
DOI10.1007/978-3-662-53008-5_20zbMATH Open1391.94752OpenAlexW2466495210MaRDI QIDQ2829231FDOQ2829231
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
Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Game theory (91A99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Non-cooperative games
- Functional Encryption: Definitions and Challenges
- On the complexity of the parity argument and other inefficient proofs of existence
- Advances in Cryptology - CRYPTO 2003
- Settling the complexity of computing two-player Nash equilibria
- On total functions, existence theorems and computational complexity
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- How to use indistinguishability obfuscation
- Candidate Multilinear Maps from Ideal Lattices
- On the (im)possibility of obfuscating programs
- Obfuscating Circuits via Composite-Order Graded Encoding
- Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
- Functional Encryption Without Obfuscation
- Indistinguishability Obfuscation from Compact Functional Encryption
- Constrained Pseudorandom Functions and Their Applications
- How to Obfuscate Programs Directly
- Indistinguishability Obfuscation: From Approximate to Exact
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
- From Selective to Adaptive Security in Functional Encryption
- Breaking the Sub-Exponential Barrier in Obfustopia
- Functional Signatures and Pseudorandom Functions
- Protecting Obfuscation against Algebraic Attacks
- The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
- Can PPAD hardness be based on standard cryptographic assumptions?
Cited In (39)
- On the Complexity of Equilibrium Computation in First-Price Auctions
- Delegation with updatable unambiguous proofs and PPAD-hardness
- Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
- From Minicrypt to Obfustopia via Private-Key Functional Encryption
- Non-interactive universal arguments
- Pseudorandom Functions: Three Decades Later
- The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
- FE and iO for Turing machines from minimal assumptions
- Succinct garbling schemes from functional encryption through a local simulation paradigm
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- From cryptomania to obfustopia through secret-key functional encryption
- From minicrypt to obfustopia via private-key functional encryption
- TFNP: An Update
- Can PPAD hardness be based on standard cryptographic assumptions?
- Unique End of Potential Line
- Constrained (Verifiable) Pseudorandom Function from Functional Encryption
- Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness
- Continuous verifiable delay functions
- Collusion-resistant functional encryption for RAMs
- Unique end of potential line
- Streaming functional encryption
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
- PPAD is as hard as LWE and iterated squaring
- Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
- Single-Key to Multi-Key Functional Encryption with Polynomial Loss
- Combiners for functional encryption, unconditionally
- From FE combiners to secure MPC and back
- Efficiently Obfuscating Re-Encryption Program Under DDH Assumption
- Amplifying the security of functional encryption, unconditionally
- Robust Transforming Combiners from Indistinguishability Obfuscation to Functional Encryption
- Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- Constrained pseudorandom functions from functional encryption
- Broadcast, trace and revoke with optimal parameters from polynomial hardness
- From Cryptomania to Obfustopia Through Secret-Key Functional Encryption
- Breaking the Sub-Exponential Barrier in Obfustopia
- The Journey from NP to TFNP Hardness
Recommendations
- Title not available (Why is that?) 👍 👎
- The Complexity of Computing a Nash Equilibrium 👍 👎
- The complexity of computing a Nash equilibrium 👍 👎
- On the Complexity of Approximating a Nash Equilibrium 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- On the Complexity of Nash Equilibria in Anonymous Games 👍 👎
- On the communication complexity of approximate Nash equilibria 👍 👎
- On the communication complexity of approximate Nash equilibria 👍 👎
- New complexity results about Nash equilibria 👍 👎
This page was built for publication: Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829231)
