research

go back ↰

See a history of my research papers by checking out my papers page, google scholar page, or my DBLP page pages.

# current topics

These are topics that I am thinking about regularly now. If you want to know more about the projects I’m involved with or want to work together to solve open problems, reach out!

• Private Information Retrieval (PIR)
• Oblivious RAM (ORAM)
• Language Model Watermarking, especially ones which are undetectable

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

• Secret sharing, especially with variable access structures
• Applications of total function complexity to cryptography and how it captures problems which are not total
• Time-memory trade-offs, as well as the quantum variants
• Post-quantum cryptography, including analyzing security against quantum attacks and applications of homomorphic lattice encryption
• Quantum cryptography, and quantum pseudo-randomness, like these papers for example
• Building tools for AI Governance (e.g. Language Model Watermarking)
• Encrypted Database Processing (both attacks and constructions)

# 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(N^1/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.

   • Can this bound be extended to show the bandwidth-memory trade-off is s ⋅ p ≥ Ω(N)? Our proofs fail when p > N^1/2, but the best known construction matches the trade-off.
   • Can the bound be moved outside of the balls in bins model? Our techniques do not easily lend themselves to a compression proof, but the state of the art bounds are not in the balls in bins model.
   • What lower bounds, in any model, exist for k-round ORAM for constant k > 1? The best known constructions achieve overhead Õ(N^{1/(k + 1)}) overhead and client memory, which I conjecture is optimal (up to log factors).

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. 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: 2024-09