TY - GEN
T1 - General Impossibility of Group Homomorphic Encryption in the Quantum World
AU - Armknecht, Frederik
AU - Gagliardoni, Tommaso
AU - Katzenbeisser, Stefan
AU - Peter, Andreas
N1 - eemcs-eprint-24762
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - METIS-304104
KW - SCS-Cybersecurity
KW - IR-91147
KW - EWI-24762
U2 - 10.1007/978-3-642-54631-0_32
DO - 10.1007/978-3-642-54631-0_32
M3 - Conference contribution
SN - 978-3-642-54630-3
T3 - Lecture Notes in Computer Science
SP - 556
EP - 573
BT - 17th International Conference on Practice and Theory in Public-Key Cryptography. PKC 2014
PB - Springer
CY - Berlin
T2 - 17th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014
Y2 - 26 March 2014 through 28 March 2014
ER -