What a lovely hat

Paper 2026/1460

A Practical Key-Recovery Attack on GRAFHEN

Abstract

We give a structural cryptanalysis of GRAFHEN, a proposed group-based fully homomorphic encryption scheme whose public rewriting rules hide a group representation used for decryption. Under the designers' isomorphism hypothesis, the compatible representations in a finite target $T$ form one free $\mathrm{Aut}(T)$-orbit. Thus every representative induces the same zero predicate. For a fixed publication, the published key-class expression is the expected trial count of uniform verified sampling rather than a lower bound on reconstruction work. More generally, a homomorphism $\psi$ gives the correct zero predicate exactly when $\ker\psi\cap\Gamma\subseteq\Lambda$, where $\Gamma$ is the ciphertext set of the presented group and $\Lambda$ its zero-ciphertext subgroup. After reconstruction, we give a finite-sample distinguishing bound for independent zero queries and an independent challenge. It requires neither uniform sampling nor generation of the full zero subgroup. For matched query and challenge distributions, the target alone puts the advantage above $1/2$ after $14$ queries at degree $7$ and $26$ at degree $11$. Our attack, HEnbane, combines automorphism-reduced search over complete group elements with algebraic forcing from short public consequences. At the level of a generic algorithmic schema, an uncapped whole-element branching fallback makes reconstruction complete for every finite effectively enumerable target with enumerable element-orbit representatives. The released software instantiates this schema for its supported symmetric-group targets and the fixed target $\mathrm{PSL}_2(343)$. The two-seed force chains used by all supplied instances are a fast path rather than a completeness assumption. It decrypts all five released symmetric challenges, with a slowest ten-run mean of $25.4$ seconds. It also solves the author-supplied $\mathrm{SL}_2(343)$ challenge for the revised parameters by reconstructing in the $\mathrm{PSL}_2(343)$ quotient and recovering the ten central lift signs over $\mathbb F_2$, averaging $37.7$ seconds end to end without exact-order hints.

Note: Improve the attack.