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 name_i 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 name_i 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 name_i values corresponding to the selected shares are correct by recomputing

using M that was just decrypted. If the k name_i'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.