Next: Delete
Up: Publius
Previous: Publish
Retrieve
The following text describes the retrieve pseudocode of Figure 3. This pseudocode is executed by the Publius client proxy in
response to a retrieve request.
The retriever, Bob, wishes to view the Publius content addressed
by Publius URL U. Bob parses out the namei values from U
and for each one computes
Thus, he discovers the index into the table of servers for
each of the shares. Next, Bob chooses k of these arbitrarily.
From this list of k servers, he chooses one and
issues an HTTP GET command to retrieve the encrypted file and the share.
Bob knows that the encrypted file,
is stored in a file
called file on each server, in the namei directory.
The key share is stored in a file called share in that same
directory.
Next, Bob retrieves the other k-1 shares in a similar fashion (If all goes
well, he does not need to retrieve any other files or shares).
Once Bob has all of the shares, he combines them to form the key, K.
Then, he decrypts the file. Next, Bob verifies that all of the namei values
corresponding to the selected shares are correct by recomputing
using M that was just decrypted. If the k namei's are
all correct (i.e. if they match the ones in the URL), Bob can
be satisfied that either the document is intact, or that someone has
found a collision in the hash function.
If something goes wrong, Bob can try a different set of k shares
and an encrypted file stored on one of the other n servers.
In the worst case, Bob may have to try
all of the possible
combinations to get the web page
before giving up. An alternate retrieval strategy would be to try all
n *
combinations of shares and documents. Each encrypted
document can be tested against each of the
share combinations.
If we are willing to initially download all the shares from all the servers then
yet another method for determining the key becomes available.
In [10], Gemmell and Sudan present the Berlekamp and Welch method
for finding the polynomial, and hence the key K, corresponding to n
shares of which at most j are corrupt. The value j must be less
than (n-d)/2 where d is
one less than the number of shares needed to form the key. However if
the number of corrupt shares is greater than (n-d)/2 we are not
quite out of luck. We can easily discover whether K is incorrect
by performing the verification step described above. Once we suspect
that key K is incorrect we can just perform a brute force search
by trying all n *
combinations of shares and documents.
The following example illustrates this point. If we have n=10
shares and require 3 shares to form K
then the Berlekamp and Welch method will generate the correct polynomial
only if less than
((10-2)/2)=4 shares are corrupted. Suppose 6 shares are
corrupt. Of course we don't know this ahead of time so we perform the
Berlekamp and Welch method which leads us to key K. Key K is tested
against a subset of, or perhaps all, the encrypted documents. All of the
tamper check failures lead us to suspect that K is incorrect. Therefore
we perform a brute force search for the correct key by trying all
n *
combinations of shares and documents. Assuming we
have a least one untampered encrypted document this method will clearly
succeed as we have 4 uncorrupted shares, only three of which are needed
to form the correct key.
Once the web page is retrieved Bob can view it in his browser.
In our implementation, all of the work is handled by the proxy.
Publius URLs are tagged as special, and they are parsed
and handled in the proxy. The proxy retrieves the page, does
all of the verification, and returns the web content to the
browser. So, all of this is transparent to the user. The user just
points and clicks as usual. Section 4
describes Publius URL's and the proxy software in detail.
Next: Delete
Up: Publius
Previous: Publish
Avi Rubin
2000-06-13