Compulsion Resistance and multi-server PIR

24 April 2008

For a long time I have been sceptical about Private Information Retrieval (PIR) schemes and security schemes based on them. My first experience of PIR was in the single server setting, where communication and computation complexity makes them impractical. Re-reading the The Pynchon Gate I realized that multi-server PIR systems are computationally cheap, bandwidth efficient and relatively simple to implement.

The ‘only’ downside of multi-server PIR is that they are subject to compulsion attacks. A powerful adversary can force servers, after a query, to reveal the client queries, and can infer which document was retrieved. This is an inherent limitation of using a collection of trusted parties, so it is difficult to eliminate. On the other hand a system can make the task of the attacker much more expensive and difficult, though the use of forward security mechanisms.

Here is a proposal for achieving forward-secure compulsion-resistant multi-server PIR: the user contacts the servers one by one, using an encryption channel providing forward secrecy (OTR would work; so would SSL using signed ephemeral DH.) After the result of the query is returned, the server securely deletes all information about the query, and forgets the session keys associated with the channel. At this point an adversary will never be able to retrieve any information about the query or the result, even if they get access to all the secrets on the server.

The user can then proceed to perform the same protocol sequentially with all the other servers participating in the PIR scheme. After sessions with each server close, the user is guaranteed that the query information will never be retrieved in the future. A single honest server, willing to provide strong guarantees against compulsion, is sufficient to guarantee this property, even if all the others log requests and are ready to hand them over to the adversary.

Furthermore the sequential nature of the requests allow a client to terminate the query early, if there is any suspicion that one or more servers act under compulsion. This could be detected through a covert channel, a change of key, or unavailability. This technique is a further argument for operators to terminate their services instead of giving in to compulsion.


One Response to “Compulsion Resistance and multi-server PIR”

  1. We went the “SSL using signed ephemeral DH” and “throw away secrets as soon as you’re done with them” approach with the design specs for Pynchon, as compulsion resistance is something we’re concerned about.

    Note that it exists in *any* distributed-trust system, including mixes and Tor. The fact that the end user is directly querying each of the PIR servers (distributors, in Pynchon’s terminology) changes the dynamic slightly, but in the end, the big risk that both face is a compromise event whereby the operators of the servers are compelled to give up individual users, and then future compromise of the system’s users. Tor, Mixmaster, etc., all have this problem as well.

    (I’d love to have a multi-server, total-trust anonymity system that doesn’t rely on collusion between all nodes being unlikely to happen for its security. We’re not there yet unless you throw usability out the window.)

    Another “only” problem with the original Pynchon proposal is the lack of Byzantine robustness (it detects Byzantine action, but doesn’t identify the Byzantine nodes).

    This has been fixed several ways; you can substitute a different PIR scheme (at the cost of weakened security) that will handle Byzantine nodes, or introduce a cut-and-choose protocol (at the cost of 2x or more extra bandwidth for the protocol) that will retain the security properties of the PIR protocol currently used by Pynchon. I’m still looking at other alternative ways to address that which may be better.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: