How Safe Is a Time Stamp?

When digitally signing a message, we too often fail to consider the safety of the whole system, and the possibility that somebody else could use our signatures malevolently.

But what about digital time-stamping? The digital nature of our world raises questions as to how one can prove that a document or application was created at a certain time.

To give an example, Margus Niitsoo, a fresh doctorate from the University of Tartu’s Computer Science Institute, talks about the Patent Office. The Patent Office often needs to prove that documents have been received by a certain date and time of day, so that anyone who tries to register the same idea afterwards can be shown to have applied later.

“What if the patent clerk wants to cheat, and obtains the rights to a promising idea by changing the time stamp?” asks Niitsoo.

Margus Niitsoo surrounded by professors: the supervisor Ahto Buldas and the opponent Berry Schoenmakers from the left, the opponent Helger Lipmaa and a colleague Dominique Unruh from the right.

Under the supervision of Ahto Buldas, professor of cryptography, Niitsoo’s doctoral dissertation focused on the safety of a time-stamping solution developed by the Estonian IT company GuardTime.

“I found a better way to measure the safety of time-stamping, so it can be performed faster. In a way, it’s as effective as it can be – there’s no pushing further.”

The title of the dissertation makes one think of magic: Black-box Oracle Separation Techniques with Applications for Time-stamping.

“When a bank allows digital signatures for transferring money, the actual system that makes it possible is like a black box for the bank. It is just assumed that these digital signatures are safe.  It is assumed that if someone wanted to break into bank operations, he couldn’t do it without first breaking the digital signing system,” he said. “Banks are not interested in knowing exactly how digital signing works, just in the fact that it does.”

What about an analogy with magic? “If a magician puts his hand into a black box and pulls out a rabbit, we can see the hand and the rabbit, but we don’t know what happened in the box, what caused the rabbit to be in there. A premise like that is a black-box premise.”

Similarly, Niitsoo views the hash function of GuardTime’s digital time-stamping technology as a black box.

“With the ongoing growth of computing power, all cryptographic codes are destined to be broken. It’s only a question of time and computing power. If someone can afford enough of the latter, everything can be broken.”

Niitsoo’s calculations show that if digital time-stamping technology were so widespread that a million time-stamps took place per second across the world, all performed using the technology by GuardTime, the number of mathematical operations needed for breaking a system like this could be expressed by a 2 with 20 zeroes. “Thus, one could say that regarding the present solution, the safety of a document marked with a digital time stamp is guaranteed to last for at least 34 years.”

Margus relaxing in the beloved Pirogov park after the PhD defense

Upon defense of his dissertation, Niitsoo became a new a record holder: He’s the youngest University of Tartu doctorate (at least for the last fifty years). Last autumn, Darja Lavõgina defended her thesis, aged 24 years, five months and ten days. Niitsoo surpassed her record, aged 24 years, four months and thirteen days.

Niitsoo could have already received his doctoral degree by the age of 23, but last autumn he postponed the process himself because he wanted a strong opponent present at his defense. EuroCrypt 2011, the international cryptography conference, presented the ideal opportunity.