Retrieving Database Information

Today, many people store information as valuable as gold — about stocks, patents, medical research, etc. — in databases that they may assume are secure. But when you query a database you leave clues for somebody — such as a dishonest database administrator — to infer what you are after.

To help surmount this, Telcordia Technologies, SAIC's wholly-owned subsidiary, (Eyal Kushilevitz and Rafail Ostrovsky) developed and patented cryptographic protocols (known as single database private information retrieval schemes) that allow users to get information from a database, while keeping the content of their queries secret (and without having to download the entire database). This technology was made even more efficient in a recent ESTC Award-winning paper (and patent) by Giovanni Di Crescenzo, Yuval Ishai, and Rafail Ostrovsky, who have extended the original method to commodity-based private information retrieval schemes.

The Telcordia solution involves using independent commodity service providers that offline send commodities — special-purpose randomized messages — via secure channels to the user and each database. The simple and modular schemes allow you to significantly reduce overall communication and computation through the offline messages, which enhances security.

The service providers need only know the data size, not the database contents or future user requests. In fact, the service providers do not need to know how many other service providers you use — they only send a single message (commodity) to each client.

Some of the commodity schemes the Telcordia researchers have developed include those for single and multiple databases, and for information-theoretic multiple databases. In addition, the authors show how to test the reliability of service providers.

The results of the research from Di Crescenzo, Ishai, and Ostrovsky, "Universal service-providers for database private information retrieval," were published in the Journal of Cryptography.

In its annual competition, SAIC's Executive Science & Technology Council recognizes some of the most innovative research and best written technical papers and books by SAIC scientists and engineers. This article is a summary from one of the award winners.