On Wednesday, the second part (special encryption) of the school began.
First, Mor Weiss introduced us to format-preserving encryption (FPE) and explained the importance of tweakable block ciphers. Tweaks are randomized, public values that provide more randomness to block ciphers (kind of like salts in hash functions). Alexandra Boldyreva taught us about some inherent weaknesses of deterministic (i.e., equality-preserving) and order-preserving encryption. Hugo Krawczyk presented the details of ESPADA/OXT. Ben Fisch showed us how a tree of Bloom filters can be used to search on encrypted data (Blind Seer).
The favourite talk of Matthias was given by Benny Pinkas on Thursday. The title was "Searchable Encryption using ORAM" and the argument for choosing that approach over the others presented before, was that, for better security guarantees, it is desirable that the sequence of memory accesses to some encrypted data reveals no more information than the running-time. Oblivious RAM (ORAM) can be informally defined as follows:
A program $P$ is called "memory oblivious" if the memory access pattern $AP(x)$ (a sequence of $\verb!read!(a)$ or $\verb!write!(a,v)$ operations) is independent of the input $x=x(i,a,v)$ (which is a function of an instruction, address and value).
More formally an oblivious memory access pattern of $P$ shall satisfy:
$$
\forall x\neq y: \left\vert x\right\vert =\left\vert y\right\vert \Longrightarrow AP(x)\approx AP(y).
$$
The "ad-hoc solution" requires $\mathcal{O}(nm)$ time and $\mathcal{O}(m)$ memory upon storing $n$ encrypted pairs $(a, v)$ of equal size $m$ in memory using a randomized encryption scheme and going through every memory cell.
If the addresses don't match, re-encrypt and overwrite data cell, else, perform the instruction, encrypt and write results.
In this one-hour talk Pinkas then focused on the simplest tree based ORAM scheme, but gave possible ways to reduce the overhead i.e. by using ORAM schemes recursively.
The basic ORAM scheme consists of the server storing a full binary tree with $\log n$ levels and $n$ leaves, where each intermediate node contains $\log n$ data items.
The client randomly maps items to leaves, which results in $\mathcal{O}(n)$ storage of $\log n$ bits.
Accessing an item requires to traverse the path, from root to leaf, obtained from the position map. In each bucket along the path remove the data item if found and assign a new random leaf to it. Upon updating the client's position map write the updated item to the root node.
To prevent overflows perform the following oblivious operations in each level:
Choose two nodes at random and pop an item from both (non-empty) buckets, move the item downwards to next node on its path and perform a dummy write operation to the other descendant of the node to hide the operation.
To summarize: The server storage holds $\mathcal{O}(n \log n)$ data items, the client stores $n$ indices requiring $\mathcal{O}(n \log n)$ bits and each access costs $\mathcal{O}(\log^2 n)$ $\verb!read!$ and $\verb!write!$ operations.
Finally he discussed security limitations, efficiency problems and presented encrypted search using ORAM:
A straight-forward solution, given $n$ data items and $k$ keywords assigned to some, is to store $\leq nm$ tuples of the form ($k$, $\langle$data item associated with $k\rangle$ ) which in general requires storing each item multiple times.
Using two ORAMs - the first to store the documents indices given a keyword associated with it (="an inverted index list"), and the second ORAM to store the data items themselves, solves the problem of performing encrypted search more elegantly without the server being able to identify which item is being read nor whether a specific data item is accessed more often.
Sadly, Benny Pinkas also pointed to a result from Naveed's 2015 eprint report --often, sending the entire database to a client is more efficient than doing searchable encryption with ORAM-- so, as with the first part of the Winter School, there is still room for improvements!
We hope we were able to give you a flavour of how amazing this event was with these two posts. If not, or if you want to deepen in the talks, it's your lucky day: They are all uploaded! (We will post a comment when they are online)
 |
| Ecrypt-Net fellows in Caesarea |
A sincere "Toda!" to the organizers, Yehuda Lindell, Benny Pinkas, and Yonit Homburger, for such a pleasant school!
No comments:
Post a Comment