[發明專利]秘密等值連接系統、連接裝置、連接方法、記錄介質

有效

• 申請號: 201780058429.8
• 申請日: 2017-09-14
• 公開（公告）號: CN109791741B
• 公開（公告）日: 2022-01-18
• 發明（設計）人: 五十嵐大;桐淵直人;濱田浩氣;諸橋玄武
• 申請（專利權）人: 日本電信電話株式會社
• 主分類號: G09C1/00
• 分類號: G09C1/00
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 鄭海濤

提供抑制通信量，同時由兩個表生成一個表的秘密等值連接技術。包括：從由表L的第1列、表R的第1列生成的元素列生成置換σ的第一置換生成單元(110)；對j＝2,..,a，從由表L的第j列生成的元素列，使用置換σ、前綴和、逆置換σ^?1生成表J的第j列的第一列生成單元(120)；由元素列([[1]],..,[[1]],[[0]],..,[[0]],[[?1]],..,[[?1]])，使用置換σ、前綴和、逆置換σ^?1生成連接結果元素列的連接結果元素列生成單元(130)；對j＝a+1,..,a+b?1，使用連接結果元素列和表R的第j?a+1列生成表J的第j列的第二列生成單元(140)；使用連接結果元素列和表R的第1列生成表J的第1列的第三列生成單元(150)。

技術領域

本發明涉及通過秘密計算，在將表中包含的信息設為秘密的情況下，將兩個表共同的關鍵屬性作為紐帶(鎹)進行兩個表的等值連接(等結合)的等值連接技術。

背景技術

作為不將加密的數值復原而得到指定的運算的運算結果的方法，有稱為秘密計算的方法(例如參照非專利文獻1)。在非專利文獻1的方法中，進行將可復原數值的多個信息分散到三個秘密計算裝置的加密，不復原數值，而可以保持將加減運算、常數和、相乘、常數倍、邏輯運算(“非”，邏輯“與”，邏輯“或”，“異或”)、數據形式變換(整數，二進數)的結果分散在三個秘密計算裝置的狀態，即保持仍被加密。一般來說，分散數不限于3而可以設為W(W為3以上的規定的常數)，通過W個秘密計算裝置的協同計算實現秘密計算的協議稱為多方(Multi party)協議。

但是，在對表的數據庫處理中，在多數情況下，數據以多個屬性值(與屬性對應的值，在圖1A、圖1B、圖1C的表的例子中作為屬性的No.、身高、體重、購買品的各自的具體的值“3”、“200”、“100”、“好喝的水”等)的組構成的記錄(Record)(在圖1A和圖1B中例示的表的各行)的集合所構成的表單位進行管理。數據庫處理中重要的處理之一有等值連接。等值連接是以圖1A或圖1B那樣的多個表作為輸入，稱為關鍵的屬性(關鍵屬性)的值(關鍵屬性值)提取全部表中共同的記錄，得到將它們橫向排列的新的表的計算。例如，若將圖1A的表Ls或圖1B的表Rs，以各表中共同的關鍵屬性(在該例中為No.)基準進行等值連接，則得到圖1C那樣的表Js。一般來說，在關系數據庫中將數據分割為較多的小的表來管理，在利用時將所需要的表等值連接來進行處理，等值連接是非常重要的處理。

作為通過秘密計算實現了表的等值連接的方法，有非專利文獻2的方法。在非專利文獻2的方法中，實現與關鍵屬性值有重復的多個表的等值連接。

【現有技術文獻】

【非專利文獻】

【非專利文獻1】千田浩司，濱田浩気，五十嵐大，高橋克巳，“軽量検証可能3パーティ秘匿関數計算の再考”，In CSS，2010.

【非專利文獻2】濱田浩気，桐淵直人，五十嵐大，“キーに重複がある場合の秘密計算向け結合アルゴリズム”，暗號と情報セキュリティシンポジウム(SCIS)2015，電子情報通信學會，2015.

發明內容

發明要解決的課題

在將秘密計算作為在多方協議中實現的計算而進行計算效率的評價的情況下，多方協議是一邊在多個方面(party)(參加者)之間進行通信一邊進行協同計算的方式，在一般的系統結構中，與各方面單獨進行的本地的計算相比，通信所需要的時間顯著巨大，本地的計算被認為可以忽略。因此，以通信的數據的量(通信量)的尺度進行計算效率的評價。

這時，在非專利文獻2的方法中，若將進行連接的兩個表的行數分別設為m、n，將進行連接的關鍵屬性的重復的元素的最大數設為k，則需要O(k(m+n)log(m+n))的通信，存在進行等值連接時在隱匿存儲了數據的服務器間需要的通信變多的問題。特別是，如先前的圖1B的屬性“購買品”那樣，對關鍵屬性“No.”存在多次出現的可能性的情況下，k的值變大，問題顯現出來。