Submit progress

on Craig Gentry, Homomorphic encryption a mathematical survey · 2022-ctrl-29

The statement

Determine whether there exists a family of fully homomorphic encryption schemes $\mathcal E=(\mathrm K,\mathrm E,\mathrm D,\mathrm V)$ , indexed by a security parameter $\lambda$ , with the following properties.

For every $\lambda$ and every possible output

(sk,ek,evk,\mathcal M,\mathcal C)\leftarrow \mathrm K(1^\lambda),

the message space $\mathcal M$ and valid-ciphertext space $\mathcal C$ are finite; $sk$ is the secret decryption key, $ek$ is the encryption key, and $evk$ is a public evaluation key. The randomized encryption algorithm $\mathrm E(ek,m;r)$ maps each $m\in\mathcal M$ to an element of $\mathcal C$ , the deterministic decryption algorithm $\mathrm D(sk,c)$ maps $\mathcal C$ to $\mathcal M$ , and

\mathrm D(sk,\mathrm E(ek,m;r))=m

for every $m\in\mathcal M$ and every encryption randomness $r$ . The algorithms are polynomial-time in $\lambda$ , with evaluation time also polynomial in the description length of the gate being evaluated.

There is a functionally complete set $\Gamma$ of gates on $\mathcal M$ such that evaluation is unbounded: for every $t$ -ary $f\in\Gamma$ and every $c_1,\ldots,c_t\in\mathcal C$ ,

\mathrm V(evk,f,c_1,\ldots,c_t)\in\mathcal C

and

\mathrm D\!\left(sk,\mathrm V(evk,f,c_1,\ldots,c_t)\right) =f\!\left(\mathrm D(sk,c_1),\ldots,\mathrm D(sk,c_t)\right).

Thus gates from $\Gamma$ may be evaluated correctly in arbitrary finite compositions, while the bit length of a ciphertext and the running time of decryption are bounded by polynomials in $\lambda$ that are independent of the number of preceding evaluations.

The scheme is IND-CPA secure: in the experiment a challenger samples the key tuple and a uniformly random bit $b$ ; after receiving all public key material, any probabilistic polynomial-time adversary may adaptively submit pairs $(m_{i,0},m_{i,1})\in\mathcal M^2$ and receives $\mathrm E(ek,m_{i,b};r_i)$ for fresh independent randomness $r_i$ (or obtains these through a left-or-right encryption oracle when $ek$ is secret), and its advantage

\left|\Pr[b'=b]-\frac12\right|

in outputting the hidden bit is negligible in $\lambda$ .

Finally, for every $\lambda$ and every possible key tuple output by $\mathrm K$ , one of the binary ciphertext operations supplied by evaluation equips $\mathcal C$ with a group law $\star$ , and the finite group $(\mathcal C,\star)$ is nonsolvable. Equivalently, if $\mathcal C^{(0)}=\mathcal C$ and $\mathcal C^{(i+1)}=[\mathcal C^{(i)},\mathcal C^{(i)}]$ is the commutator subgroup, then $\mathcal C^{(i)}\ne\{1\}$ for every $i\ge 0$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.