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.

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.

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.

Threshold encryption

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