[發明專利]秘密分散系統、數據分散裝置、分散數據變換裝置以及秘密分散方法有效

申請號：	201380035818.0	申請日：	2013-07-04
公開（公告）號：	CN104429019B	公開（公告）日：	2017-06-20
發明（設計）人：	千田浩司;五十嵐大;濱田浩氣;菊池亮	申請（專利權）人：	日本電信電話株式會社
主分類號：	H04L9/08	分類號：	H04L9/08;G06F21/62
代理公司：	北京市柳沈律師事務所11105	代理人：	于小寧
地址：	日本***	國省代碼：	暫無信息
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	秘密分散系統數據裝置變換方法以及程序
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及計算量型秘密分散技術以及多方(multiparty)計算技術。

背景技術

秘密分散(secret sharing)是將數據變換為多個分散值，若利用一定個數以上的分散值則能夠恢復原來的數據，根據少于一定個數的分散值完全無法恢復原來的數據的技術。將分散值的總數設為N，將進行恢復所需的分散值的最少數目設為K(≤N)時，存在對N、K的值沒有限制的方式和有限制的方式。

作為秘密分散的代表性方式，有Shamir秘密分散方式(例如，參照非專利文獻1)。在該方式的例子中，將p設為質數，將GF(p)設為位數p的有限體，根據針對a∈GF(p)成為f(0)＝a的、以x作為變量的K-1次式f(x)，獲得a的分散值S_i(a)＝f(i)(i＝1,...,N)。將n₁、……、n_K設為1以上且N以下的相互不同的整數，以下的關系成立，因此能夠根據任意的不同的K個分散值恢復a。

【數1】

此外，作為秘密分散的一種，有基于計算量的安全性，根據少于一定個數的分散值完全無法恢復原來的數據的、計算量型秘密分散方式(例如，參照非專利文獻2)。在該方式的例子中，利用公共密鑰加密對信息a＝(a₀,a₁,...,a_K-1)(a₀、a₁、……、a_K-1∈GF(p))進行加密，根據由該密文c＝ (c₀,c₁,...,c_K-1)(其中，c₀、c₁、……、c_K-1∈GF(p))決定的、以x作為變量的K-1次式f(x)＝c₀+c₁x+…+c_K-1x^K-1獲得c的分散值T_i(c)＝f(i)(i＝1,...,N)。此外，公共密鑰另外通過Shamir秘密分散方式等分散。則，將n₁、……、n_K設為1以上且N以下的互相不同的整數，能夠根據式f(x)的K個點(n_i,f(n_i))(i＝1,...,K)唯一地求出式f(x)的系數c₀、c₁、……、c_K-1。這只要針對以c₀、c₁、……、c_K-1作為變量的以下的矩陣求出c₀、c₁、……、c_K-1的解即可。

【數2】

然后，恢復公共密鑰，對c進行解密就能夠獲得a。

另一方面，提出了以秘密分散作為主要技術的多方計算方式。多方計算是各計算主體i(i＝1,...,N)分別以信息a_i作為輸入，對其他的計算主體不透漏信息a_i，獲取特定的函數值F_i(a₁,...,a_N)的技術。在上述的Shamir秘密分散方式中，根據信息a,b∈GF(p)的分散值S_i(a)、S_i(b)，不透漏各計算主體的輸入，能夠獲得a+b的分散值S_i(a+b)以及ab的分散值S_i(ab)(參照非專利文獻3)。即，只要是Shamir秘密分散方式，就能夠進行加法以及乘法的多方計算。另外，將滿足S_i(a)+S_i(b)＝S_i(a+b)的關系的秘密分散稱為具有加法同態(additive homomorphic)的秘密分散。