Shift-type homomorphic encryption and its application to fully homomorphic encryption

F. Armknecht, S. Katzenbeisser, Andreas Peter

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

    2 Citations (Scopus)
    40 Downloads (Pure)


    This work addresses the characterization of homomorphic encryption schemes both in terms of security and design. In particular, we are interested in currently existing fully homomorphic encryption (FHE) schemes and their common structures and security. Our main contributions can be summarized as follows: • We define a certain type of homomorphic encryption that we call shift-type and identify it as the basic underlying structure of all existing homomorphic encryption schemes. It generalizes the already known notion of shift-type group homomorphic encryption. • We give an IND-CPA characterization of all shift-type homomorphic encryption schemes in terms of an abstract subset membership problem. • We show that this characterization carries over to all leveled FHE schemes that arise by applying Gentry’s bootstrapping technique to shift-type homomorphic encryption schemes. Since this is the common structure of all existing schemes, our result actually characterizes the IND-CPA security of all existing bootstrapping-based leveled FHE. • We prove that the IND-CPA security of FHE schemes that offer a certain type of circuit privacy (for FHE schemes with a binary plaintext space we require circuit privacy for a single AND-gate and, in fact, all existing binary-plaintext FHE schemes offer this) and are based on Gentry’s bootstrapping technique is equivalent to the circular security of the underlying bootstrappable scheme.
    Original languageUndefined
    Title of host publication5th International Conference on Cryptology in Africa, AFRICACRYPT 2012
    Place of PublicationBerlin
    Number of pages18
    ISBN (Print)978-3-642-31410-0
    Publication statusPublished - 2012
    Event5th International Conference on Cryptology in Africa 2012 - Al Akhawayn University, Ifrane, Morocco
    Duration: 10 Jul 201212 Jul 2012
    Conference number: 5

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference5th International Conference on Cryptology in Africa 2012
    Abbreviated titleAfricaCrypt 2012
    Internet address


    • SCS-Cybersecurity
    • Homomorphic
    • Encryption
    • IR-86177
    • EWI-23388
    • Application
    • METIS-297666
    • Shift-Type

    Cite this