\section{Introduction}\label{section::introduction}
\subsection{Trusted time-stamping}
The simplest approach to digital time-stamping relies on a trusted third party (TTP).
If Alice wants to time-stamp a document and prove the document's existence at the time-stamp's time to Bob at some later time, she can ask a time-stamp authority (TSA) to cryptographically sign a secure hash of her document together with the current time.
Bob accepts the TSA's signature as proof of the document's existence at the specified time. \footfullcite{Haber1991Timestamp}
This scheme requires complete trust of both Alice and Bob in the impartiality of the TSA.
Bob needs to trust the TSA to keep its private key secure and to never produce time-stamps for the past (an attack which I will refer to as "backdating").
Alice needs to trust the availability of the time-stamping service provided by the TSA whenever she wants to time-stamp a document.
This trust in a single authority can be problematic in practice.
Even if we could assume complete impartiality of the TSA with regard to Alice and Bob, what happens if the party responsible for running the TSA wants to time-stamp a document of their own?
Clearly, to ensure impartiality, another TSA would need to be used.
But now what if neither of our TSAs can be assumed to be impartial with regard to yet another party who wants to time-stamp a document?
Manually keeping track of which TSA can be trusted under which circumstances quickly becomes impractical.
The notion of distributed trust will simplify matters considerably.
\subsection{Distributed trust}
\subsubsection{Publication and witnesses}
Trusted time-stamping requires complete trust in the time-stamp authority.
This does not mean, however, that the TSA is actually \emph{trustworthy}.
We can decrease the amount of trust that we need to put in any single party by distributing trust across multiple parties.
In the context of time-stamping, we can achieve this by requiring the TSA to \emph{publish} its time-stamps to a large number of \emph{witnesses}.
The publication can be implemented in many different ways, which we will take a look at in more detail later.
For now, the reader may imagine that the TSA publishes its time-stamps in a newspaper.
The time-stamping company \emph{Surety} actually employed this method of publication in practice. (Citation needed)
Witnesses keep a record of the time-stamps issued by the TSA.
They do not accept time-stamps issued too far in the past.
Staying with the example of time-stamps published in a newspaper, the newspaper archives of public libraries can act as witnesses.
To prevent backdating attacks, a library only archives a newspaper which it receives on the printed date of publication.
When a client wants to verify the validity of a time-stamp, they can now ask a selection of witnesses for confirmation.
Using our example of newspaper archives, a client visits a handful of library archives and confirms that the time-stamp in question is actually printed in the archived newspapers of that date.
Clients only accept time-stamps for which they find a sufficient number of witnesses.
Using such a publication scheme, a malicious TSA can no longer carry out a backdating attack all by itself.
Instead, it would require the active cooperation of a sufficiently large number of witnesses in order to convince a client of the validity of a backdated time-stamp.
The client's trust is thus \emph{distributed} over the TSA, the publication process and the witnesses.
\subsubsection{Quantifying distributed trust}
Let us now introduce a mathematical model for the publication scheme outlined in the previous section.
Say the TSA publishes its time-stamps to $N$ witnesses.
It should be emphasized that a witness is required to keep a record of time-stamps.
Going back to our example of time-stamps published in a newspaper, $N$ does \emph{not} correspond to the number of copies printed.
Instead, $N$ refers to the number of places that keep archives of the newspaper.
We assume that there exist a number $E$ of malicious witnesses that collude together with the TSA in an attempt to backdate time-stamps.
Finally, a client consults a number $n$ of witnesses to verify a time-stamp.
The client only accepts the time-stamp if all $n$ selected witnesses confirm its existence at the given time.
Let $e$ be the number of maliciously colluding witnesses selected by the client.
Evidently, a successful backdating attack occurs when the client selects only colluding witnesses, so when $e=n$.
Let us now further assume that the client selects its $n$ witnesses from the total number of witnesses $N$ completely at random.
Our problem is now equivalent to the urn problem when ``drawing without replacement''.
$e$ thus follows the hypergeometric distribution. \footfullcite[pp.~117-119]{Forbes2010Statistical}
\begin{equation}
\left. P(e=k)=\binom{E}{k}\binom{N-E}{n-k} \middle/ \binom{N}{n}\right.
\end{equation}
The probability of a successful backdating attack is then given by the equation:
\begin{equation}
\left. P(e=n)=\binom{E}{n} \middle/ \binom{N}{n}\right.
\end{equation}
Figure~\ref{figure::backdating_probability_hypergeometric} graphs this probability as a function of $E$ for different values of $n$.
\begin{figure}
\includegraphics{figures/backdating_probability_hypergeometric.png}
\caption{\label{figure::backdating_probability_hypergeometric}
Probability of a successful backdating attack according to the hypergeometric distribution.
$N=30$ witnesses keep records of the time-stamps issued by the TSA.
Of these witnesses, a number $E$ (plotted on the x-axis) maliciously collude with the TSA in order to backdate time-stamps.
To check a time-stamp's validity, a client consults $n$ randomly selected witnesses.
The backdating attack is successful if all $n$ selected witnesses are malicious.
As expected, the probability of a successful backdating attack increases with an increasing number of colluding witnesses $E$, reaching 1 when $N=E$.
The client can decrease the likelihood of a successful backdating attack by consulting more witnesses, as can be observed from the different graph lines.
}
\end{figure}
In practice, the selection of witnesses may not be truly random.
Sticking to our example of newspaper archives, a client will likely prefer libraries which are geographically close to them.
A network protocol for distributed trust may also favor witnesses with small round-trip times in order to increase performance.
An attacker may be able to leverage this by placing colluding witnesses at favorable locations.
We can model this by introducing a weight parameter $\omega$, where a malicious witness is $\omega$ times more likely to be selected than an honest witness.
$e$ then follows Fisher's noncentral hypergeomtric distribution. \footfullcite{Fog2008Sampling}
\begin{align}
e_{\mathrm{min}}&=\max(0, n+E-N)\\
e_{\mathrm{max}}&=\min(n, E)\\
P(e=k)&=\left. \binom{E}{k}\binom{N-E}{n-k}\omega^k \middle/ \sum_{k'=e_{\mathrm{min}}}^{e_{\mathrm{max}}} \binom{E}{k'}\binom{N-E}{n-k'}\omega^{k'} \right.
\end{align}
With the probability of a successful backdating attack being:
\begin{equation}
P(e=n)=\left. \binom{E}{n}\omega^n \middle/ \sum_{k'=e_{\mathrm{min}}}^{e_{\mathrm{max}}} \binom{E}{k'}\binom{N-E}{n-k'}\omega^{k'} \right.
\end{equation}
Figure~\ref{figure::backdating_probability_noncentral} graphs this probability as a function of $E$ for different values of $\omega$.
\begin{figure}
\includegraphics{figures/backdating_probability_noncentral.png}
\caption{\label{figure::backdating_probability_noncentral}
Probability of a successful backdating attack according to Fisher's noncentral hypergeometric distribution.
$N=30$ witnesses keep records of the time-stamps issued by the TSA.
Of these witnesses, a number $E$ (plotted on the x-axis) maliciously collude with the TSA in order to backdate time-stamps.
To check a time-stamp's validity, a client consults $n=8$ randomly selected witnesses.
When selecting a witness, a malicious witness is $\omega$ times more likely to be selected than an honest witness.
The backdating attack is successful if all $n$ selected witnesses are malicious.
As expected, the probability of a successful backdating attack increases with an increasing number of colluding witnesses $E$, reaching 1 when $N=E$.
Increasing values of $\omega$ increase the chances of a successful backdating attack, as can be observed from the different graph lines.
For $\omega=1$, the graph matches the hypergeometric distribution of Fig.~\ref{figure::backdating_probability_hypergeometric}.
For large values of $\omega$, the graph approaches a step function with the step at $n=8$.
}
\end{figure}
Note that these equations are equivalent to the hypergeomtric distribution when $\omega=1$.
This is the optimal case, limiting the probability of a successful backdating attack as much as possible.
$\omega$ approaches infinity if the attacker can ensure that the client will only select malicious witnesses.
In this case, the probability of a successful backdating attack approaches a step function with the step at $n=E$.
\begin{equation}
\lim_{\omega\rightarrow \infty} P(e=n)=
\begin{cases}
0 & n<E\\
1 & n\geq E
\end{cases}
\end{equation}
\subsubsection{Increasing availability}
\begin{figure}
\includegraphics{figures/backdating_probability_hypergeometric_available.png}
\caption{\label{figure::backdating_probability_hypergeometric_available}
Probability of a successful backdating attack according to the hypergeometric distribution when allowing witness unavailability.
$N=30$ witnesses keep records of the time-stamps issued by the TSA.
Of these witnesses, a number $E$ (plotted on the x-axis) maliciously collude with the TSA in order to backdate time-stamps.
To check a time-stamp's validity, a client consults $n=8$ randomly selected witnesses.
It accepts the time-stamp if it receives valid responses from $n'$ witnesses.
The backdating attack is successful if at least $n'$ of the selected witnesses are malicious.
Decreasing values of $n'$ increase the chances of a successful backdating attack, as can be observed from the different graph lines.
}
\end{figure}
In a real distributed service, we can not assume that a client can always reach any witness it desires.
Network partitions or denial of service attacks may render witnesses temporarily unavailable.
We include a new parameter $n'$ into our model to accomodate this possibility.
While the client still asks $n$ randomly selected witnesses to verify a time-stamp, it accepts the time-stamp as soon as it receives $n'$ valid responses from the witnesses, with $n'<n$.
A backdating attack is now successful when $e\geq n'$.
In the case of the hypergeometric distribution, this leaves us with the following equation.
\begin{equation}
\left. P(e\geq n')=\sum_{k=n'}^n\binom{E}{k}\binom{N-E}{n-k} \middle/ \binom{N}{n}\right.
\end{equation}
Figure~\ref{figure::backdating_probability_hypergeometric_available} graphs this probability as a function of $E$ for different values of $n'$.
The probability of a successful backdating attack according to Fisher's distribution is then:
\begin{equation}
P(e\geq n')=\sum_{k=n'}^n\left. \binom{E}{k}\binom{N-E}{n-k}\omega^k \middle/ \sum_{k'=e_{\mathrm{min}}}^{e_{\mathrm{max}}} \binom{E}{k'}\binom{N-E}{n-k'}\omega^{k'} \right.
\end{equation}
Figure~\ref{figure::backdating_probability_noncentral_available} graphs this probability as a function of $E$ for different values of $n'$.
\begin{figure}
\includegraphics{figures/backdating_probability_noncentral_available.png}
\caption{\label{figure::backdating_probability_noncentral_available}
Probability of a successful backdating attack according to Fisher's noncentral hypergeometric distribution when allowing witness unavailability.
$N=30$ witnesses keep records of the time-stamps issued by the TSA.
Of these witnesses, a number $E$ (plotted on the x-axis) maliciously collude with the TSA in order to backdate time-stamps.
To check a time-stamp's validity, a client consults $n=8$ randomly selected witnesses.
It accepts the time-stamp if it receives valid responses from $n'$ witnesses.
When selecting a witness, a malicious witness is $\omega=10$ times more likely to be selected than an honest witness.
The backdating attack is successful if at least $n'$ of the selected witnesses are malicious.
Decreasing values of $n'$ increase the chances of a successful backdating attack, as can be observed from the different graph lines.
}
\end{figure}