Boosting Batch Arguments and RAM Delegation
Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs
Abstract
We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly (m)· k1−є, where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly (m, logk), which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with succinctness poly(logT).
Topics & Concepts
SuccinctnessMathematical proofComputer scienceVerifiable secret sharingComputationDelegationTheoretical computer scienceDiscrete mathematicsAlgorithmMathematicsProgramming languageGeometrySet (abstract data type)LawPolitical scienceCryptography and Data SecurityDistributed systems and fault tolerancePrivacy-Preserving Technologies in Data