Jane Street

P1: Suppose I have a secret list of positive integers: (v_1, v_2, ..., v_n). You can't see my list, but you can ask me dot product questions. Give me any list of numbers (x_1, x_2, ..., x_n) of the same length, and I'll tell you x_1 \cdot v_1 + x_2 \cdot v_2 + ... + x_n \cdot v_n. Figure out my secret list using as few questions as possible.

Curious to see how this problem has surprising connections to lattice-based cryptography and fully homomorphic encryption? Learn more here.

P2: Suppose you have many black-box majority functions on three binary inputs. Is it possible to chain them to construct a majority function on 2025 binary inputs? You can duplicate inputs and outputs of the black-box function for free. (From TST 2018/4)

P3: The CKKS fully homomorphic encryption scheme gives a way to encrypt vectors in {C}^{32{,}768} such that anyone can add encrypted vectors elementwise, multiply encrypted vectors elementwise, or "rotate" ciphertexts \left(z_1, z_2, \ldots, z_{65536}\right) \mapsto\left(z_i, z_{i+1}, \ldots, z_{i-1}\right) by any "offset" i. Suppose that:

• encrypted addition takes 4 microseconds
• encrypted multiplication takes 5600 microseconds
• encrypted rotation takes 6100 microseconds

Find a fast arithmetic circuit that computes the Fourier transform on an encrypted vector, conditioned on the multiplicative depth of the circuit being at most three.

P4: Are there any nontrivial solutions to the system of equations

\begin{align*}
a+b+c+d &\equiv 0 \quad(\bmod p) \\
a^2+b^2+c^2+d^2 &\equiv 0 \quad(\bmod p) \\
a^3+b^3+c^3+d^3 &\equiv 0 \quad(\bmod p)
\end{align*}

for p=2^{127} - 1?

P5: The programming language circom allows users to prove that they have an assignment to a set of variables satisfying a system of quadratic constraints

\begin{aligned}
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
&\vdots \\
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
\end{aligned}

without revealing the complete assignment of variables¹. Some of the variables are set to be public, Some of the variables are set to be public, and the rest are set to be private

(a) Give a system of quadratic constraints in private variables x, s_1, s_2, s_3, \ldots that has a satisfying solution if and only if x \in\left\{0,1, \ldots, 2^{64}-1\right\}.

(b) Give a system of quadratic constraints in private variables x, s_1, s_2, s_3, \ldots that has a satisfying solution if and only if r \ne 1.

(c) Give a system of quadratic constraints in one public variable n \in\left\{2,3, \ldots, 2^{64}-1\right\} and private variables s_1, s_2, s_3, \ldots such that finding a satisfying solution to the system of quadratic constraints is equivalent to finding a nontrivial factorization of n.

(d) Give a system of quadratic constraints in 64 public variables \ell_0, \ell_1, \ldots, \ell_{63} \in\left\{0,1, \ldots, 2^{64}-1\right\} and private variables s_1, s_2, s_3, \ldots such that finding a satisfying solution to the system of quadratic constraints is equivalent to finding a nontrivial factorization of \ell_0+2^{64} \ell_1+2^{128} \ell_2+ \cdots+2^{4032} \ell_{63}.