Homomorphic encryption protocols and applications in privacy preserving computation

doi:10.12267/j.issn.2096-5931.2022.08.012

Abstract

Abstract:

Homomorphic encryption is a cryptography technology based on the computational complexity theory of mathematical problems. It supports the calculation of data under the encrypted state, and the decrypted calculation result is consistent with the plaintext calculation result. As a hot research topic in privacy preserving computation, homomorphic encryption can be used in diverse application scenarios. We first introduce the development process of homomorphic encryption and relevant technologies. We then elaborate on the use cases of homomorphic encryption in typical application scenarios, such as secure intersection, secure querying, multi-party joint computing, and multi-party joint modeling. Finally, this paper analyzes and discusses the technical challenges and some research directions of current homomorphic encryption technologies.

Key words: homomorphic encryption, private set intersection, private information retrieval, secure multi-party computation, federated learning, privacy preserving computating

CLC Number:

TP309.2

SHAO Hang, GAO Siqi, ZHONG Li, FU Zhihui, MENG Dan, LI Xiaolin. Homomorphic encryption protocols and applications in privacy preserving computation[J]. Information and Communications Technology and Policy, 2022, 48(8): 75-88.

Add to citation manager EndNote|Ris|BibTeX

URL:

http://ictp.caict.ac.cn/EN/10.12267/j.issn.2096-5931.2022.08.012

http://ictp.caict.ac.cn/EN/Y2022/V48/I8/75

Figures/Tables 12

References 42

[1]	刘钦菊, 路献辉, 李杰, 等. 全同态加密自举技术的研究现状及发展趋势[J]. 密码学报, 2021, 8(5):795-807. DOI: 10.13868/j.cnki.jcr.000477. doi: 10.13868/j.cnki.jcr.000477
[2]	RIVEST R L, SHAMIR A, ADLEMAN L M. Cryptographic communications system and method: US Patent 4405829[P], 1983.
[3]	GAMAL T E. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1984(31):469-472.
[4]	PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[J]. EUROCRYPT’99, Czech Republic, May, 1999.
[5]	GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The Forty-First Annual ACM Symposium on Theory of Computing, 2009:169-178.
[6]	DIJK M V, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[J]. Springer, Berlin, Heidelberg, 2010.
[7]	BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2):831-871. doi: 10.1137/120868669 URL
[8]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3):1-36.
[9]	FAN J, VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. Cryptology Eprint Archive, 2012.
[10]	CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[J]. International Conference on the Theory and Application of Cryptology and Information Security, 2017:409-437.
[11]	GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[J]. Annual Cryptology Conference, 2013:75-92.
[12]	ALPERIN-SHERIFF J, PEIKERT C. Faster bootstrapping with polynomial error[J]. Annual Cryptology Conference, 2014: 297-314.
[13]	DUCAS L, MICCIANCIO D. FHEW: bootstrapping homomorphic encryption in less than a second[J]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2015:617-640.
[14]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. TFHE: fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34-91. doi: 10.1007/s00145-019-09319-x URL
[15]	CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[J]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018:360-384.
[16]	CHEN H, CHILLOTTI I, SONG Y. Improved bootstrapping for approximate homomorphic encryption[J]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2019:34-54.
[17]	Cryptofun[EB/OL]. [2022-03-01]. https://github. com/arnaucube/cryptofun.
[18]	IBM. HELIB[EB/OL]. [2022-03-01]. .
[19]	Microsoft. SEAL[EB/OL]. [2022-03-01]. .
[20]	HEAAN[EB/OL]. [2022-03-01]. https://github. com/snucrypto/HEAAN.
[21]	FHEW[EB/OL]. [2022-03-01]. https://github.com/lducas/FHEW.
[22]	TFHE[EB/OL]. [2022-03-01]. https://github.com/tfhe/tfhe.
[23]	PALISADE[EB/OL]. [2022-03-01]. https://gitlab.com/palisade/palisade-development.
[24]	KOLESNIKOV V, KUMARESAN R, ROSULEK M, et al. Efficient batched oblivious PRF with applications to private set intersection[C]. 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016: 818-829.
[25]	CHEN H, LAINE K, RINDAL P. Fast private set intersection from homomorphic encryption[C]. 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017:1243-1255.
[26]	CHEN H, HUANG Z, LAINE K, et al. Labeled PSI from fully homomorphic encryption with malicious security[C]. 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018: 1223-1237.
[27]	CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private information retrieval[C]. IEEE 36th Annual Foundations of Computer Science, 1995: 41-50.
[28]	ANGEL S, CHEN H, LAINE K, et al. PIR with compressed queries and amortized query processing[C]// 2018 IEEE symposium on security and privacy (SP), 2018: 962-979.
[29]	Microsoft. SEALPIR[EB/OL]. [2022-03-01]. https://github.com/microsoft/SealPIR.
[30]	PATEL S, PERSIANO G, YEO K. Private stateful information retrieval[C]. 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018: 1002-1019.
[31]	王婧琳. 基于同态加密的金融数据安全共享方案研究及实现[D]. 哈尔滨工业大学, 2020.
[32]	AONO Y, HAYASHI T, WANG L, et al. Privacy-preserving deep learning via additively homomorphic encryption[J]. IEEE Transactions on Information Forensics and Security, 2017, 13(5): 1333-1345. doi: 10.1109/TIFS.2017.2787987 URL
[33]	ZHANG C, LI S, XIA J, et al. BatchCrypt: efficient homomorphic encryption for cross-silo federated learning[C]// 2020 USENIX Annual Technical Conference, 2020: 493-506.
[34]	MCMAHAN B, MOORE E, RAMAGE D, et al. Communication-efficient learning of deep networks from decentralized data[C]// Artificial intelligence and statistics. PMLR, 2017:1273-1282.
[35]	LIU Y, KANG Y, XING C, et al. A secure federated transfer learning framework[J]. IEEE Intelligent Systems, 2020, 35(4):70-82. doi: 10.1109/MIS.2020.2988525 URL
[36]	YANG S, REN B, ZHOU X, et al. Parallel distributed logistic regression for vertical federated learning without third-party coordinator[J]. arXiv preprint arXiv: 1911. 09824, 2019.
[37]	CHENG K, FAN T, JIN Y, et al. Secureboost: A lossless federated learning framework[J]. IEEE Intelligent Systems, 2021, 36(6): 87-98.
[38]	LI Z, HUAGN Z, CHEN C, et al. Quantification of the leakage in federated learning[J]. arXiv preprint arXiv: 1910. 05467, 2019.
[39]	CHEN C, ZHOU J, WANG L, et al. When homomorphic encryption marries secret sharing: Secure large-scale sparse logistic regression and applications in risk control[C]// 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 2652-2662.
[40]	FANG W, ZHAO D, TAN J, et al. Large-scale secure XGB for vertical federated learning[C]// 30th ACM International Conference on Information & Knowledge Management, 2021: 443-452.
[41]	ALPERIN-SHERIFF J, PEIKERT C. Faster bootstrapping with polynomial error[C]// Annual Cryptology Conference, 2014:297-314.
[42]	DUCAS L, MICCIANCIO D. FHEW: bootstrapping homomorphic encryption in less than a second[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2015:617-640.

开源库	贡献者	HE方案
Cryptofun^[17]	Arnaucube	RSA/ElGamal/Paillier/etc
HELIB^[18]	IBM	BGV/CKKS
SEAL^[19]	微软	BGV/BFV/CKKS
FEAAN^[20]	首尔大学	CKKS
FHEW^[21]	Ducas、Micciancio	FHEW
TFHE^[22]	Chillotti等	TFHE和FHEW
PALISADE^[23]	MIT、UCSD	BFV/BGV/FHEW/TFHE/CKKS

开源库	贡献者	HE方案
Cryptofun^[17]	Arnaucube	RSA/ElGamal/Paillier/etc
HELIB^[18]	IBM	BGV/CKKS
SEAL^[19]	微软	BGV/BFV/CKKS
FEAAN^[20]	首尔大学	CKKS
FHEW^[21]	Ducas、Micciancio	FHEW
TFHE^[22]	Chillotti等	TFHE和FHEW
PALISADE^[23]	MIT、UCSD	BFV/BGV/FHEW/TFHE/CKKS

N_X	N_Y	方案	离线时间/s	在线时间/s	在线通信量/MB
2²⁴	11 041	CCS2018^[26]	656.00	20.10	41.48
	11 041	CCS2017^[25]	71.00	44.70	23.20
	5 535	CCS2018^[26]	806.00	22.01	16.39
	5 535	CCS2017^[25]	64.00	40.10	20.10
2²⁰	11 041	CCS2018^[26]	43.00	4.49	14.34
	11 041	CCS2017^[25]	6.40	6.40	11.50
	5 535	CCS2018^[26]	43.00	4.23	11.50
	5 535	CCS2017^[25]	4.30	4.30	5.60

N_X	N_Y	方案	离线时间/s	在线时间/s	在线通信量/MB
2²⁴	11 041	CCS2018^[26]	656.00	20.10	41.48
	11 041	CCS2017^[25]	71.00	44.70	23.20
	5 535	CCS2018^[26]	806.00	22.01	16.39
	5 535	CCS2017^[25]	64.00	40.10	20.10
2²⁰	11 041	CCS2018^[26]	43.00	4.49	14.34
	11 041	CCS2017^[25]	6.40	6.40	11.50
	5 535	CCS2018^[26]	43.00	4.23	11.50
	5 535	CCS2017^[25]	4.30	4.30	5.60