(57)【要約】  秘密表参照システムは、d及びvが結合されたv'∈Fm+ntの[v']を生成する第一結合部１１nと、rのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つr''の[r'']を生成する差分計算部１２nと、r''及びm次元の零が結合されたr'∈Fm+ntの[r']を生成する第二結合部１３nと、v'を昇順に安定ソートする置換σの{{σ}}を生成する置換計算部１４nと、r'に置換σを適用したs:=σ(r')の[s]を生成する置換適用部１５nと、sのprefix-sum s'の[s']を生成するベクトル生成部１６nと、s'に置換σの逆置換σ-1を適用したs''の[s'']を生成する逆置換適用部と、s''のnt+1番目以降の要素からなるx∈Fmの[x]を生成する出力部１７nと、を備えている。
2019176831.tif 000002
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密表参照システムであって、
Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rは上記ルックアップテーブルの出力値の集合の要素からなるベクトルであり、
上記複数の秘密計算装置は、
上記ベクトルdのシェア[d]及び上記ベクトルvのシェア[v]を用いて、上記ベクトルd及び上記ベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する複数の第一結合部と、
上記ベクトルrのシェア[r]を用いて、上記ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する複数の差分計算部と、
上記シェア[r'']を用いて、上記ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する複数の第二結合部と、
上記シェア[v']を用いて、上記ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、
上記シェア[r']及び上記シェア{{σ}}を用いて、上記ベクトルr'に上記置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する複数の置換適用部と、
上記シェア[s]を用いて、上記ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する複数のベクトル生成部と、
上記シェア[s']及び上記シェア{{σ}}を用いて、上記ベクトルs'に上記置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する複数の逆置換適用部と、
上記シェア[s'']を用いて、上記ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する複数の出力部と、
を含む、
秘密表参照システム。
【請求項２】
請求項１の秘密表参照システムの秘密計算装置。
【請求項３】
Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rは上記ルックアップテーブルの出力値の集合の要素からなるベクトルであり、
第一結合部が、上記ベクトルdのシェア[d]及び上記ベクトルvのシェア[v]を用いて、上記ベクトルd及び上記ベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する第一結合ステップと、
差分計算部が、上記ベクトルrのシェア[r]を用いて、上記ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する差分計算ステップと、
第二結合部が、上記シェア[r'']を用いて、上記ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する第二結合ステップと、
置換計算部が、上記シェア[v']を用いて、上記ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する置換計算ステップと、
置換適用部が、上記シェア[r']及び上記シェア{{σ}}を用いて、上記ベクトルr'に上記置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する置換適用ステップと、
ベクトル生成部が、上記シェア[s]を用いて、上記ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成するベクトル生成ステップと、
逆置換適用部が、上記シェア[s']及び上記シェア{{σ}}を用いて、上記ベクトルs'に上記置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する逆置換適用ステップと、
出力部が、上記シェア[s'']を用いて、上記ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する出力ステップと、
を含む秘密表参照方法。
【請求項４】
請求項３の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関し、特に、秘匿性を保ったままルックアップテーブルを参照する技術に関する。
【背景技術】
【０００２】
秘匿性を保ったままルックアップテーブルを参照する技術として、非特許文献１に記載された技術が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】濱田浩気，五十嵐大，千田浩司，"秘密計算一括写像計算の効率化"，2014年暗号と情報セキュリティシンポジウム
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１に記載された技術では、通信量が比較的多かった。【０００５】
この発明は、通信量が従来よりも少ない秘密表参照システム、方法、秘密計算装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様による秘密表参照システムは、複数の秘密計算装置を含む秘密表参照システムであって、Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rはルックアップテーブルの出力値の集合の要素からなるベクトルであり、複数の秘密計算装置は、ベクトルdのシェア[d]及びベクトルvのシェア[v]を用いて、ベクトルd及びベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する複数の第一結合部と、ベクトルrのシェア[r]を用いて、ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する複数の差分計算部と、シェア[r'']を用いて、ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する複数の第二結合部と、シェア[v']を用いて、ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、シェア[r']及びシェア{{σ}}を用いて、ベクトルr'に置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する複数の置換適用部と、シェア[s]を用いて、ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する複数のベクトル生成部と、シェア[s']及びシェア{{σ}}を用いて、ベクトルs'に置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する複数の逆置換適用部と、シェア[s'']を用いて、ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する複数の出力部と、を備えている。
【発明の効果】
【０００７】
この発明によれば、通信量を従来よりも少なくすることができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、秘密表参照システムの機能構成を例示する図である。
【図２】図２は、秘密計算装置の機能構成を例示する図である。
【図３】図３は、秘密表参照方法の処理手続きを例示する図である。
【発明を実施するための形態】
【０００９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１０】
図１を参照して、実施形態の秘密表参照システムの構成例を説明する。秘密表参照システムは、N（≧2）台の秘密計算装置１1,…,１Nを含む。本形態では、秘密計算装置１1, …, １Nはそれぞれ通信網２へ接続されている。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などである。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１1, …, １Nへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密計算装置１1, …, １Nへオフラインで入力するように構成してもよい。
【００１１】
図２を参照して、秘密表参照システムに含まれる秘密計算装置１n（n=1, …, N）の構成例を説明する。秘密計算装置１nは、例えば、図２に示すように、第一結合部１１nと、差分計算部１２nと、第二結合部１３nと、置換計算部１４nと、置換適用部１５nと、ベクトル生成部１６nと、逆置換適用部１７nと、出力部１８nとを備えている。この秘密計算装置１n（1≦n≦N）の各構成部が他の秘密計算装置１n'（n'=1, …, N、ただしn≠n'）の各構成部と協調しながら後述する各ステップの処理を行うことにより実施形態の秘密表参照方法が実現される。
【００１２】
なお、各ステップの処理は、秘密計算により行われる。すなわち、秘密計算装置１nは、シェアを復元することなく、言い換えればシェアの中身を知ることなく、各ステップの処理を行う。
【００１３】
秘密計算装置１nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１nは、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１nに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１nの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００１４】
図３を参照して、実施形態の秘密表参照システムが実行する秘密表参照方法の処理手続きを説明する。
【００１５】
＜ステップＳ１＞
第一結合部１１1,…,１１Nに、ベクトルdのシェア[d]及びベクトルvのシェア[v]が入力される。
【００１６】
第一結合部１１1,…,１１Nは、シェア[d]とシェア[v]を結合してシェア[v']∈[F]m+ntを生成する。より詳細には、第一結合部１１1,…,１１Nは、シェア[d]及びシェア[v]を用いて、ベクトルd及びベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する（ステップＳ１）。
【００１７】
生成されたシェア[v']は、置換計算部１４1,…,１４Nに出力される。
【００１８】
Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数である。また、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntである。ベクトルvは、例えばある表のある属性の属性値からなるベクトルである。αを任意のベクトルとして、[α]はαが秘密分散されたシェアである。
【００１９】
[F]m+nt,Fntの上付き文字の中のntは、「nt」を意味する。このように、上付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。
【００２０】
例えば、ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}である場合には、ベクトルd=(0,1,2,3)Tとなる。このとき、ベクトルv=(1,3,1)Tである場合には、ベクトルv'=(0,1,2,3,1,3,1)Tとなる。
【００２１】
＜ステップＳ２＞
差分計算部１２1,…,１２Nに、ベクトルrのシェア[r]が入力される。
【００２２】
差分計算部１２1,…,１２Nは、シェア[r]に基づいてシェア[r'']を生成する。より詳細には、差分計算部１２1,…,１２Nは、シェア[r]を用いて、ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する（ステップＳ２）。
【００２３】
生成されたシェア[v']は、置換計算部１４1,…,１４Nに出力される。
【００２４】
rは、ルックアップテーブルの出力値の集合の要素からなるベクトルである。
【００２５】
ベクトルr''のi番目の要素は、「ベクトルrのi番目の要素」-「ベクトルrのi-1番目の要素」である。ただし、i=1の場合には、ベクトルr''のi番目の要素は、ベクトルrのi番目の要素となる。すなわち、ベクトルr''の１番目の要素は、ベクトルrの１番目の要素となる。
【００２６】
例えば、ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}である場合には、ベクトルr=(1,5,2,3)Tとなる。この場合、ベクトルr''=(1,4,-3,1)Tとなる。
【００２７】
＜ステップＳ３＞
第二結合部１３1,…,１３Nに、シェア[r'']が入力される。
【００２８】
第二結合部１３1,…,１３Nは、シェア[r'']と零ベクトルを結合してシェア[r']∈[F]m+ntを生成する。より詳細には、第二結合部１３1,…,１３Nは、シェア[r'']を用いて、ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する（ステップＳ３）。
【００２９】
生成されたシェア[r']は、置換適用部１５1,…,１５Nに出力される。
【００３０】
例えば、ベクトルr''=(1,4,-3,1)Tであり、m=3である場合には、ベクトルr'=(1,4,-3,1,0,0,0)Tとなる。
【００３１】
＜ステップＳ４＞
置換計算部１４1,…,１４Nに、シェア[v']が入力される。
【００３２】
置換計算部１４1,…,１４Nは、シェア[v']の{{σ}}を生成する。より詳細には、置換計算部１４1,…,１４Nは、シェア[v']を用いて、ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する（ステップＳ４）。
【００３３】
生成されたシェア{{σ}}は、置換適用部１５1,…,１５Nに出力される。
【００３４】
安定ソートとは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。βを任意の置換として、{{β}}はβが秘密分散されたシェアである。
【００３５】
ソート{{σ}}の生成は、例えば以下の参考文献１に記載された方法で行うことができる。
【００３６】
〔参考文献１〕五十嵐大，濱田浩気，菊池亮，千田浩司，"インターネット環境レスポンス1秒の統計処理を目指した, 秘密計算基数ソートの改良"，2014年暗号と情報セキュリティシンポジウム
例えば、ベクトルv'=(0,1,2,3,1,3,1)Tである場合には、置換σは以下の式（１）のようになる。
【００３７】
【数１】
2019176831.tif 000003
【００３８】
＜ステップＳ５＞
置換適用部１５1,…,１５Nに、シェア[r']及びシェア{{σ}}が入力される。
【００３９】
置換適用部１５1,…,１５Nは、シェア[r']に{{σ}}を適用してシェア[s]:=[σ(r')]を生成する。より詳細には、置換適用部１５1,…,１５Nは、シェア[r']及びシェア{{σ}}を用いて、ベクトルr'に置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する（ステップＳ５）。
【００４０】
生成されたシェア[s]はベクトル生成部１６1,…,１６Nに出力される。
【００４１】
置換{{σ}}の適用は、参考文献１に記載された方法で行うことができる。
【００４２】
例えば、ベクトルr'=(1,4,-3,1,0,0,0)Tであり、置換σが式（１）で示される置換である場合には、ベクトルs=(1,4,0,0,-3,1,0)Tとなる。
【００４３】
＜ステップＳ６＞
ベクトル生成部１６1,…,１６Nに、シェア[s]が入力される。
【００４４】
ベクトル生成部１６1,…,１６Nは、シェア[s]のprefix-sum [s']を生成する。より詳細には、ベクトル生成部１６1,…,１６Nは、シェア[s]を用いて、ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する（ステップＳ６）。
【００４５】
生成されたシェア[s']は、逆置換適用部１７1,…,１７Nに出力される。
【００４６】
例えば、ベクトルs=(1,4,0,0,-3,1,0)Tである場合には、ベクトルs'=(1,5,5,5,2,3,3)Tとなる。
【００４７】
＜ステップＳ７＞
逆置換適用部１７1,…,１７Nに、シェア[s']及びシェア{{σ}}が入力される。
【００４８】
逆置換適用部１７1,…,１７Nは、シェア[s']に{{σ}}を逆適用してシェア[s'']を生成する。より詳細には、逆置換適用部１７1,…,１７Nは、シェア[s']及びシェア{{σ}}を用いて、ベクトルs'に置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する（ステップＳ７）。
【００４９】
生成されたシェア[s'']は、出力部１８1,…,１８Nに出力される。
【００５０】
逆置換{{σ-1}}の適用は、例えば以下の参考文献２に記載された方法で行うことができる。
【００５１】
〔参考文献２〕桐淵直人，五十嵐大，諸橋玄武，濱田浩気，"属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装"，2016年コンピュータセキュリティシンポジウム
例えば、ベクトルs'=(1,5,5,5,2,3,3)Tであり、置換σが式（１）で示される置換である場合には、ベクトルs''=(1,5,2,3,5,3,5)Tとなる。
【００５２】
なお、逆置換σ-1を適用とは、置換σを逆適用するということである。
【００５３】
＜ステップＳ８＞
出力部１８1,…,１８Nに、シェア[s'']が入力される。
【００５４】
出力部１８1,…,１８Nは、シェア[s'']のnt+1番目以降の要素列を出力する。より詳細には、出力部１８1,…,１８Nは、シェア[s'']を用いて、ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する（ステップＳ８）。
【００５５】
生成されたシェア[x]が、秘密表参照システムによる最終的な計算結果として出力される。
【００５６】
例えば、ベクトルs''=(1,5,2,3,5,3,5)Tであり、nt=4である場合には、ベクトルx=(5,3,5)Tとなる。
【００５７】
ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}であり、ベクトルv=(1,3,1)Tである場合には、ベクトルx=(5,3,5)Tは、ベクトルv=(1,3,1)Tに対するルックアップテーブルtの参照結果となっている。
【００５８】
このように、逆置換σ-1を用いることで、従来よりも通信量を少なくすることができる。
【００５９】
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６０】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６２】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６５】
１1,…,１N  秘密計算装置
１１1,…,１１N  第一結合部
１２1,…,１２N  差分計算部
１３1,…,１３N  第二結合部
１４1,…,１４N  置換計算部
１５1,…,１５N  置換適用部
１６1,…,１６N  ベクトル生成部
１７1,…,１７N  逆置換適用部
１８1,…,１８N  出力部
２  通信網
【図１】
2019176831.tif 000004
【図２】
2019176831.tif 000005
【図３】
2019176831.tif 000006
【手続補正書】
【提出日】令和2年9月3日(2020.9.3)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
生成されたシェア[ｒ'']は、第二結合部１３1,…,１３Nに出力される。
【国際調査報告】
2019176831.tif 000007
2019176831.tif 000008