信息通信技术与政策 ›› 2022, Vol. 48 ›› Issue (8): 75-88.doi: 10.12267/j.issn.2096-5931.2022.08.012
邵航, 高思琪, 钟离, 傅致晖, 孟丹, 李晓林
收稿日期:
2022-03-10
出版日期:
2022-08-15
发布日期:
2022-08-26
作者简介:
SHAO Hang, GAO Siqi, ZHONG Li, FU Zhihui, MENG Dan, LI Xiaolin
Received:
2022-03-10
Online:
2022-08-15
Published:
2022-08-26
摘要:
同态加密技术是一种基于数学难题的计算复杂性理论的密码学技术,支持数据以密态方式进行计算,计算结果解密后与明文计算的结果一致,在多样化复杂应用场景中具有很好的普适性,是目前隐私计算领域的一个热点研究方向。通过对同态加密技术的发展历程以及相关的技术路线进行梳理,解析了同态加密在安全求交、隐匿查询、多方联合计算、多方联合建模等典型隐私计算应用场景的技术融合应用,并对同态加密目前广泛落地应用过程中碰到的关键问题进行分析,最后对同态加密的研究发展方向进行探讨。
中图分类号:
邵航, 高思琪, 钟离, 傅致晖, 孟丹, 李晓林. 同态加密在隐私计算中的应用综述[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.
开源库 | 贡献者 | HE方案 |
---|---|---|
Cryptofun[ | Arnaucube | RSA/ElGamal/Paillier/etc |
HELIB[ | IBM | BGV/CKKS |
SEAL[ | 微软 | BGV/BFV/CKKS |
FEAAN[ | 首尔大学 | CKKS |
FHEW[ | Ducas、Micciancio | FHEW |
TFHE[ | Chillotti等 | TFHE和FHEW |
PALISADE[ | MIT、UCSD | BFV/BGV/FHEW/TFHE/CKKS |
表1 同态加密开源库列举
开源库 | 贡献者 | HE方案 |
---|---|---|
Cryptofun[ | Arnaucube | RSA/ElGamal/Paillier/etc |
HELIB[ | IBM | BGV/CKKS |
SEAL[ | 微软 | BGV/BFV/CKKS |
FEAAN[ | 首尔大学 | CKKS |
FHEW[ | Ducas、Micciancio | FHEW |
TFHE[ | Chillotti等 | TFHE和FHEW |
PALISADE[ | MIT、UCSD | BFV/BGV/FHEW/TFHE/CKKS |
NX | NY | 方案 | 离线时间/s | 在线时间/s | 在线通信量/MB |
---|---|---|---|---|---|
224 | 11 041 | CCS2018[ | 656.00 | 20.10 | 41.48 |
CCS2017[ | 71.00 | 44.70 | 23.20 | ||
5 535 | CCS2018[ | 806.00 | 22.01 | 16.39 | |
CCS2017[ | 64.00 | 40.10 | 20.10 | ||
220 | 11 041 | CCS2018[ | 43.00 | 4.49 | 14.34 |
CCS2017[ | 6.40 | 6.40 | 11.50 | ||
5 535 | CCS2018[ | 43.00 | 4.23 | 11.50 | |
CCS2017[ | 4.30 | 4.30 | 5.60 |
表2 方案对比
NX | NY | 方案 | 离线时间/s | 在线时间/s | 在线通信量/MB |
---|---|---|---|---|---|
224 | 11 041 | CCS2018[ | 656.00 | 20.10 | 41.48 |
CCS2017[ | 71.00 | 44.70 | 23.20 | ||
5 535 | CCS2018[ | 806.00 | 22.01 | 16.39 | |
CCS2017[ | 64.00 | 40.10 | 20.10 | ||
220 | 11 041 | CCS2018[ | 43.00 | 4.49 | 14.34 |
CCS2017[ | 6.40 | 6.40 | 11.50 | ||
5 535 | CCS2018[ | 43.00 | 4.23 | 11.50 | |
CCS2017[ | 4.30 | 4.30 | 5.60 |
FHE={FHE.Keygen,FHE.Enc,FHE.Const_Add,FHE.Add,FHE.Const_Mult,FHE.Mult,FHE.Dec} |
---|
1.function Setup(DB): return (pk,sk)=FHE.Keygen() //生成公、私秘钥对 |
2.function Query(pk,idx,n): for i=0 to n-1 do ci=Enc(pk,i= =idx?1:0) return q={c0,c1,…,cn-1} |
3.function Answer(q={c0,c1,…,cn-1},DB): for i=0 to n-1 do a_i=FHE.Const_Mult(DBi,ci) //明文*密文 return a=FHE.Add(a0,a1,…,an-1) //密文+密文 |
4.function Extract(sk,a): Return FHE.Dec(sk,a) |
表3 SealPIR协议框架
FHE={FHE.Keygen,FHE.Enc,FHE.Const_Add,FHE.Add,FHE.Const_Mult,FHE.Mult,FHE.Dec} |
---|
1.function Setup(DB): return (pk,sk)=FHE.Keygen() //生成公、私秘钥对 |
2.function Query(pk,idx,n): for i=0 to n-1 do ci=Enc(pk,i= =idx?1:0) return q={c0,c1,…,cn-1} |
3.function Answer(q={c0,c1,…,cn-1},DB): for i=0 to n-1 do a_i=FHE.Const_Mult(DBi,ci) //明文*密文 return a=FHE.Add(a0,a1,…,an-1) //密文+密文 |
4.function Extract(sk,a): Return FHE.Dec(sk,a) |
查询方:R; 被查询方:S |
---|
R:st=PSIR.Init(1λ,1c) S:⊥=PSIR.Init (1λ,D) |
R:(st',Query)=PSIR.Query(q,st) |
S:Reply=PSIR.Reply(Query,D) |
R:B=PSIR.Extract(Reply,st') |
R:st″=PSIR.UpdateState((st'),(D)) S:⊥=PSIR.UpdateState((st'),(D)) |
表4 PSIR协议框架
查询方:R; 被查询方:S |
---|
R:st=PSIR.Init(1λ,1c) S:⊥=PSIR.Init (1λ,D) |
R:(st',Query)=PSIR.Query(q,st) |
S:Reply=PSIR.Reply(Query,D) |
R:B=PSIR.Extract(Reply,st') |
R:st″=PSIR.UpdateState((st'),(D)) S:⊥=PSIR.UpdateState((st'),(D)) |
[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. |
[1] | 王吾冰, 刘博, 范渊, 陶立峰, 徐东德. 基于可信执行环境的机密计算框架设计及安全性分析[J]. 信息通信技术与政策, 2022, 48(8): 8-18. |
[2] | 韦韬, 潘无穷, 李婷婷, 卫振强. 可信隐私计算:破解数据密态时代“技术困局”[J]. 信息通信技术与政策, 2022, 48(5): 15-24. |
[3] | 吕艾临, 闫树. 隐私计算跨平台互联互通的若干思考[J]. 信息通信技术与政策, 2022, 48(5): 2-6. |
[4] | 周建平, 郑培钿, 王云河, 靳晨, 时代. 浅析隐私保护计算技术对数据交易流通模式的影响[J]. 信息通信技术与政策, 2022, 48(5): 25-33. |
[5] | 符芳诚, 刘舒, 程勇, 陶阳宇. 基于同态加密和秘密分享的纵向联邦LR协议研究[J]. 信息通信技术与政策, 2022, 48(5): 34-44. |
[6] | 贾轩, 白玉真, 马智华. 隐私计算应用场景综述[J]. 信息通信技术与政策, 2022, 48(5): 45-52. |
[7] | 王雪, 李武璐, 李原, 何林芳, 刘春伟, 李思思. 隐私计算在普惠金融领域的应用研究[J]. 信息通信技术与政策, 2022, 48(5): 53-59. |
[8] | 陈如梵, 王林, 郭兰停, 郑灏, 孙琪, 李帜, 王爽. 生物医疗场景下的隐私保护计算应用*[J]. 信息通信技术与政策, 2022, 48(5): 60-67. |
[9] | 杨靖世, 王思源, 袁博, 刘嘉夕. 隐私计算产品性能测评标准化研究[J]. 信息通信技术与政策, 2022, 48(5): 7-14. |
[10] | 韩宗达, 邓宇涛, 程祥. 不经意关键词检索技术综述[J]. 信息通信技术与政策, 2022, 48(5): 82-90. |
[11] | 赵精武, 周瑞珏. 隐私计算技术:数据流动与数据安全的协同保护规则构建*[J]. 信息通信技术与政策, 2021, 47(7): 53-. |
[12] | 梁灯. 隐私计算定向广告应用的法律边界[J]. 信息通信技术与政策, 2021, 47(7): 66-75. |
[13] | 柴迪. 阈值同态加密在隐私计算中的应用[J]. 信息通信技术与政策, 2021, 47(7): 82-86. |
[14] | 闫树, 吕艾临. 隐私计算发展综述[J]. 信息通信技术与政策, 2021, 47(6): 1-11. |
[15] | 袁博, 王思源. 隐私计算产品评估体系[J]. 信息通信技术与政策, 2021, 47(6): 12-18. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
您是第 位访问者
版权所有 © 2020 信息通信技术与政策 备案序号: 京ICP备09013372号
地址: 北京市海淀区花园北路52号 电话: 010-62300192 传真: 010-68027707 E-mail: ictp@caict.ac.cn