**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)$.

**Category / Keywords: **foundations / Kolmogorov complexity, Polynomial evaluation, Verifiable computation, Verifiable delay function

**Date: **received 14 Feb 2021

**Contact author: **dfrancat at stevens edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210217:100607 (All versions of this report)

**Short URL: **ia.cr/2021/162

[ Cryptology ePrint archive ]