Changes between Version 7 and Version 8 of WikiStart

Oct 11, 2012 9:44:58 PM (7 years ago)

Add illustration


  • WikiStart

    v7 v8  
    1313One question many people have when hearing of the problem, is whether providing this property is even possible. First, it's is clear there is a trivial solution --- just download the entire mirror's contents. However, this is very inefficient. Can we do better? 
    1517Suppose a client wants to privately retrieve an update from two mirrors so that neither mirror knows which update the client is retrieving. Let’s suppose that a vendor has produced a release containing 4 updates of the same size called A, B, C, and D. This release is currently being served by the two mirrors. The client will generate a random string of bits of length 4 (one bit for each update in the release) and send this to the first mirror. The mirror receives the random string and then will XOR together a response containing each update where there is a 1 value in that position. For example, the string 1010 would contain A XOR C. Then the client takes the random string they sent to the first mirror and flips the bit of the update they want. Let’s suppose the client wanted update D, if the first string was 1010, they would send 1011 to the second mirror. The second mirror sends back a response that contains all of the updates with a 1 XORed together (or A XOR C XOR D in our example). The client can then XOR the retrieved strings together to obtain the update D.