Batch fully homomorphic encryption over the integers

Jung Hee Cheon, Jean Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tancrède Lepoint, Mehdi Tibouchi, Aaram Yun

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

204 Scopus citations

Abstract

We extend the fully homomorphic encryption scheme over the integers of van Dijk et al.(DGHV) into a batch fully homomorphic encryption scheme, i.e. to a scheme that supports encrypting and homomorphically processing a vector of plaintexts as a single ciphertext. We present two variants in which the semantic security is based on different assumptions. The first variant is based on a new decisional problem, the Decisional Approximate-GCD problem, whereas the second variant is based on the more classical computational Error-Free Approximate-GCD problem but requires additional public key elements. We also show how to perform arbitrary permutations on the underlying plaintext vector given the ciphertext and the public key. Our scheme offers competitive performance even with the bootstrapping procedure: we describe an implementation of the homomorphic evaluation of AES, with an amortized cost of about 12 minutes per AES ciphertext on a standard desktop computer; this is comparable to the timings presented by Gentry et al.at Crypto 2012 for their implementation of a Ring-LWE based fully homomorphic encryption scheme.

Original languageEnglish
Title of host publicationAdvances in Cryptology, EUROCRYPT 2013 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages315-335
Number of pages21
DOIs
StatePublished - 2013
Event32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013 - Athens, Greece
Duration: 26 May 201330 May 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7881 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013
Country/TerritoryGreece
CityAthens
Period26/05/1330/05/13

Keywords

  • Approximate GCD
  • Batch Encryption
  • Chinese Remainder Theorem
  • Fully Homomorphic Encryption
  • Homomorphic AES

Fingerprint

Dive into the research topics of 'Batch fully homomorphic encryption over the integers'. Together they form a unique fingerprint.

Cite this