Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A proof of time or knowledge

Benjamin Wesolowski 1, 2
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : This note was written in 2016. Rejected from PKC 2017, some of the ideas herein later developed into the Eurocrypt 2019 article Efficient verifiable delay functions. Other ideas, such as the construction of fading signatures, and a discussion on their (in)feasibility, never appeared in public work. In light of the recent development of time-sensitive cryptography, some of this content may have become of interest. The reader may notice that the notion of proof of time or knowledge essentially coincides with what is now known as a (trapdoor) verifiable delay function. This paper introduces proofs of time or knowledge, a new primitive in the field of time-sensitive cryptography pioneered by Rivest, Shamir and Wagner in 1996. A party, Alice, has a pair of secret and public keys. Given a piece of data m, a proof of time or knowledge allows to generate a proof p such that anyone can easily verify that either p has been generated by Alice (i.e., she used her secret key), or the party who computed p spent a prescribed amount ∆ of wall-clock time to compute p from m. Suppose that a party, Bob, knows that the message m was not known by Alice before a point in time t0. Then, Bob can infer that Alice computed the proof p if, and only if, the point in time t0 + ∆ has not been reached yet (in this case, (m, p) has the same value as a signature of Alice on m). After point in time t0 + ∆ (or if no bound t0 is known), the pair (m, p) is an indistinguishable proof of time or knowledge, since anyone could have produced it.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Benjamin Wesolowski Connect in order to contact the contributor
Submitted on : Friday, October 15, 2021 - 3:41:04 PM
Last modification on : Saturday, December 4, 2021 - 3:44:03 AM


Files produced by the author(s)


  • HAL Id : hal-03380471, version 1



Benjamin Wesolowski. A proof of time or knowledge. 2021. ⟨hal-03380471⟩



Record views


Files downloads