Amplifier polynomials for FHE (proposed by Brian and Colin)

Let $d=320$, and consider the affine space $V := \mathbb{F}_2^d$ (as an affine variety). We would like to find a small-ish $k$ (any $k<1000$ should be fine) and a sequence of polynomial maps (i.e. morphism of algebraic varieties) $f_1,f_2,\dots,f_k\colon V \rightarrow V$ such that each $f_i$ is quadratic and the composed polynomial $f := f_1 \circ f_2 \circ \dots \circ f_k$ is an amplifier in the following sense:

• Let $p_1,p_2,\dots,p_d$ be iid Bernoulli(0.60) random variables, and form the point $p=(p_1,p_2,\dots,p_d)$. Then with high probability $f(p)$ should have at least $75\%$ of its coordinates equal to $1$.
• Let $p_1,p_2,\dots,p_d$ be iid Bernoulli(0.40) random variables, and form the point $p=(p_1,p_2,\dots,p_d)$. Then with high probability $f(p)$ should have at most $25\%$ of its coordinates equal to $1$.

For security reasons, we would also like each $f_i$ to not be low-rank, in the sense that we want the matrix $$\left(\frac{\partial^2}{\partial x_k \, \partial x_\ell}(L \circ f_i)\right)_{1\le k,\ell\le d}$$ to have rank $>128$ for each $i$ and for each linear form $L\colon V \rightarrow \mathbb{F}_2$ (here $L$ must be not identically zero). (Without this assumption, we could just take each $\pi_j \circ f_i$ to be the $\mathsf{MAJORITY}$ function of $3$ randomly-chosen input coordinates.)

Motivation

A solution to this problem could potentially be used to build a new FHE scheme.

The encryption scheme is simple: a bit is encoded as a vector $v \in \mathbb{F}_2^d$. If the bit is 0, then $v$ must have at least 75% of its entries equal to zero; if 1, at least 75% of its entries must equal 1. The secret key is an invertible $d$-by-$d$ matrix $S$, and the encryption of $v$ is simply $S v$.

In other words: the encryption of $0$ is $(0, 0, ..., 0)$ “with noise”, and similarly for $1$.

The problem: homomorphic operations (however they are implemented) will create “noise”, increasing the error ratio until the message cannot be decoded.

An “amplifier polynomial” (conjugated by the linear transformation $S$) would enable noise reduction without decryption – just like bootstrapping in traditional FHE.

This problem does not solve the problem of security: We need to know that the “evaluation keys” (for example the amplifier polynomial, conjugated by $S$) do not leak information about $S$. The low-rank condition in the problem is intended to thwart a known attack, but there may be further, unknown attacks not addressed by this problem.