Cryptology ePrint Archive: Report 2017/1013

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

Wouter Castryck and 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.

Category / Keywords: public-key cryptography / homomorhic encryption, packing

Date: received 12 Oct 2017, last revised 6 Feb 2018

Contact author: ilia at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20180206:165017 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]