Processing Analytical Queries over Encrypted Data
Štěpán Kozák
Fl MUNI
14.10.2013
Štěpán Kozák (Fl MUNI)
4 □ ► <S
Processing Analytical Queries over Encrypte
14.10.2013 1/12
Motivation of search outsourcing
Industry needs to have a cheap storage with search as a service over the stored data.
Key advantages of clouds:
• Low initial investments a Low storage costs
• Very good scalability and flexibility
Problems of the outsourcing:
• Data can be sensitive!
• High cost of data transfer via network
<n><fl><8><5>    1 -00,0
^^Processing Analytical Queries over Encrypte 14.10.2013 2 / 12
MONOMI
MONOMI is the privacy-preserving extension over Postgre database. Supports 19 out of 22 TPC-H queries.
Štěpán Kozák (Fl MUNI)
Processing Analytical Queries over Encrypte 14.10.2013       3 / 12
MONOMI - Cryptography it uses
Encryption scheme	SQL operations	Leakage
Randomized AES	None	None
Deterministic AES	GROUP BY, EQUI-JOIN	Duplicates
OPE	ORDER BY, <, > predicates	Order
Paillier	a + b, SUM(a)	None
Processing Analytical Queries over Encrypte 14.10.2013       4 / 12
MONOMI - Example
Consider following Orders table with scheme:
OrderlD (int)   Price (float)
MONOMI stores the columns in the following way
a OrderlD encrypted with deterministic AES a Price encrypted with Paillier encryption
Štěpán Kozák (Fl MUNI)
□
Processing Analytical Queries over Encrypte
MONOMI - Example query 1
Consider issuing following query:
SELECT DrderlD FROM Orders WHERE Price > 100
How does it translate within MONOMI?
Štěpán Kozák (Fl MUNI)
4 □ ► <S
Processing Analytical Queries over Encrypte
14.10.2013       6 / 12
MONOMI - Example query 1
Original query:
SELECT DrderlD FROM Orders WHERE Price > 100
Transformed query:
SELECT OrderID_Det_AES FROM Orders
WHERE Price_OPE > Encrypt_0PE(100)
^Processing Analytical Queries over Encrypte 14.10.2013       7 / 12
MONOMI - Example query 2
Consider issuing following query:
SELECT SUM(Price) AS Total FROM Orders GROUP BY OrderlD HAVING Total > 100
How does it translate within MONOMI?
Štěpán Kozák (Fl MUNI)
4 □ ► <S
Processing Analytical Queries over Encrypte
14.10.2013       8 / 12
MONOMI - Example query 2
Original query:
SELECT SUM(Price) AS Total FROM Orders GROUP BY OrderlD HAVING Total > 100
Transformed query:
SELECT PAILLIER_SUM(Price_Paillier) AS Total FROM Orders
GROUP BY OrderID_Det_AES
<n> <S> <H <l >    1 -00,0 ^^Processing Analytical Queries over Encrypte 14.10.2013       9 / 12
MONOMI Optimizer
• Per-row precomputations
MONOMI materializes some precalculated values so it's possible to operate with them in an encrypted manner
• Space-efficient encryption
Especially Paillier cryptosystem uses very large integers (2048 bit) to store ciphertexts. MONOMI packs values from multiple columns in a single row and packs values from multiple rows, into a single Paillier plaintext.
Štěpán Kozák (Fl MUNI)
Processing Analytical Queries over Encrypte
14.10.2013       10 / 12
MONOMI Designer
Tool which computes recommended physical design
• What encryption should be used for particular columns
• Which computed columns to precompute
Takes as the input
• Sample query set
• Sample data set to be used
Štěpán Kozák (Fl MUNI)
Processing Analytical Queries over Encrypte
14.10.2013       11 / 12
MONOMI Performance
The authors say the over head is only 1.24x comparing to unencrypted DB (ranging from 1.03x to 2.33x).
However ...
They do not consider the communication cost.
Štěpán Kozák (Fl MUNI)
Processing Analytical Queries over Encrypte
14.10.2013       12 / 12
Questions
Štěpán Kozák (Fl MUNI)
Processing Analytical Queries over Encrypte
14.10.2013       13 / 12