Rational arguments: single round delegation with sublinear verification

DOI10.1145/2554797.2554845MaRDI QIDQ2988906zbMATH OpenOpenAlexFDO

Authors Siyao Guo, Pavel Hubáček, Alon Rosen, Margarita Vald

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2554797.2554845

zbMATH Keywords

threshold circuitsdelegation of computationsuccinct argumentsrational cryptography

Mathematics Subject Classification ID

Cryptography (94A60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Recommendations

• Rational sumchecks
• Efficient rational proofs with strong utility-gap guarantees
• Rational proofs with multiple provers
• Efficient rational proofs for space bounded computations
• Delegating computation: interactive proofs for muggles

Cites work

• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Fully homomorphic encryption using ideal lattices
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(13)

• Structural complexity of rational interactive proofs
• scientific article; zbMATH DE number 7525466 (Why is no real title available?)
• Rational sumchecks
• Outsourcing computation: the minimal refereed mechanism
• Rational proofs with multiple provers
• Verifiable crowd computing: coping with bounded rationality
• Perfectly secure message transmission against independent rational adversaries
• Fair and rational delegation computation protocol
• Automata, Languages and Programming
• Verifiable crowd computing: coping with bounded rationality
• Efficient Probabilistically Checkable Debates
• Sumcheck-based delegation of quantum computing to rational server
• Rational delegation computing protocol based on rational trust model

This page was built for publication: Rational arguments: single round delegation with sublinear verification

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