General Impossibility of Group Homomorphic Encryption in the Quantum World

Frederik Armknecht, Tommaso Gagliardoni, Stefan Katzenbeisser, Andreas Peter

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    15 Citations (Scopus)

    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.
    Original languageUndefined
    Title of host publication17th International Conference on Practice and Theory in Public-Key Cryptography. PKC 2014
    Place of PublicationBerlin
    PublisherSpringer
    Pages556-573
    Number of pages18
    ISBN (Print)978-3-642-54630-3
    DOIs
    Publication statusPublished - 2014
    Event17th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014 - Buenos Aires, Argentina
    Duration: 26 Mar 201428 Mar 2014

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume8383

    Conference

    Conference17th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2014
    Period26/03/1428/03/14
    OtherMarch 26-28, 2014

    Keywords

    • METIS-304104
    • SCS-Cybersecurity
    • IR-91147
    • EWI-24762

    Cite this