微信服务号

微信订阅号

2025年6月16日 10:45 星期一
首页 > 过刊浏览>2023年第34卷第11期 >5408-5423. DOI:10.13328/j.cnki.jos.006737
PDF HTML阅读 XML下载 导出引用 引用提醒
分布式数据集极差与极值和的保密计算
作者:
作者简介:

李顺东(1963－),男,博士,教授,博士生导师,主要研究领域为密码学,信息安全;家珠亮(1992－),女,硕士生,主要研究领域为密码学,信息安全;赵雪玲(1996－),女,硕士生,主要研究领域为密码学,信息安全

通讯作者:

李顺东，shundong@snnu.edu.cn

中图分类号:

TP309


Secure Computation of Range and Sum of Extremums on Distributed Datasets
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [39]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    随着信息通信技术的不断突破与发展, 信息获取变得非常便利. 与此同时, 隐私信息也更容易泄露. 将智能领域与安全多方计算技术相结合, 有望解决隐私保护问题. 目前, 安全多方计算已经解决了许多不同隐私保护问题, 但还有更多的问题等待人们去解决. 对于极差、极值和的安全多方计算问题目前研究的结果很少, 极差、极值和作为统计学的常用工具在实际中有广泛的应用, 研究极差、极值和的保密计算具有重要意义. 提出新编码方法, 用新编码方法解决了两种不同的安全多方计算问题, 一是极差的保密计算问题, 二是极值和的保密计算问题. 新编码方法结合Lifted ElGamal门限密码系统, 设计多方参与、每方拥有一个数据场景下分布式隐私数据集极差的保密计算协议; 将新编码方法稍作改动解决相同场景下保密计算极值和的问题. 以此为基础, 对新编码方法进一步修改, 结合Paillier密码系统设计了两方参与、每方拥有多个数据情况下分布式隐私数据集极差、极值和的保密计算协议. 用模拟范例方法证明协议在半诚实模型下的安全性. 最后, 用模拟实验测试协议的复杂性. 效率分析和实验结果表明所提协议简单高效, 可广泛用于实际应用中, 是解决其他很多安全多方计算问题的重要工具.

    Abstract:

    Due to the continuous breakthrough and development of information and communication technologies, information access has become convenient on the one hand. On the other hand, private information is now easier to leak than before. The combination of the intelligent field and secure multiparty computation (SMC) technology is expected to solve privacy protection problems. Although SMC has solved many different privacy protection problems so far, problems that remain to be settled are numerous. Research results about the SMC of range and the sum of extremums are currently seldom reported. As a common statistical tool, range and sum of extremums have been widely used in practice. Therefore, the secure computation of range and the sum of extremes are of great research significance. This study proposes a new encoding method and solves two types of SMC problems by the method: One is the secure computation of range, and the other is that of the sum of extremums. The new encoding method is combined with the Lifted ElGamal threshold cryptosystem to design a secure range computation protocol for distributed private datasets in the scenario in which multiple parties participate and each party has one data. Then, the new encoding method is slightly modified for the secure computation of the sum of extremums in the same scenario. On this basis, the study further modifies the new encoding method and combines it with the Paillier cryptosystem to design a protocol for the secure computation of range and the sum of extremums on distributed private datasets in the scenario in which two parties participate and each party has more than one data. Furthermore, this study proves that the proposed protocols are secure in the semi-honest model with the simulation paradigm. Finally, the complexities of these protocols are tested by simulation experiments. The results of the efficiency analysis and experiments show that the simple and efficient proposed protocols can be widely used in practical applications and are important tools for solving many other SMC problems.

    参考文献
    [1] Yao AC. Protocols for secure computations. In: Proc. of the 23rd Annual Symp. on Foundations of Computer Science. Chicago: IEEE Computer Society, 1982. 160–164.
    [2] Goldreich O, Micali S, Wigderson A. How to play any mental game. In: Proc. of the 19th Annual ACM Symp. on Theory of Computing. New York: ACM, 1987. 218–229.
    [3] Goldwasser S. Multi party computations: Past and present. In: Proc. of the 16th Annual ACM Symp. on Principles of Distributed Computing. Santa Barbara: ACM, 1997. 1–6.
    [4] Yasin S, Haseeb K, Qureshi RJ. Cryptography based E-commerce security: A review. International Journal of Computer Science Issues, 2012, 9(2): 132–137.
    [5] Miyajima H, Shigei N, Miyajima H, Norio S. A proposal of profit sharing method for secure multiparty computation. International Journal of Innovative Computing, Information and Control, 2018, 14(2): 727–735.
    [6] Zhao C, Zhao SN, Zhao MH, Chen ZX, Gao CZ, Li HW, Tan YA. Secure multi-party computation: Theory, practice and applications. Information Sciences, 2019, 476: 357–372. [doi: 10.1016/j.ins.2018.10.024]
    [7] Collins MJ. Efficient secure multiparty computation of sparse vector dot products. Journal of Discrete Mathematical Sciences and Cryptography, 2018, 21(5): 1107–1117. [doi: 10.1080/09720529.2018.1453623]
    [8] Park H, Moon J. Irregular product coded computation for high-dimensional matrix multiplication. In: Proc. of the 2019 IEEE Int’l Symp. on Information Theory. Paris: IEEE, 2019. 1782–1786.
    [9] Liu XM, Choo KKR, Deng RH, Lu RX, Weng J. Efficient and privacy-preserving outsourced calculation of rational numbers. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 27–39. [doi: 10.1109/TDSC.2016.2536601]
    [10] Kim M, Yang H, Lee J. Private coded matrix multiplication. IEEE Transactions on Information Forensics and Security, 2020, 15: 1434–1443. [doi: 10.1109/TIFS.2019.2940895]
    [11] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption. In: Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security. Dallas: ACM, 2017. 1243–1255.
    [12] Egert R, Fischlin M, Gens D, Jacob S, Senker M, Tillmanns J. Privately computing set-union and set-intersection cardinality via bloom filters. In: Proc. of the 20th Australasian Conf. on Information Security and Privacy. Brisbane: Springer, 2015. 413–430.
    [13] 李光, 王亚东. 一种改进的基于奇异值分解的隐私保持分类挖掘方法. 电子学报, 2012, 40(4): 739–744.
    Li G, Wang YD. An improved Privacy-Preserving classification mining method based on singular value decomposition. Acta Electronica Sinica, 2012, 40(4): 739–744 (in Chinese with English abstract)
    [14] Zhu H, Liu F, Li H. Efficient and privacy-preserving polygons spatial query framework for location-based services. IEEE Internet of Things Journal, 2017, 4(2): 536–545. [doi: 10.1109/JIOT.2016.2553083]
    [15] Sun GS, Qian Q. Deep learning and visualization for identifying malware families. IEEE Transactions on Dependable and Secure Computing, 2021, 18(1): 283–295. [doi: 10.1109/TDSC.2018.2884928]
    [16] Phong LT, Aono Y, Hayashi T, Wang LH, Moriai S. Privacy-Preserving deep learning via additively homomorphic encryption. IEEE Transactions on Information Forensics and Security, 2018, 13(5): 1333–1345. [doi: 10.1109/TIFS.2017.2787987]
    [17] Liu C, Zhu LH, He XJ, Chen JJ. Enabling privacy-preserving shortest distance queries on encrypted graph data. IEEE Transactions on Dependable and Secure Computing, 2021, 18(1): 192–204. [doi: 10.1109/TDSC.2018.2880981]
    [18] Ge SS, Zeng P, Lu RX, Choo KKR. FGDA: Fine-grained data analysis in privacy-preserving smart grid communications. Peer-to-Peer Networking and Applications, 2018, 11(5): 966–978. [doi: 10.1007/s12083-017-0618-9]
    [19] Essex A. Secure approximate string matching for privacy-preserving record linkage. IEEE Transactions on Information Forensics and Security, 2019, 14(10): 2623–2632. [doi: 10.1109/TIFS.2019.2903651]
    [20] Bag S, Hao F, Shahandashti SF, Ray IG. SEAL: Sealed-Bid auction without auctioneers. IEEE Transactions on Information Forensics and Security, 2020, 15: 2042–2052. [doi: 10.1109/TIFS.2019.2955793]
    [21] 李占利, 陈立朝, 陈振华, 刘娅茹. 云环境下多方保密计算最大值、最小值及其统计学应用. 密码学报, 2019, 6(2): 219–233. [doi: 10.13868/j.cnki.jcr.000297]
    Li ZL, Chen LC, Chen ZH, Liu YR. Secure multiparty computation of the maximum and the minimum in cloud environment and its statistics application. Journal of Cryptologic Research, 2019, 6(2): 219–233 (in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000297]
    [22] Sciancalepore S, Di Pietro R. PPRQ: Privacy-preserving MAX/MIN range queries in IoT networks. IEEE Internet of Things Journal, 2021, 8(6): 5075–5092. [doi: 10.1109/JIOT.2020.3037115]
    [23] Zhang Y, Chen QJ, Zhong S. Efficient and privacy-preserving min and k th min computations in mobile sensing systems. IEEE Transactions on Dependable and Secure Computing, 2017, 14(1): 9–21. [doi: 10.1109/TDSC.2015.2432814]
    [24] Yao YL, Xiong NX, Park JH, Ma L, Liu JF. Privacy-preserving max/min query in two-tiered wireless sensor networks. Computers & Mathematics with Applications, 2013, 65(9): 1318–1325. [doi: 10.1016/j.camwa.2012.02.003]
    [25] 窦家维, 马丽, 李顺东. 最小值问题的安全多方计算及其应用. 电子学报, 2017, 45(7): 1715–1721.
    Dou JW, Ma L, Li SD. Secure multi-party computation for minimum and its applications. Acta Electronica Sinica, 2017, 45(7): 1715–1721 (in Chinese with English abstract).
    [26] 杨晓艺, 李顺东, 亢佳. 保密替换及其在保密科学计算中的应用. 计算机学报, 2018, 41(5): 1132–1142. [doi: 10.11897/SP.J.1016.2018.01132]
    Yang XY, Li SD, Kang J. Private substitution and its applications in private scientific computation. Chinese Journal of Computers, 2018, 41(5): 1132–1142 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2018.01132]
    [27] 杨颜璟, 李顺东, 杜润萌. 最大最小值的保密计算. 密码学报, 2020, 7(4): 483–497. [doi: 10.13868/j.cnki.jcr.000383]
    Yang YJ, Li SD, Du RM. Private maximum and minimum computation. Journal of Cryptologic Research, 2020, 7(4): 483–497 (in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000383]
    [28] 李顺东, 徐雯婷, 王文丽, 张萌雨. 恶意模型下的最大(小)值保密计算. 计算机学报, 2021, 44(10): 2076–2089. [doi: 10.11897/SP.J.1016.2021.02076]
    Li SD, Xu WT, Wang WL, Zhang MY. Secure maximum (minimum) computation in malicious model. Chinese Journal of Computers, 2021, 44(10): 2076–2089 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2021.02076]
    [29] Goldreich O. Foundations of Cryptography. II: Basic Applications. Cambridge: Cambridge University Press, 2004.
    [30] Reimer B, Fried R, Mehler B, Joshi G, Bolfek A, Godfrey KM, Zhao N, Goldin R, Biederman J. Brief report: Examining driving behavior in young adults with high functioning autism spectrum disorders: A pilot study using a driving simulation paradigm. Journal of Autism and Developmental Disorders, 2013, 43(9): 2211–2217. [doi: 10.1007/s10803-013-1764-4]
    [31] Liu J, Asokan N, Pinkas B. Secure deduplication of encrypted data without additional independent servers. In: Proc. of the 22nd ACM SIGSAC Conf. on Computer and Communications Security. Denver: ACM, 2015. 874–885.
    [32] Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469–472. [doi: 10.1109/TIT.1985.1057074]
    [33] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proc. of the 1999 Int’l Conf. on the Theory and Application of Cryptographic Techniques. Prague: Springer, 1999. 223–238.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李顺东,家珠亮,赵雪玲.分布式数据集极差与极值和的保密计算.软件学报,2023,34(11):5408-5423

复制
分享
文章指标
  • 点击次数:504
  • 下载次数: 2066
  • HTML阅读次数: 1374
  • 引用次数: 0
历史
  • 收稿日期:2021-11-29
  • 最后修改日期:2022-02-21
  • 在线发布日期: 2023-05-18
  • 出版日期: 2023-11-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第20057818位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号