A proof of time or knowledge

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