Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity: (Revisiting Space-Based Security in the Adaptive Setting)

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 Fp[ 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 λ) our VCBF achieves O((d+ 1 ) λ) minimum capacity, whereas verification requires just O(λ). The minimum capacity of our VCBF construction holds against adversaries that perform a constant number of random memory accesses during evaluation. 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.

Original languageEnglish (US)
Title of host publicationPublic-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsAlexandra Boldyreva, Vladimir Kolesnikov
PublisherSpringer Science and Business Media Deutschland GmbH
Pages63-93
Number of pages31
ISBN (Print)9783031313707
DOIs
StatePublished - 2023
Externally publishedYes
Event26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, United States
Duration: May 7 2023May 10 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13941 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023
Country/TerritoryUnited States
CityAtlanta
Period5/7/235/10/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Adaptive security
  • Kolmogorov complexity
  • Polynomial evaluation
  • Verifiable computation
  • Verifiable delay function

Fingerprint

Dive into the research topics of 'Verifiable Capacity-Bound Functions: A New Primitive from Kolmogorov Complexity: (Revisiting Space-Based Security in the Adaptive Setting)'. Together they form a unique fingerprint.

Cite this