Digital timestamping is a cryptographic technique allowing a xing a reliable date to a digital document. The security of most existing timestamping systems is based on the security of the used cryptographic techniques as hash functions. However, a hash function has a limited lifetime. In this context, we provide a non-interactive timestamping scheme in the bounded storage model (BSM) whose security is not related to the life of any cryptographic technique. We prove, in fact, that our timestamping scheme is eternally secure even against an adversary with unlimited computing power.
In the last years, digital documents are beginning to replace paper documents in several areas. For this reason, it is important to locate a digital document in time to prove its existence and integrity since a given date. This task is achieved through a timestamping system that operates in two phases: a timestamping phase allowing one or more Timestamping Authority (TSA) to a x a reliable date to a document and generate the associated timestamp and a veri cation phase allowing any potential veri er to verify the correctness of the produced timestamp.
The security of most existing timestamping systems [
Generally, in cryptography, the proposed systems and the used functions are
secure under the assumption that there is a limit of the computational power of
any user or adversary. In the bounded storage model, the proposed systems must
be secure even against an adversary with an unlimited computational power. The
BSM was proposed by Maurer in 1992 [
In the BSM, we assume that a long random string R of r bits is transmitted during the round t (between t and t + 1). If s is the maximum storage capacity of any entity in t, then s r. Notice the space of R is f0; 1gr where r is the size of the string R. Similarly, we consider that a document D of size d has a value in f0; 1gd. In the timestamping scheme proposed by Moran, to timestamp a document D, its content is used to select a few blocks from R whose values will be inserted in the timestamp T . Any veri er must save randomly some blocks of R (using a function named Sketch(R)) in order to verify, later, the validity of any timestamp made during the round t. Verifying the validity of a timestamp associated to a document D is performed at a later date by a veri er who has simply to verify that there are no con icts between his sketch and the timestamp of D. However, in this solution, a timestamp includes some additional values of R. If the veri er cannot store during the round t more than s bits of R, he may at the veri cation time store s0 with s0 > s. Each veri cation of a timestamp generated in the round t can lead him to discover new blocks of R. After a number of veri cation processes, he can reconstruct partially, if not entirely R and backdate any document.
To remedy this problem, we propose a timestamping protocol allowing
verifying the timestamp of a document D without learning additional values of R.
To this aim, instead of inserting the blocks of R in the timestamp, these blocks
will be the secret of the stamper. The veri er must then prove that he has the
value of a given block in his sketch and the stamper has to prove that he has used
this value to create the timestamp. In the veri cation process of this scheme,
a veri er may accept or reject a timestamp without discovering any additional
information about the string R transmitted during the round t. The idea is to
timestamp the document D locally using the secret sharing scheme of Shamir
[
In this section, we introduce some notations that we will use later in this paper.
- Randomizer: We call "randomizer" and we denote R the random string transmitted during a round t. This string is divided into n blocks of size b bits indexed from 1 to n and denoted R1, . . . , Rn. Knowing that the length of R is r bits and the size of a block is b bits, r = n.b. For each subset S I(R) where I(R) is the set of indexes of blocks Ri (1 i n), we denote RjS the set of blocks of R 8 i 2 S.
- Hamming Distance: A vector being a set of blocks, we de ne the Hamming Distance between two vectors c1 and c2 denoted DH as the number of blocks for which the two vectors di er.
- Threshold secret sharing: The threshold secret sharing is a technique for dividing a secret S into l shares such that the coalition of at least shares is necessary to reconstruct the secret while the coalition of at most 1 shares do not reveal even partially the secret ( < l). A -out of-l threshold secret sharing scheme is denoted SSS( ; l).
- Shamir secret sharing scheme: The secret sharing scheme based on Shamir's polynomial interpolation scheme is a SSS( ; l). We denote it SSSS ( ; l). The principle is to x a polynomial P of degree 1 and X a set of values (X = X1; : : : ; Xl). The secret sharing function denoted Share takes as input the secret S and generates the set of shares Share(S) = (S1; : : : ; Sl) such that 8i; 1 i l, Si = P (Xi). The Reconstruction function denoted Share 1 take as input a subset of X denoted XS = [XS1 ; : : : ; XS ] such that jXS j = and the associated shares: Share 1(XS ; SXS1 ; : : : ; SXS ) = P , with P a polynomial such that 8 Xi 2 XS and Si 2 [SXS1 ; : : : ; SXS ], P (Xi) = Si. The secret S is computed as follows: S = P (0). 5 5.1
A stamper is represented by the two following functions:
- Store(D; R) that uses Shamir's secret sharing process to compute Share(D) for a given document D. Then, It computes the vector RjShare(D) and stores it. More formally, Store(D; R) consists in computing Share(D) = (D1, . . . ,Dl), where Di is the ithindexspecif iedbyD:T othevector(RD1 ; : : : ; RDl ) is associated the vector Share(D) where RDi is the block of R indexed by Di. We denote this vector RjShare(D), where the notation R I means the values of blocks j of R indexed by I1, . . . , In, with I = I1, . . . , In.
De nition 1. Store(D; R) = RjShare(D).
- Stamp(D; Store(D; R)) uses Shamir's reconstruction process to nd the unique polynomial passing through the points Pi(x; y) where x is a block of the vector RjShare(D) and y the associated blocks in Share(D). This polynomial is the timestamp T .
De nition 2. T = Share 1(RjShare(D); Share(D)). 5.2
A veri er is represented by the two following functions:
- Sketch(R) allows choosing, randomly, a set of indexes denoted H with H I(R), computing RjH and storing this vector.
De nition 3. Sketch(R) = (H; RjH ).
- V erif y(Sketch(R); D; T ) allows verifying that there are no con icts between Sketch(R) and T .
De nition 4. V erif y(Sketch(R); D; T ) allows verifying the following equality : T (RjH\Share(D)) = H \ Share(D)
In other words: De nition 5. V erif y(Sketch(R), D; T ) allows verifying that DH(T (RjH \ Share(D)), H \ Share(D)) = 0 for a timestamp T . If this equality is veried, the timestamp T is accepted by the veri er and is said "valid". 5.3
An adversary consists in the two following functions:
- Store (R) which saves a subset of R called C. The di erence between Sketch(R) and Store (R) is that Sketch(R) is computed "online" while Store (R) function may not be.
- Stamp (D; C) that given a document D and a string C tries to produce a timestamp T of D.
De nition 6. Stamp (D; C) = R jShare(D).
De nition 7. T
= Share 1(R jShare(D); Share(D)).
Where R jShare(D) is the vector of blocks associated to Share(D) according to T . If an adversary A produces for a document D and a randomizer R, a timestamp T that is equal to the timestamp T produced by Stamp(D; Store(D; R)), we say that he backdates "correctly" the document. More formally: De nition 8. An adversary backdates a document D with a success probability for a given randomizer R if : P r[V erif y(Sketch(R); D, Stamp (D; Store (R)))] De nition 9. An adversary backdates correctly a document D for a given randomizer R if DH(V1; V2) = 0 with V1 = R jShare(D) and V2 = RjShare(D). and V2 = RjShare(D).
De nition 10. An adversary backdates correctly a document D for a given randomizer R with at most err errors, if DH(V1; V2) err, with V1 = R jShare(D) 6
Given the following parameters: - s : the storage capacity of the most powerful adversary. - r : the size of the random string R transmitted during a round t. - b: the size of a block of the random string R transmitted during a round t.
- l: the number of indexes speci ed by a given document.
- n: the number of blocks of the random string R transmitted during a round t.
We assume that:
(1) r s : The size of the random string R transmitted during a round t is greater than the storage capacity of the most powerful user of the system.
(2) 1 <n=jHj l: The rst inequality means that the number of the blocks of R transmitted during a round t is greater than the number of blocks in a sketch saved by a potential user. The second inequality means that there exists an integer u > 1 such that n = u. jHj with u much smaller than the number of indexes speci ed by a document.
(3) 2b r=b: The number of possible values for a block of size b bits is greater than the number of blocks of the string R transmitted during a round t.
(4) r=b > l: The number of blocks of the string R transmitted during a round t is greater than the number of shares used in the adopted Shamir's secret sharing scheme.
(5) b 1: The size of a block of R is much greater than 1 bit.
In our security study we demonstrate mainly two important characteristics of our non-interactive timestamping scheme. First, we prove that backdating documents in our timestamping scheme has a negligible probability. Second, we prove that the timestamps provided by our timestamping scheme have an eternal validity. 6.1
In our timestamping scheme, the probability that an adversary backdates a document D for a string R already transmitted using his stored blocks of R is negligible. This proof is established in two steps. In the rst step, we show that if an adversary A wants to backdate successfully a document D for a random string R, then he must backdate it "correctly" for this string R with an error err negligible. In the second step, we show that the probability of backdating correctly a document D for a random string R is negligible.
First step If the adversary produces a timestamp of D such that the vector of blocks associated to Share(D) according to this timestamp is far in Hamming distance from the vector of blocks associated to the timestamp produced by Stamp(D; Store(D; R)) then the veri er may with a high probability reject the timestamp of the adversary because the values indexed by Share(D) according to the timestamp do not match the values indexed by Share(D) according to his sketch. Given a correct timestamp T and a timestamp produced by an adversary A for the document D and the random string R denoted T , the adversary backdates the document D for R successfully, if he produces a timestamp T such that the vector of blocks associated to Share(D) according to T denoted R jShare(D) is close in Hamming distance to RjShare(D). In this case, we say that the adversary backdates \correctly"the document D for the random string R with err errors. Where err is an integer very close to zero. More formally, let A be an adversary. Denote Rsuccessful(D) = R successful(D) the set of strings R for which A has the necessary storage to try to backdate the document D with a probability of success greater than .
Lemma 1. If an adversary backdates a document D for a random string R
with a probability of success then he backdates it \correctly"with at most
(n=jHj)ln(1= ) errors. [
Let i be an indice of H, the probability that i be in IN CORRECT (D; R) is : P r[i 2 IN CORRECT (D; R)] = err =n.
The probability that i does not belong to IN CORRECT (D; R) is 1 P r[i 2 IN CORRECT (D; R)] = 1 err =n.
The probability that all the elements of jHj do not belong to IN CORRECT (D; R) n=jHj:ln(1= ).
P r[8i 2 H, i 2= IN CORRECT (D; R)] = jHj:(1 err =n) e (err jHj)=n.
If an adversary backdates a document D for a random string R with a probability of success e (err jHj)=n e (errjHj)=n then he backdates it correctly with at most err
Denote Rcorrect(D) the set of strings R for which A can \correctly"backdate D with at most (n=jHj)ln(1= ) errors.
[
n=jHj:ln(1= ) then, Rsuccessful(D) is a subset of Rcorrect(D).
Proof. According to the lemma 1, if an adversary backdates a document D for a random string R with a probability of success then he backdates it correctly with at most err n=jHj:ln(1= ). So, if a random string R belongs to Rsuccessful(D) then it belongs to Rcorrect(D). Thus, Rsuccessful(D) subseteq Rcorrect(D). In addition, more the probability of success become close to 1, more this error become close to 0. So, successfully backdating means correctly backdating with a \negligible"error. We prove, in the second step, that the probability that the random string R chosen by the adversary to backdate a document D be in Rcorrect(D) is negligible.
Second step We now prove that for an adversary A a document D and a string R: P r[R 2 Rcorrect(D)] is negligible.
the size of a block of R.
1 then P r[R 2 Rcorrect(D)] is negligible, with b
P r[R 2 Rcorrect(D)] probability is negligible.
Proof. We proved in the rst step, that if an adversary backdates a document \successfully", he backdated it \correctly"with at most a negligible error. Then we proved in the second stage that the probability that the string R for which the adversary tries to backdate the document D be in Rcorrect(D) is negligible.
In fact, knowing that the size of blocks of a random string R is b and the number of these blocks is n, the number of possible random strings is (2b)n.
Moreover, to backdate a document D, the adversary has to create a timestamp T for D such that at least l err blocks of R indexed by D are used to generate T .
In other words, he can try to backdate D only for random strings for which he knows the values of at least l err blocks from the l blocks indexed by D. Thus, since the adversary tries to correctly backdate D with at most err errors, the number of random strings he can use is at most (2b)n l.
So, the probability that a random string R belongs to Rcorrect(D) is: (2b)n l/(2b)n 1=2lb. Since l 1 and b 1, this 6.2
In [
Proof. The inequality 2b r=b means that the number of values for a block of size b bits is greater than the number of blocks of the string R transmitted during a round t.
l is the number of indices speci ed by a given document, this number must always be less than the number of blocks of R. So, r=b > l.
It follows that the 2b l, which means that the number of possible values for a block of R is much greater than the number of indices speci ed by the document D.
For each timestamp Tj (1 j ), if the adversary gives any value v from the 2b possible values of a block of R, it will recover a given index i.
However, the fact that i = Tj (v) does not mean that Ri = v. This means that i is the value associated to v by the polynomial Tj but the couple (i, v) does not necessarily belong to the string R. In other words, the string R may not associate the value v to the block indexed by i. Moreover, it may exist i such that Ri0 = v and there is no way to verify if i = i0. The only points of Tj for which the adversary knows that they belong to R are the points whose indices are speci ed by the document associated to Tj . The probability that the adversary chooses one of these points is l=2b 1.
To obtain the k points required to forge a fake timestamp, the probability is negligible since it is the product of the probabilities of selecting each of the points belonging to a valid timestamp.
Thus, the adversary can obtain the k points needed to forge a fake timestamp for a document D for a random string R with a negligible probability. 7
In this paper, we have presented a non-interactive timestamping solution in the bounded storage model. Our solution is not interactive and hides even the fact that a timestamping occurred. It also ensures total con dentiality of the provided timestamps. In addition, our solution provides eternal security for the provided timestamps. In fact, neither increasing the storage capacity of an adversary or the evolution of his computing power will compromise a provided timestamp. Thus, our solution is more secure than existing systems whose timestamps can be challenged when the computing power or storage capacity of users increase. In this context, we studied the security of our solution and formally proved that the possibility of cheating is negligible. In our future work, we plan to adopt new secret sharing schemes for timestamping.