Concept - Querying an Encrypted Database

• Equality works: WHERE Did = 15 is sent as WHERE Did = 1000110111001110 (the encrypted value) (s.32).
• Range queries fail: WHERE Salary > 7000 cannot work because the encrypted values do not preserve the ordering of the original attribute (s.33).
• Fix (s.34-36): encrypt each row as one block $E(k,B)$ and keep an index per attribute that maps value ranges to index numbers (Eid 1-200 $\to$ 1, 201-400 $\to$ 2, 401-600 $\to$ 3, 601-800 $\to$ 4, 801-1000 $\to$ 5; names A,B $\to$ 1 … I,J $\to$ 5).

Worked example (s.36): query “eid < 300”.

1. Query processor requests all records with $I(eid)\le 2$ (s.36). Using the index table on s.34, index 2 covers Eid 201-400, so it overshoots.
2. Server returns those encrypted rows.
3. Processor decrypts all rows returned and discards those that do not match the original query (e.g. Eid 320, from the table on s.34-35).
4. It returns the plaintext rows to the user.

Further research solutions: CryptDB (link on s.37).

Related: Concept - Database Encryption. Appears in 05 Database Security - Chunk 01 (s.1-38).