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)
- 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
-
CC BY