Tobias Boelter and Rishabh Poddar and Raluca Ada Popa

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2017-7

April 28, 2017

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-7.pdf

We present the first one-roundtrip protocol for performing range, range-aggregate, and order-by-limit queries over encrypted data, that both provides semantic security and is efficient. We accomplish this task by chaining garbled circuits over a search tree, using branch-chained garbled circuits, as well as carefully designing garbled circuits. We then show how to build a database index that can answer order comparison queries. We implemented and evaluated our index. We demonstrate that queries as well as inserts and updates are efficient, and that our index outperforms previous interactive constructions. This index is part of the Arx database system, whose source code will be released in the near future.

Advisors: Raluca Ada Popa

---

BibTeX citation:

@mastersthesis{Boelter:EECS-2017-7,
    Author= {Boelter, Tobias and Poddar, Rishabh and Popa, Raluca Ada},
    Title= {A Secure One-Roundtrip Index for Range Queries},
    School= {EECS Department, University of California, Berkeley},
    Year= {2017},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-7.html},
    Number= {UCB/EECS-2017-7},
    Abstract= {We present the first one-roundtrip protocol for performing range, range-aggregate, and order-by-limit queries over encrypted data, that both provides semantic security and is efficient. We accomplish this task by chaining garbled circuits over a search tree, using branch-chained garbled circuits, as well as carefully designing garbled circuits. We then show how to build a database index that can answer order comparison queries. We implemented and evaluated our index. We demonstrate that queries as well as inserts and updates are efficient, and that our index outperforms previous interactive constructions. This index is part of the Arx database system, whose source code will be released in the near future.},
}

EndNote citation:

%0 Thesis
%A Boelter, Tobias 
%A Poddar, Rishabh 
%A Popa, Raluca Ada 
%T A Secure One-Roundtrip Index for Range Queries
%I EECS Department, University of California, Berkeley
%D 2017
%8 April 28
%@ UCB/EECS-2017-7
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-7.html
%F Boelter:EECS-2017-7