同态加密在隐私计算中的应用综述

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

中图分类号:

TP309.2

邵航, 高思琪, 钟离, 傅致晖, 孟丹, 李晓林. 同态加密在隐私计算中的应用综述[J]. 信息通信技术与政策, 2022, 48(8): 75-88.

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.

导出引用管理器 EndNote|Ris|BibTeX

链接本文:

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

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

图/表 12

参考文献 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