## 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 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 ^{λ}) 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 language | English (US) |
---|---|

Title of host publication | Public-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings |

Editors | Alexandra Boldyreva, Vladimir Kolesnikov |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 63-93 |

Number of pages | 31 |

ISBN (Print) | 9783031313707 |

DOIs | |

State | Published - 2023 |

Externally published | Yes |

Event | 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, United States Duration: May 7 2023 → May 10 2023 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13941 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 |
---|---|

Country/Territory | United States |

City | Atlanta |

Period | 5/7/23 → 5/10/23 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Keywords

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