點(diǎn)和區(qū)間包含問題的保密計(jì)算

吳宏鋒　胡振華

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

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

中圖分類號(hào)： TP309? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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 引言

安全多方計(jì)算（Secure Multi-Party Computation，SMC）問題是從具體的密碼學(xué)問題中抽象出來的，對(duì)它的研究以及由此得到的一些結(jié)論對(duì)具體的密碼學(xué)問題有著指導(dǎo)意義，它可以從原則上告訴人們哪些問題是可以解決的，哪些是不可以解決的。但是，由于安全多方計(jì)算問題是一個(gè)非常抽象的問題，使得人們很難找到有效的算法去實(shí)現(xiàn)它，從而導(dǎo)致了它在具體應(yīng)用上的局限性。對(duì)于一個(gè)具體的密碼學(xué)問題，可以先根據(jù)安全多方計(jì)算的結(jié)論在原則上確定這個(gè)問題是否可以解決，如果可以解決，就需要具體問題具體分析，尋找解決該問題的具體解決方案。實(shí)際上，安全多方計(jì)算蘊(yùn)含了對(duì)任何密碼學(xué)協(xié)議問題在原則上的實(shí)現(xiàn)方案，它是分布式密碼學(xué)和分布式計(jì)算研究的一個(gè)基本問題。

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

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

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

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

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

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

2 預(yù)備知識(shí)

2.1 安全性定義

（1）兩方計(jì)算

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

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

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

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

（3）半誠(chéng)實(shí)模型和惡意模型

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

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

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

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

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

2.2 符號(hào)說明

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

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

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

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

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

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

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

解密過程：對(duì)上式得出的密文c，計(jì)算得出明文，

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

2.4 數(shù)字承諾

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

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

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

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

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

作者簡(jiǎn)介：

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

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

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