Publish

The following text describes the publish pseudocode of Figure 1. This pseudocode is executed by the Publius client proxy in response to a publish request. To publish Publius content, M, the publisher, Alice, first generates a random symmetric key, K. She then encrypts M to produce , M encrypted under K, using a strong symmetric cipher. Next, Alice splits K into n shares using Shamir secret sharing, such that any k of them can reproduce the secret. For each of the n shares, Alice computes

That is, each share has a corresponding name. The name is calculated by concatenating the share with the message, taking a cryptographic hash, H, of the two, and xoring the first half of the hash output with the second half. We call the xor of the two halves wrap. In our system, we use MD5 [20] as the hash function, so each name_i is 8 bytes long. Note that the name_i's are dependent on every bit of the web page contents and the share contents. The name_i values are used in the Publius server addressing scheme described below. Recall that each publisher possesses a static list of size m of the available servers in the system. For each of the n shares, we compute

to obtain n values each between 1 and m. If at least d unique values are not obtained, we start over and pick another K. The value d represents the minimum number of unique servers that will hold the Publius content. Clearly this value needs to be greater than or equal to k since at least k shares are needed to reconstruct the key K. d should be somewhat smaller than m. It is clearly desirable to reduce the number of times we need to generate a new key K. Therefore we need to create a sufficient number of shares so that, with high probability, d unique servers are found. This problem is equivalent to the well known Coupon Collectors Problem [15]. In the Coupon Collectors Problem there are y different coupons that a collector wishes to collect. The collector obtains coupons one at a time, randomly with repetitions. The expected number of coupons the collector needs to collect before obtaining all y different coupons is