Nowadays, attackers have large amount of resources (e.g., computational and space capabilities) that are used for malicious purposes, e.g., stealing sensitive information (such as passwords). To face these capacious adversaries, “resource-demanding” functions have been developed: Functions that deliberately consume (on evaluation) large quantities of resources (e.g., time, space, energy). In this talk, I will introduce a new notion of resource-demanding function named verifiable capacity-bound function (VCBF). The main VCBF property is that it 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, a VCBF can be viewed as a “space” analog of a verifiable delay function, introduced by Boneh et al. (CRYPTO18). I will then present the first VCBF construction relying on evaluating a degree-d polynomial f from $\mathbb{F}_p[x]$ at a random point. To prove the space complexity of the construction I will describe an analysis at the intersection of Kolmogorov complexity and cryptography.