go back ↰
See a history of my research by checking out my google scholar or my DBLP pages.1
These are topics that I am thinking about regularly now.
Below a list of topics that I’ve read about and would like to work on again in the future. For some, I have specific questions I’d like to attack, and for others, my interest is more open ended.
I’d like to see these questions resolved. If you’re interested in attacking any of them, please shoot me a message, and I can give you more thoughts/details about them. Or if any have been closed, please let me know! I’d be excited to see how they are resolved.
Our paper proves, in a balls in bins model, that an ORAM with p = O(N1/2) overhead running in a single round requires at least s = Ω(N/p) bits of client memory. But there are some very simple follow up questions that we failed to answer with our technique.
This paper introduces the notion of (s,ℓ)-security for adversaries observing a server for s windows of length ℓ. It also proves that (s,ℓ)-security requires Ω(log n) overhead for s ≥ 3 and ℓ ≥ 1 or for s ≥ 4 and ℓ ≥ 0. Prior work had already shown the overhead is Θ(log ℓ) for s = 1 with a bound and construction. There is also a simple construction with Θ(1) overhead for (2,0)-security. But what is the best construction or lower bound for (2,ℓ)-security for ℓ ≥ 1 and for (3,0)-security?
What is the best bounded-memory attack and lower bound for distinguishing a truncated permutation from a random function? Prior work summarizes the attacks and bounds for the setting with unbounded memory, which is solved completely. Even a conjectured trade-off is not obvious, because the optimal attack does not require remembering every past input.
What is the best attack for distinguishing the XOR of two random permutations from a random function? In the appendix of this paper, they bound the distinguishing advantage with q samples by (q/N)1.5, but I’m unaware of a matching attack.
Can the bounded-memory distinguishing bound for a random permutation versus a random function be slightly improved? This paper proves that the advantage for an m-bit attack with q samples is at most O(mqlog q/N), but the best attack is Ω(mq/N). I suspect the log q is just an artifact of the proof technique and a more direct technique will remove it, especially because there are other bounds which bound the divergence by O(mq/N) or O(mq/Nlog N) and apply Pinsker’s inequality.
Last updated: 2023-11