You are looking at a specific version 20210217:100607 of this paper. See the latest version.

Paper 2021/162

Verifiable Capacity-bound Functions: A New Primitive from Kolmogorov Complexity

Giuseppe Ateniese and Long Chen and Danilo Francati and Dimitrios Papadopoulos and Qiang Tang

Abstract

We initiate the study of verifiable capacity-bound function (VCBF). The main VCBF property imposes a lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even with unbounded resources, should produce an output without spending this minimum memory capacity. Moreover, a VCBF allows for an efficient public verification process: Given a proof-of-correctness, checking the validity of the output takes significantly fewer memory resources, sublinear in the target minimum capacity. Finally, it achieves soundness, i.e., no computationally bounded adversary can produce a proof that passes verification for a false output. With these properties, we believe a VCBF can be viewed as a “space” analog of a verifiable delay function. We then propose the first VCBF construction relying on evaluating a degree-$d$ polynomial $f$ from $\mathbb{F}_p[x]$ at a random point. We leverage ideas from Kolmogorov complexity to prove that sampling $f$ from a large set (i.e., for high-enough $d$) ensures that evaluation must entail reading a number of bits proportional to the size of its coefficients. Moreover, our construction benefits from existing verifiable polynomial evaluation schemes to realize our efficient verification requirements. In practice, for a field of order $O(2^\lambda)$ our VCBF achieves $O((d + 1)\lambda)$ minimum capacity, whereas verification requires just $O(\lambda)$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Kolmogorov complexityPolynomial evaluationVerifiable computationVerifiable delay function
Contact author(s)
dfrancat @ stevens edu
History
2023-02-19: last of 6 revisions
2021-02-17: received
See all versions
Short URL
https://ia.cr/2021/162
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.