OP-0690OpenControl and information theory

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

Cryptography and Information Security · ICM 2022: Craig Gentry, Homomorphic encryption a mathematical survey

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem 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$ .

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

Construct a security-parameter-indexed family of finite groups $\widetilde G_\lambda$ , none of which is a Coxeter group, together with surjective homomorphisms

\pi_\lambda:\widetilde G_\lambda\longrightarrow S_5,

such that the following conditions hold. Multiplication, inversion, uniform sampling, and bounded-length representation in $\widetilde G_\lambda$ are computable in polynomial time; a secret trapdoor permits polynomial-time evaluation of $\pi_\lambda$ ; public data include lifts to $\widetilde G_\lambda$ of the constants in a group-word realization of the NAND gate in $S_5$ ; and the public key permits sampling every fiber of $\pi_\lambda$ . Prove that, given all public parameters and the public kernel-sampling data, every probabilistic polynomial-time algorithm has negligible advantage in distinguishing a uniform sample from $\ker\pi_\lambda$ from a uniform sample from $\widetilde G_\lambda$ .

Source reference: Koji Nuida, “Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory,” in International Symposium on Mathematics, Quantum Theory, and Cryptography, Mathematics for Industry 33, Springer, 2021, pp. 57–78, open problem following the finite-Coxeter-group analysis in Section 5.3, DOI: https://doi.org/10.1007/978-981-15-5191-8_8; IACR ePrint 2014/097: https://eprint.iacr.org/2014/097.

Question 2

Let $G$ be a finite nonabelian group in which a functionally complete set of Boolean gates is realized by group words, let $H$ be a finite nonabelian group, and let $P_0$ be a finite presentation of $G\times H$ . Construct and analyze a polynomial-time randomized sequence of Tietze transformations that maps $P_0$ to a public presentation $P$ of an isomorphic group $\widetilde G$ , while the transformation transcript is kept secret. Prove that the transcript permits efficient computation of the projection

\pi:\widetilde G\cong G\times H\longrightarrow G,

but that, without the transcript, every probabilistic polynomial-time adversary given $P$ and polynomially many independent uniform samples from $\ker\pi$ has negligible advantage in distinguishing a fresh uniform sample from $\ker\pi$ from a uniform sample from $\widetilde G$ . In particular, determine a sufficient distribution and number of Tietze transformations for this kernel-indistinguishability property.

Source reference: Koji Nuida, “Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory,” in International Symposium on Mathematics, Quantum Theory, and Cryptography, Mathematics for Industry 33, Springer, 2021, pp. 57–78, first explicitly listed problem in the Tietze-transformation approach of Section 5.4, DOI: https://doi.org/10.1007/978-981-15-5191-8_8; IACR ePrint 2014/097: https://eprint.iacr.org/2014/097.

Question 3

Let $P$ be a finite presentation of a finite group $\widetilde G\cong G\times H$ obtained from a standard direct-product presentation by a secret randomized sequence of Tietze transformations. Construct an algorithm that receives only $P$ and two words in its generators, together with a polynomial $p$ , such that for every security parameter $\lambda$ and all $P$ -words $u,v$ of length at most $p(\lambda)$ , the algorithm runs in time polynomial in $\lambda$ and outputs a $P$ -word of length at most $p(\lambda)$ representing the product $uv$ in $\widetilde G$ . The same bound must continue to hold after arbitrarily many repeated multiply-and-reduce operations; the algorithm is not given the secret Tietze-transformation transcript or the hidden projection $\widetilde G\to G$ .

Source reference: Koji Nuida, “Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory,” in International Symposium on Mathematics, Quantum Theory, and Cryptography, Mathematics for Industry 33, Springer, 2021, pp. 57–78, second explicitly listed problem in the Tietze-transformation approach of Section 5.4, DOI: https://doi.org/10.1007/978-981-15-5191-8_8; IACR ePrint 2014/097: https://eprint.iacr.org/2014/097.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The exact existence problem is unresolved. No verified construction is known that simultaneously has unbounded compact fully homomorphic evaluation, IND-CPA security, and a finite nonsolvable valid-ciphertext group for every generated key. Conversely, no impossibility theorem rules out every such nonsolvable group.

Craig Gentry, “Homomorphic Encryption: A Mathematical Survey,” Proceedings of the International Congress of Mathematicians 2022, vol. 2, 2022, pp. 956–1006, DOI 10.4171/ICM2022/165. Section 3.5 records that there were neither general attacks nor plausibly secure constructions for nonsolvable-group homomorphic encryption, identifies necessary attacks to avoid, and Section 5 reports the conditional group-theoretic approach below. This states the gap but does not resolve it.

Koji Nuida, “Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory,” in International Symposium on Mathematics, Quantum Theory, and Cryptography, Mathematics for Industry 33, Springer, 2021, pp. 57–78, DOI 10.1007/978-981-15-5191-8_8; preprint IACR ePrint 2014/097. Theorem 1 proves a conditional construction: a finite surjection $\widetilde G\to G$ , a group realization of a functionally complete gate set in $G$ , efficient group operations, and computational indistinguishability of $\ker\pi$ from $\widetilde G$ imply CPA-secure FHE. Proposition 1 supplies NAND realizations in nonabelian finite simple groups. The proposed Coxeter-group instance is nevertheless noncompact because $\widetilde G$ is infinite or its word representatives grow without bound, and the paper explicitly leaves a finite compact secure realization open.

Koji Nuida, “On Compression Functions over Groups with Applications to Homomorphic Encryption,” Journal of Algebra and Its Applications, forthcoming, DOI 10.1142/S0219498827500642; arXiv:2208.02468. This resolves a narrower functionality component by constructing an optimal compression word over $A_5$ and proving nonexistence over every other group of order at most 60. It does not construct or prove IND-CPA security for a ciphertext group.

Maya Gusak and Chris Leonardi, “Post-Quantum Fully Homomorphic Encryption with Group Ring Homomorphisms,” IACR Cryptology ePrint Archive, 2023/1450, 2023, direct URL. This studies the Ostrovsky–Skeith/nonabelian-group route and proves that efficiently decomposable semisimple group rings cannot satisfy the required security framework. The result eliminates a broad candidate family but not arbitrary nonsolvable finite groups.

Pierre Guillot, Auguste Hoang Duc, Michel Koskas, and Florian Méhats, “Introducing GRAFHEN: Group-based Fully Homomorphic Encryption without Noise,” arXiv, 2025, arXiv:2510.21483; IACR ePrint 2025/1907. GRAFHEN proposes a compact group-word construction over symmetric groups and realizes Boolean addition and multiplication by group words. Its security section gives attack analysis and computational evidence, not a reduction establishing IND-CPA security.

Rémi Géraud-Stewart, “GRAFHEN is not IND-CPA secure,” IACR Cryptology ePrint Archive, 2026/700, 2026, direct URL. Theorem 1 constructs a polynomial-time cross-reduction distinguisher with nonnegligible advantage for generic GRAFHEN keys; the paper also extends the attack to the public reduction-oracle setting and proves barriers to repairing the symmetric-group semidirect-product action. Thus GRAFHEN does not supply the construction required by the statement, but this cryptanalysis is scheme-specific and is not a universal impossibility theorem.

Established progress therefore covers (i) functionally complete Boolean computation inside nonabelian simple groups, (ii) a conditional reduction of security to a hidden-kernel subgroup-membership problem, and (iii) attacks excluding several natural matrix, group-ring, and rewriting-system instantiations. What remains open is either to instantiate the conditional framework with finite compact ciphertext groups and a rigorous IND-CPA reduction, or to prove that every possible nonsolvable-group instantiation is impossible.

References

[1]ICM Conjectures · 2022-ctrl-29 link
[2]ICM 2022: Craig Gentry, Homomorphic encryption a mathematical survey link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Source & evidence

2022-ctrl-29

ICM snapshot retrieved 8 September 2026. Source review state: unreviewed. The status text and 3 remaining questions are reproduced with attribution; no independent proof audit has been performed here.

Source date: 2026-08-18
Imported: 2026-09-08

How we use sources ↗

Record

Difficulty: HardResisted sustained effort by specialists.
Posed: 2022
Source: Curated problem listICM ConjecturesICM 2022: Craig Gentry, Homomorphic encryption a mathematical surveyOriginal statement ↗
Citation: ICM 2022: Craig Gentry, Homomorphic encryption a mathematical survey
Added: 5 Nov 2026
Views: 0

Fields

Control and information theory