Alice and Bob both have a copy of a database that holds the following items: 10101 - 0 11100 - 1 00010 - 2 01101 - 3 Carol wants to obtain item number three without Bob or Alice learning which of the items she is interested in. First she generates a random bit string equal in length to the number of items in the database. 0010 next she generates a bit string that xors to 0 with the first at every position except the database item she wants 0011 she sends one of these strings to Alice and the other to Bob. They xor messages from the database together if their position is marked by 1 in the string the receive from Carol. Alice gets 0010 so she simply replies with the message at position 2: 00010, bob receives 0011 so he replies with the xor of message 2 and 3: 00010 xor 01101 = 01111 Alice and Bob send their replies to Carol who xor them together 01111 xor 00010 = 01101, which is item at position three in the database neither Alice nor Bob can determine which of the items was requested. I think this is pretty neat, especially for databases with hundreds of thousands of entries mirrored over a dozen different non-cooperating servers .