Problems

Problems marked with (*) are problems that are more amenable to being viewed as a self-contained math problem with a short statement, that don’t require as much background reading in crypto or otherwise.

If you make progress on any of these, send us a message at [email protected].

Fully homomorphic encryption

• Fast polynomial multiplication and decomposition (*) [Research Workshop 2024]. We’d like an analog of fast multiplication in $\mathbb{Z}[x] / (2^m, X^{2^n+1})$ for implementation on hardware.

• Algebraic digit extraction (*) [Research Workshop 2025]. How can we build a polynomial circuit that computes a specific function whose input is an integer in $[0,p^n)$? The goal is to build an efficient circuit for integer bootstrapping in FHE. Some ideas towards a solution are given here.

• Amplifier polynomials for FHE (*) [Research Workshop 2025]. How can we construct sequence of polynomial maps satisfying some mathematical properties? A solution to this problem could potentially be used to build a new FHE scheme.

• Matrix challenge (for breaking obfuscation) (*) [Research Workshop 2025]. How can we recover secret $d \times d$ matrices from a determinant of their formal linear combination? Solving this problem would make progress toward breaking a proposed obfuscation scheme for affine determinant programs.

• Parallelizing blind rotation (*) [Research Workshop 2025]. How can we efficiently calculate several blind rotations in parallel? This calculation would let us make a certain fully homomorphic encryption scheme (TFHE) more efficient.

Oblivious RAM, private information retrieval, etc.

• Improved bounds for Path ORAM [Research Workshop 2024]. The Path ORAM protocol is a neat simple procedure for hiding memory access problems, based on placing the memory blocks into a tree. It has a bucket size $Z$ in the protocol, and it’s been proved when $Z=5$ that the protocol works with high probability. However, empirical evidence suggests it should work for $Z=3$ and $Z=4$ too. Can you prove it?

• Private information retrieval problems [Research Workshop 2024]. A few directions for improvements on the private information retrieval (PIR).

Zero-knowledge proofs, SNARKs etc.

• Outsourcing ZK proof generation to an untrusted server [Research Workshop 2024]. This could be done in theory with FHE, but we’d like a practical way to do this.

• Fast computation of Bézout polynomials (*) [Research Workshop 2024]. Given distinct field elements $a_1$ through $a_m$, let $z = \prod (X-a_i)$, and $z'$ is derivative. We’d like a fast algorithm to compute polynomials $s$ and $t$ such that $s \cdot z + t \cdot z' = 1$. This is motivated by a zkSNARK application in which $(s,t)$ provide a succinct proof that $(a_1, \dots, a_m)$ has no repeated elements.

• A new algebraic hash function [Research Workshop 2024]. Try to break a proposed SNARK-friendly hash function with a simple definition.

• Range checks (*) [Research Workshop 2024]. Optimize the number of operations needed for a range-check circuit. We have some progress for public y with verifier precomputed and interactive approaches.

• Non-native arithmetic and CRT codes [Research Workshop 2024].

• (Solved) Proximity gaps up to unique decoding (*) [Research Workshop 2024]. This conjecture was resolved by a counterexample found at the research workshop.
• (Solved) Testing a system of polynomials for roots (*) [Research Workshop 2024]. We found references for this problem which are documented in this page.

• Sharding protocol efficiency [Research Workshop 2025]. Can you improve the efficiency of a sharding protocol that was proposed for the Ethereum blockchain? Specifically, can you decrease the amount of data that must be sent for coefficients and commitments?

• (Solved) Substring matching [Research Workshop 2025]. Can you write down an efficient arithmetic circuit to prove that a bunch of strings $Y^1, Y^2, ..., Y^r$ are substrings of a given string $X$? Two solutions are given here and here.

Threshold encryption

• Efficient weighted threshold signatures (*)[Research Workshop 2024]. Find an efficient scheme for weighted threshold signatures.

Other

• Sparse matrices for LPN (*) [Research Workshop 2025]. Find an infinite family of matrices in $\mathbb{F}_2^{n \times m}$ whose eigenvalues have many nonzero entries. The motivation for this problem is learning parity with noise (LPN).