A Secure Multi-Party Strings Sorting Protocol Based on National Cryptographic Algorithm

ZHOU Yousheng; DING Shan; ZUO Xiangjian; LIU Yuanni

doi:10.11999/JEIT240028

Volume 46 Issue 9

Sep. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(9): 3763-3770

ZHOU Yousheng, DING Shan, ZUO Xiangjian, LIU Yuanni. A Secure Multi-Party Strings Sorting Protocol Based on National Cryptographic Algorithm[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3763-3770. doi: 10.11999/JEIT240028

Citation:

ZHOU Yousheng, DING Shan, ZUO Xiangjian, LIU Yuanni. A Secure Multi-Party Strings Sorting Protocol Based on National Cryptographic Algorithm[J]. Journal of Electronics & Information Technology, 2024, 46(9): 3763-3770. doi: 10.11999/JEIT240028

Citation:

PDF( 745 KB)

A Secure Multi-Party Strings Sorting Protocol Based on National Cryptographic Algorithm

doi: 10.11999/JEIT240028

1.
College of Cyberspace Security and Information Law, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2.
College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (62272076), The Science and Technology Research Program of Chongqing Municipal Education Commission (KJQN202200625), The Natural Science Foundation of Chongqing, China (CSTB2022NSCQ-MSX0038)

Received Date: 2024-01-18
Rev Recd Date: 2024-07-14

Available Online: 2024-08-02

Publish Date: 2024-09-26

Abstract

Abstract

The secure sorting problem is derived from the millionaire problem and is a fundamental problem in secure multi-party computation research. Multi-party string sorting is of great significance for the research of database confidential queries and electronic voting sum problems. The existing research on secure sorting problems mostly focuses on private data sorting or two-party string sorting. Efficient multi-party string sorting schemes are still being explored. Based on the improved SM2 homomorphic encryption algorithm and threshold cryptography algorithm, this paper first proposes a confidentiality multi-party single character sorting protocol in a semi honest model, and then designs a weight-based confidentiality single character sorting protocol and a confidentiality multi-party string sorting protocol. Simulation paradigm is used to demonstrate the security of three protocols. The paper conducts performance analysis and simulation experiments on the three protocols. The results show that the performance of the proposed secure multi-party single character sorting protocol and secure multi-party string sorting protocol is significantly improved compared to existing similar schemes.
- Secure multi-party computation,
- Privacy-preserving sorting,
- Homomorrphic encryption,
- Threshold cryptography,
- National cryptographic algorithm

FullText(HTML)

References(24)

References

[1]	YAO A C. Protocols for secure computations[C]. The 23rd Annual Symposium on Foundations of Computer Science, Chicago, USA, 1982: 160–164. doi: 10.1109/SFCS.1982.38.
[2]	JÓNSSON K V, KREITZ G, and UDDIN M. Secure multi-party sorting and applications[J]. IACR Cryptology ePrint Archive, 2011, 2011: 122–142.
[3]	CHOI S G, HWANG K W, KATZ J, et al. Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces[C]. The Cryptographers’ Track at the RSA Conference, San Francisco, USA, 2012: 416–432. doi: 10.1007/978-3-642-27954-6_26.
[4]	FAN Xingyue, WU Ting, ZHENG Qiuhua, et al. HSE-Voting: A secure high-efficiency electronic voting scheme based on homomorphic signcryption[J]. Future Generation Computer Systems, 2020, 111: 754–762. doi: 10.1016/j.future.2019.10.016.
[5]	HUSZTI A. A homomorphic encryption-based secure electronic voting scheme[J]. Publicationes Mathematicae Debrecen, 2011, 79(3/4): 479–496. doi: 10.5486/PMD.2011.5142.
[6]	QU Wenlei, WU Lei, WANG Wei, et al. A electronic voting protocol based on blockchain and homomorphic signcryption[J]. Concurrency and Computation: Practice and Experience, 2022, 34(16): e5817. doi: 10.1002/cpe.5817.
[7]	NAIDU P S, KHARAT R, TEKADE R, et al. E-voting system using visual cryptography & secure multi-party computation[C]. 2016 International Conference on Computing Communication Control and automation, Pune, India, 2016: 1–4. doi: 10.1109/ICCUBEA.2016.7860062.
[8]	HAGA R, TOYODA K, SHINODA Y, et al. Card-based secure sorting protocol[C]. The 17th International Workshop on Security, Tokyo, Japan, 2022: 224–240. doi: 10.1007/978-3-031-15255-9_12.
[9]	唐春明, 石桂花, 姚正安. 排序问题的安全多方计算协议[J]. 中国科学: 信息科学, 2011, 41(7): 789–797. doi: 10.1360/zf2011-41-7-789. TANG Chunming, SHI Guihua, and YAO Zheng’an. Secure multi-party computation protocol for sequencing problem[J]. Science China Information Sciences, 2011, 54(8): 1654–1662. doi: 10.1360/zf2011-41-7-789.
[10]	YUE Conghan, ZOU Qinghua, YANG Moude, et al. A practical secure multi-party sorting scheme based on radix sorting and homomorphic encryption[C]. 2022 International Conference on Blockchain Technology and Information Security, Huaihua, China, 2022: 127–130. doi: 10.1109/ICBCTIS55569.2022.00039.
[11]	邱梅, 罗守山, 刘文, 等. 利用RSA密码体制解决安全多方多数据排序问题[J]. 电子学报, 2009, 37(5): 1119–1123. doi: 10.3321/ j.issn:0372-2112.2009.05.037. QIU Mei, LUO Shoushan, LIU Wen, et al. A solution of secure multi-party multi-data ranking problem based on RSA encryption scheme[J]. Acta Electronica Sinica, 2009, 37(5): 1119–1123. doi: 10.3321/j.issn:0372-2112.2009.05.037.
[12]	ASHAROV G, HAMADA K, IKARASHI D, et al. Efficient secure three-party sorting with applications to data analysis and heavy hitters[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 125–138. doi: 10.1145/3548606.3560691.
[13]	DAI Hua, REN Hui, CHEN Zhiye, et al. Privacy-preserving sorting algorithms based on logistic map for clouds[J]. Security and Communication Networks, 2018, 2018: 2373545. doi: 10.1155/2018/2373545.
[14]	李顺东, 杜润萌, 杨颜璟, 等. 安全多方多数据排序[J]. 计算机学报, 2020, 43(8): 1448–1462. doi: 10.11897/SP.J.1016.2020.01448. LI Shundong, DU Runmeng, YANG Yanjing, et al. Secure multiparty multi-data ranking[J]. Chinese Journal of Computers, 2020, 43(8): 1448–1462. doi: 10.11897/SP.J.1016.2020.01448.
[15]	窦家维, 汪榆淋. 安全排序协议及其应用[J]. 软件学报, 2022, 33(11): 4316–4333. doi: 10.13328/j.cnki.jos.006326. DOU Jiawei and WANG Yulin. Secure sorting protocols and their applications[J]. Journal of Software, 2022, 33(11): 4316–4333. doi: 10.13328/j.cnki.jos.006326.
[16]	李顺东, 亢佳, 杨晓艺, 等. 基于字符串排序的高效保密数据库查询[J]. 软件学报, 2018, 29(7): 1893–1908. doi: 10.13328/j.cnki.jos.005358. LI Shundong, KANG Jia, YANG Xiaoyi, et al. String sorting based efficient secure database query[J]. Journal of Software, 2018, 29(7): 1893–1908. doi: 10.13328/j.cnki.jos.005358.
[17]	李顺东, 亢佳, 杨晓艺, 等. 多个字符排序的安全多方计算[J]. 计算机学报, 2018, 41(5): 1172–1188. doi: 10.11897/SP.J.1016.2018.01172. LI Shundong, KANG Jia, YANG Xiaoyi, et al. Secure multiparty characters sorting[J]. Chinese Journal of Computers, 2018, 41(5): 1172–1188. doi: 10.11897/SP.J.1016.2018.01172.
[18]	ODED G. Foundations of Cryptography: Volume 2, Basic Applications[M]. New York: Cambridge University Press, 2009: 599–764.
[19]	唐飞, 凌国玮, 单进勇. 基于国密SM2和SM9的加法同态加密方案[J]. 密码学报, 2022, 9(3): 535–549. doi: 10.13868/j.cnki.jcr.000532. TANG Fei, LING Guowei, and SHAN Jinyong. Additive homomorphic encryption schemes based on SM2 and SM9[J]. Journal of Cryptologic Research, 2022, 9(3): 535–549. doi: 10.13868/j.cnki.jcr.000532.
[20]	中华人民共和国国家质量监督检验检疫总局, 中国国家标准化管理委员会. GB/T 32918.4-2016 信息安全技术 SM2椭圆曲线公钥密码算法第4部分: 公钥加密算法[S]. 北京: 中国标准出版社, 2017. General Administration of Quality Supervision, Inspection and Quarantine of the People’s Republic of China, Standardization Administration of the People’s Republic of China. GB/T 32918.4-2016 Information security technology—public key cryptographic algorithm SM2 based on elliptic curves—part 4: Public key encryption algorithm[S]. Beijing: Standards Press of China, 2017.
[21]	CRAMER R, GENNARO R, and SCHOENMAKERS B. A secure and optimally efficient multi-authority election scheme[J]. European Transactions on Telecommunications, 1997, 8(5): 481–490. doi: 10.1002/ett.4460080506.
[22]	DESMEDT Y and FRANKEL Y. Threshold cryptosystems[C]. The Conference on the Theory and Application of Cryptology, Santa Barbara, USA, 1990: 307–315. doi: 10.1007/0-387-34805-0_28.
[23]	KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203–209. doi: 10.1090/S0025-5718-1987-0866109-5.
[24]	ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469–472. doi: 10.1109/TIT.1985.1057074.