1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
1. Merkle - Protocols for public key cryptosystems
==================================================
Protocol to build a proof that you possess some content (e.g a public key) that
is part of a larger set of data known by everyone (the set of all public keys)
* put each piece of data at the leaves of a binary tree
* each internal node of the tree computes the hash of its left child concatenated
with its right child
* everybody computes the hash tree and stores the root hash plus the hashes going from
the root to his own leaf
* The list of hashes from the root to f yields a proof that f is part of the big set
of files. Indeed, one can test that repeatedly hashing f yields the
same hashes.
Space : log(N) where N is the number of files
Problem : everyone must compute the hash tree and thus must know every file
2. Benaloh, de Mare - Efficient Broadcast Time-Stamping
=======================================================
Almost the same as 1., but here applied to time-stamping. New concept : proceed
in rounds
* the root hash of the previous round is added to each leaf file before hashing it.
=> the proof now depends on the round => it's possible to proove that the file was present at
a given round
Space : log(N)
Problem : you need to know the root time-stamp of the previous round to time-stamp
a document. Not a big issue
3. Benaloh, de Mare - One-way accumulators: a decentralized alternative to digital signatures
=============================================================================================
Improvement of 2. Use of quasi-commutative hash functions :
h(h(x,y1),y2) = h(h(x,y2)y1)
Thus, starting from a common value x, the order with which the hashing is done
doesn't matter.
* everyone agrees on a starting value x (for example the root hash of previous round)
* everyone computes the total hash :
z = h(h(h(.....h(x,y1),y2),y3).....)
and the hash of everybody except his own y_i : z_i
* then (z_i,y_i) yields a proof that y_i is part of the big set of files. Indeed :
z = h(z_i, y_i)
Space : constant !!
Problem : you still need to know the whole set of files
Maybe this can be used to store a branch in pacemaker...
4. Maniatis, Baker - Secure history preservation through timeline entanglement
==============================================================================
* Idea of tamper-evident log/history.
* If h_(k-1) is your history up to date k-1. If event e_k occurs at time
k then :
h_k = H(h_(k-1),H(e_k)) is your new history
* Same idea as in 2. : h_k, e_k is a proof
5. Haeberlen - PeerReview: Practical Accountability for Distributed Systems
===========================================================================
Use the idea of 4 to build a review protocol.
* each node keeps his own log
* at any time a node can commit to event e_k by broadcasting (h_k,e_k) to its witnesses
* it's possible to challenge a node on event e_k : the node should answer h_(k-1) such that
h_k = H(h_(k-1),H(e_k))
This relies heavily on peer reviews as in AVMON
|
