Paper 2026/700 Original: eprint.iacr.org/2026/700 ↗
GRAFHEN is not IND-CPA secure
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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2026-04-29: last updated
- 2026-04-09: published
- Short URL
- https://ia.cr/2026/700
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}