Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

DOI10.1007/978-3-662-53008-5_20MaRDI QIDQ2829231zbMATH OpenOpenAlexFDO

Authors Sanjam Garg, Omkant Pandey, 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

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

Recommendations

• The complexity of finding Nash equilibria
• The complexity of computing a Nash equilibrium
• The complexity of computing a Nash equilibrium
• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• scientific article; zbMATH DE number 549855
• On the complexity of Nash equilibria in anonymous games
• New complexity results about Nash equilibria

Cites work

• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• Advances in Cryptology - CRYPTO 2003
• Breaking the sub-exponential barrier in obfustopia
• Can PPAD hardness be based on standard cryptographic assumptions?
• Candidate Multilinear Maps from Ideal Lattices
• Candidate indistinguishability obfuscation and functional encryption for all circuits
• Constrained pseudorandom functions and their applications
• From selective to adaptive security in functional encryption
• Functional encryption without obfuscation
• Functional encryption: definitions and challenges
• Functional signatures and pseudorandom functions
• How to obfuscate programs directly
• How to use indistinguishability obfuscation
• Indistinguishability obfuscation from compact functional encryption
• Indistinguishability obfuscation from semantically-secure multilinear encodings
• Indistinguishability obfuscation: from approximate to exact
• Non-cooperative games
• Obfuscating circuits via composite-order graded encoding
• On the (im)possibility of obfuscating programs
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Protecting obfuscation against algebraic attacks
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• The impossibility of obfuscation with auxiliary input or a universal simulator
• Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding

Cited in

(39)

• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Delegation with updatable unambiguous proofs and PPAD-hardness
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Non-interactive universal arguments
• 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
• Single-key to multi-key functional encryption with polynomial loss
• Breaking the sub-exponential barrier in obfustopia
• From Minicrypt to Obfustopia via private-key functional encryption
• From cryptomania to obfustopia through secret-key functional encryption
• From minicrypt to obfustopia via private-key functional encryption
• 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
• The journey from NP to TFNP hardness
• Continuous verifiable delay functions
• Unique end of potential line
• Collusion-resistant functional encryption for RAMs
• Streaming functional encryption
• Pseudorandom functions: three decades later
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• PPAD is as hard as LWE and iterated squaring
• Combiners for functional encryption, unconditionally
• From FE combiners to secure MPC and back
• From cryptomania to obfustopia through secret-key functional encryption
• Amplifying the security of functional encryption, unconditionally
• Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
• TFNP: an update
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Constrained pseudorandom functions from functional encryption
• Efficiently obfuscating re-encryption program under DDH assumption
• Broadcast, trace and revoke with optimal parameters from polynomial hardness
• Robust transforming combiners from indistinguishability obfuscation to functional encryption

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)