Paper 2023/1450

Post-Quantum Fully Homomorphic Encryption with Group Ring Homomorphisms

Christopher Leonardi, ISARA Corporation
Maya Gusak, ISARA Corporation
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.