Paper 2023/1012
Arithmetic Sketching
Abstract
This paper introduces arithmetic sketching, an abstraction of a primitive that several previous works use to achieve lightweight, lowcommunication zeroknowledge verification of secretshared vectors. An arithmetic sketching scheme for a language $\mathcal{L} \in \mathbb{F}^n$ consists of (1) a randomized linear function compressing a long input x to a short “sketch,” and (2) a small arithmetic circuit that accepts the sketch if and only if $x \in \mathcal{L}$, up to some small error. If the language $\mathcal{L}$ has an arithmetic sketching scheme with short sketches, then it is possible to test membership in $\mathcal{L}$ using an arithmetic circuit with few multiplication gates. Since multiplications are the dominant cost in protocols for computation on secretshared, encrypted, and committed data, arithmetic sketching schemes give rise to lightweight protocols in each of these settings. Beyond the formalization of arithmetic sketching, our contributions are: – A general framework for constructing arithmetic sketching schemes from algebraic varieties. This framework unifies schemes from prior work and gives rise to schemes for useful new languages and with improved soundness error. – The first arithmetic sketching schemes for languages of sparse vectors: vectors with bounded Hamming weight, bounded $L_1$ norm, and vectors whose few nonzero values satisfy a given predicate. – A method for “compiling” any arithmetic sketching scheme for a language $\mathcal{L}$ into a lowcommunication malicioussecure multiserver protocol for securely testing that a clientprovided secretshared vector is in $\mathcal{L}$. We also prove the first nontrivial lower bounds showing limits on the sketch size for certain languages (e.g., vectors of Hammingweight one) and proving the nonexistence of arithmetic sketching schemes for others (e.g., the language of all vectors that contain a specific value).
Note: This version includes additional related work and a few minor edits.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2023
 Keywords
 secret sharingmultiparty computationsketching
 Contact author(s)

dabo @ cs stanford edu
eboyle @ alum mit edu
henrycg @ csail mit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il  History
 20230724: revised
 20230629: received
 See all versions
 Short URL
 https://ia.cr/2023/1012
 License

CC BYNCSA
BibTeX
@misc{cryptoeprint:2023/1012, author = {Dan Boneh and Elette Boyle and Henry CorriganGibbs and Niv Gilboa and Yuval Ishai}, title = {Arithmetic Sketching}, howpublished = {Cryptology ePrint Archive, Paper 2023/1012}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1012}}, url = {https://eprint.iacr.org/2023/1012} }