Submit progress

on Computing on the edge of chaos Structure and randomness in encrypted computation · 2014-ctrl-28

The statement

Determine whether there exists a family of efficiently represented finite-group pairs $\{(G_\lambda,H_\lambda)\}_{\lambda\in\mathbb N}$ , of unbounded size as the security parameter $\lambda$ grows, together with public group descriptions and a secret trapdoor, satisfying all of the following conditions.

For every $\lambda$ , the subgroup $H_\lambda$ is normal in $G_\lambda$ , and both groups are perfect:

G_\lambda=[G_\lambda,G_\lambda] \qquad\text{and}\qquad H_\lambda=[H_\lambda,H_\lambda],

where $[K,L]$ denotes the subgroup generated by all commutators $[k,l]=klk^{-1}l^{-1}$ with $k\in K$ and $l\in L$ . Group elements have encodings on which multiplication, inversion, equality testing, and sampling procedures run in time polynomial in $\log |G_\lambda|$ . There is also a probabilistic polynomial-time public rerandomization algorithm which, from any finite generating set for either $G_\lambda$ or $H_\lambda$ , outputs a randomized list of at most $B(\lambda)$ elements, for some polynomial $B$ , that generates the same group.

Define the Perfect Group Pair Decision problem for this family as follows. The public input contains descriptions and generating sets for $G_\lambda$ and $H_\lambda$ , and the challenge is a rerandomized generating list promised to generate either $G_\lambda$ or $H_\lambda$ . It must be computationally infeasible for every probabilistic polynomial-time algorithm, given only the public input, to decide which of the two groups the challenge generates with nonnegligible advantage over random guessing. In contrast, the secret trapdoor associated with $(G_\lambda,H_\lambda)$ must allow a probabilistic polynomial-time algorithm to distinguish the two promised cases with all but negligible error.

The required family must therefore support the following noise-free encryption of bits. A ciphertext for $1$ is a rerandomized generating list for $G_\lambda$ , and a ciphertext for $0$ is a rerandomized generating list for $H_\lambda$ ; the Perfect Group Pair Decision hardness condition must make these two ciphertext ensembles semantically secure, while the trapdoor permits decryption. For ciphertexts generating unknown groups $K_1,K_2\in\{G_\lambda,H_\lambda\}$ , an OR gate is evaluated by rerandomizing generators for their join

\langle K_1,K_2\rangle=\langle K_1\cup K_2\rangle,

and an AND gate is evaluated by rerandomizing generators for $[K_1,K_2]$ . Thus the construction must permit compact evaluation of arbitrarily large monotone Boolean circuits: the join is $G_\lambda$ exactly when at least one input group is $G_\lambda$ , and, because $H_\lambda\trianglelefteq G_\lambda$ and both groups are perfect, the commutator subgroup is $G_\lambda$ exactly when both input groups are $G_\lambda$ .

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.