Secure Computation of Range and Sum of Extremums on Distributed Datasets
Author:
Affiliation:

Clc Number:

TP309

  • Article
  • | |
  • Metrics
  • |
  • Reference [39]
  • |
  • Related [20]
  • | | |
  • Comments
    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.

    Reference
    [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.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:491
  • PDF: 1968
  • HTML: 1198
  • Cited by: 0
History
  • Received:November 29,2021
  • Revised:February 21,2022
  • Online: May 18,2023
  • Published: November 06,2023
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063