GRAFHEN is not IND-CPA secure

Remi Geraud-Stewart

Paper 2026/700

GRAFHEN is not IND-CPA secure

Remi Geraud-Stewart

, Amazon

Abstract

GRAFHEN is a recently proposed noise-free fully homomorphic encryption scheme based on rewriting systems in symmetric groups. We show that GRAFHEN is not IND-CPA secure by constructing a polynomial-time cross-reduction distinguisher whose advantage can be amplified to overwhelming via d! scrambled cross-evaluations. We prove an unconditional information-theoretic lower bound using the near-uniformity of word maps on symmetric groups. We further prove structural barriers to repair: for G= Sn, any semidirect product action compatible with decryption reduces to conjugation, collapsing back to the original attack.

Note: v4: Appendix addressing minor comments. v3: Extended in the NF-oracle model. v2: Revised to address feedback on a preliminary version of the draft.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: fully homomorphic encryption rewriting system symmetric group noise-free
Contact author(s): rgerauds @ amazon fr
History: 2026-04-29: last of 3 revisions; 2026-04-09: received; See all versions
Short URL: https://ia.cr/2026/700
License: CC BY

BibTeX

@misc{cryptoeprint:2026/700,
      author = {Remi Geraud-Stewart},
      title = {{GRAFHEN} is not {IND}-{CPA} secure},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/700},
      year = {2026},
      url = {https://eprint.iacr.org/2026/700}
}