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

有效

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

1.一種基于共享秘密的計算方法，其特征在于，兩個參與方Alice和Bob以多項式的形式共享了秘密s、s₁、p，并且公開知道一個除數N，分別調用Multiply、DivideConst、Divide和Mod方法，雙方求出s·s₁、和s mod p的結果并分別以多項式的形式共享這些結果；

所述Multiply方法中，兩個參與方Alice和Bob分別計算出結果res₁、res₂，且res₁、res₂以多項式的形式共享秘密s·s₁，具體過程如下：

A1)Alice和Bob以多項式f(x)＝s+tx和g₁(x)＝s₁+t₁x的形式共享了秘密s和s₁，Alice擁有f(1)、g₁(1)，Bob擁有f(2)、g₁(2)；Alice輸入f(1)、g₁(1)，Bob輸入f(2)、g₁(2)，Alice計算得到res₁，Bob計算得到res₂；定義多項式h(x)＝s·s₁+(s·t₁+t·s₁)x+t·t₁x²，Alice計算h(1)＝f(1)·g₁(1)，Bob計算h(2)＝f(2)·g₁(2)；

A2)Alice選擇隨機數r₁、r₂，將temp₁＝f(1)+r₁、temp₂＝g₁(1)+r₂發送給Bob；

A3)Bob計算temp₃＝f(2)-temp₁、temp₄＝g₁(2)-temp₂；

A4)調用SumProduct方法，Alice輸入r₁、r₂，Bob輸入temp₃、temp₄，雙方共同計算出多項式h(x)的二次項系數t·t₁，所述二次項系數t·t₁用X表示，且X＝(r₁+temp₃)(r₂+temp₄)，所述SumProduct方法計算過程如下：

(A41)Alice自定義公鑰同態加密算法Γ_A的公私鑰對，公鑰pk公開，私鑰sk自己秘密保存；

(A42)Alice輸入r₁、r₂，Bob輸入temp₃、temp₄，雙方希望在各自保證r₁、r₂、temp₃、temp₄秘密的情況下計算出X＝(r₁+temp₃)(r₂+temp₄)；

(A43)Alice利用pk將r₁、r₂、r₁r₂加密為Γ_A(r₁)、Γ_A(r₂)、Γ_A(r₁r₂)后發送給Bob；

(A44)Bob利用pk將temp₃·temp₄加密為Γ_A(temp₃·temp₄)；

(A45)Bob計算發送給Alice；

(A46)Alice利用sk解密Γ_A(X)得到X并公開給Bob；

A5)Alice計算res₁＝h(1)-X，Bob計算res₂＝h(2)-4X，并且有多項式k(x)＝s·s₁+(s·t₁+t·s₁)x使得res₁＝k(1)，res₂＝k(2)，計算完畢；

所述DivideConst方法中，兩個參與方Alice和Bob分別計算出結果res₃、res₄，且res₃、res₄以多項式的形式共享秘密具體過程如下：

B1)Alice和Bob以多項式的形式共享秘密s，對于多項式f(x)＝s+tx，Alice擁有f(1)，Bob擁有f(2)，并且公開除數N，Alice輸入f(1)和N，Bob輸入f(2)和N；

B2)Alice和Bob雙方進行帶余除法計算，Alice計算f(1)＝d₁·N+c₁，Bob計算f(2)＝d₂·N+c₂；其中c₁之0，c₂＜0；

B3)雙方第一次調用“姚氏百萬富翁協議”，Alice輸入2c₁，Bob輸入c₃＝2N+c₂，若執行結果為“1”或“0”，則d₂＝d₂-2，并跳轉至步驟B5)，否則跳轉至步驟B4)；

B4)雙方第二次調用“姚氏百萬富翁協議”，Alice輸入2c₁，Bob輸入c₄＝N+c₂，若執行結果為“1”或“0”，那么d₂＝d₂-1；

B5)Alice計算res₃＝d₁，Bob計算res₄＝d₂，且res₃、res₄以多項式的形式共享秘密

B6)所述“姚氏百萬富翁協議”具體為解決“姚氏百萬富翁”問題的一個兩方協議，Alice輸入秘密a，Bob輸入秘密b，當a＞b時，協議輸出1，當a＝b時，協議輸出0，當a＜b時，協議輸出-1；

所述Divide方法中，兩個參與方Alice和Bob分別計算出結果res₅、res₆，且res₅、res₆以多項式的形式共享秘密具體過程如下：

C1)Alice和Bob分別以多項式的形式共享了s和p，對于秘密多項式f(x)＝s+tx和g(x)＝p+t₂x，Alice擁有f(1)和g(1)，Bob擁有f(2)和g(2)；

C2)調用Inverse方法，Alice輸入g(1)，Bob輸入g(2)，Alice計算得到pp₁，Bob計算得到pp₂，且pp₁、pp₂以多項式的形式共享秘密其中λ為Inverse方法中計算得到的大公開參數；所述Inverse方法具體過程如下：

(C21)Alice和Bob以多項式的形式共享了p，假定其中Alice擁有p₁，Bob擁有p₂；

(C22)Alice和Bob分別公布各自共享秘密的bit長度α₁和α₂，取α＝max(α₁，α₂)，β＝max(4α，60)，λ＝α+β；

(C23)Alice置[u₀]₁＝2^β，Bob置[u₀]₂＝2^β，則[u₀]₁和[u₀]₂以多項式的形式共享秘密u₀＝2^β；

(C24)循環執行下述步驟：

(a)調用所述Multiply方法，雙方以多項式的形式共享計算結果z_i+1＝u_i·p；

(b)調用所述DivideConst方法，雙方以多項式的形式共享計算結果

(c)調用所述Multiply方法，雙方以多項式的形式共享計算結果v_i+1＝2^β+1·u_i-u_i·w_i+1；

(d)調用所述DivideConst方法，雙方以多項式的形式共享計算結果

(C25)輸出結果，雙方以多項式的形式共享計算結果u_i+1，所述計算結果u_i+1也就是的近似值；

(C3)調用所述Multiply和所述DivideConst方法，Alice輸入f(1)、pp₁和2^λ，Bob輸入f(2)、pp₂和2^λ，Alice計算出res₅，Bob計算出res₆，且res₅、res₆以多項式的形式共享秘密計算完畢；

所述Mod方法中，兩個參與方Alice和Bob分別計算出結果res₇、res₈，且res₇、res₈以多項式的形式共享秘密s mod p，具體過程如下：

D1)Alice和Bob分別以多項式的形式共享了s和p，對于秘密多項式f(x)＝s+tx和g(x)＝p+t₂x，Alice擁有f(1)、g(1)，Bob擁有f(2)、g(2)；

D2)調用所述Inverse方法，Alice輸入g(1)，Bob輸入g(2)，Alice計算得到pp₁，Bob計算得到pp₂，其中pp₁、pp₂以多項式的形式共享秘密λ為所述Inverse方法中的大公開參數；

D3)調用所述Multiply和所述DivideConst方法，Alice輸入f(1)、pp₁和λ，Bob輸入f(2)、pp₂和λ，雙方以多項式的形式共享計算結果Alice擁有q₁，Bob擁有q₂；

D4)調用所述Multiply方法，Alice輸入g(1)和q₁，Bob輸入g(2)和q₂，雙方以多項式的形式共享了計算結果q′＝q·p，Alice擁有q′₁，Bob擁有q′₂；

D5)Alice計算res₇＝f(1)-q′₁，Bob計算res₈＝f(2)-q′₂，且res₇、res₈以多項式的形式共享秘密s mod p，計算完畢。