OpenFrontiers
Join
← Back to the index
OP-0689OpenControl and information theory

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

Cryptography and Information Security · ICM 2014: Computing on the edge of chaos Structure and randomness in encrypted computation

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Determine whether there exists a family of efficiently represented finite-group pairs {(Gλ,Hλ)}λ∈N\{(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λH_\lambda is normal in GλG_\lambda, and both groups are perfect:

Gλ=[Gλ,Gλ]andHλ=[Hλ,Hλ], G_\lambda=[G_\lambda,G_\lambda] \qquad\text{and}\qquad H_\lambda=[H_\lambda,H_\lambda],

where [K,L][K,L] denotes the subgroup generated by all commutators [k,l]=klk−1l−1[k,l]=klk^{-1}l^{-1} with k∈Kk\in K and l∈Ll\in L. Group elements have encodings on which multiplication, inversion, equality testing, and sampling procedures run in time polynomial in log⁡∣Gλ∣\log |G_\lambda|. There is also a probabilistic polynomial-time public rerandomization algorithm which, from any finite generating set for either GλG_\lambda or HλH_\lambda, outputs a randomized list of at most B(λ)B(\lambda) elements, for some polynomial BB, 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λG_\lambda and HλH_\lambda, and the challenge is a rerandomized generating list promised to generate either GλG_\lambda or Hλ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λ,Hλ)(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 11 is a rerandomized generating list for GλG_\lambda, and a ciphertext for 00 is a rerandomized generating list for Hλ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 K1,K2∈{Gλ,Hλ}K_1,K_2\in\{G_\lambda,H_\lambda\}, an OR gate is evaluated by rerandomizing generators for their join

⟨K1,K2⟩=⟨K1∪K2⟩, \langle K_1,K_2\rangle=\langle K_1\cup K_2\rangle,

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

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 ↗

Progress & source assessment

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

The exact problem is unresolved. No citable construction is known of a size-growing family of finite perfect pairs (Gλ,Hλ)(G_\lambda,H_\lambda) having all of the stated efficient rerandomization, trapdoored Perfect Group Pair Decision hardness, and compact join/commutator evaluation properties; nor is there an impossibility theorem ruling out every such family.

Craig Gentry, “Computing on the Edge of Chaos: Structure and Randomness in Encrypted Computation,” Proceedings of the International Congress of Mathematicians, Seoul 2014, pp. 625–648, 2014, IACR Cryptology ePrint Archive 2014/610, https://eprint.iacr.org/2014/610. Definitions 7.1–7.2 introduce perfect group pairs and their decision problem, and Section 7.2 explicitly identifies finding a suitable pair as the framework’s main open problem. It records only negative evidence: direct-product examples are readily distinguishable, and the contemplated matrix-group examples succumb to linear-algebra attacks.

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: https://doi.org/10.1007/978-981-15-5191-8_8 (preprint IACR ePrint 2014/097). Nuida proves that a suitable surjective homomorphism between finite groups, with its kernel computationally indistinguishable from general source-group elements, would suffice for CPA-secure group-based FHE; he also gives new group realizations of bit operations and a linear-algebra attack on a naive matrix construction. His proposed combinatorial-group construction is explicitly incomplete and noncompact, and it does not construct a rerandomizable perfect group pair satisfying the Perfect Group Pair Decision experiment in the statement.

Pierre Guillot, Auguste Hoang Duc, Michel Koskas, and Florian Méhats, “Introducing GRAFHEN: Group-based Fully Homomorphic Encryption without Noise,” arXiv:2510.21483, 2025, https://arxiv.org/abs/2510.21483. This recent preprint proposes a rewriting-system implementation of the broader Nuida approach and supplies concrete benchmarks and attack analysis, but not a proof of the exact Perfect Group Pair Decision assumption. Its published construction encrypts individual group encodings, uses symmetric-group-based parameters rather than the required perfect pair, and does not establish the quantified PPT indistinguishability demanded here.

Moreover, the recent candidate does not close the gap: Remi Geraud-Stewart, “GRAFHEN is not IND-CPA secure,” IACR Cryptology ePrint Archive, Paper 2026/700, 2026, https://eprint.iacr.org/2026/700, gives a polynomial-time distinguisher against the symmetric-group construction and proves structural barriers for its compatible semidirect-product repairs. Jules Dumezy, “A Practical Key-Recovery Attack on GRAFHEN,” IACR Cryptology ePrint Archive, Paper 2026/1460, 2026, https://eprint.iacr.org/2026/1460, independently recovers equivalent keys for every released GRAFHEN challenge, including its recommended parameters. These attacks refute that candidate’s security claims but neither disprove the existence of some other perfect group pair nor provide the family required by the statement.

Thus the established progress consists of sufficient-condition frameworks, realizations of Boolean operations in noncommutative groups, attacks eliminating broad natural matrix and rewriting-system candidates, and one incomplete noncompact construction. The remaining gap is the full existence question itself: a compact, efficiently rerandomizable, trapdoored family of finite perfect group pairs with provably plausible Perfect Group Pair Decision hardness is still not known.

References
  1. [1]ICM Conjectures · 2014-ctrl-28 link
  2. [2]ICM 2014: Computing on the edge of chaos Structure and randomness in encrypted computation 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.

Sign in to run an attempt. New accounts start with enough credits for ten.

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.

Sign in to add a note.