(57)【要約】  複数の秘密計算装置を含む秘密重複排除システムであって、複数の秘密計算装置は、ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部１１nと、ベクトルvに置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する複数の置換適用部１２nと、ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数のベクトル生成部１３nと、ベクトルeに置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する複数の逆置換適用部１４nと、を備えている。
2019188320.tif 000002
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密重複排除フィルタ生成システムであって、
Fは任意の体であり、mは２以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、
上記複数の秘密計算装置は、
上記ベクトルvのシェア[v]を用いて、上記ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、
上記シェア[v]及び上記シェア{{σ}}を用いて、上記ベクトルvに上記置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する複数の置換適用部と、
上記シェア[σ(v)]を用いて、上記ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数のベクトル生成部と、
上記シェア[e]及び上記シェア{{σ}}を用いて、上記ベクトルeに上記置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する複数の逆置換適用部と、
を含む秘密重複排除フィルタ生成システム。
【請求項２】
請求項１の秘密重複排除フィルタ生成システムを含み、
上記複数の秘密計算装置は、上記シェア[v]及び上記シェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する重複排除部を更に含む、
秘密重複排除システム。
【請求項３】
請求項１の秘密重複排除フィルタ生成システム又は請求項２の秘密重複排除システムの秘密計算装置。
【請求項４】
Fは任意の体であり、mは２以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、
置換計算部が、上記ベクトルvのシェア[v]を用いて、上記ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する置換計算ステップと、
置換適用部が、上記シェア[v]及び上記シェア{{σ}}を用いて、上記ベクトルvに上記置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する置換適用ステップと、
ベクトル生成部が、上記シェア[σ(v)]を用いて、上記ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成するベクトル生成ステップと、
逆置換適用部が、上記シェア[e]及び上記シェア{{σ}}を用いて、上記ベクトルeに上記置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する逆置換適用ステップと、
を含む秘密重複排除フィルタ生成方法。
【請求項５】
請求項４の秘密重複排除フィルタ生成方法と、
重複排除が、上記シェア[v]及び上記シェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する重複排除ステップと、
を含む秘密重複排除方法。
【請求項６】
請求項３の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関する。この発明は、特に、秘匿性を保ったまま重複を排除するフィルタを生成する技術、及び、生成されたフィルタを用いて重複を排除する技術に関する。
【背景技術】
【０００２】
秘密計算技術の分野において、秘匿性を保ったまま、表のある属性の属性値の重複を排除する技術が求められている。【０００３】
しかし、秘密計算技術の分野において、秘匿性を保ったまま、表のある属性の属性値の重複を排除する技術は知られていない。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
この発明は、秘匿性を保ったまま重複を排除するフィルタを生成する秘密重複排除フィルタ生成システム、秘匿性を保ったまま、生成されたフィルタを用いて重複を排除する秘密重複排除システム、これらの方法、秘密計算装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００５】
この発明の一態様による秘密重複排除フィルタ生成システムは、複数の秘密計算装置を含む秘密重複排除フィルタ生成システムであって、Fは任意の体であり、mは２以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、複数の秘密計算装置は、ベクトルvのシェア[v]を用いて、ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、シェア[v]及びシェア{{σ}}を用いて、ベクトルvに置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する複数の置換適用部と、シェア[σ(v)]を用いて、ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数のベクトル生成部と、シェア[e]及びシェア{{σ}}を用いて、ベクトルeに置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する複数の逆置換適用部と、を備えている。【０００６】
この発明の一態様による秘密重複排除システムは、秘密重複排除フィルタ生成システムを備えており、秘密計算装置は、シェア[v]及びシェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する重複排除部を更に備えている。【０００７】
この発明の一態様による秘密計算装置は、上記秘密重複排除フィルタ生成システム又は上記秘密重複排除システムの秘密計算装置である。
【発明の効果】
【０００８】
この発明によれば、秘匿性を保ったまま重複を排除するフィルタを生成することができる。また、秘匿性を保ったまま、生成されたフィルタを用いて重複を排除することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、秘密重複排除フィルタ生成システム及び秘密重複排除システムの機能構成を例示する図である。
【図２】図２は、秘密計算装置の機能構成を例示する図である。
【図３】図３は、秘密重複排除フィルタ生成方法及び秘密重複排除システムの処理手続きを例示する図である。
【発明を実施するための形態】
【００１０】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１１】
図１を参照して、実施形態の秘密重複排除システム及び秘密重複排除フィルタ生成システムの構成例を説明する。秘密重複排除システム及び秘密重複排除フィルタ生成システムは、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、ベクトル生成部１３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に、ベクトルvのシェア[v]が入力される。
【００２０】
置換計算部１１1,…,１１Nは、シェア[v]の{{σ}}を生成する。
【００２１】
より詳細には、置換計算部１１1,…,１１Nは、ベクトルvのシェア[v]を用いて、ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する（ステップＳ１）。安定ソートとは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。
【００２２】
生成されたシェア{{σ}}は、置換適用部１２1,…,１２Nに出力される。
Fは任意の体であり、mは２以上の整数である。また、vはm次元ベクトルv∈Fｍである。ベクトルvは、例えばある表のある属性の属性値からなるベクトルである。
【００２３】
例えば、ベクトルvが、「身長」という属性の属性値からなるベクトルであり、v=(160,150,160,170,160)であるとする。この場合、置換σは以下の式（１）のようになる。
【００２４】
【数１】
2019188320.tif 000003
【００２５】
なお、ベクトルvの各要素は、ビット分解されたものであってもよい。すなわち、ベクトルvの各要素は、その各要素が0,1のビットで表現されたものであってもよい。また、ベクトルvは、ある表の複数の属性の属性値を結合した値からなるベクトルであってもよい。
【００２６】
＜ステップＳ２＞
置換適用部１２1,…,１２Nに、シェア[v]及びシェア{{σ}}が入力される。
【００２７】
置換適用部１２1,…,１２Nは、シェア[v]にシェア{{σ}}を適用してシェア[σ(v)]を生成する。
【００２８】
より詳細には、置換適用部１２1,…,１２Nは、シェア[v]及びシェア{{σ}}を用いて、ベクトルvに置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する（ステップＳ２）。
【００２９】
生成されたシェア[σ(v)]は、ベクトル生成部１３1,…,１３Nに出力される。
【００３０】
例えば、ベクトルv=(160,150,160,170,160)であり、置換σが式（１）で示される置換である場合には、ベクトルσ(v)=(150,160,160,160,170)となる。
【００３１】
＜ステップＳ３＞
ベクトル生成部１３1,…,１３Nに、シェア[σ(v)]が入力される。
【００３２】
ベクトル生成部１３1,…,１３Nは、i=1,…,mとして、[ei]:=[σ(v)i≠σ(v)i-1]、ただし[e1]=1となる[e]を生成する。ここで、σ(v)iは、ベクトルσ(v)のi番目の要素であり、eiはベクトルeのi番目の要素である。
【００３３】
より詳細には、ベクトル生成部１３1,…,１３Nは、シェア[σ(v)]を用いて、ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する（ステップＳ３）。ただし、ベクトルeの最初の要素は１であるとする。
【００３４】
生成されたシェア[e]は、逆置換適用部１４1,…,１４Nに出力される。
【００３５】
例えば、ベクトルσ(v)=(150,160,160,160,170)である場合には、ベクトルe=(1,1,0,0,1)となる。
【００３６】
＜ステップＳ４＞
逆置換適用部１４1,…,１４Nに、シェア[e]及びシェア{{σ}}が入力される。
【００３７】
逆置換適用部１４1,…,１４Nは、シェア[e]にシェア{{σ}}を逆適用してシェア[σ-1(e)]を生成する。
【００３８】
より詳細には、逆置換適用部１４1,…,１４Nは、シェア[e]及びシェア{{σ}}を用いて、ベクトルeに置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する（ステップＳ４）。σ-1(e)は、重複排除処理に用いられるベクトルであり、フィルタとも言う。
【００３９】
生成されたシェア[σ-1(e)]が、秘密重複排除フィルタ生成システムの出力となる。秘密重複排除フィルタ生成処理に続けて秘密重複排除処理が行われる場合には、生成されたシェア[σ-1(e)]は、秘密重複排除システムに出力される。
【００４０】
例えば、ベクトルe=(1,1,0,0,1)であり、置換σが式（１）で示される置換である場合には、ベクトルσ-1(e)=(1,1,0,1,0)となる。
【００４１】
＜ステップＳ５＞
重複排除部１５1,…,１５Nに、シェア[v]及びシェア[σ-1(e)]が入力される。
【００４２】
重複排除部１５1,…,１５Nは、vσ-1(e)のシェア[vσ-1(e)]を生成する。
より詳細には、重複排除部１５1,…,１５Nは、シェア[v]及びシェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する（ステップＳ５）。
【００４３】
例えば、ベクトルv=(160,150,160,170,160)であり、ベクトルσ-1(e)=(1,1,0,1,0)である場合には、ベクトルvσ-1(e)=(160,150,0,170,0)となる。このように、ベクトルvσ-1(e)は、ベクトルvから重複した要素を排除したベクトルとなっている。
【００４４】
この実施形態によれば、秘匿性を保ったまま重複を排除するフィルタを生成することができる。また、この実施形態によれば、秘匿性を保ったまま、生成されたフィルタを用いて重複を排除することができる。
【００４５】
［変形例］
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。
【００４６】
例えば、重複排除部１５1,…,１５Nは、シェア[σ-1(e)]を生成する基になった属性以外の属性の属性値のベクトルwに対してフィルタσ-1(e)を適用したものwσ-1(e)のシェア[wσ-1(e)]を、シェア[w]及びシェア[σ-1(e)]を用いて求めてもよい。
【００４７】
例えば、「身長」という属性から得られたベクトルσ-1(e)=(1,1,0,1,0)であり、「性別」という属性の属性値のベクトルw=(男,女,男,女,男)である場合には、ベクトルwσ-1(e)=(男,女,0,女,0)となる。重複排除部１５1,…,１５Nは、シェア[w]及びシェア[σ-1(e)]を用いて、このようなベクトルwσ-1(e)のシェア[wσ-1(e)]を求めてもよい。
【００４８】
また、重複排除部１５1,…,１５Nは、複数の属性の属性値のベクトルのそれぞれに対してフィルタσ-1(e)を適用したもののシェアを求めてもよい。
【００４９】
また、実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５０】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５２】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019188320.tif 000004
【図２】
2019188320.tif 000005
【図３】
2019188320.tif 000006
【手続補正書】
【提出日】令和2年9月4日(2020.9.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の秘密計算装置を含む秘密重複排除フィルタ生成システムであって、
Fは任意の体であり、mは２以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、
上記複数の秘密計算装置は、
上記ベクトルvのシェア[v]を用いて、上記ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、
上記シェア[v]及び上記シェア{{σ}}を用いて、上記ベクトルvに上記置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する複数の置換適用部と、
上記シェア[σ(v)]を用いて、上記ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成する複数のベクトル生成部と、
上記シェア[e]及び上記シェア{{σ}}を用いて、上記ベクトルeに上記置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する複数の逆置換適用部と、
を含む秘密重複排除フィルタ生成システム。
【請求項２】
請求項１の秘密重複排除フィルタ生成システムを含み、
上記複数の秘密計算装置は、上記シェア[v]及び上記シェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する重複排除部を更に含む、
秘密重複排除システム。
【請求項３】
請求項１の秘密重複排除フィルタ生成システム又は請求項２の秘密重複排除システムの秘密計算装置。
【請求項４】
Fは任意の体であり、mは２以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、
置換計算部が、上記ベクトルvのシェア[v]を用いて、上記ベクトルvを昇順に安定ソートする置換σのシェア{{σ}}を生成する置換計算ステップと、
置換適用部が、上記シェア[v]及び上記シェア{{σ}}を用いて、上記ベクトルvに上記置換σを適用したベクトルσ(v)のシェア[σ(v)]を生成する置換適用ステップと、
ベクトル生成部が、上記シェア[σ(v)]を用いて、上記ベクトルσ(v)のある要素とそのある要素の前の要素とが、違う場合には１を、同じ場合には０をそのある要素に対応する要素として持つベクトルeのシェア[e]を生成するベクトル生成ステップと、
逆置換適用部が、上記シェア[e]及び上記シェア{{σ}}を用いて、上記ベクトルeに上記置換σの逆置換σ-1を適用したベクトルσ-1(e)のシェア[σ-1(e)]を生成する逆置換適用ステップと、
を含む秘密重複排除フィルタ生成方法。
【請求項５】
請求項４の秘密重複排除フィルタ生成方法と、
重複排除部が、上記シェア[v]及び上記シェア[σ-1(e)]を用いて、vσ-1(e)のシェア[vσ-1(e)]を生成する重複排除ステップと、
を含む秘密重複排除方法。
【請求項６】
請求項３の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2019188320.tif 000007
2019188320.tif 000008
2019188320.tif 000009
2019188320.tif 000010