TY - JOUR
T1 - CRT-based fully homomorphic encryption over the integers
AU - Cheon, Jung Hee
AU - Kim, Jinsu
AU - Lee, Moon Sung
AU - Yun, Aaram
N1 - Funding Information:
We would like to thank Taekyoung Kwon and Hyung Tae Lee for valuable comments. The first, second, and third authors were supported by the ICT R&D program of MSIP/IITP [No. 10047212] and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. 2014R1A2A1A11050917 ). The third author was also supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education ( NRF-2012R1A1A2039129 ). The last author was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2011-0025127 ).
Publisher Copyright:
© 2015 Published by Elsevier Inc.
PY - 2015/7/20
Y1 - 2015/7/20
N2 - In 1978, Rivest, Adleman and Dertouzos introduced the basic concept of privacy homomorphism that allows computation on encrypted data without decryption. It was an interesting work whose idea precedes the recent development of fully homomorphic encryption, although actual example schemes proposed in the paper are all susceptible to simple known-plaintext attacks. In this paper, we revisit one of their proposals, in particular the third scheme which is based on the Chinese Remainder Theorem and is ring homomorphic. It is known that only a single pair of known plaintext/ciphertext is needed to break this scheme. However, by exploiting the standard technique to insert an error to a message before encryption, we can cope with this problem. We present a secure modification of their proposal by showing that the proposed scheme is fully homomorphic and secure against the chosen plaintext attacks under the approximate GCD assumption and the sparse subset sum assumption when the message space is restricted to Z2k. Interestingly, the proposed scheme can be regarded as a generalization of the DGHV scheme with larger plaintext space. Our scheme has O∼(λ5) ciphertext expansion overhead while the DGHV has O∼(λ8) for the security parameter λ. When restricted to the homomorphic encryption scheme with depth of O(logλ), the overhead is reduced to O∼(λ). Our scheme can be used in applications requiring a large message space ZQ for logQ=O(λ4), or SIMD style operations on ZQk for logQ=O(λ),k=O(λ3), with O∼(λ5) ciphertext size as in the DGHV.
AB - In 1978, Rivest, Adleman and Dertouzos introduced the basic concept of privacy homomorphism that allows computation on encrypted data without decryption. It was an interesting work whose idea precedes the recent development of fully homomorphic encryption, although actual example schemes proposed in the paper are all susceptible to simple known-plaintext attacks. In this paper, we revisit one of their proposals, in particular the third scheme which is based on the Chinese Remainder Theorem and is ring homomorphic. It is known that only a single pair of known plaintext/ciphertext is needed to break this scheme. However, by exploiting the standard technique to insert an error to a message before encryption, we can cope with this problem. We present a secure modification of their proposal by showing that the proposed scheme is fully homomorphic and secure against the chosen plaintext attacks under the approximate GCD assumption and the sparse subset sum assumption when the message space is restricted to Z2k. Interestingly, the proposed scheme can be regarded as a generalization of the DGHV scheme with larger plaintext space. Our scheme has O∼(λ5) ciphertext expansion overhead while the DGHV has O∼(λ8) for the security parameter λ. When restricted to the homomorphic encryption scheme with depth of O(logλ), the overhead is reduced to O∼(λ). Our scheme can be used in applications requiring a large message space ZQ for logQ=O(λ4), or SIMD style operations on ZQk for logQ=O(λ),k=O(λ3), with O∼(λ5) ciphertext size as in the DGHV.
KW - Approximate gcd
KW - Chinese remainder theorem
KW - DGHV
KW - Homomorphic encryption
KW - Privacy homomorphism
UR - http://www.scopus.com/inward/record.url?scp=84926687996&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2015.03.019
DO - 10.1016/j.ins.2015.03.019
M3 - Article
AN - SCOPUS:84926687996
SN - 0020-0255
VL - 310
SP - 149
EP - 162
JO - Information Sciences
JF - Information Sciences
ER -