Cryptography Reference
In-Depth Information
Searching for the file could be accomplished by broadcasting
N
i
to all of the servers, asking them to compute
S
j
))
,and
see if they have the file. This might help someone recover a file after
some time or allow a central payment mechanism to figure out who
to pay for storage.
h
(
N
i
+
name
(
10.5.2 Entanglement
One technique for preventing the destruction of some documents is
to tie their existence to other documents so that one can't be deleted
without others being destroyed in the process. Some say that the
future of the documents becomes
entangled
.
James Aspnes, Joan
Feigenbaum, Aleksandr
Yampol skiy , and Sheng
Zhong consider some of
the theoretical aspects of
All or Nothing
Entanglement in
[AFYZ04].
Here's a simple algorithm for mixing the fate that is based on
some of the simplest secret sharing algorithms from Chapter 4.
Given a file,
F
, break it into
n
parts
F
1
+
F
2
+
...
+
F
n
so that
F
can only
be reconstructed by someone who holds all
n
pieces. (Let
+
stand for
exclusive-or.) Ordinarily,
1
pieces would be built with a random
number source. In this case, let's choose parts of other documents
for these pieces.
That is, let
n ā
be a sequence of parts to documents that
acts as the storage for the entangled documents. To store
P
1
,P
2
,P
3
,...
F
,usethese
steps:
1. Choose a set of
n ā
1
parts from the set of
m
parts of files previ-
ously locked away in storage,
P
1
,P
2
,P
3
,...P
m
. Use some ran-
dom number generator driven by the file name. This might
mean using
h
(
key
+
name
(
F
))
as a seedwhere
key
is an optional
key and
name
(
F
)
is some name given to the file. Call these
P
r
1
,P
r
2
,P
r
3
...
represents the choices made by
the random number generator driven by
where
r
1
,r
2
,...
h
(
key
+
name
(
F
))
.
2. Compute
P
m+1
=
F
+
P
r
1
+
P
r
2
+
...
+
P
r
nā1
.
3. Create a table entry that links
P
m+1
with
name
(
F
)
.
This solution makes it impossible to delete a file without en-
dangering some of the files that were stored after it. There are still
some weaknesses from this approach.The table linking
P
m+1
with
)
lets someone know exactly which block to delete to de-
stroy the file. It won't be possible to tell which other files are endan-
gered unless there's no key used to compute the sequence of random
blocks chosen for each file,
name
(
F
.
One possible solution is to use a hash table
2
with holes for
r
1
,r
2
,...
k
2
In this case, the word
hash
is used as a data structure designer might use it, not a
cryptographer.
