|
|
|
# Presentation notes
|
|
|
|
|
|
|
|
Good afternoon everyone, my name is Dmytro Bogatov, I am here to present you our work "A comparative evaluation of order-revealing encryption schemes and secure range-query protocols".
|
|
|
|
The work was done with Professor George Kollios and Professor Leonid Reyzin.
|
|
|
|
|
|
|
|
We focus our work on a specific type of queries - the secure range queries.
|
|
|
|
In this setting, an honest-but-curios server holds the client's data (usually encrypted).
|
|
|
|
The clients issue the range queries - queries of the type "give me all the records with this attribute in this range" - to the server.
|
|
|
|
Server correctly responds to the query returning at least the set of correct records (but possibly including little fraction of extra records).
|
|
|
|
The attack model is a snapshot model.
|
|
|
|
The adversary can look at the snapshot of server's data at any point in time.
|
|
|
|
The goal is to let adversary learn as little as possible about the data.
|
|
|
|
We specifically target data at rest - no communication or access pattern leakage.
|
|
|
|
However, we do include ORAM as baseline in the benchmark.
|
|
|
|
|
|
|
|
There are many solutions proposed in the literature, ranging from OREs to dedicated range-query protocols.
|
|
|
|
These solution has never been benchmarked against each other under a common testbed.
|
|
|
|
Even their security definitions and leakages are different, some definitions define a clear leakage function, like the first differing bit, others use indistinguishability definitions.
|
|
|
|
What is worse is that some construction were only theoretical while most of others had only a prototype implementation.
|
|
|
|
|
|
|
|
Our work fills these addresses these problems.
|
|
|
|
We have implemented 5 ORE schemes and 5 range query protocols.
|
|
|
|
We provide detailed theoretical analysis of their security and performance.
|
|
|
|
We implemented them in the same language and the same framework.
|
|
|
|
They even use the same primitive implementations - when a constructions needs, for example, a PRF, it will use the same PRF implementation as all the others.
|
|
|
|
We have run extensive simulations using various data sizes, distributions, query sets and other parameters.
|
|
|
|
|
|
|
|
Let describe what ORE schemes we analyzed.
|
|
|
|
The firs one is a scheme by Alexandra Boldyreva where upon encrypting a number one splits |
