吳宏鋒　胡振華

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

關(guān)鍵詞：密碼學;安全多方計算;點與區(qū)間的保密計算;計算幾何

中圖分類號： 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）問題是從具體的密碼學問題中抽象出來的，對它的研究以及由此得到的一些結(jié)論對具體的密碼學問題有著指導意義，它可以從原則上告訴人們哪些問題是可以解決的，哪些是不可以解決的。但是，由于安全多方計算問題是一個非常抽象的問題，使得人們很難找到有效的算法去實現(xiàn)它，從而導致了它在具體應用上的局限性。對于一個具體的密碼學問題，可以先根據(jù)安全多方計算的結(jié)論在原則上確定這個問題是否可以解決，如果可以解決，就需要具體問題具體分析，尋找解決該問題的具體解決方案。實際上，安全多方計算蘊含了對任何密碼學協(xié)議問題在原則上的實現(xiàn)方案，它是分布式密碼學和分布式計算研究的一個基本問題。

安全多方計算最早是由Yao[1]在1942年通過百萬富翁問題提出兩方安全計算問題引入的，經(jīng)過Goldreich、Micali、Wigderson[2]等學者的發(fā)展，安全多方計算已經(jīng)成為近年來國際密碼學研究的熱點問題之一，是網(wǎng)絡信息安全、隱私探索的關(guān)鍵技術(shù)。在1987年，Goldwasser[3]曾預言，安全多方計算將成為密碼學中一個必不可少的組成部分，這激勵著許多學者不斷研究探索，并在多方面取得了豐碩的成果。Yao[4]用混淆電路的方法證明了所有的安全多方計算問題都是可解的，Goldreich等人[2，5]給出了基于心理游戲（mental game）的通用解決方案，但是這兩種方案的效率都很低，僅有理論意義，所以Goldreich指出，理論上證明所有的安全多方計算問題的可解性并不表示不再需要對具體問題具體分析，相反的由于效率的原因，應該對具體問題提出具體的解決方案，一般條件下提出的一些解決方案是不切實際的，所以就需要對已有的問題進行更加深入的研究，以提出更有效的解決方案，使安全多方計算可以更好地應用于社會生活中。目前研究的安全多方計算問題多應用于軍事或者航空航天方面，主要包括四類：保密的科學計算問題、保密的計算幾何問題、保密的統(tǒng)計分析問題和數(shù)據(jù)挖掘問題。雖然人們已經(jīng)研究出很多的安全多方計算問題，并提出相應的解決方案，但這些方案的效率還亟待提高，除此之外還有許多新的問題需要研究。本文研究的點和區(qū)間的包含問題就是需要用新的方法研究的一個保密計算問題。

百萬富翁問題[6]是指有兩個百萬富翁，他們想要知道兩人誰更富有，但是又不想暴露自己的具體財產(chǎn)數(shù)目?？梢园堰@個問題轉(zhuǎn)化為一個安全兩方計算問題。設表示兩個富翁，所需計算的函數(shù)定義為：

其中，是富翁的財產(chǎn)數(shù)目，是富翁的財產(chǎn)數(shù)目。在這個問題中，兩個富翁需要得到共同的函數(shù)值。在百萬富翁這一兩方計算問題的基礎上可以抽象出多方計算問題就是解決一組互不信任的參與方之間保護隱私的協(xié)同計算問題。在確保輸入的獨立性、計算的正確性的同時不泄露各隱私輸入值給其他成員，其具體定義為：設是n個參與者的集合，他們想要共同安全的計算某個給定有n個輸入和n個輸出的函數(shù)，其中函數(shù)f的n個輸入分別由n個參與者秘密地掌握而不被他人知道，在計算結(jié)束后，每個參與者分別得到各自的輸出。這里的安全性是指即使在某些參與者有欺騙行為的情況下，仍然可以保持計算結(jié)果的正確性，即計算結(jié)束后每個誠實的參與者都能得到正確的輸出，同時還要求保證參與者輸入的保密性，即每個參與者除了知道以及從中推導出的信息之外，得不到任何其他信息。

點和區(qū)間的保密計算是一個相對較新的安全多方計算問題，它在保密計算幾何、保密信息過濾、保密信息查詢等方面有重要的理論意義與應用價值。點和區(qū)間的保密計算問題是指保密的判斷一個保密的數(shù)是否包含于另一個保密的區(qū)間內(nèi)。2016年，郭奕旻等人[7]第一次利用安全多方計算思想提出點和區(qū)間的保密計算問題，并將數(shù)和區(qū)間的范圍擴展到有理數(shù)范圍。李順東等人[8]研究過保密數(shù)與有限集合的區(qū)間包含問題，但所提出的協(xié)議不適用于所有的區(qū)間。在此基礎上，Nishide等人[9]設計出了基于秘密共享的比特分解協(xié)議，給出了具體應用的解決方案，但對該協(xié)議的分析有一定的缺陷。在郭奕旻等人[7]以百萬富翁協(xié)議為基本思想的基礎上，利用計算幾何理論，將有理數(shù)區(qū)間保密計算問題中輸入的有理數(shù)看成是過原點的直線的斜率，將點和區(qū)間的保密計算問題歸結(jié)為直線之間的位置關(guān)系，然后根據(jù)平面直角坐標系上三點定義的三角形面積計算公式，將有理數(shù)的大小比較規(guī)約到算數(shù)不等式的判定問題。2018年，陳振華等人[10]將數(shù)域擴展到實數(shù)，利用函數(shù)的單調(diào)性和Paillier同態(tài)加密研究點和區(qū)間的包含問題，但其實質(zhì)是對近似小數(shù)乘以倍數(shù)后變?yōu)榻普麛?shù)考慮，不是精確的判定算法。2018年和2019年，竇家維等人[11，12]進一步研究了有理數(shù)和有理數(shù)區(qū)間的保密計算問題，構(gòu)造多項式表示區(qū)間，把有理數(shù)域內(nèi)點與區(qū)間的保密問題轉(zhuǎn)化為整數(shù)上的向量內(nèi)積值的正負判定問題，進一步提高了協(xié)議的計算效率。

本文研究有理數(shù)域上的點與區(qū)間的保密計算問題，構(gòu)造了一個新的安全保密計算協(xié)議，證明了協(xié)議在半誠實模型下的安全性，與現(xiàn)有的其他文獻相比，本文的協(xié)議具有更低的計算復雜度。

本文的內(nèi)容安排為：第2節(jié)介紹了預備知識，第3節(jié)介紹了協(xié)議的計算原理，第4節(jié)為具體的協(xié)議及安全性分析，第5節(jié)是協(xié)議的性能分析及比較，第6節(jié)給出總結(jié)和展望。

2 預備知識

2.1 安全性定義

（1）兩方計算

兩方計算是將隨機的一個輸入對映射成輸出對的隨機計算過程，用函數(shù)可以表示為：

在任意一個兩方計算問題中，一方參與者輸入數(shù)據(jù)x，另一方參與者輸入數(shù)據(jù)y，他們都希望通過保密計算得到各自相應的輸出和。

（2）理想的雙方保密協(xié)議

理想的雙方保密計算協(xié)議是指在有一個既不會透露隱私信息，也不會傳遞虛假信息的可靠第三方的基礎上，參與者A和B分別把自己的保密數(shù)據(jù)告訴第三方，由第三方單獨計算出最后的結(jié)果函數(shù)，并將結(jié)果分別發(fā)給A和B，而不透露其他信息，且各自的參與者也不能從中得到其他信息。這種協(xié)議是雙方保密計算協(xié)議安全性最高的協(xié)議，但是在現(xiàn)實復雜的網(wǎng)絡中，參與者雙方都信任的第三方是不存在的，因此需設計沒有可信第三方存在的情況下安全可靠的協(xié)議，并與理想?yún)f(xié)議比較來檢驗其安全性和保密性。

（3）半誠實模型和惡意模型

半誠實參與者是指在參與協(xié)議的過程中，完全按照協(xié)議內(nèi)容進行計算，不會欺騙參與者，也不會泄露信息，但可能會收集和保留在執(zhí)行協(xié)議時獲得的一切數(shù)據(jù)，并試圖從這些數(shù)據(jù)中推斷出額外的其他信息。本文所提出的協(xié)議是在半誠實模型下進行的。

惡意參與者在參與協(xié)議的過程中可能會破壞協(xié)議或盜取別人的信息，從而推斷出其他的信息，導致參與者隱私的泄露，還有可能在協(xié)議中控制別的參與者按照自己設計的方式來參與協(xié)議，這類參與者也稱為主動攻擊者。假設執(zhí)行協(xié)議時有惡意參與者的存在，則屬于惡意模型下的保密協(xié)議問題[13，14]。

到目前為止，研究最多的是半誠實模型下的安全多方計算問題，這是因為[1]：（1）多方保密計算的參與者大多數(shù)是半誠實的;（2）研究半誠實下的安全多方保密計算是研究惡意模型保密計算的基礎，有了半誠實模型下的安全協(xié)議，才可針對協(xié)議中出現(xiàn)的惡意行為進行改進從而轉(zhuǎn)變?yōu)閻阂饽Ｐ拖碌陌踩Ｃ苡嬎銋f(xié)議[15]。

（4）隱私的模擬范例[16]

對于任意的一個半誠實參與者，在執(zhí)行協(xié)議的過程中，參與者所獲得的信息都可以通過他自己的輸入和輸出進行模擬，而且得到的信息序列不可區(qū)分，則說明協(xié)議是安全的。如果一個多方計算協(xié)議能夠進行這樣的模擬，即說明所有的參與者都不可能從協(xié)議的執(zhí)行過程中得到其他參與者的任何信息。這個就是研究安全多方計算問題時普遍接受的模擬范例。

2.2 符號說明

設為概率時間多項式函數(shù)，是計算函數(shù)的協(xié)議。設Alice擁有數(shù)據(jù)x，Bob擁有數(shù)據(jù)y，在不暴露各自隱私x與y的前提下，共同合作計算函數(shù)，計算的目的是為了讓Alice和Bob分別得到多項式函數(shù)的兩個分量。Alice在合作計算的過程中得到的信息序列為，輸出為，Bob在合作計算的過程中得到的信息序列為，輸出為。

定義（半誠實參與者的保密性）：協(xié)議保密的計算，如果存在概率多項式時間模擬器與，使得以下兩式：

同時成立，則認為協(xié)議保密地計算，其中表示計算不可區(qū)分。

2.3 Paillier同態(tài)加密算法

Paillier加密體制是一種具有加法同態(tài)性的公鑰加密系統(tǒng)，并且是語義安全的，其加密體制描述為[17]：

密鑰生成：選取兩個大的素數(shù)，計算，。定義函數(shù)，隨機選取的一個生成元g，使得，則加密方案的公鑰為，私鑰為。

加密過程：對明文，隨機選擇整數(shù)，計算得到密文，

解密過程：對上式得出的密文c，計算得出明文，

Paillier同態(tài)加密算法具有加法同態(tài)性：

2.4 數(shù)字承諾

數(shù)字承諾[18]是指有兩方參與的一個兩階段協(xié)議，這兩方分別為承諾者與接收者。第一個階段為承諾階段（commitment phase），第二個階段為承諾揭示階段（reveal phase或open phase）。通過此協(xié)議，承諾者能夠?qū)崿F(xiàn)自己與一個數(shù)字的綁定，這種綁定滿足保密性（secrecy）與確定性（binding）。保密性是指承諾者做出承諾后，接收者無法獲得有關(guān)承諾者所承諾數(shù)字的任何信息;確定性是指接收者只接受承諾者發(fā)送的合法數(shù)字，若承諾者欺騙，接收者可以發(fā)現(xiàn)并拒絕接收。協(xié)議也是可靠的（viable），即如果雙方都遵守協(xié)議，那么在協(xié)議的第二階段，承諾者需要向接收者提供復雜的信息，也可能僅提供他自己承諾的數(shù)值與在承諾階段所選擇的隨機數(shù)供接收者驗證。只有利用相應的承諾值與隨機數(shù)能夠?qū)С鲈诔兄Z階段接收者收到的全部信息時，接收者才能接受相應的承諾值。接收者應該能夠獲得承諾者所承諾的唯一數(shù)字。要求一個承諾方案必須保證承諾者在承諾階段不會向接收者泄露有關(guān)承諾值的任何信息，而且承諾者在承諾之后無法改變自己的承諾值，并且保證這樣的協(xié)議是可行的，即協(xié)議能夠在概率多項式時間內(nèi)完成。

[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] 郭奕旻， 周素芳， 竇家維， 等. 高效的區(qū)間保密計算及應用[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] 陳振華， 李順東， 陳立朝， 等. 點和區(qū)間關(guān)系的全隱私保密判定[J]. SCIENCE CHINA Information Sciences， 2018， 48（58）： 187-204.

[11] 竇家維， 王文麗， 劉旭紅，等.有理區(qū)間的安全多方計算與應用[J]. 電子學報， 2018， 046（009）：2057-2062.

[12] 竇家維，王文麗，李順東.區(qū)間位置關(guān)系的保密判定[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] 李順東， 王道順. 現(xiàn)代密碼學： 理論， 方法與研究前沿[M]. 科學出版社， 2009.

[19] 吳宏鋒，閆晶晶. 基于大規(guī)模矩陣Jordan分解的外包計算[J]. 網(wǎng)絡空間安全，2019， 2（10）： 89-95.

作者簡介：

吳宏鋒（1976-），男，漢族，北京人，博士，北方工業(yè)大學，副教授;主要研究方向和關(guān)注領域：數(shù)論、密碼學。

胡振華（1995-），女，漢族，山西呂梁人，北方工業(yè)大學，碩士;主要研究方向和關(guān)注領域：密碼學。

（本文為“2020年429首都網(wǎng)絡安全日”活動征文）