Paper 2023/1450
Post-Quantum Fully Homomorphic Encryption with Group Ring Homomorphisms
Abstract
Gentry's groundbreaking work showed that a fully homomorphic, provably secure scheme is possible via bootstrapping a somewhat homomorphic scheme. However, a major drawback of bootstrapping is its high computational cost. One alternative is to use a different metric for noise so that homomorphic operations do not accumulate noise, eliminating the need for boostrapping altogether. Leonardi and Ruiz-Lopez present a group-theoretic framework for such a ``noise non-accumulating'' multiplicative homomorphic scheme, but Agathocleous et al. expose weaknesses in this framework when working over finite abelian groups. Tangentially, Li and Wang present a ``noise non-accumulating'' fully homomorphic scheme by performing Ostrovsky and Skeith's transform on a multiplicative homomorphic scheme of non-abelian group rings. Unfortunately, the security of Li and Wang's scheme relies on the Factoring Large Numbers assumption, which is false given an adversary with a quantum computer. In this work, we seek to modify Li and Wang's scheme to be post-quantum secure by fitting it into the Leonardi and Ruiz-Lopez framework for non-abelian rings. We discuss improved security assumptions for Li and Wang encryption and assess the shortcomings of working in a non-abelian setting. Finally, we show that a large class of semisimple rings is incompatible with the Leonardi and Ruiz-Lopez framework.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Post-QuantumHomomorphic EncryptionAbstract GroupsCryptanalysisNon-Abelian GroupsLHN
- Contact author(s)
-
chris leonardi @ isara com
maya gusak @ uwaterloo ca - History
- 2023-09-24: approved
- 2023-09-22: received
- See all versions
- Short URL
- https://ia.cr/2023/1450
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1450, author = {Christopher Leonardi and Maya Gusak}, title = {Post-Quantum Fully Homomorphic Encryption with Group Ring Homomorphisms}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1450}, year = {2023}, url = {https://eprint.iacr.org/2023/1450} }