Rafail Is No Secret

Never say anything in an electronic message that you wouldn’t want appearing, and attributed to you, in tomorrow morning’s front-page headline in the New York Times—Colonel David Russell.

Rafail Ostrovsky is a professor of computer science at the UCLA Samueli School of Engineering. Ken and I have been friends with him for many years, long before he moved to UCLA. He is one of the world experts in security theory and practice. And he is especially strong at seeing new attacks and then finding defenses for them. See his web home site for some details.

Rafail was just awarded the 2022 McDowell award. For visionary contributions to computer security theory and practice, including foreseeing new cloud vulnerabilities and then pioneering corresponding novel solutions.

Again first seeing attacks, then inventing defenses.

A Key Result

One of Rafail’s neat results is how to create strong keys from biological data. This is joint work with Yevgeniy Dodis, Leonid Reyzin, and Adam Smith and is Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.

Rather than try and generate keys from silly to generate patterns such as: my name + 3.14159 the idea is to use your own biological data. This paper unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. Yet it allows strong keys.

A Non-Typical Result

Rafail has a paper that is titled Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution and is joint with Brett Hemenway Falk and Daniel Noble both of University of Pennsylvania. Their paper solves a nice problem, but we believe is unique for its abstract:

There once was a table of hashes
That held extra items in stashes
It all seemed like bliss
But things went amiss
When the stashes were stored in the caches

More Results

Here is another of Rafail’s results that demonstrates his many abilities. The paper is titled Public Key Encryption with Keyword Search and is joint with Dan Boneh, Giovanni Di Crescenzo, and Giuseppe Persiano. Consider a mail server that stores various messages publicly encrypted for Alice by others. Using our mechanism Alice can send the mail server a key that will enable the server to identify all messages containing some specific keyword, but learn nothing else. We define the concept of public key encryption with keyword search and give several constructions.

This result is interesting in that Rafail creates a problem that allows security to be partial. The full text is safe but it is still possible to search the text for certain keywords. This allows the security to be weaken, but not to be weaken all the way.

It is surprising that security can be weaken partially, but not all the way. It might seem likely that this weaken notation of security could be too dangerous. One of the advantages of precise security models is that such results can be safely defined and shown to be safe. This is the fundamental advantage of modern formal definitions for security.

Open Problems

Rafail is one of the top researchers in security in the broadest sense. He is one of the best at defining new types of security and then showing that such notions are actually safe.

Congrats to him for the McDowell award.