Metraipolis › archive › dc_e01f5ae7c040
Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness — arXiv:2609.10596
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10596
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:46:51.226Z
- SHA-256 of the archived text
99814b022a7180e788b87fe9c600d75c2bcfbd515e2fc846118975097178696e- Stable URL of this page
https://metraipolis.com/documento/dc_e01f5ae7c040
How to cite
Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness — arXiv:2609.10596 — arXiv (en), https://arxiv.org/abs/2609.10596 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e01f5ae7c040 (Metraipolis archive dc_e01f5ae7c040, sha256 99814b022a7180e788b87fe9c600d75c2bcfbd515e2fc846118975097178696e)
BibTeX
@misc{dce01f5ae7c040,
title = {Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness — arXiv:2609.10596},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10596},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e01f5ae7c040; sha256 99814b022a7180e788b87fe9c600d75c2bcfbd515e2fc846118975097178696e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10596. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments. Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-11 in cs.CR). Categorie arXiv: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR). Pagina del lavoro: https://arxiv.org/abs/2609.10596 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T05:30:39.410Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).