Information Technology Reference
In-Depth Information
H
root
=H
2,0
=
h ( H | H )
N
2,0
1,0
1,1
N
1,0
H
1,0
=
h ( H | H )
N
1,1
H
1,1
=
h ( H | H )
0,0
0,1
0,2
0,3
N
0,0
N
0,1
N
0,2
N
0,3
H
0,0
=
h ( c )
H
0,1
=
h ( c )
H
0,2
=
h ( c )
H
0,3
=
h ( c )
0
1
2
3
Fig. 2.
Sample MHT
variable stored by node
N
i,j
. Nodes at level 0 are called “leaves” and they rep-
resent the data stored in the tree. In the case of revocation, leaves represent the
set
Φ
of certificates that have been revoked,
Φ
=
{
c
0
,c
1
,...,c
j
,...,c
n
}
.
(1)
Where
c
j
is the data stored by leaf
N
0
,j
. Then,
H
0
,j
is computed as (2)
H
0
,j
=
h
(
c
j
)
.
(2)
Where
h
is a OWHF. To build the MHT, a set of
t
adjacent nodes at a given
level
i
;
N
i,j
,
N
i,j
+1
, ...,
N
i,j
+
t−
1
, are combined into one node in the upper level,
node that we denote by
N
i
+1
,k
. Then,
H
i
+1
,k
is obtained by applying
h
to the
concatenation of the
t
cryptographic variables (3)
H
i
+1
,k
=
h
(
H
i,j
|
H
i,j
+1
|
...
|
H
i,j
+
t−
1
)
.
(3)
At the top level there is only one node called “root”.
H
root
is a digest for all
the data stored in the MHT.
The sample MHT of Fig. 2 is a binary tree because adjacent nodes are com-
bined in pairs to form a node in the next level (
t
= 2) and
H
root
=
H
2
,
0
.
Definition 1.
The
D
igest is defined as
{
RDI
ID
,H
root
, V alidity P eriod
}
SIG
RDI
.
Definition 2.
The
ath
c
j
is defined as the set of cryptographic values necessary
to compute
H
root
from the leaf
c
j
.
P
Remark 1.
Notice that the
D
igest is trusted data because it is signed by the RDI
(identified by
RDI
ID
) and it is unique within the tree while
P
ath is different
for each leaf.
Claim.
If the MHT provides a response with the proper
P
ath
c
j
and the MHT
D
igest, an End Entity can verify if
c
j
∈
Φ
.
Example 1.
Let us suppose that a certain user wants to find out if
c
1
belongs
to the sample MHT of Fig. 2. Then
igest
=
{RDI
ID
,H
2
,
0
, V alidity P eriod}
SIG
RDI
. The response verification consists in
P
ath
c
1
=
{
N
0
,
0
,N
1
,
1
}
and
D