保密计算交集对应元素和的最大值

马秀莲; 张倦倦; 李顺东

doi:10.12263/DZXB.20221177

您当前的位置：

首页 >

文章列表页 >

保密计算交集对应元素和的最大值

学术论文 | 更新时间：2025-12-08

- 保密计算交集对应元素和的最大值
- Maximum Value of Sum of Intersection Elements of Secret Calculation
- 电子学报 2023年51卷第7期页码：1835-1841
- 作者机构：
  
  陕西师范大学计算机科学学院，陕西西安 710119
- 作者简介：
  
  [ "马秀莲女，1997年9月出生于青海省西宁市.现为陕西师范大学计算机科学学院硕士生.主要研究方向为密码学与信息安全.E-mail: xiulian@snnu.edu.cn" ]
  [ "张倦倦女，2000年2月出生于陕西省榆林市.现为陕西师范大学计算机科学学院硕士生.主要研究方向为密码学与信息安全.E-mail: zjuanjuan@snnu.edu.cn" ]
  [ "李顺东（通讯作者）男，1963年12月出生于河南省平顶山市.现为陕西师范大学计算机科学学院博士生导师.主要研究方向为密码学与信息安全." ]
- 基金信息：
  
  国家自然科学基金(61272435)
- DOI：10.12263/DZXB.20221177
  中图分类号： TP309
- 收稿：2022-10-17，
  
  修回：2023-06-19，
  
  纸质出版：2023-07-25
- 稿件说明：
移动端阅览
马秀莲,张倦倦,李顺东.保密计算交集对应元素和的最大值[J].电子学报,2023,51(07):1835-1841.

MA Xiu-lian,ZHANG Juan-juan,LI Shun-dong.Maximum Value of Sum of Intersection Elements of Secret Calculation[J].ACTA ELECTRONICA SINICA,2023,51(07):1835-1841.
马秀莲,张倦倦,李顺东.保密计算交集对应元素和的最大值[J].电子学报,2023,51(07):1835-1841. DOI： 10.12263/DZXB.20221177.

MA Xiu-lian,ZHANG Juan-juan,LI Shun-dong.Maximum Value of Sum of Intersection Elements of Secret Calculation[J].ACTA ELECTRONICA SINICA,2023,51(07):1835-1841. DOI： 10.12263/DZXB.20221177.

摘要

安全多方计算是国际密码学的研究热点之一，隐私集合问题是安全多方计算的重要研究方向.本文提出了一个新的安全多方计算问题：Alice和Bob分别拥有集合

</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></mfenced></mrow></mfenced></mrow><mrow><mi>i</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>l</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mrow></msubsup></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677326&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677314&type=

19.64266586

5.50333309

和

</mo><msub><mrow><mi>y</mi></mrow><mrow><mi>j</mi></mrow></msub><msubsup><mrow><mo stretchy="false">)</mo><mo stretchy="false">}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>l</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow></msubsup></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677331&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677334&type=

18.28800011

4.48733330

，他们想要保密计算

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677352&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677349&type=

7.61999989

3.21733332

时的最大值

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677355&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677354&type=

15.57866764

3.89466691

.该问题在教育、网购等领域具有重要的理论和现实意义.针对这个问题，我们在半诚实模型下提出了两个安全协议.第一个协议基于编码方法和保密移位思想，适用于元组中元素数据范围已知的情况.第二个协议利用Paillier密码算法和添加假元素的方法，适用于元素数据范围未知的情况.最后，我们使用公认的模拟范式证明了两个协议是安全的.

Abstract

Secure multi-party computation is one of the research hotspots in the international cryptographic community. Privacy set problem is an important research direction of secure multi-party computation. In this paper

we propose a novel secure multi-party computation problem

i.e.

Alice and Bob have two private sets

</mo><msub><mrow><mi>x</mi></mrow><mrow><mi>i</mi></mrow></msub><msubsup><mrow><mo stretchy="false">)</mo><mo stretchy="false">}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>l</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></mrow></msubsup></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677360&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677344&type=

17.61066628

4.14866638

and

</mo><mtext> </mtext><msub><mrow><mi>y</mi></mrow><mrow><mi>j</mi></mrow></msub></mrow></mfenced><mo stretchy="false">}</mo></mrow><mrow><mi>j</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><msub><mrow><mi>l</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></mrow></msubsup><mo>

</mo><mtext> </mtext></math>

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677367&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677361&type=

21.59000015

4.57200003

and they want to compute

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677382&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677369&type=

15.57866764

3.89466691

where

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677388&type=

https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=47677386&type=

7.61999989

3.21733332

. This problem has important theoretical and practical significance in education

online shopping and other fields. In response to this problem

we propose two security protocols in the semi-honest model. The first protocol

which is based on an encoding method and secure shift

is for the case where two tuples of elements of the private sets are elements of a known set whose cardinality is not large. The second protocol

which is based on Paillier cryptosystem and the method of adding fake elements

is for the case where two tuples of elements of the private sets are not known. Finally

we demonstrate the security of both protocols using recognized simulation paradigm.

关键词

Keywords

references

YAO A C . Protocols for secure computations [C]// 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) . Piscataway : IEEE , 2008 : 160 - 164 .

GOLDREICH O , MICALI S , WIGDERSON A . How to play ANY mental game [C]// The 19th Annual ACM Conference on Theory of Computing . New York : ACM , 1987 : 218 - 229 .

DOU J W , GONG L M , LI S D , et al . Efficient private subset computation [J]. Security and Communication Networks , 2016 , 9 ( 18 ): 5965 - 5976 .

陈振华 , 李顺东 , 王道顺 , 等 . 非加密方法安全计算集合包含关系 [J]. 计算机研究与发展 , 2017 , 54 ( 7 ): 1549 - 1556 .

CHEN Z H , LI S D , WANG D S , et al . Protocols for secure computation of set-inclusion with the unencrypted method [J]. Journal of Computer Research and Development , 2017 , 54 ( 7 ): 1549 - 1556 . (in Chinese)

SUN H L , WEI L F , WANG L B , et al . A trusted and privacy-preserving carpooling matching scheme in vehicular networks [J]. Journal of Information Security , 2022 , 13 ( 1 ): 1 - 22 .

YANG L , LI C , CHENG Y T , et al . Achieving privacy-preserving sensitive attributes for large universe based on private set intersection [J]. Information Sciences , 2022 , 582 : 529 - 546 .

ADAVOUDI JOLFAEI A , MALA H , ZAREZADEH M . EO-PSI-CA: Efficient outsourced private set intersection cardinality [J]. Journal of Information Security and Applications , 2022 , 65 : 102996 .

ALI M , MOHAJERI J , SADEGHI M R , et al . Attribute-based fine-grained access control for outscored private set intersection computation [J]. Information Sciences , 2020 , 536 : 222 - 243 .

YAO L , CHEN Z Y , WANG X , et al . Sensitive label privacy preservation with anatomization for data publishing [J]. IEEE Transactions on Dependable and Secure Computing , 2021 , 18 ( 2 ): 904 - 917 .

SHU X K , YAO D F , BERTINO E . Privacy-preserving detection of sensitive data exposure [J]. IEEE Transactions on Information Forensics and Security , 2015 , 10 ( 5 ): 1092 - 1103 .

RAGHUVIR Y A , GOVINDARAJAN S , VIJAYAKUMAR S , et al . Advancement on security applications of private intersection sum protocol [C]// Proceedings of the Future Technologies Conference (FTC) 2021 , Volume 3 . Cham : Springer International Publishing , 2021: 104 - 116 .

KOLESNIKOV V , KUMARESAN R , ROSULEK M , et al . Efficient batched oblivious PRF with applications to private set intersection [C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM , 2016 : 818 - 829 .

YANG X C , YI X , KELAREV A , et al . A distributed networked system for secure publicly verifiable self-tallying online voting [J]. Information Sciences , 2021 , 543 : 125 - 142 .

ION M , KREUTER B , NERGIZ A E , et al . On deploying secure computing: Private intersection-sum-with-cardinality [C]// 2020 IEEE European Symposium on Security and Privacy (EuroS&P) . Piscataway : IEEE , 2020 : 370 - 389 .

GOLDREICH O . The Fundamental of Cryptography: Basic Applications [M]. London : Cambridge University Press , 2004 : 599 - 764 .

杨晓艺 , 李顺东 , 亢佳 . 保密替换及其在保密科学计算中的应用 [J]. 计算机学报 , 2018 , 41 ( 5 ): 1132 - 1142 .

YANG X Y , LI S D , KANG J . Private substitution and its applications in private scientific computation [J]. Chinese Journal of Computers , 2018 , 41 ( 5 ): 1132 - 1142 . (in Chinese)

李顺东 , 张萌雨 . 盲百万富翁问题的高效解决方案 [J]. 计算机学报 , 2020 , 43 ( 9 ): 1755 - 1768 .

LI S D , ZHANG M Y . An efficient solution to the blind millionaires' problem [J]. Chinese Journal of Computers , 2020 , 43 ( 9 ): 1755 - 1768 . (in Chinese)

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

元组集合子集的保密计算

最小值问题的安全多方计算及其应用

严格可证明安全的两方协同SM2签名协议

k-min问题安全多方计算方案及应用