Paper 2017/1013

Homomorphic SIM$^2$D Operations: Single Instruction Much More Data

Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren

Abstract

In 2014, Smart and Vercauteren introduced a packing technique for homomorphic encryption schemes by decomposing the plaintext space using the Chinese Remainder Theorem. This technique allows to encrypt multiple data values simultaneously into one ciphertext and execute Single Instruction Multiple Data operations homomorphically. In this paper we improve and generalize their results by introducing a flexible Laurent polynomial encoding technique and by using a more fine-grained CRT decomposition of the plaintext space. The Laurent polynomial encoding provides a convenient common framework for all conventional ways in which input data types can be represented, e.g. finite field elements, integers, rationals, floats and complex numbers. Our methods greatly increase the packing capacity of the plaintext space, as well as one’s flexibility in optimizing the system parameters with respect to efficiency and/or security.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
homomorhic encryptionpacking
Contact author(s)
ilia @ esat kuleuven be
History
2018-02-06: last of 2 revisions
2017-10-18: received
See all versions
Short URL
https://ia.cr/2017/1013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1013,
      author = {Wouter Castryck and Ilia Iliashenko and Frederik Vercauteren},
      title = {Homomorphic SIM$^2$D Operations: Single Instruction Much More Data},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1013},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1013}},
      url = {https://eprint.iacr.org/2017/1013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.