home.md

@@ -26,4 +26,83 @@ They even use the same primitive implementations - when a constructions needs, f
 We have run extensive simulations using various data sizes, distributions, query sets and other parameters.
 
 Let describe what ORE schemes we analyzed.
-The firs one is a scheme by Alexandra Boldyreva where upon encrypting a number one splits 
+
+The first one is a scheme by Alexandra Boldyreva where the encryption algorithm works by splitting the domain into two parts according to a value sampled from the hypergeometric distribution, and splitting the range in half recursively. 
+When the domain size contains a single element, the corresponding ciphertext is sampled uniformly from the current range.
+
+The second scheme by Nathan Chenette works by representing the number as a bit string and encrypting each bit substring using PRF from the first bit to the whole string and adding the next bit to it.
+The comparison works by going through the pairs of encyrptions looking for the pair when one is greater than the other by one.
+
+The scheme by Kevin Lewi and David Wu improves the idea by doing this operations in blocks, not bits.
+This way the user can tune security to performance ratio choosing the block size.
+
+The scheme by David Cash improves the algorithm even further.
+Instead of using PRF they use randomized property-preserving hash.
+User still looks for a pair when one ciphertext is greater than the other by one, but this time one needs to compare all ciphers of one number if all ciphers of the other, resulting in a better security but quadratic complexity.
+
+The last controversial scheme by Florian Kershenbaum is stateful but frequency hiding.
+Each new encryption results in a new ciphertexts, but it comes at an expense of maintaining a state proportional to the database size.
+
+Let me now turn to the values we have measured.
+We intentionally did not measure the wall-clock time.
+It would be inaccurate and very hardware-dependent.
+Instead we count the number of times the scheme calls a primitive.
+Along with that we count the ciphertext or state size (whichever is greater) and rank the schemes by their leakage.
+
+This is how the full table looks like.
+I will not go into the specifics.
+Note that most values depend on $`n`$ the number of bits in the number.
+In the evaluation, we have the same table but with numbers instead of formulas.
+
+Let me know turn to protocols.
+Here are the five protocols we analyzed.
+
+The first one is a B+ tree coupled with each of the ORE scheme from the previous slide.
+We have implemented the B+ tree including its non-trivial deletion algorithm from scratch to enable best instrumentation for benchmark purposes.
+B+ protocol generally behaves the same with any ORE scheme inside.
+Its performance depends on ORE's performance and ORE's ciphertext size which defines the number of items in a block thus affecting the fanout.
+
+Kerschbaum's protocol works over the array of symmetrically encrypted values modularly shifted by some random offset.
+Upon query the client performs an interactive binary search over rotated structure looking for the endpoints.
+The server returns the values between the endpoints.
+
+Partial Order-Preserving Encoding protocol works over buffer trees.
+Upon insertion all values always go to the root.
+Upon query the root is being interactively restructured.
+Thus, for the first query the structure is large unsorted buffer.
+After enough queries the structure looks like a B-tree.
+That is why we differentiate between the first query (cold start) and the subsequent (warm start).
+
+Logarithmic-BRC by Ioannis Demertiz creates an SSE dictionary from the data.
+The dictionary maps keywords to documents.
+The keyword is a range, and the documents are the values.
+The strong side of this protocol is that it scales not with the data, but with the query result size.
+
+Last protocol is baseline - ORAM.
+We used PathORAM as ORAM and B+ tree as the underlying structure.
+A B+ tree node is a block of ORAM.
+To answer a query a server traverses a B+ tree, but each time the node is accessed, this access goes through the ORAM.
+
+The values we measured are again not a wall-clock time.
+We have tracked the number of I/O requests that the protocol makes.
+We also tracked the communication amount - the number of messages and its size.
+As with ORE schemes, we rank the protocols by their security.
+
+This time most of the values depend on the data size.
+Some constantly, linearly, logarithmically or square-logarithmically.
+Logarithmic-BRC is unique in a way that it depends on the result size.
+Again, this same table with numbers instead of complexities is in the paper.
+
+I am going to skip the animation.
+Here are some of the plots from evaluation.
+This show relative performance of the protocols on different tasks.
+You can notice that B+ tree works the same for different OREs except when ORE ciphertext is large.
+The cost of interactive protocols vs non-interactive is apparent.
+Lastly, the ORAM, although the baseline, is performing in-line with some other protocols.
+
+Finally, we have shown all pros and cons of each of the constructions, and we have found a use case for each.
+We have open-sourced their implementations and fixed some bugs, including security vulnerabilities.
+For some constructions we even improved their performance.
+Lastly, we show some non-obvious positive results for Logarithmic-BRC and ORAM.
+
+Thank you, an I am happy to answer any questions.
\ No newline at end of file