點和區間包含問題的保密計算

吳宏鋒　胡振華

摘? ?要：安全多方計算問題是近年來密碼學研究的熱點問題，其中多方保密計算是網絡空間隱私保護與信息安全的關鍵技術。文章研究了計算幾何中有理數域內點和區間包含問題的保密計算問題，即保密的判定一個隱私的有理數是否屬于一個保密的有理區間。文章利用安全多方計算的思想設計了一個高效的安全協議，并證明了協議在半誠實模型下的安全性，與現有的其他文獻相比，本文的協議具有更低的計算復雜度。

關鍵詞：密碼學;安全多方計算;點與區間的保密計算;計算幾何

中圖分類號： 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首都網絡安全日”活動征文）