Minimizing ESOP Expressions for Fully Homomorphic Encryption

Jheng Hao Ye; Si Quan Chen; Ming-Der Shieh

doi:10.1109/ISCAS.2018.8351389

Minimizing ESOP Expressions for Fully Homomorphic Encryption

Jheng Hao Ye, Si Quan Chen, Ming-Der Shieh

Department of Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

With the rapid growth of cloud computing services, fully homomorphic encryption (FHE) has attracted much attention because a homomorphic evaluation can be directly performed on ciphertexts to ensure data privacy. This work explores the constraints and an associated minimization algorithm for exclusive sum-of-products (ESOP) expressions based on a homomorphism map and features of FHE. An efficient ESOP minimization algorithm based on the Sierpinski gasket and the triangle rule is proposed to reduce the maximum degree of the ESOP expression, thus relaxing the need to perform the recryption operation on ciphertexts. Experimental results show that about 23% of all candidate 4-variable functions can be further improved by the proposed algorithm to minimize the maximum degree of ESOP as compared with the results obtained using the traditional minimization algorithm.

Original language	English
Title of host publication	2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781538648810
DOIs	https://doi.org/10.1109/ISCAS.2018.8351389
Publication status	Published - 2018 Apr 26
Event	2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Florence, Italy Duration: 2018 May 27 → 2018 May 30

Publication series

Name	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	2018-May
ISSN (Print)	0271-4310

Other

Other	2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018
Country/Territory	Italy
City	Florence
Period	18-05-27 → 18-05-30

All Science Journal Classification (ASJC) codes

Electrical and Electronic Engineering

Access to Document

10.1109/ISCAS.2018.8351389

Cite this

Ye, J. H., Chen, S. Q., & Shieh, M.-D. (2018). Minimizing ESOP Expressions for Fully Homomorphic Encryption. In 2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings Article 8351389 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 2018-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISCAS.2018.8351389

@inproceedings{c22c9be4719e44209c91a5ee9a06f048,

title = "Minimizing ESOP Expressions for Fully Homomorphic Encryption",

abstract = "With the rapid growth of cloud computing services, fully homomorphic encryption (FHE) has attracted much attention because a homomorphic evaluation can be directly performed on ciphertexts to ensure data privacy. This work explores the constraints and an associated minimization algorithm for exclusive sum-of-products (ESOP) expressions based on a homomorphism map and features of FHE. An efficient ESOP minimization algorithm based on the Sierpinski gasket and the triangle rule is proposed to reduce the maximum degree of the ESOP expression, thus relaxing the need to perform the recryption operation on ciphertexts. Experimental results show that about 23% of all candidate 4-variable functions can be further improved by the proposed algorithm to minimize the maximum degree of ESOP as compared with the results obtained using the traditional minimization algorithm.",

author = "Ye, {Jheng Hao} and Chen, {Si Quan} and Ming-Der Shieh",

year = "2018",

month = apr,

day = "26",

doi = "10.1109/ISCAS.2018.8351389",

language = "English",

series = "Proceedings - IEEE International Symposium on Circuits and Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings",

address = "United States",

note = "2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 ; Conference date: 27-05-2018 Through 30-05-2018",

}

Ye, JH, Chen, SQ & Shieh, M-D 2018, Minimizing ESOP Expressions for Fully Homomorphic Encryption. in 2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings., 8351389, Proceedings - IEEE International Symposium on Circuits and Systems, vol. 2018-May, Institute of Electrical and Electronics Engineers Inc., 2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018, Florence, Italy, 18-05-27. https://doi.org/10.1109/ISCAS.2018.8351389

Minimizing ESOP Expressions for Fully Homomorphic Encryption. / Ye, Jheng Hao; Chen, Si Quan; Shieh, Ming-Der.
2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2018. 8351389 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 2018-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Minimizing ESOP Expressions for Fully Homomorphic Encryption

AU - Ye, Jheng Hao

AU - Chen, Si Quan

AU - Shieh, Ming-Der

PY - 2018/4/26

Y1 - 2018/4/26

N2 - With the rapid growth of cloud computing services, fully homomorphic encryption (FHE) has attracted much attention because a homomorphic evaluation can be directly performed on ciphertexts to ensure data privacy. This work explores the constraints and an associated minimization algorithm for exclusive sum-of-products (ESOP) expressions based on a homomorphism map and features of FHE. An efficient ESOP minimization algorithm based on the Sierpinski gasket and the triangle rule is proposed to reduce the maximum degree of the ESOP expression, thus relaxing the need to perform the recryption operation on ciphertexts. Experimental results show that about 23% of all candidate 4-variable functions can be further improved by the proposed algorithm to minimize the maximum degree of ESOP as compared with the results obtained using the traditional minimization algorithm.

AB - With the rapid growth of cloud computing services, fully homomorphic encryption (FHE) has attracted much attention because a homomorphic evaluation can be directly performed on ciphertexts to ensure data privacy. This work explores the constraints and an associated minimization algorithm for exclusive sum-of-products (ESOP) expressions based on a homomorphism map and features of FHE. An efficient ESOP minimization algorithm based on the Sierpinski gasket and the triangle rule is proposed to reduce the maximum degree of the ESOP expression, thus relaxing the need to perform the recryption operation on ciphertexts. Experimental results show that about 23% of all candidate 4-variable functions can be further improved by the proposed algorithm to minimize the maximum degree of ESOP as compared with the results obtained using the traditional minimization algorithm.

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

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

U2 - 10.1109/ISCAS.2018.8351389

DO - 10.1109/ISCAS.2018.8351389

M3 - Conference contribution

AN - SCOPUS:85057125546

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

BT - 2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Circuits and Systems, ISCAS 2018

Y2 - 27 May 2018 through 30 May 2018

ER -

Minimizing ESOP Expressions for Fully Homomorphic Encryption

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this