Delegation with updatable unambiguous proofs and PPAD-hardness
From MaRDI portal
Publication:2104236
DOI10.1007/978-3-030-56877-1_23zbMath1504.94153OpenAlexW3048764796MaRDI QIDQ2104236
Omer Paneth, Yael Tauman Kalai, Lisa Yang
Publication date: 7 December 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-56877-1_23
Related Items (6)
SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Towards reducing delegation overhead in replication-based verification: an incentive-compatible rational delegation computing scheme ⋮ Non-interactive universal arguments ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
Cites Work
- Unnamed Item
- On the complexity of the parity argument and other inefficient proofs of existence
- On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Spooky Encryption and Its Applications
- Settling the complexity of computing two-player Nash equilibria
- Magic Functions
- Algebraic methods for interactive proof systems
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- Non-interactive delegation and batch NP verification from standard computational assumptions
- Witness Maps and Applications
- Simple verifiable delay functions
- The Complexity of Computing a Nash Equilibrium
- Fiat-Shamir: from practice to theory
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- How to delegate computations publicly
- How to use indistinguishability obfuscation
- How to delegate computations
- Constant-round interactive proofs for delegating computation
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
- Recursive composition and bootstrapping for SNARKS and proof-carrying data
- Delegation for bounded space
- From Minicrypt to Obfustopia via Private-Key Functional Encryption
This page was built for publication: Delegation with updatable unambiguous proofs and PPAD-hardness
