Paper 2021/162

Verifiable Capacity-bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting space-based security in the adaptive setting)

Giuseppe Ateniese, George Mason University
Long Chen, Institute of Software, Chinese Academy of Sciences
Danilo Francati, Aarhus University
Dimitrios Papadopoulos, Hong Kong University of Science and Technology
Qiang Tang, University of Sydney

We initiate the study of verifiable capacity-bound function (VCBF). The main VCBF property imposes a strict lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even with unbounded computational 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)$. The minimum capacity of our VCBF construction holds against adversaries that perform a constant number of random memory accesses. This poses the natural question of whether a VCBF with high minimum capacity guarantees exists when dealing with adversaries that perform non-constant (e.g., polynomial) number of random accesses.

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2023
Kolmogorov complexityAdaptive securityPolynomial evaluationVerifiable computationVerifiable delay function
Contact author(s)
danilofrancati @ gmail com
2023-02-19: last of 6 revisions
2021-02-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Ateniese and Long Chen and Danilo Francati and Dimitrios Papadopoulos and Qiang Tang},
      title = {Verifiable Capacity-bound Functions: A New Primitive from Kolmogorov Complexity (Revisiting space-based security in the adaptive setting)},
      howpublished = {Cryptology ePrint Archive, Paper 2021/162},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.