Team for Research in
Ubiquitous Secure Technology

Targeted malleability: homomorphic encryption for restricted computations
Dan Boneh, Gil Segev, Brent Waters

Citation
Dan Boneh, Gil Segev, Brent Waters. "Targeted malleability: homomorphic encryption for restricted computations". Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012.

Abstract
We put forward the notion of targeted malleability: given a homomorphic encryption scheme, in various scenarios we would like to restrict the homomorphic computations one can perform on encrypted data. We introduce a precise framework, generalizing the foundational notion of non-malleability introduced by Dolev, Dwork, and Naor (SICOMP '00), ensuring that the malleability of a scheme is targeted only at a specific set of "allowable" functions.

In this setting we are mainly interested in the efficiency of such schemes as a function of the number of repeated homomorphic operations. Whereas constructing a scheme whose ciphertext grows linearly with the number of such operations is straightforward, obtaining more realistic (or merely non-trivial) length guarantees is significantly more challenging.

We present two constructions that transform any homomorphic encryption scheme into one that offers targeted malleability. Our constructions rely on standard cryptographic tools and on succinct non-interactive arguments, which are currently known to exist in the standard model based on variants of the knowledge-of-exponent assumption. The two constructions offer somewhat different efficiency guarantees, each of which may be preferable depending on the underlying building blocks.

Electronic downloads

Citation formats  
  • HTML
    Dan Boneh, Gil Segev, Brent Waters. <a
    href="http://www.truststc.org/pubs/900.html"
    >Targeted malleability: homomorphic encryption for
    restricted computations</a>, Proceedings of the 3rd
    Innovations in Theoretical Computer Science Conference, 2012.
  • Plain text
    Dan Boneh, Gil Segev, Brent Waters. "Targeted
    malleability: homomorphic encryption for restricted
    computations". Proceedings of the 3rd Innovations in
    Theoretical Computer Science Conference, 2012.
  • BibTeX
    @inproceedings{BonehSegevWaters12_TargetedMalleabilityHomomorphicEncryptionForRestricted,
        author = {Dan Boneh and Gil Segev and Brent Waters},
        title = {Targeted malleability: homomorphic encryption for
                  restricted computations},
        booktitle = {Proceedings of the 3rd Innovations in Theoretical
                  Computer Science Conference},
        year = {2012},
        abstract = {We put forward the notion of targeted
                  malleability: given a homomorphic encryption
                  scheme, in various scenarios we would like to
                  restrict the homomorphic computations one can
                  perform on encrypted data. We introduce a precise
                  framework, generalizing the foundational notion of
                  non-malleability introduced by Dolev, Dwork, and
                  Naor (SICOMP '00), ensuring that the malleability
                  of a scheme is targeted only at a specific set of
                  "allowable" functions. <p> In this setting we are
                  mainly interested in the efficiency of such
                  schemes as a function of the number of repeated
                  homomorphic operations. Whereas constructing a
                  scheme whose ciphertext grows linearly with the
                  number of such operations is straightforward,
                  obtaining more realistic (or merely non-trivial)
                  length guarantees is significantly more
                  challenging. <p> We present two constructions that
                  transform any homomorphic encryption scheme into
                  one that offers targeted malleability. Our
                  constructions rely on standard cryptographic tools
                  and on succinct non-interactive arguments, which
                  are currently known to exist in the standard model
                  based on variants of the knowledge-of-exponent
                  assumption. The two constructions offer somewhat
                  different efficiency guarantees, each of which may
                  be preferable depending on the underlying building
                  blocks.},
        URL = {http://www.truststc.org/pubs/900.html}
    }
    

Posted by Mary Stewart on 4 Apr 2012.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.