关键词:
Computer science
Mathematics
Cryptography
Construction
Random variables
Bandwidths
Concrete
Dissertations & theses
Polynomials
Codes
Algorithms
Heuristic
Energy consumption
Reading
摘要:
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, etc.). In this light, a recent work of Boneh et al. (CRYPTO18) introduces the notion of verifiable delay function, a time-demanding function that requires a minimum number of steps (time complexity) in order to be evaluated. The main property, that puts verifiable delay functions apart from the state of the art resource-demanding functions, is the possibility of checking the correctness of the computation efficiently, i.e., the time complexity of the verification process is significantly smaller than the time complexity required in order to evaluate the function. In this dissertation, we investigate further the area of verifiable resource-demanding functions by proposing the notion of 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, 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. To prove the space