Rafail Ostrovsky - Publications

How to Protect Searching Software so That it is Impossible to Reverse-Engineer
(Or a more technical title: Private Searching on Streaming Data)

Informal Problem statment: One of the important challenges in sieving through corporate or unclassified data (for corporate security or national security purposes) is to hide queries (i.e. what information is being sought). That is, given unclassified sources, such as newspaper feeds, reports on the weather conditions around the world or streams of email messages or data files, find only those that fit secret classified criteria and return only matching data to the corporate security or classified setting. The problem is to create a compiler that takes a search query and creates a compiled sieving executable code (with a small encrypted storage) that can be run on all the machines in the organization/business and need not run only on the classified machines. The guarantee is that the sieving software on the unclassified machines should not reveal any information about the query itself or the data collected. The guarantee must be "bulletproof" - given the full access to the object code it should be provably impossible to extract any information about the queries or the data that the sieving code has collected. The developed technology has applications both to national security and corporate security alike.

A tutorial [40-min PowerPoint presentation] (with animation) or a [full hour] presentation.

Popular Press Covering This Work:

Private Searching on Streaming Data

Rafail Ostrovsky, William Skeith

Abstract: In this paper, we consider the problem of private searching on streaming data, where we can efficiently implement searching for documents under a secret criteria (such as presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of a Private Information Retrieval (to more general queries and to a streaming environment as well as to public-key program obfuscation); as positive results on privacy-preserving data-mining; and as a delegation of hidden program computation to other machines.

KEYWORDS: Code Obfuscation, Crypto-computing, Software security, Database security, Public-key Encryption with special properties, Private Information Retrieval, Privacy-Preserving Keyword Search, Secure Algorithms for Streaming Data, Privacy-Preserving Data-mining, Secure Delegation of Computation, Searching with Privacy, Mobile code.

comment: Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005) Springer-Verlag/IACR Lecture Notes in Computer Science, pp. 223-240.
Full version appeared in Journal of Cryptology Volume 20:4, pp. 397-430, October 2007.

Fetch PostScript file of the paper.ps or Fetch PDF file of the paper.pdf

You can alsoe fetch patent application.

Back to Publications List