Tarik Moataz - Encrypted Search: from Research to Real-World Systems
?
0 likes?60 views
- Encrypted search techniques like property-preserving encryption (PPE) and structured encryption (STE) allow searching on encrypted data while protecting confidentiality. - PPE maintains relations like equality between plaintext and ciphertext, enabling simple queries but is vulnerable to inference attacks. STE provides stronger security but has higher overhead. - While research prototypes demonstrate encrypted search is possible, deployment challenges remain around performance, functionality and security tradeoffs for real-world databases. Vendors are working to integrate encrypted search into database products.
![Property-Preserving Encryption (PPE)
Maintains a well-defined relation between the original data
?equality, order, orthogonality, prefix etc
15
Deterministic
encryption [BBN06]
=plaintext plaintext
=Z2hqc2Rh Z2hqc2Rh
Order preserving
encryption [BCLO09]
<16 20
<6372 18974
Prefix preserving
encryption [BBKN01]
?Secure Security
b2trbSxkZg b2trbSxkZgj2Rh?
Aroki Systems https://aroki.com](https://image.slidesharecdn.com/tarikmoatazcsnp20-200208230737/85/Tarik-Moataz-Encrypted-Search-from-Research-to-Real-World-Systems-15-320.jpg)
![PPE Security
Snapshot Adversary
20
PPE attacks
Inference Attacks [NKW15]
? sorting attack
? Cumulative attack
｀15
｀16
¨17
｀18
Extension 2 of Inference Attacks [GSNBR17]
? non-crossing attack
? w/ non-ideal OPE leakage attack
? known plaintext/ciphertext attacks
Extension 1 of Inference Attacks [DDC16]
? inter-column correlation attack
? intra+inter-column correlation attack
? leakage attacks
Extension 3 of Inference Attacks [BGCRS18]
? non-crossing attack
? w/ non-ideal OPE leakage attack
? known plaintext/ciphertext attacks
Up to 100% of data
recovery in the weakest
adversarial model
Aroki Systems https://aroki.com](https://image.slidesharecdn.com/tarikmoatazcsnp20-200208230737/85/Tarik-Moataz-Encrypted-Search-from-Research-to-Real-World-Systems-20-320.jpg)
![Structured Encryption (STE) [CK10]
DS
EDS
Setup 1k, DSEDS,
Token , qtk
tk
Query tk, EDSans
ans
!22Aroki Systems https://aroki.com](https://image.slidesharecdn.com/tarikmoatazcsnp20-200208230737/85/Tarik-Moataz-Encrypted-Search-from-Research-to-Real-World-Systems-22-320.jpg)
![Setup 1k, DSEDS,
Token , qtk
Query tk, EDSans
!23
DS
EDS
tk
ans
Structured Encryption (STE) [CK10]
Setup Leakage?
LS
Query Leakage?
LQ](https://image.slidesharecdn.com/tarikmoatazcsnp20-200208230737/85/Tarik-Moataz-Encrypted-Search-from-Research-to-Real-World-Systems-23-320.jpg)
![STE Cryptanalysis
30
STE attacks
Snapshot adversary
｀20 No known attack
STE attacks
Persistent adversary
｀12 IKK attack [IKK12]
? Requires 95% knowledge of
the user data
｀15 Count attack [CGPR15]
? Requires 80% knowledge of
the user data
｀16 Range attack [KKNO16]
? Distribution assumptions
STE attacks
Active adversary
｀16 File injection [ZKP16]
Query recovery - no data recovery](https://image.slidesharecdn.com/tarikmoatazcsnp20-200208230737/85/Tarik-Moataz-Encrypted-Search-from-Research-to-Real-World-Systems-30-320.jpg)
Tarik Moataz - Encrypted Search: from Research to Real-World Systems
- 1. Encrypted Search From Research to Real-World Systems Tarik Moataz CSNP Boston Chapter Jan 23rd 2020 AROKI? SYSTEMS
- 2. A little bit about me´ ? Currently ? Chief Technology Officer at Aroki Systems (https://aroki.com ) ? Associate Director of the Encrypted Systems Lab at Brown University ? Visiting Scientist at Brown University ? Background ? PhD in Computer Science with a focus on Encrypted Search ? Some of my Projects: ? Pixek - an e2e encrypted Photo App (https://pixek.com) ? Clusion - an open source Encrypted Search Java Library 2
- 3. 3
- 4. 4 4% 14,717,618,286* *Since 2013 Aroki Systems https://aroki.com
- 5. Why so Few? 5 ＾´because it would have hurt Yahoo¨s ability to index and search message data´￣ ！ J. Bonforte in NY Times Cost?Incompetence? Lazyness? Aroki Systems https://aroki.com
- 6. Once Upon a Time: No Encryption Memory App !6 TLS Full disk encryption Disk Adversary can see decrypted information in RAM Transparent database encryption Current Situation Aroki Systems https://aroki.com
- 7. Once Upon a Time: No Encryption Memory App !7 Disk Adversary sees nothing (Almost) Utopian Situation Aroki Systems https://aroki.com
- 8. Q:can we search on encrypted data? 8Aroki Systems https://aroki.com
- 10. 10 tk Encrypted Search Aroki Systems https://aroki.com
- 11. Cryptographic Building Blocks 11 Property-Preserving Encryption (PPE) Fully-Homomorphic Encryption (FHE) Functional Encryption (FE) Oblivious RAM (ORAM) Structured Encryption (STE) Aroki Systems https://aroki.com
- 13. Evolution from 2000-2019 13 Property-Preserving Encryption (PPE) Oblivious RAM (ORAM) Structured Encryption (STE) DET｀06 OPE｀09 OPE proofs｀11 CryptDB｀12 MS Always Enc｀15 PPE attacks｀15 Snapshot PPE｀16 ORAM｀92 Tree-based ORAM ｀12 SSE｀00 Efficient SSE｀06 STE｀10 Boolean SSE¨13 OXT; BlindSeer¨14 SQL¨17 Inference attacks¨12 Path ORAM｀13 Volume attacks ｀19 OblivP2P｀16 CS2¨12 Clusion; OpenSSE¨16 Distribution-Hiding PPE｀18
- 14. Q:what is property-preserving encryption? 14Aroki Systems https://aroki.com
- 15. Property-Preserving Encryption (PPE) Maintains a well-defined relation between the original data ?equality, order, orthogonality, prefix etc 15 Deterministic encryption [BBN06] =plaintext plaintext =Z2hqc2Rh Z2hqc2Rh Order preserving encryption [BCLO09] <16 20 <6372 18974 Prefix preserving encryption [BBKN01] ?Secure Security b2trbSxkZg b2trbSxkZgj2Rh? Aroki Systems https://aroki.com
- 16. PPE-based Encrypted Search Encryption 16 Employee Age Salary Sam 35 120K Lilly 30 135K Harry 35 135K HR Employees Table Deterministic Encryption Employee Age Salary eXR5bmR Z2hqc2Rh cHF1ZmJk d2Vyd3Nl bHdrdWV5 aGV5ZGJz ZGZzZGV Z2hqc2Rh aGV5ZGJz Encrypted HR Employees Table Aroki Systems https://aroki.com
- 17. PPE-based Encrypted Search Search 17 SELECT * FROM Employees Where Salary = 135k Q = Q Employee Age Salary eXR5bmR Z2hqc2Rh cHF1ZmJk d2Vyd3Nl bHdrdWV5 aGV5ZGJz ZGZzZGV Z2hqc2Rh aGV5ZGJz Encrypted HR Employees Table SELECT * FROM Employees Where Salary = aGV5ZGJz Q = Deterministic Encryption Aroki Systems https://aroki.com
- 18. ? Legacy-friendliness ? No changes to backends ? (Almost) Zero overhead ? Only encryption and decryption added to the client-side processing ? High functionality ? DTE and OPE enable the evaluation of complex queries 18 But what about security? PPE-based Encrypted Search Pros & Cons Aroki Systems https://aroki.com
- 19. Adversarial Models in Encrypted Search Background 19 Snapshot Adversaries Take (multiple) snapshot(s) of the encrypted data ?Device theft Persistent Adversaries Observe the entire state of the database including searches and updates ?Machine compromise ?Malicious host Active Adversaries Are persistent adversaries that CAN deviate from the protocol ?File injection
- 20. PPE Security Snapshot Adversary 20 PPE attacks Inference Attacks [NKW15] ? sorting attack ? Cumulative attack ｀15 ｀16 ¨17 ｀18 Extension 2 of Inference Attacks [GSNBR17] ? non-crossing attack ? w/ non-ideal OPE leakage attack ? known plaintext/ciphertext attacks Extension 1 of Inference Attacks [DDC16] ? inter-column correlation attack ? intra+inter-column correlation attack ? leakage attacks Extension 3 of Inference Attacks [BGCRS18] ? non-crossing attack ? w/ non-ideal OPE leakage attack ? known plaintext/ciphertext attacks Up to 100% of data recovery in the weakest adversarial model Aroki Systems https://aroki.com
- 21. Q:what is structured encryption? 21Aroki Systems https://aroki.com
- 22. Structured Encryption (STE) [CK10] DS EDS Setup 1k, DSEDS, Token , qtk tk Query tk, EDSans ans !22Aroki Systems https://aroki.com
- 23. Setup 1k, DSEDS, Token , qtk Query tk, EDSans !23 DS EDS tk ans Structured Encryption (STE) [CK10] Setup Leakage? LS Query Leakage? LQ
- 24. 24 File collection File1 File2 File3 File4 File5 File6 data crypto cryptosecurity data data data privacy privacy crypto data security privacy crypto File1 File3 File4 File6 File2 File4 File5 File2 File3 File6 Inverted index STE-based Encrypted Search Instance Aroki Systems https://aroki.com
- 25. 25 STE-based Encrypted Search Instance STE ? encryption data security privacy crypto File1 File3 File4 File6 File2 File4 File5 File2 File3 File6 Aroki Systems https://aroki.com
- 26. 26 STE-based Encrypted Search Instance ＾data￣Q = tk Think of the token as solution to a maze STE encryption ＾pt1￣, ＾pt2￣, ＾pt3", ＾pt4￣tk = Aroki Systems https://aroki.com
- 27. ? (Almost) Zero overhead ? Optimal search ? High functionality ? Exact, range and Boolean search ? Legacy-friendliness ? Recently solved - was unsolved for almost 20 years 27 But what about security? STE-based Encrypted Search Pros & Cons Aroki Systems https://aroki.com
- 28. STE Security Snapshot Adversary 28 Encrypted data structure No query 1st query 2nd query ´ Aroki Systems https://aroki.com
- 29. STE Security Persistent Adversary 29 Encrypted data structure No query 1st query 2nd query ´ Note that the adversary does not learn the content, but the memory locations Aroki Systems https://aroki.com
- 30. STE Cryptanalysis 30 STE attacks Snapshot adversary ｀20 No known attack STE attacks Persistent adversary ｀12 IKK attack [IKK12] ? Requires 95% knowledge of the user data ｀15 Count attack [CGPR15] ? Requires 80% knowledge of the user data ｀16 Range attack [KKNO16] ? Distribution assumptions STE attacks Active adversary ｀16 File injection [ZKP16] Query recovery - no data recovery
- 31. Tradeoffs: Performance vs. Security 31 Performance STE/SSE-based PPE-based FHE-based ORAM-based skFE-based pkFE-based Leakage Aroki Systems https://aroki.com
- 32. Tradeoffs: Functionality vs. Performance 32 SK-FE-based STE/SSE-based PPE-based FHE-based ORAM-based PK-FE-based Performance Functionality Aroki Systems https://aroki.com
- 33. Q:can encrypted search be deployed? 33Aroki Systems https://aroki.com
- 34. Why Isn¨t Encrypted Search Deployed? 34
- 35. End-to-End Encryption Messaging / Video 35 messaging video Aroki Systems https://aroki.com
- 36. Q: what about databases? 36Aroki Systems https://aroki.com
- 37. 37 PPE-based Always Encrypted End-to-End Encryption Databases STE-based (coming soon) AROKI? SYSTEMS Aroki Systems https://aroki.com PPE-based + Trusted hardware 2019