Delegation with updatable unambiguous proofs and PPAD-hardness

DOI10.1007/978-3-030-56877-1_23MaRDI QIDQ2104236zbMATH OpenOpenAlexFDO

Authors Yael Tauman Kalai, Omer Paneth, Lisa Yang

Publication date 7 December 2022

Full work available at URL https://doi.org/10.1007/978-3-030-56877-1_23

zbMATH Keywords

delegationPPAD-hardnessunambiguous proofszero-testable encryption

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• PPAD is as hard as LWE and iterated squaring
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• How to delegate computations publicly
• How to delegate computations
• The complexity of computing a Nash equilibrium

Cites work

• scientific article; zbMATH DE number 7650354 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Constant-round interactive proofs for delegating computation
• Delegation for bounded space
• Fiat-Shamir: from practice to theory
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• From Minicrypt to Obfustopia via private-key functional encryption
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• How to delegate computations
• How to delegate computations publicly
• How to use indistinguishability obfuscation
• Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
• Magic functions
• Non-interactive delegation and batch NP verification from standard computational assumptions
• On the complexity of the parity argument and other inefficient proofs of existence
• On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
• Recursive composition and bootstrapping for SNARKs and proof-carrying data
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• Simple verifiable delay functions
• Spooky Encryption and Its Applications
• The complexity of computing a Nash equilibrium
• Witness maps and applications

Cited in

(7)

• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Non-interactive universal arguments
• Towards reducing delegation overhead in replication-based verification: an incentive-compatible rational delegation computing scheme
• Monotone-policy aggregate signatures
• Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• PPAD is as hard as LWE and iterated squaring

This page was built for publication: Delegation with updatable unambiguous proofs and PPAD-hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104236)