Maximum Value of Sum of Intersection Elements of Secret Calculation

MA Xiu-lian; ZHANG Juan-juan; LI Shun-dong

doi:10.12263/DZXB.20221177

您当前的位置：

首页 >

文章列表页 >

Maximum Value of Sum of Intersection Elements of Secret Calculation

PAPERS | 更新时间：2025-12-08

- Maximum Value of Sum of Intersection Elements of Secret Calculation
- ACTA ELECTRONICA SINICA Vol. 51, Issue 7, Pages: 1835-1841(2023)
- 作者机构：
  
  陕西师范大学计算机科学学院，陕西西安 710119
- 作者简介：
- 基金信息：
  
  Foundation Item(s):　National Natural Science Foundation of China(61272435)
- DOI：10.12263/DZXB.20221177
  CLC： TP309
- Received：17 October 2022，
  
  Revised：2023-06-19，
  
  Published：25 July 2023
- 稿件说明：
移动端阅览
马秀莲,张倦倦,李顺东.保密计算交集对应元素和的最大值[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)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Secure Computation of Subsets from Tuple Sets

Secure Multi-Party Computation for Minimum and Its Applications

A Two-Party SM2 Signing Protocol with Strict Provable Security

k-min Security Multi-Party Computing Solution and Application

Related Author

LI Shun-dong

DU Ji-xin

YU Jia-tong

WU Chuan-yu

DOU Jia-wei

MA Li

LI Shun-dong

CHENG Yi-fan

Related Institution

School of Computer Science, Shaanxi Normal University

School of Mathematics and Information Science, Shaanxi Normal University

School of Mathematics and Information Science Shaanxi Normal University Xi'an Shaanxi China

School of Computer Science Shaanxi Normal University Xi'an Shaanxi China

SSC Holding Company Ltd.， Chengmai

⁰