### General Impossibility of Group Homomorphic Encryption in the Quantum World

Frederik Armknecht, Tommaso Gagliardoni, Stefan Katzenbeisser, and Andreas Peter

##### Abstract

Group homomorphic encryption represents one of the most important building blocks in modern cryptography. It forms the basis of widely-used, more sophisticated primitives, such as CCA2-secure encryption or secure multiparty computation. Unfortunately, recent advances in quantum computation show that many of the existing schemes completely break down once quantum computers reach maturity (mainly due to Shor’s algorithm). This leads to the challenge of constructing quantum-resistant group homomorphic cryptosystems. In this work, we prove the general impossibility of (abelian) group homomorphic encryption in the presence of quantum adversaries, when assuming the IND-CPA security notion as the minimal security requirement. To this end, we prove a new result on the probability of sampling generating sets of finite (sub-)groups if sampling is done with respect to an arbitrary, unknown distribution. Finally, we provide a sufficient condition on homomorphic encryption schemes for our quantum attack to work and discuss its satisfiability in non-group homomorphic cases. The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2014
Keywords
Homomorphic EncryptionSemantic SecurityQuantum AlgorithmsSampling Group Generators
Contact author(s)
tommaso @ gagliardoni net
History
2014-01-13: revised
See all versions
Short URL
https://ia.cr/2014/029

CC BY

BibTeX

@misc{cryptoeprint:2014/029,
author = {Frederik Armknecht and Tommaso Gagliardoni and Stefan Katzenbeisser and Andreas Peter},
title = {General Impossibility of Group Homomorphic Encryption in the Quantum World},
howpublished = {Cryptology ePrint Archive, Paper 2014/029},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/029}},
url = {https://eprint.iacr.org/2014/029}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.