[Cryptography] Best internet crypto clock

Jerry Leichter leichter at lrw.com
Sat Oct 4 15:50:01 EDT 2014


On Oct 3, 2014, at 10:34 PM, Henry Baker <hbaker1 at pipeline.com> wrote:
>>> In old B/W movies, when a person was kidnapped, the kidnapper sent a photo of the person together with a picture of the front page of today's newspaper to prove that he had the kidnapped person _on or after the date_ of the newspaper.
> No.  But I would like to see some simple, robust Internet crypto services, starting with a simple crypto clock with reasonable resolution that can't be hacked by anyone, not even the NSA.
> 
> To a first approximation, the Bitcoin blockchain is the only current candidate, although at a much coarser resolution, a hash of all of the Fortune 500 daily closing stock prices would also function.
> 
> If there are any other candidates -- e.g., NIST "beacons" with some less-corruptible authentication mechanism -- that have the same level of non-hackability, I'd be interested in finding out about them.
There are two issues here:  The clock, and the original problem of establishing that some event occurred no later than a given time.

The first isn't hard to solve, in the traditional way of producing trustworthy random number generators:  Simply have NIST, the NSA, the EFF, the Russian and Chinese governments - whoever is willing - implement beacons.  To produce a beacon you trust, choose any subset, combine the "random" numbers, and sign the result in the usual way.  The subset and the method of combination are all public and committed to; all the inputs are public.  Since the individual beacons can only be corrupted by entirely stopping them, or by producing predictable (to the attacker) values, unless someone corrupts *all* the sources, the combination is unpredictable.

The question of replicating the "picture of the kidnapped person" scenario, however, seems impossible.  Consider what it claims to deliver:  Anyone looking at the photo, at any time after it was made, can be sure that the person in the photo was actually alive when the photo was taken, and the photo could not have been taken earlier than the date on the newspaper.  Well, maybe that was more or less true back in the days of black-and-white photography; but there would not be the slightest difficulty in faking such a photograph today using Photoshop or similar software.  You then are reduced to the battle of the photo experts - the ones who produce better and better fakes vs. the ones doing better and better detection of fakes.

The fundamental thing you're trying to prove is that some *event* - the taking of the photograph - took place after some time T.  This isn't the kind of thing we deal with in cryptography, where the usual starting point is "some string of bits" B.  Proving that "some string of bits" could not have been produced before T seems difficult.  In fact, if you pose the problem as "combine B with some other string of bits S(T), such that the result proves that B was not known before T", the problem is clearly insoluble.

(Before you go, oh, but you can commit a hash of B to the blockchain at time T - that solves the *inverse* problem:  It proves that you knew B *no later than* T.)

If you instead go back to trying to solve the original problem, you can pose it a different way:  I want to "apply" my victim to S(T) to produce an output that (a) only the victim could have produced; (b) could only be produced with the knowledge of S(T).  For example, suppose that voice-printing were an infallible way of identifying a speaker.  Then we could use a recording of the victim reading S(T) aloud.  (Of course, "infallible" has to include the ability to detect splices and other ways of modifying or combining recordings made earlier to produce the "proof of life".)  Having him write it out with pen and paper would work about as well.

If there were a way to produce a (digital) signature based on "something you are" - assuming that this becomes unavailable after death - then the victim's signature of S(T) would serve this purpose.  Some of the work on biometrics might eventually get us there, though it seems doubtful.

I'm not even sure how to pose a general version of this problem.  There are some special cases that work and might be useful.  Extending the signature example, suppose we have a tamper-proof signing box.  Using it to sign S(T) is proof of possession of the box at some time after T.  Perhaps this could provide some kind of proof of receipt.

                                                        -- Jerry



More information about the cryptography mailing list