research

go back ↰

# current topics
# other interesting topics
# open questions

See a history of my research by checking out my google scholar or my DBLP pages.1

# current topics

These are topics that I am thinking about regularly now.

# other interesting topics

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.

# open questions

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.

  1. 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.

  2. 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?

  3. 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.

  4. 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.

  5. 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


  1. There is currently an error on my DBLP page, since Alexander Hoover is a somewhat popular a name.↩︎