Private Directory Server Project

This is the home of the Private Information Retrieval (PIR) Server project of Alex Iliev and Sean Smith, at the Dartmouth College PKI Lab.


PIR aims to enable a user Aphro to retrieve information from a server, without the server being able to tell what she got. For example Aphro may want to get a book description from a library website, but she for whatever reason doesn't want the library to know which book it was. More accurately, she doesn't want the library to be able to know.

In this prototype we address the less sexy subject of retrieving X.509 certificates from an LDAP certificate directory.

When Bacchus wants to send an encrypted message to Cupid, he needs Cupid's public key. In many setups he gets the key with a certificate from some directory, say one run by Mercury. Mercury however then knows that Bacchus wants to send a secret message to Cupid—there's part of the secret gone! What Bacchus would prefer is if he could fetch Cupid's certificate from Mercury, and Mercury could only learn that Bacchus retrieved some certificate from his directory.


We make use of secure coprocessors (SCOP) at the server site.

A trivial solution to the problem would be to put the whole database (X.509 directory in our case) inside the coprocessor. Then, Aphro could connect securely (eg. SSL) to the SCOP and retrieve her desired certificate. Since computation in the SCOP cannot be observed, even by root at the host machine (root secure), the certificate retrieval is private to Aphro.

The problem with the above is that the current SCOP of choice–the IBM 4758–has 4MB of RAM. Thus, the database has to be stored partially or fully outside the SCOP, on the host. The challenge then becomes that the SCOP, on behalf of Aphro, privately retrieves an item from a database stored on the untrusted host.

The essence of the current approach is that the SCOP performs a private permutation on the database, and then reads items directly from the permuted database. The permutation is private in the sense that the host should not know the correspondence between items in the original and permuted datasets. We currently use a Benes permutation network to carry out the permutation.

Lately we have been investigating how to compute and perform a private permutation using a logarithmic amount of space inside the SCOP. The previous approach required using O(N lg N) bits to store a random permutation, and that much again to compute the routing of the Benes network.


Workshop Paper

Linked from the publications page.

Tech Report

Dartmouth TR2003-442
Alex Iliev
Last modified: Feb 20, 2004