[發(fā)明專利]秘密右移位運(yùn)算系統(tǒng)及方法、秘密除法運(yùn)算系統(tǒng)及方法、秘密計(jì)算裝置以及記錄介質(zhì)

有效

• 申請?zhí)枺?/td>: 201980066066.1
• 申請日: 2019-10-10
• 公開（公告）號: CN112805770B
• 公開（公告）日: 2023-10-03
• 發(fā)明（設(shè)計(jì)）人: 五十嵐大
• 申請（專利權(quán)）人: 日本電信電話株式會社
• 主分類號: G09C1/00
• 分類號: G09C1/00
• 代理公司: 北京市柳沈律師事務(wù)所 11105
• 代理人: 金蘭

在秘密計(jì)算中實(shí)現(xiàn)高速的右移位運(yùn)算以及除法運(yùn)算。公開值倍部(11)從值a的分散值[a]計(jì)算[a']＝[2^ua]。第一變換部(12)將[a']變換為加法的秘密分散。右移位運(yùn)算部(13)計(jì)算s_i＝a'_i＞＞b+u。第二變換部(14)將s變換為線性秘密分散。第一比特變換部(15)將a'_i的低位u比特變換為{a'_i mod 2^u}。商轉(zhuǎn)移部(16)得到?Σ_im{a'_i mod 2^u}的低位u比特作為{q}。第二比特變換部(17)將a'_i的低位b+u比特變換為{a'_iR}＝{a'_i mod 2^b+u}。加法運(yùn)算部(18)計(jì)算{z}＝Σ_im{a'_iR}+{q}，得到{z}的第b+u比特以后的比特串{z_Q}。第三變換部(19)將{q}、{z_Q}變換為線性秘密分散。輸出計(jì)算部(20)輸出[s]?[2^l?(b+u)q]+[z_Q]作為[a＞＞b]。

技術(shù)領(lǐng)域

本發(fā)明涉及在秘密計(jì)算中進(jìn)行右移位運(yùn)算以及除法運(yùn)算的技術(shù)。

背景技術(shù)

所謂秘密計(jì)算，是指保持將數(shù)據(jù)隱匿的狀態(tài)來計(jì)算任意的函數(shù)的加密技術(shù)。利用該特征，無論系統(tǒng)運(yùn)用者還是數(shù)據(jù)利用者，都被期待不遺漏數(shù)據(jù)的靈活利用數(shù)據(jù)的方式。已知，在秘密計(jì)算中存在幾種方式，其中將秘密分散設(shè)為結(jié)構(gòu)要素，數(shù)據(jù)的處理單位小，能夠進(jìn)行高速的處理。

所謂秘密分散，是指將秘密信息變換為被稱為份額的幾個片斷的方法。例如，有從秘密信息生成n個份額，從k個以上的份額可以復(fù)原秘密，但是從不足k個的份額不泄漏秘密信息的被稱為(k,n)閾值法的秘密分散。關(guān)于秘密分散的具體的構(gòu)成方法，已知Shamir秘密分散、復(fù)制秘密分散等。在本說明書中，將通過秘密分散被分散的值的1個片斷稱為“份額”。另外，將全部份額的集合全體稱為“被分散的值”或者“分散值”。

右移位運(yùn)算是計(jì)算機(jī)等中的基本的運(yùn)算之一，在各種情形下被利用。例如，右移位運(yùn)算可以利用為降低數(shù)值精度的運(yùn)算。另外，除數(shù)為2的冪的情況下的除法運(yùn)算可以通過右移位運(yùn)算來實(shí)現(xiàn)。在非專利文獻(xiàn)1中，公開了在秘密計(jì)算中在位數(shù)2的冪的整數(shù)環(huán)上進(jìn)行移位運(yùn)算的方法。

現(xiàn)有技術(shù)文獻(xiàn)

非專利文獻(xiàn)

非專利文獻(xiàn)1：D.Bogdanov,M.Niitsoo,T.Toft,and J.Willemson,High-performance secure multi-party computation for data mining applications,International Journal of Information Security,Volume 11,Issue 6,Pages 403-418,November 2012.

發(fā)明內(nèi)容

發(fā)明要解決的課題

可是，在非專利文獻(xiàn)1中公開的方法，只能在位數(shù)2的冪的整數(shù)環(huán)上利用，所以存在如下課題，即如果在域上重復(fù)乘法運(yùn)算等使數(shù)值精度增大的運(yùn)算則引起溢出(overflow)，從而無法進(jìn)行計(jì)算。

本發(fā)明的目的是，鑒于上述那樣的技術(shù)的課題，提供實(shí)現(xiàn)高速的右移位運(yùn)算以及除法運(yùn)算的秘密計(jì)算技術(shù)。

用于解決課題的方案