点和区间包含问题的保密计算

吴宏锋　胡振华

摘   要：安全多方计算问题是近年来密码学研究的热点问题，其中多方保密计算是网络空间隐私保护与信息安全的关键技术。文章研究了计算几何中有理数域内点和区间包含问题的保密计算问题，即保密的判定一个隐私的有理数是否属于一个保密的有理区间。文章利用安全多方计算的思想设计了一个高效的安全协议，并证明了协议在半诚实模型下的安全性，与现有的其他文献相比，本文的协议具有更低的计算复杂度。

关键词：密码学;安全多方计算;点与区间的保密计算;计算几何

中图分类号： TP309          文献标识码：A

Abstract： The problem of secure multi-party computing is a hot issue in cryptography research in recent years. Among them， multi-party secret computing is a key technology for privacy protection and information security in cyberspace. In this paper， we study the secret calculation problem of the inclusion problem of points and intervals in the field of rational numbers in computational geometry， that is， whether the privacy rational number belongs to a confidential rational interval. This paper uses the idea of secure multi-party computing to design an efficient security protocol， and proves the security of the protocol under the semi-honest model. Compared with other existing literature， the computational complexity of this protocol is lower.

Key words： cryptography; secure multiparty computation; secret computation of points and intervals; computing geometry

1 引言

安全多方计算（Secure Multi-Party Computation，SMC）问题是从具体的密码学问题中抽象出来的，对它的研究以及由此得到的一些结论对具体的密码学问题有着指导意义，它可以从原则上告诉人们哪些问题是可以解决的，哪些是不可以解决的。但是，由于安全多方计算问题是一个非常抽象的问题，使得人们很难找到有效的算法去实现它，从而导致了它在具体应用上的局限性。对于一个具体的密码学问题，可以先根据安全多方计算的结论在原则上确定这个问题是否可以解决，如果可以解决，就需要具体问题具体分析，寻找解决该问题的具体解决方案。实际上，安全多方计算蕴含了对任何密码学协议问题在原则上的实现方案，它是分布式密码学和分布式计算研究的一个基本问题。

安全多方计算最早是由Yao[1]在1942年通过百万富翁问题提出两方安全计算问题引入的，经过Goldreich、Micali、Wigderson[2]等学者的发展，安全多方计算已经成为近年来国际密码学研究的热点问题之一，是网络信息安全、隐私探索的关键技术。在1987年，Goldwasser[3]曾预言，安全多方计算将成为密码学中一个必不可少的组成部分，这激励着许多学者不断研究探索，并在多方面取得了丰硕的成果。Yao[4]用混淆电路的方法证明了所有的安全多方计算问题都是可解的，Goldreich等人[2，5]给出了基于心理游戏（mental game）的通用解决方案，但是这两种方案的效率都很低，仅有理论意义，所以Goldreich指出，理论上证明所有的安全多方计算问题的可解性并不表示不再需要对具体问题具体分析，相反的由于效率的原因，应该对具体问题提出具体的解决方案，一般条件下提出的一些解决方案是不切实际的，所以就需要对已有的问题进行更加深入的研究，以提出更有效的解决方案，使安全多方计算可以更好地应用于社会生活中。目前研究的安全多方计算问题多应用于军事或者航空航天方面，主要包括四类：保密的科学计算问题、保密的计算几何问题、保密的统计分析问题和数据挖掘问题。虽然人们已经研究出很多的安全多方计算问题，并提出相应的解决方案，但这些方案的效率还亟待提高，除此之外还有许多新的问题需要研究。本文研究的点和区间的包含问题就是需要用新的方法研究的一个保密計算问题。

百万富翁问题[6]是指有两个百万富翁，他们想要知道两人谁更富有，但是又不想暴露自己的具体财产数目。可以把这个问题转化为一个安全两方计算问题。设表示两个富翁，所需计算的函数定义为：

其中，是富翁的财产数目，是富翁的财产数目。在这个问题中，两个富翁需要得到共同的函数值。在百万富翁这一两方计算问题的基础上可以抽象出多方计算问题就是解决一组互不信任的参与方之间保护隐私的协同计算问题。在确保输入的独立性、计算的正确性的同时不泄露各隐私输入值给其他成员，其具体定义为：设是n个参与者的集合，他们想要共同安全的计算某个给定有n个输入和n个输出的函数，其中函数f的n个输入分别由n个参与者秘密地掌握而不被他人知道，在计算结束后，每个参与者分别得到各自的输出。这里的安全性是指即使在某些参与者有欺骗行为的情况下，仍然可以保持计算结果的正确性，即计算结束后每个诚实的参与者都能得到正确的输出，同时还要求保证参与者输入的保密性，即每个参与者除了知道以及从中推导出的信息之外，得不到任何其他信息。

点和区间的保密计算是一个相对较新的安全多方计算问题，它在保密计算几何、保密信息过滤、保密信息查询等方面有重要的理论意义与应用价值。点和区间的保密计算问题是指保密的判断一个保密的数是否包含于另一个保密的区间内。2016年，郭奕旻等人[7]第一次利用安全多方计算思想提出点和区间的保密计算问题，并将数和区间的范围扩展到有理数范围。李顺东等人[8]研究过保密数与有限集合的区间包含问题，但所提出的协议不适用于所有的区间。在此基础上，Nishide等人[9]设计出了基于秘密共享的比特分解协议，给出了具体应用的解决方案，但对该协议的分析有一定的缺陷。在郭奕旻等人[7]以百万富翁协议为基本思想的基础上，利用计算几何理论，将有理数区间保密计算问题中输入的有理数看成是过原点的直线的斜率，将点和区间的保密计算问题归结为直线之间的位置关系，然后根据平面直角坐标系上三点定义的三角形面积计算公式，将有理数的大小比较规约到算数不等式的判定问题。2018年，陈振华等人[10]将数域扩展到实数，利用函数的单调性和Paillier同态加密研究点和区间的包含问题，但其实质是对近似小数乘以倍数后变为近似整数考虑，不是精确的判定算法。2018年和2019年，窦家维等人[11，12]进一步研究了有理数和有理数区间的保密计算问题，构造多项式表示区间，把有理数域内点与区间的保密问题转化为整数上的向量内积值的正负判定问题，进一步提高了协议的计算效率。

本文研究有理数域上的点与区间的保密计算问题，构造了一个新的安全保密计算协议，证明了协议在半诚实模型下的安全性，与现有的其他文献相比，本文的协议具有更低的计算复杂度。

本文的内容安排为：第2节介绍了预备知识，第3节介绍了协议的计算原理，第4节为具体的协议及安全性分析，第5节是协议的性能分析及比较，第6节给出总结和展望。

2 预备知识

2.1 安全性定义

（1）两方计算

两方计算是将随机的一个输入对映射成输出对的随机计算过程，用函数可以表示为：

在任意一个两方计算问题中，一方参与者输入数据x，另一方参与者输入数据y，他们都希望通过保密计算得到各自相应的输出和。

（2）理想的双方保密协议

理想的双方保密计算协议是指在有一个既不会透露隐私信息，也不会传递虚假信息的可靠第三方的基础上，参与者A和B分别把自己的保密数据告诉第三方，由第三方单独计算出最后的结果函数，并将结果分别发给A和B，而不透露其他信息，且各自的参与者也不能从中得到其他信息。这种协议是双方保密计算协议安全性最高的协议，但是在现实复杂的网络中，参与者双方都信任的第三方是不存在的，因此需设计没有可信第三方存在的情况下安全可靠的协议，并与理想协议比较来检验其安全性和保密性。

（3）半诚实模型和恶意模型

半诚实参与者是指在参与协议的过程中，完全按照协议内容进行计算，不会欺骗参与者，也不会泄露信息，但可能会收集和保留在执行协议时获得的一切数据，并试图从这些数据中推断出额外的其他信息。本文所提出的协议是在半诚实模型下进行的。

恶意参与者在参与协议的过程中可能会破坏协议或盗取别人的信息，从而推断出其他的信息，导致参与者隐私的泄露，还有可能在协议中控制别的参与者按照自己设计的方式来参与协议，这类参与者也称为主动攻击者。假设执行协议时有恶意参与者的存在，则属于恶意模型下的保密协议问题[13，14]。

到目前为止，研究最多的是半诚实模型下的安全多方计算问题，这是因为[1]：（1）多方保密计算的参与者大多数是半诚实的;（2）研究半诚实下的安全多方保密计算是研究恶意模型保密计算的基础，有了半诚实模型下的安全协议，才可针对协议中出现的恶意行为进行改进从而转变为恶意模型下的安全保密计算协议[15]。

（4）隐私的模拟范例[16]

对于任意的一个半诚实参与者，在执行协议的过程中，参与者所获得的信息都可以通过他自己的输入和输出进行模拟，而且得到的信息序列不可区分，则说明协议是安全的。如果一个多方计算协议能够进行这样的模拟，即说明所有的参与者都不可能从协议的执行过程中得到其他参与者的任何信息。这个就是研究安全多方计算问题时普遍接受的模拟范例。

2.2 符号说明

设为概率时间多项式函数，是计算函数的协议。设Alice拥有数据x，Bob拥有数据y，在不暴露各自隐私x与y的前提下，共同合作计算函数，计算的目的是为了让Alice和Bob分别得到多项式函数的两个分量。Alice在合作计算的过程中得到的信息序列为，输出为，Bob在合作计算的过程中得到的信息序列为，输出为。

定义（半诚实参与者的保密性）：协议保密的计算，如果存在概率多项式时间模拟器与，使得以下两式：

同时成立，则认为协议保密地计算，其中表示计算不可区分。

2.3 Paillier同态加密算法

Paillier加密体制是一种具有加法同态性的公钥加密系统，并且是语义安全的，其加密体制描述为[17]：

密钥生成：选取两个大的素数，计算，。定义函数，随机选取的一个生成元g，使得，则加密方案的公钥为，私钥为。

加密过程：对明文，随机选择整数，计算得到密文，

解密过程：对上式得出的密文c，计算得出明文，

Paillier同态加密算法具有加法同态性：

2.4 數字承诺

数字承诺[18]是指有两方参与的一个两阶段协议，这两方分别为承诺者与接收者。第一个阶段为承诺阶段（commitment phase），第二个阶段为承诺揭示阶段（reveal phase或open phase）。通过此协议，承诺者能够实现自己与一个数字的绑定，这种绑定满足保密性（secrecy）与确定性（binding）。保密性是指承诺者做出承诺后，接收者无法获得有关承诺者所承诺数字的任何信息;确定性是指接收者只接受承诺者发送的合法数字，若承诺者欺骗，接收者可以发现并拒绝接收。协议也是可靠的（viable），即如果双方都遵守协议，那么在协议的第二阶段，承诺者需要向接收者提供复杂的信息，也可能仅提供他自己承诺的数值与在承诺阶段所选择的随机数供接收者验证。只有利用相应的承诺值与随机数能够导出在承诺阶段接收者收到的全部信息时，接收者才能接受相应的承诺值。接收者应该能够获得承诺者所承诺的唯一数字。要求一个承诺方案必须保证承诺者在承诺阶段不会向接收者泄露有关承诺值的任何信息，而且承诺者在承诺之后无法改变自己的承诺值，并且保证这样的协议是可行的，即协议能够在概率多项式时间内完成。

[3] Goldwasser S. Multi party computations： past and present[C]//Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing. ACM， 1997： 1-6.

[4] Yao A C. How to generate and exchange secrets[C]//27th Annual Symposium on Foundations of Computer Science （sfcs 1986）. IEEE， 1986： 162-167.

[5] Goldreich， O. The fundamental of cryptography： basic applications [M].Cambridge University Press， 2001.

[6] 刘木兰. 密钥共享体制与安全多方计算[J]. 北京电子科技学院学报， 2006， 14（4）： 1-8.

[7] 郭奕旻， 周素芳， 窦家维， 等. 高效的区间保密计算及应用[J]. 计算机学报， 2017， 40（7）： 1664-1679.

[8] Shundong L， Daoshun W， Yiqi D， et al. Symmetric cryptographic solution to Yaos millionaires problem and an evaluation of secure multiparty computations[J]. Information Sciences， 2008， 178（1）： 244-255.

[9] Nishide T， Ohta K. Multiparty computation for interval， equality， and comparison without bit-decomposition protocol[C]//International Workshop on Public Key Cryptography. Springer， Berlin， Heidelberg， 2007： 343-360.

[10] 陈振华， 李顺东， 陈立朝， 等. 点和区间关系的全隐私保密判定[J]. SCIENCE CHINA Information Sciences， 2018， 48（58）： 187-204.

[11] 窦家维， 王文丽， 刘旭红，等.有理区间的安全多方计算与应用[J]. 电子学报， 2018， 046（009）：2057-2062.

[12] 窦家维，王文丽，李顺东.区间位置关系的保密判定[J]. 计算机学报， 2019， 42（05）：105-118.

[13] Lindell Y. Fast cut-and-choose-based protocols for malicious and covert adversaries [J]. Journal of Cryptology， 2016， 29（2）： 456-490.

[14] Lindell Y， Pinkas B. An efficient protocol for secure two-party computation in the presence of malicious adversaries[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Berlin， Heidelberg， 2007： 52-78.

[15] Freedman M J， Nissim K， Pinkas B. Efficient private matching and set intersection[C]//International conference on the theory and applications of cryptographic techniques. Sprin-ger， Berlin， Heidelberg， 2004： 1-19.

[16] Reimer B， Fried R， Mehler B， et al. Brief report： Examining driving behavior in young adults with high functioning autism spectrum disorders： A pilot study using a driving simulation paradigm[J]. Journal of autism and developmental disorders， 2013， 43（9）： 2211-2217.

[17] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C] //Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques， Springer， Prague， Czech Republic， 1999：223-238.

[18] 李順东， 王道顺. 现代密码学： 理论， 方法与研究前沿[M]. 科学出版社， 2009.

[19] 吴宏锋，闫晶晶. 基于大规模矩阵Jordan分解的外包计算[J]. 网络空间安全，2019， 2（10）： 89-95.

作者简介：

吴宏锋（1976-），男，汉族，北京人，博士，北方工业大学，副教授;主要研究方向和关注领域：数论、密码学。

胡振华（1995-），女，汉族，山西吕梁人，北方工业大学，硕士;主要研究方向和关注领域：密码学。

（本文为“2020年429首都网络安全日”活动征文）