Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud

James Dyer, Martin Dyer, Jie Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

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 which require linearly decreasing entropy. We have evaluated these four algorithms by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods, and dramatically out-perform running times of directly comparable schemes by a factor of up to 1000, and considerably more than that for fully homomorphic schemes, used in the same context. The results clearly demonstrate the practical applicability of our schemes.

Original languageEnglish
Title of host publicationCryptography and Coding
Subtitle of host publication16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings
EditorsMáire O’Neill
Place of PublicationCham
PublisherSpringer Verlag
Pages44-76
Number of pages33
ISBN (Electronic)9783319710457
ISBN (Print)9783319710440
DOIs
Publication statusPublished - 26 Nov 2017
Externally publishedYes
Event16th IMA International Conference on Cryptography and Coding, IMACC 2017 - Oxford, United Kingdom
Duration: 12 Dec 201714 Dec 2017

Publication series

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

Conference

Conference16th IMA International Conference on Cryptography and Coding, IMACC 2017
CountryUnited Kingdom
CityOxford
Period12/12/1714/12/17

Fingerprint

Secure Computation
Homomorphic Encryption
Cryptography
Polynomials
Integer
Entropy
Polynomial
Computing
Homomorphic
Timing
Linearly
Sufficient

Cite this

Dyer, J., Dyer, M., & Xu, J. (2017). Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. In M. O’Neill (Ed.), Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings (pp. 44-76). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10655 LNCS). Cham: Springer Verlag. https://doi.org/10.1007/978-3-319-71045-7_3
Dyer, James ; Dyer, Martin ; Xu, Jie. / Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings. editor / Máire O’Neill. Cham : Springer Verlag, 2017. pp. 44-76 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{a0150a91d7b74ac3aa717885d9598400,
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 which require linearly decreasing entropy. We have evaluated these four algorithms by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods, and dramatically out-perform running times of directly comparable schemes by a factor of up to 1000, and considerably more than that for fully homomorphic schemes, used in the same context. 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 = "2017",
month = "11",
day = "26",
doi = "10.1007/978-3-319-71045-7_3",
language = "English",
isbn = "9783319710440",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "44--76",
editor = "M{\'a}ire O’Neill",
booktitle = "Cryptography and Coding",

}

Dyer, J, Dyer, M & Xu, J 2017, Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. in M O’Neill (ed.), Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10655 LNCS, Springer Verlag, Cham, pp. 44-76, 16th IMA International Conference on Cryptography and Coding, IMACC 2017, Oxford, United Kingdom, 12/12/17. https://doi.org/10.1007/978-3-319-71045-7_3

Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. / Dyer, James; Dyer, Martin; Xu, Jie.

Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings. ed. / Máire O’Neill. Cham : Springer Verlag, 2017. p. 44-76 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10655 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud

AU - Dyer, James

AU - Dyer, Martin

AU - Xu, Jie

PY - 2017/11/26

Y1 - 2017/11/26

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 which require linearly decreasing entropy. We have evaluated these four algorithms by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods, and dramatically out-perform running times of directly comparable schemes by a factor of up to 1000, and considerably more than that for fully homomorphic schemes, used in the same context. 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 which require linearly decreasing entropy. We have evaluated these four algorithms by computing low-degree polynomials. The timings of these computations are extremely favourable by comparison with even the best of existing methods, and dramatically out-perform running times of directly comparable schemes by a factor of up to 1000, and considerably more than that for fully homomorphic schemes, used in the same context. 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=85038208626&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-71045-7_3

DO - 10.1007/978-3-319-71045-7_3

M3 - Conference contribution

SN - 9783319710440

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 44

EP - 76

BT - Cryptography and Coding

A2 - O’Neill, Máire

PB - Springer Verlag

CY - Cham

ER -

Dyer J, Dyer M, Xu J. Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. In O’Neill M, editor, Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings. Cham: Springer Verlag. 2017. p. 44-76. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-71045-7_3