[發明專利]一種基于共享秘密的計算方法

有效

• 申請號: 201810057559.6
• 申請日: 2018-01-22
• 公開（公告）號: CN110071796B
• 公開（公告）日: 2021-09-03
• 發明（設計）人: 劉翔宇;張方國
• 申請（專利權）人: 中山大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L29/06
• 代理公司: 廣州市深研專利事務所(普通合伙) 44229
• 代理人: 陳雅平

本發明基于兩方多項式秘密共享方案，設計了一組共享秘密的乘法、除法和模運算的計算方法。具體地，假定參與方Alice和Bob多項式共享了秘密s、s₁、p，公開了除數N，那么通過分別調用本發明中的Multiply、DivideConst、Divide和Mod方法，Alice和Bob能夠多項式共享計算結果s·s₁、和smod p，同時保持了s、s₁、p的秘密不被任何一方知道。本發明所設計的方法能夠有效應用于雙方RSA簽名、密鑰管理、電子投票等需要安全兩方計算的場景。

技術領域

本發明屬于安全兩方計算領域，特別涉及了一種基于兩方共享秘密的乘法、除法和模運算的計算方法。

背景技術

隨著大數據時代的到來，各種各樣的信息呈指數爆炸型增長。由于數據隱私性的存在，在很多多方參與的計算場景中，如何保持各自的秘密信息而又都得到計算的結果這一問題變得相當棘手。比如說著名的“百萬富翁協議”即描述了這樣一個現實應用問題：兩個爭強好勝的百萬富翁碰面了，他們想比較出誰更富有，但是又不想公開出自己的財富信息。一般地，可以借助于可信第三方來解決這一問題，即多個參與方分別秘密地發送自己的信息給可信第三方，由第三方計算出結果后公布給大家或者秘密地告知部分參與方。而在現實生活中，尋找可信第三方并不是那么容易，一方面出于計算參與方對第三方的有限的信任程度，另一方面，由于第三方掌握了全部秘密信息，有可能會受到竊密者的重點攻擊。在密碼學中，每個人都擁有自己的秘密信息，我們稱之為參與方們共享了所有的秘密信息(每個人擁有所有秘密信息中自己的那部分)，如何在沒有可信第三方的情況下進行共享秘密的計算被稱之為安全多方計算，具體到兩個參與方就是安全兩方計算。

1978年公鑰思想提出以后，加密密鑰和解密秘鑰分離開來，密鑰的大量分配與管理任務促成了密碼學中的密鑰管理這一重要分支。好比現實生活中我們為了防止秘密泄露或者個人權利過大，往往會把一個權力或一個秘密分散給幾個人去管理保存一樣，現在假設n人的團隊共享一個秘密s，規定至少有t個參與方(2≤t≤n)同時在場才能還原出s，抽象成數學術語就是(n,t)門限秘密共享。我們要求任何少于t個參與方的人都不能得到秘密的任何1bit信息。目前安全多方計算中應用最廣泛的是基于拉格朗日插值的多項式秘密共享方案，除此之外還有基于中國剩余定理、基于k維空間幾何學的方案等。基于秘密共享的安全多方計算(尤其是安全兩方計算)有諸多應用場景，比如進行多人密鑰管理和導彈發射等重大事件的分治控制，兩人或多人利用自己共享的部分秘密共同計算生成有效的數字簽名，在電子投票中，把每人的票轉化成共享秘密，再多方計算出最終的投票結果等等。

在基于拉格朗日插值的兩方多項式秘密共享方案中，由秘密s和隨機數t構成了秘密多項式f(x)＝s+tx，Alice和Bob分別秘密擁有一對(x,f(x))信息，如Alice擁有f(1)，Bob擁有f(2)。當需要還原出s時，雙方發送自己的秘密給對方，任何一方均可以利用拉格朗日插值法計算出s＝2f(1)-f(2)。而只有一個插值信息的話，無論如何也計算不出秘密s。在本發明所述內容中，如無特別說明，我們指Alice擁有(1,f(1))，Bob擁有(2,f(2))。

鑒于安全多方計算有如此大的應用需要，密碼學中對于其計算方法的研究也是層出不窮。然而在具體的基于多項式插值秘密共享方案的安全兩方計算中，只有共享秘密的加法、減法有直接的計算方法，而乘法、除法和模運算這種則需要根據具體場景采用相關的密碼學方法來實現。

基于此，本發明提出了一種基于兩方共享秘密的乘法、除法和模運算的計算方法。

發明內容

本發明設計了一種基于兩方共享秘密的乘法、除法和模運算的計算方法，具體如下：

該方法涉及Alice和Bob兩個參與方，他們多項式共享了秘密s、s₁、p并且公開知道一個除數N，分別調用Multiply、DivideConst、Divide和Mod方法雙方可求出s·s₁、和smodp的結果并分別多項式共享這些結果。其中：