Papers
Papers
A. Iliev, S.W. Smith.
"Private Information Storage with Logarithmic-space Secure Hardware."
Information Security Management, Education, and Privacy
(containing the proceedings of
i-NetSec 04: 3rd Working Conference on Privacy and Anonymity in Networked and Distributed Systems.)
Kluwer. 201--216. 2004.
Recent research in ``practical PIR'' has limited the players to the user and server and limited the user's work to negotiating a session key (eg. as in SSL)---but then added a secure coprocessor to the server and required the secure coprocessor to encrypt/permute the dataset (and often gone ahead and built real systems).
Practical PIR (PPIR) thus consists of trying to solve a privacy problem for a large dataset using the small internal space of the coprocessor. This task is very similar to the one undertaken by the older Oblivious RAMs work, and indeed the latest PPIR work uses techniques developed for Oblivious RAMs. Previous PPIR work had two limitations: the internal space required was still O (N lg N) bits, and records could only be read privately, not written.
In this paper, we present a design and experimental results that overcome these limitations. We reduce the internal memory to O(\lg N) by basing the pseudorandom permutation on a Luby-Rackoff style block cipher, and by re-designing the oblivious shuffle to reduce space requirements and avoid unnecessary work. This redesign yields both a time and a space savings. These changes expand the system's applicability to larger datasets and domains such as private file storage.
These results have been implemented for the IBM 4758 secure coprocessor platform, and are available for download.
|
Back to home page | Maintained by Sean Smith, sws@cs.dartmouth.edu |