1 Practical Private Range Search RevisitedIoannis Demertzis* University of Maryland Stavros Papadopoulos Intel Labs & MIT Odysseas Papapetrou* EPFL, Lausanne, Switzerland Antonios Deligiannakis Technical University of Crete Minos Garofalakis Technical University of Crete *Work performed while the author was at the Technical University of Crete

2 Cloud Computing Pros: Near infinite scalability for big data analyticEasy and ubiquitous access on solid data Cost reduction with the use of shared infrastructure + Affordable for small and medium businesses Cons: - Serious security and privacy concerns regarding outsourcing and querying on private company or personal data Solution: Privacy Preserving Querying 2

3

4 IDEAL SOLUTION Privacy Preserving QueryingEncrypt(DB) Client ? Encrypted Database Later: Encrypted(query) Untrusted Cloud Encrypted(results) Client

5 Solutions for Encrypted SearchEfficiency Security High Low CryptDB CipherBase MONOMI Google BigQuery Microsoft SQL 2016 Always Encrypted … PPE Secure & Efficient OPE DET SSE Efficient ORAM Func/Pred Enc Secure FHE Not all schemes are explained (Feel free to ask me during the poster session!!)

6 No Practical and Secure solution!Why? Practical Private Range Search? No Practical and Secure solution! Our Contribution: Range Searchable Symmetric Encryption (RSSE) schemes 6

7 Related Work – Private Range SearchHacigumus et al. (2002) Hore et al. (2004, 2012) Efficiency Security High Low OPE DET PPE FHE Secure & Efficient RSSE ? Popa et al. (2013) Kerschbaum et al. (2014) Ostrovsky et. al (1990) Goldreich et. al (1996) Stefanov et al. (2011,2013, 2013) Efficient Li et al. (2015) ORAM Func/Pred Enc Gentry et al. 2010 Boneh et al. (2007) Shi et al. (2007) Lu et al. (2012) Secure Not all schemes are explained (Feel free to ask me during the poster session!!)

8 What is Searchable Symmetric Encryption?Leakage is the amount of information that the untrusted cloud learns Untrusted Cloud Client ? search query: keyword

9 Searchable Symmetric Encryption (SSE) schemesClient Untrusted Cloud k1 F1 F4 F2 k2 F3 F6 F4 F2 k3 F5 F1 F1 F2 F3 F4 F5 F6

10 Searchable Symmetric Encryption (SSE) schemesClient Untrusted Cloud k1 F1 F4 F2 k2 F3 F6 F4 F2 k3 F5 F1 F1 F2 F3 F4 F5 F6

11 Searchable Symmetric Encryption (SSE) schemesClient Untrusted Cloud L1 leakage: total leakage prior to query execution e.g. size of each encrypted file, size of encrypted index k1 F1 F4 F2 k2 F3 F6 F4 F2 k3 F5 F1 F1 F2 F3 F4 F5 F6

12 Searchable Symmetric Encryption (SSE) schemesClient Search pattern: whether a search query is repeated L2 leakage (leakage during query execution) Untrusted Cloud token k1 k1 F1 F4 F2 k2 F3 F6 F4 F2 k3 F5 F1 F1 F2 F3 F4 F5 F6 Access pattern: encrypted document ids and files that satisfy the search query

13 Security Game Real Scheme Simulator L1 ( Adversary ) Enc ( ) + Enc( ) w1 | L2( w1 ) w1 Adversary token1 … … wN | L2( wN) wN tokenN 13

14 Trivial Solution 1 - Quadratic ApproachMain idea: Replicate each tuple to all possible ranges it belongs to (For domain [0,m]  O(m2) possible ranges) Untrusted Cloud Client SELECT * FROM TABLE as T WHERE T.SALARY ≥ 2K and T.SALARY ≤ 3K 1 2 3 F1 F4 F2 F3 F6 F5 2-3 1-2 F1 F4 F2 F3 F6 2-3 F3 F6 F4 F2 F5 F1 1-3 F5 F1 F4 F2 F3 F6 Optimal Security - O(1) Query Size - O(r) Search Time - O(nm2) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

15 Trivial Solution 2 – Linear ApproachClient Main idea: Transform the range queries to point queries Untrusted Cloud SELECT * FROM TABLE as T WHERE T.SALARY ≥ 1K and T.SALARY ≤ 8K 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 F1 F4 F2 F6 F3 F5 Weaker Security - O(R) Query Size – O(R+r) Search Time - O(n) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

16 Linear Approach (BRC-URC)Client Main idea: Use Delegatable-PRFs (DPRFs) Kiayas et al.CCS’13 Untrusted Cloud SELECT * FROM TABLE as T WHERE T.SALARY ≥ 1K and T.SALARY ≤ 8K a a b c d e f g 1 2 3 4 5 6 7 8 F1 F4 F2 F6 F3 F5 Weaker Security - O(logR) Query Size - O(logR+r) Search Time - O(n) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

17 Logarithmic-Best Range Cover ApproachClient Main idea: Increase the space by replicating each tuple to the dyadic intervals in which it belongs (xlogm) Untrusted Cloud F2 F4 F1 F6 F3 F5 1-8 F1 F4 F2 1-4 F5 F3 F6 5-8 F3 F5 F1 F4 F2 1-2 3-4 F6 5-6 7-8 1 2 3 4 5 6 7 8 F1 F4 F2 F6 F5 F3 Intermediate Security - O(logR) Query Size - O(logR+r) Search Time - O(nlogm) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

18 Logarithmic-Best Range Cover ApproachClient Main idea: Answer the queries with the minimum number of nodes which cover the range Untrusted Cloud 1-4 BRC(1,4) = 1-8 BRC(2,5) = 2 3-4 5 1-4 5-8 1-2 3-4 5-6 7-8 Equal size ranges have tokens of unequal size 1 2 3 4 5 6 7 8 Complex tokens have a specific structure Intermediate Security - O(logR) Query Size - O(logR+r) Search Time - O(nlogm) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

19 Logarithmic-Uniform Range Cover ApproachClient Main idea: Answer all the queries with the same size with the same number of tokens Untrusted Cloud 1 2 3-4 URC(1,4) = 1-8 URC(2,5) = 2 3-4 5 1-4 5-8 1-2 3-4 5-6 7-8 Equal size ranges have tokens of unequal size 1 2 3 4 5 6 7 8 Complex tokens have a specific structure Solved by Logarithmic-SRC/Logarithmic SRCi Intermediate Security - O(logR) Query Size - O(logR+r) Search Time - O(nlogm) Space – No False Positives n: dataset size, r: result size, m: domain size , R: query range size

20 Logarithmic-Single Range Cover ApproachClient Main idea: Answer all the queries with one token Untrusted Cloud SRC(4,5) = 1-8 1-8 O(n) False Positives 1-4 5-8 1-2 3-4 5-6 7-8 1 2 3 4 5 6 7 8 False Positives Actual Answer False Positives Optimal Security – O(1) Query Size - O(n) Search Time - O(nlogm) Space – O(n) False Positives n: dataset size, r: result size, m: domain size , R: query range size

21 Logarithmic-Single Range Cover ApproachClient Main idea: Augment the tree structure with extra nodes without increasing asymptotically the space Untrusted Cloud SRC(4,5) = 4-5 1-8 O(range) False Positives values 1-4 3-6 5-8 All the tuples have value = 1 1-4 SRC(2,4) = 2-3 4-5 6-7 1-2 3-4 5-6 7-8 O(n) False Positives 1 2 3 4 5 6 7 8 If we have only one value per leaf then O(result size) False Positives False Positive value Flatten the distribution (Assign one value per leaf) Actual Values Logarithmic SRCi Optimal Security - O(1) Query Size - O(n) Search Time - O(nlogm) Space – O(n) False Positives n: dataset size, r: result size, m: domain size , R: query range size

22 Logarithmic-Single Range Cover-i ApproachClient Main idea: Augment the tree structure with extra nodes without increasing asymptotically the space Untrusted Cloud SRC(4,5) = 4-5 1-8 O(range) False Positives values 1-4 3-6 5-8 All the tuples have value = 1 1-4 SRC(2,4) = 2-3 4-5 6-7 1-2 3-4 5-6 7-8 O(n) False Positives 1 2 3 4 5 6 7 8 If we have only one value per leaf then O(result size) False Positives Flatten the distribution (Assign one value per leaf) Logarithmic SRCi Optimal Security - O(1) Query Size – O(R+r) Search Time - O(nlogm) Space – O(R+r) False Positives n: dataset size, r: result size, m: domain size , R: query range size

23 ? Thank you!!! Questions??? Secure & Efficient Efficient Secure HighEfficiency Security High Low OPE DET PPE FHE ? Secure & Efficient Efficient ORAM Func/Pred Enc Secure We will present the experimental evaluation in the Poster Session