Iterative Oblivious Pseudo-Random Functions and Applications
Erik-Oliver Blaß, Florian Kerschbaum, Travis Mayberry · Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security · 2022
We consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server.