Practical homomorphic encryption over the integers for secure computation in the cloud

James Dyer, Martin Dyer, Jie Xu

Research output: Contribution to journalArticle

Abstract

We present novel homomorphic encryption schemes for integer arithmetic, intended primarily for use in secure single-party computation in the cloud. These schemes are capable of securely computing arbitrary degree polynomials homomorphically. In practice, ciphertext size and running times limit the polynomial degree, but this appears sufficient for most practical applications. We present four schemes, with increasing levels of security, but increasing computational overhead. Two of the schemes provide strong security for high-entropy data. The remaining two schemes provide strong security regardless of this assumption. These four algorithms form the first two levels of a hierarchy of schemes, and we also present the general cases of each scheme. We further elaborate how a fully homomorphic system can be constructed from one of our general cases. In addition, we present a variant based upon Chinese Remainder Theorem secret sharing. We detail extensive evaluation of the first four algorithms of our hierarchy by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods and dramatically outperform many well-publicised schemes. The results clearly demonstrate the practical applicability of our schemes.

Original languageEnglish
Pages (from-to)549-579
Number of pages31
JournalInternational Journal of Information Security
Volume18
Issue number5
Early online date9 Feb 2019
DOIs
Publication statusPublished - Oct 2019
Externally publishedYes

Fingerprint

Cryptography
Polynomials
Entropy

Cite this

@article{679b7d07bcf74076a691e6fa7d24f69f,
title = "Practical homomorphic encryption over the integers for secure computation in the cloud",
abstract = "We present novel homomorphic encryption schemes for integer arithmetic, intended primarily for use in secure single-party computation in the cloud. These schemes are capable of securely computing arbitrary degree polynomials homomorphically. In practice, ciphertext size and running times limit the polynomial degree, but this appears sufficient for most practical applications. We present four schemes, with increasing levels of security, but increasing computational overhead. Two of the schemes provide strong security for high-entropy data. The remaining two schemes provide strong security regardless of this assumption. These four algorithms form the first two levels of a hierarchy of schemes, and we also present the general cases of each scheme. We further elaborate how a fully homomorphic system can be constructed from one of our general cases. In addition, we present a variant based upon Chinese Remainder Theorem secret sharing. We detail extensive evaluation of the first four algorithms of our hierarchy by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods and dramatically outperform many well-publicised schemes. The results clearly demonstrate the practical applicability of our schemes.",
keywords = "Computing on encrypted data, Cryptography, Homomorphic encryption, Secure computation in the cloud, Symmetric encryption",
author = "James Dyer and Martin Dyer and Jie Xu",
year = "2019",
month = "10",
doi = "10.1007/s10207-019-00427-0",
language = "English",
volume = "18",
pages = "549--579",
journal = "International Journal of Information Security",
issn = "1615-5262",
publisher = "Springer Verlag",
number = "5",

}

Practical homomorphic encryption over the integers for secure computation in the cloud. / Dyer, James; Dyer, Martin; Xu, Jie.

In: International Journal of Information Security, Vol. 18, No. 5, 10.2019, p. 549-579.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Practical homomorphic encryption over the integers for secure computation in the cloud

AU - Dyer, James

AU - Dyer, Martin

AU - Xu, Jie

PY - 2019/10

Y1 - 2019/10

N2 - We present novel homomorphic encryption schemes for integer arithmetic, intended primarily for use in secure single-party computation in the cloud. These schemes are capable of securely computing arbitrary degree polynomials homomorphically. In practice, ciphertext size and running times limit the polynomial degree, but this appears sufficient for most practical applications. We present four schemes, with increasing levels of security, but increasing computational overhead. Two of the schemes provide strong security for high-entropy data. The remaining two schemes provide strong security regardless of this assumption. These four algorithms form the first two levels of a hierarchy of schemes, and we also present the general cases of each scheme. We further elaborate how a fully homomorphic system can be constructed from one of our general cases. In addition, we present a variant based upon Chinese Remainder Theorem secret sharing. We detail extensive evaluation of the first four algorithms of our hierarchy by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods and dramatically outperform many well-publicised schemes. The results clearly demonstrate the practical applicability of our schemes.

AB - We present novel homomorphic encryption schemes for integer arithmetic, intended primarily for use in secure single-party computation in the cloud. These schemes are capable of securely computing arbitrary degree polynomials homomorphically. In practice, ciphertext size and running times limit the polynomial degree, but this appears sufficient for most practical applications. We present four schemes, with increasing levels of security, but increasing computational overhead. Two of the schemes provide strong security for high-entropy data. The remaining two schemes provide strong security regardless of this assumption. These four algorithms form the first two levels of a hierarchy of schemes, and we also present the general cases of each scheme. We further elaborate how a fully homomorphic system can be constructed from one of our general cases. In addition, we present a variant based upon Chinese Remainder Theorem secret sharing. We detail extensive evaluation of the first four algorithms of our hierarchy by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods and dramatically outperform many well-publicised schemes. The results clearly demonstrate the practical applicability of our schemes.

KW - Computing on encrypted data

KW - Cryptography

KW - Homomorphic encryption

KW - Secure computation in the cloud

KW - Symmetric encryption

UR - http://www.scopus.com/inward/record.url?scp=85061310732&partnerID=8YFLogxK

U2 - 10.1007/s10207-019-00427-0

DO - 10.1007/s10207-019-00427-0

M3 - Article

VL - 18

SP - 549

EP - 579

JO - International Journal of Information Security

JF - International Journal of Information Security

SN - 1615-5262

IS - 5

ER -