(57)【特許請求の範囲】
【請求項１】
N個(N≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)(ただしr∈{1,...,R}, R≧2)を秘匿化することで得られた秘匿化属性値μ(r,1),..., μ(r,N)の入力を受け付ける入力部と、
前記N個の属性ATT(1),...,ATT(N)の一部であるm(j)(ただしm(j)＜N, j∈{1,...,J}, J≧1)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成する匿名化部と、
前記秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成する提供情報生成部と、
前記提供情報D(n(j,1),...,n(j,m(j)))を出力する出力部と、
を有し、
J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である、匿名データ装置。
【請求項２】
請求項１の匿名データ装置であって、
前記秘匿化属性値μ(r,1),..., μ(r,N)の秘密計算が可能であり、
前記匿名化部は、秘密計算による匿名化処理を秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に施して秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))を匿名化し、前記秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成する、匿名データ装置。
【請求項３】
請求項１または２の匿名データ装置であって、
前記提供情報生成部は、前記R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)をランダムに並び替えたR個の集合SUB(q(1),j),SUB(q(2),j),...,SUB(q(R),j)(ただしq(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})に対応するR個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)(ただしq(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})を生成し、前記R個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)に対応する前記提供情報D(n(j,1),...,n(j,m(j)))を生成する、匿名データ装置。
【請求項４】
請求項１から３の何れかの匿名データ装置であって、
m(j)≦M, 1≦M＜Nであり、前記匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))が含む正しい属性値に対応する値を表現するためのデータ量の合計が所定値以下である、匿名データ装置。
【請求項５】
N個(ただしN≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)(ただしr∈{1,...,R}, R≧2)を秘匿化することで得られた秘匿化属性値μ(r,1),..., μ(r,N)を出力するデータ提供装置と、
前記秘匿化属性値μ(r,1),..., μ(r,N)の入力を受け付け、前記N個の属性ATT(1),...,ATT(N)の一部であるm(j)(ただしm(j)＜N, j∈{1,...,J}, J≧1)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成し、前記秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成し、前記提供情報D(n(j,1),...,n(j,m(j)))を出力する匿名データ装置と、
前記提供情報D(n(j,1),...,n(j,m(j)))の入力を受け付ける分析装置と、
を有し、
J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である、匿名データ提供システム。
【請求項６】
出力部で、N個(ただしN≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)(ただしr∈{1,...,R}, R≧2)を秘匿化することで得られた秘匿化属性値μ(r,1),..., μ(r,N)を出力するステップと、
入力部で、前記秘匿化属性値μ(r,1),..., μ(r,N)の入力を受け付けるステップと、
匿名化部で、前記N個の属性ATT(1),...,ATT(N)の一部であるm(j)(ただしm(j)＜N, j∈{1,...,J}, J≧1)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成するステップと、
提供情報生成部で、前記秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成するステップと、
第２出力部で、前記提供情報D(n(j,1),...,n(j,m(j)))を出力するステップと、
第２入力部で、前記提供情報D(n(j,1),...,n(j,m(j)))の入力を受け付けるステップと、
を有し、
J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを統計的に匿名化して提供する技術に関する。
【背景技術】
【０００２】
従来、データベースにおける個別データを統計的手法により匿名化する技術として、非特許文献１に記載された維持-置換撹乱によるPk-匿名化がある。
非特許文献１では、データ提供者から提供されたデータの集まりであるテーブルを匿名化する。一人のデータ提供者からのデータのまとまりはテーブル上で行として表現され、レコードと呼ばれる。各レコードはいくつかの予め定められた項目に対する値から成り立ち、この項目のことを属性と呼ぶ。属性に対する値を属性値と呼ぶ。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】五十嵐大， 千田浩司， 高橋克巳， “k-匿名性の確率的指標への拡張とその適用例，” CSS2009， 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
たとえデータ提供者そのものを特定するための情報がレコードに含まれていなくても、レコードに含まれる属性値からデータ提供者を特定するための情報が得られ、その匿名性が低下する場合がある。一般に、レコードに対応する属性の個数が多いほど、そのレコードを提供したデータ提供者の匿名性が低下する。また、各属性値が持つ情報が大きいほど、それらを含むレコードを提供したデータ提供者の匿名性が低下する。従って、データ提供者の匿名性を統計的に所望の高さに維持しようとすれば、当該レコードに対応する属性の個数や各属性値の情報の大きさを制限しなければならない。そのため、提供されるレコードに対応する属性の個数が多いほど各属性値の情報を小さくしなければならず、データの有用性が低下する。
【課題を解決するための手段】
【０００５】
本発明では、匿名データ装置が、N個(N≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)(ただしr∈{1,...,R}, R≧2)を秘匿化することで得られた秘匿化属性値μ(r,1),..., μ(r,N)の入力を受け付け、N個の属性ATT(1),...,ATT(N)の一部であるm(j)( ただしm(j)＜N, j∈{1,...,J}, J≧1)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))( ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成し、秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成し、提供情報D(n(j,1),...,n(j,m(j)))を出力する。
【０００６】
ここで、匿名データ装置には、N個の属性ATT(1),...,ATT(N)すべてに対応する秘匿化属性値μ(r,1),..., μ(r,N)が与えられるが、秘匿化属性値μ(r,1),..., μ(r,N)は秘匿化されているため、Nの大きさにかかわらず匿名データ装置に対する匿名性が維持できる。匿名データ装置から出力される提供情報D(n(j,1),...,n(j,m(j)))は、m(j)(ただしm(j)＜N)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))のみに対応するものであるため、提供情報D(n(j,1),...,n(j,m(j)))の提供を受けるものに対する統計的な匿名性を所望の高さに維持しつつ、Nを大きくできる。
【発明の効果】
【０００７】
本発明では、提供情報の有用性を保ちつつ、レコードに対応する属性の個数を増加させることができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態の匿名データ提供システムの機能構成を説明するための図である。
【図２】図２Ａは、実施形態のデータ提供装置の機能構成を説明するための図である。図２Ｂは、実施形態の匿名データ装置の機能構成を説明するための図である。図２Ｃは、実施形態の分析装置の機能構成を説明するための図である。
【図３】図３Ａは、実施形態のデータ提供装置の処理を説明するための図である。図３Ｂは、実施形態の匿名データ装置の処理を説明するための図である。図３Ｃは、実施形態の分析装置の処理を説明するための図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
〔概要〕
実施形態の概要を説明する。
実施形態では、データ提供者から提供されたデータの集まりであるテーブル形式のデータベースを匿名化する。一人のデータ提供者からのデータのまとまりはテーブル上で行として表現され、レコードと呼ばれる。各レコードはいくつかの予め定められた項目に対する値から成り立ち、この項目のことを属性と呼ぶ。属性に対する値を属性値と呼ぶ。
【００１０】
実施形態の匿名データ提供システムは、データ提供装置、匿名データ装置、及び分析装置を有する。データ提供装置は、N個(ただしN≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)( ただしr∈{1,...,R}, R≧2)を秘匿化することで得られた秘匿化属性値μ(r,1),..., μ(r,N)を出力する。匿名データ装置は、匿化属性値μ(r,1),..., μ(r,N)の入力を受け付け、N個の属性ATT(1),...,ATT(N)の一部であるm(j)( ただしm(j)＜N, j∈{1,...,J}, J≧1)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成する。例えば、秘匿化属性値μ(r,1),..., μ(r,N)の秘密計算が可能であり、匿名データ装置は、秘密計算による匿名化処理を秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に施して秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))を匿名化し、秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成する。さらに匿名データ装置は、秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成し、提供情報D(n(j,1),...,n(j,m(j)))を出力する。
【００１１】
ここで、匿名データ装置には、N個の属性ATT(1),...,ATT(N)すべてに対応する秘匿化属性値μ(r,1),..., μ(r,N)が与えられるが、秘匿化属性値μ(r,1),..., μ(r,N)は秘匿化されているため、Nの大きさにかかわらず匿名データ装置に対する匿名性が維持できる。匿名データ装置から出力される提供情報D(n(j,1),...,n(j,m(j)))は、m(j)(ただしm(j)＜N)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))のみに対応するものであるため、分析装置に対する統計的な匿名性を所望の高さに維持しつつ、Nを大きくできる。例えばm(j)≦M, 1≦M＜Nであり、匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))が含む正しい属性値に対応する値を表現するためのデータ量の合計が所定値以下の場合、Nの大きさにかかわらず、分析装置に対する統計的な匿名性の高さを、当該所定値以下のデータ量で表現される属性値から得られる匿名性の高さ程度に制限できる。従って、提供情報の有用性を保ちながら、レコードに対応する属性の個数を増加させることができる。
【００１２】
好ましくは、J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である。言い換えると、例えば、集合{n(j1,1),...,n(j1,m(j1))}は集合{n(j2,1),...,n(j2,m(j2))}の要素を含まず、集合{n(j2,1),...,n(j2,m(j2))}は集合{n(j1,1),...,n(j1,m(j1))}の要素を含まない。すなわち、分析装置に提供された提供情報D(n(j1,1),...,n(j1,m(j1)))に対応する属性と提供情報D(n(j2,1),...,n(j2,m(j2)))に対応する属性とは重複しない。これにより、提供情報D(n(j1,1),...,n(j1,m(j1)))と提供情報D(n(j2,1),...,n(j2,m(j2)))とは独立した情報となる。
【００１３】
好ましくは、匿名データ装置は、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)をランダムに並び替えたR個の集合SUB(q(1),j),SUB(q(2),j),...,SUB(q(R),j)(q(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})に対応するR個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)(q(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})を生成し、R個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成する。SUB(r,j)=SUB’(r,j)(ただしr∈{1,...,R})であってもよいし、SUB(r,j)≠SUB’(r,j)であってもよい。これらの提供情報D(n(j,1),...,n(j,m(j)))は、集合SUB(1,j),SUB(2,j),...,SUB(R,j)の順序に関する情報（集合SUB(r,j)のそれぞれのrに関する情報）を含まない。そのため、分析装置に対する所望の高さの統計的な匿名性を十分に維持できる。特に、このような提供情報であって、なおかつ、J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である場合、分析装置は、提供情報D(n(j1,1),...,n(j1,m(j1))),D(n(j2,1),...,n(j2,m(j2)))から、同一のrに対応するm(j1)及びm(j2)よりも多い個数の属性値に関する情報を一切得ることができない。その結果、分析装置に対する所望の高さの統計的な匿名性を確実に維持できる。
【００１４】
匿名データ装置から出力される提供情報D(n(j,1),...,n(j,m(j)))は秘匿化された情報であってもよいし、秘匿化されていない情報であってもよい。提供情報D(n(j,1),...,n(j,m(j)))が秘匿化された情報である場合、匿名データ装置にはデータ提供者の情報が一切漏れない。提供情報D(n(j,1),...,n(j,m(j)))が秘匿化されていない情報である場合、匿名データ装置に対するデータ提供者の匿名性は、分析装置に対するデータ提供者の匿名性と同等となる。
【００１５】
〔第１実施形態〕
第１実施形態を説明する。
＜構成＞
図１に例示するように、第１実施形態の匿名データ提供システム１は、データ提供装置１１０−１〜Ｒ（R≧2）、匿名データ装置１２０−１〜Ｔ（T≧1）、及び分析装置１３０を有する。これらはネットワークや可搬型記録媒体などを介して情報のやり取りが可能である。説明の簡略化のため、本形態では１個の分析装置１３０のみを説明するが、分析装置が複数存在してもよい。
【００１６】
図２Ａに例示するように、第１実施形態のデータ提供装置１１０−ｒ（r∈{1,...,R}）は、入力部１１１−ｒ、出力部１１１−ｒ、記憶部１１３−ｒ、メモリ１１４−ｒ、制御部１１５−ｒ、及び秘匿化部１１７−ｒを有する。図２Ｂに例示するように、第１実施形態の匿名データ装置１２０−ｔ（t∈{1,...,T}）は、入力部１２１−ｔ、出力部１２２−ｔ、記憶部１２３−ｔ、メモリ１２４−ｔ、制御部１２５−ｔ、提供情報生成部１２６−ｔ、及び匿名化部１２７−ｔを有する。図２Ｃに例示するように、第１実施形態の分析装置１３０は、入力部１３１、出力部１３２、記憶部１３３、メモリ１３４、制御部１３５、及び分析部１３６を有する。
【００１７】
データ提供装置１１０−１〜Ｒ、匿名データ装置１２０−１〜Ｔ、及び分析装置１３０は、例えば、CPU(central processing unit), RAM(random-access memory), ROM(read-only memory)等を備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。データ提供装置１１０−１〜Ｒ、匿名データ装置１２０−１〜Ｔ、及び分析装置１３０は、それぞれが有する制御部１１５−ｒ，１２５−ｔ，１３５の制御のもとで各処理を実行する。各処理部から出力されたデータは、それぞれの装置が有するメモリ１１４−ｒ，１２４−ｔ，１３４に格納され、必要に応じて読み出されて他の処理に利用される。
【００１８】
＜秘匿データの保管処理＞
図３Ａに例示するように、各データ提供装置１１０−ｒ（図２Ａ）の入力部１１１−ｒに、レコードを構成するN個(N≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)が入力され、記憶部１１３−ｒに格納される（ステップＳ１１１）。本形態のNは整数の定数である。以下にN=4、ATT(1)=「年齢」, ATT(2)=「性別」, ATT(3)=「住所」, ATT(4)=「年収」である場合の１個のレコードを例示する（ステップＳ１１１）。
【表１】
0005758315.tif 000002
【００１９】
属性値ν(r,1),...,ν(r,N)は秘匿化部１１７−ｒに入力される。秘匿化部１１７−ｒは、属性値ν(r,1),...,ν(r,N)を秘匿化し、それによって得られたN個の秘匿化属性値μ(r,1),..., μ(r,N)を出力する（ステップＳ１１３）。秘匿化とは、秘匿化後の値から秘匿化前の値を得ることを困難にする処理を意味する。例えば、秘密分散や暗号化などが秘匿化の例である。また、秘匿化後の値で秘密計算が可能な秘匿化方式も存在する。秘密計算が可能な秘匿化方式の具体例は、秘匿回路方式（例えば、参考文献１：柴田賢介, 千田浩司, 五十嵐大, 山本太郎, 高橋克巳，“表計算ソフトをフロントエンドとした委託型２パーティ秘匿回路計算システム”， CSS2009, 2009.）、加法的秘密分散方式（例えば、参考文献２：千田浩司, 濱田浩気, 五十嵐大, 高橋克巳， “軽量検証可能３パーティ秘匿関数計算の再考”， CSS2010, 2010.）、エルガマル暗号方式（例えば、参考文献３：千田浩司, 谷口展郎, 山本剛, 岡崎聖人, 塩野入理, 金井敦， “エルガマル暗号に基づく秘匿回路計算の実装と応用”， CSS2005, pp. 475 - 480, 2005.）などである。N個の秘匿化属性値μ(r,1),..., μ(r,N)は出力部１１２−ｒに入力される。出力部１１２−ｒは、秘匿化属性値μ(r,1),..., μ(r,N)を出力する（ステップＳ１１４）。
【００２０】
秘匿化属性値μ(r,1),..., μ(r,N)は、ネットワーク等を介して匿名データ装置１２０−１〜Ｔに送られる。秘匿化方式に応じ、各匿名データ装置１２０−１〜Ｔに送られる秘匿化属性値μ(r,1),..., μ(r,N)が同一である場合と同一でない場合とがある。秘匿化属性値μ(r,1),..., μ(r,N)は、匿名データ装置１２０−ｔ（図２Ｂ）のそれぞれの入力部１２１−ｔに入力され、記憶部１２３−ｔに格納される。これにより、記憶部１２３−ｔには、属性ATT(1),...,ATT(N)及びr={1,...,R}に秘匿化属性値μ(r,1),..., μ(r,N)が対応付けられたデータベースが格納される。以下にN=4、ATT(1)=「年齢」, ATT(2)=「性別」, ATT(3)=「住所」, ATT(4)=「年収」である場合のデータベースを例示する。なお、SEC(α)はαが秘匿化された値を表す。
【表２】
0005758315.tif 000003
【００２１】
＜データの提供＞
図３Ｃに例示するように、分析装置１３０（図２Ｃ）の出力部１３２は、N個の属性ATT(1),...,ATT(N)から選択されたm(j)(ただしm(j)≦M, 1≦M＜N)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))( ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})を表す識別子である属性識別子を出力する（ステップＳ１３１）。なお、本形態のMは整数の定数である。属性識別子は、ネットワーク等を経由して匿名データ装置１２０−ｔのそれぞれに送られる。
【００２２】
図３Ｂに例示するように、属性識別子は匿名データ装置１２０−ｔ（図２Ｂ）の入力部１２１−ｔに入力され、記憶部１２３ｔに格納される（ステップＳ１２１）。属性識別子は匿名化部１２７−ｔに入力される。匿名化部１２７−ｔは、属性識別子が表すm(j)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))を記憶部１２３−ｔから抽出する。匿名化部１２７−ｔは、抽出した秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に対し、匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成する。
【００２３】
匿名化とは、提供情報から情報提供者そのものを特定するための情報（氏名等）を排除するだけでなく、データに含まれる正しい属性値のデータ量を削減することを意味する。例えば、属性値の粒度を低下させたり、一部の属性値を所定の確率で異なる値に置換したりすることが匿名化に相当する。例えば表２の最初のレコードの場合、属性「年齢」「性別」「住所」「年収」それぞれの属性値を「30代」「男」「東京都」「500万円代」に変換したり、所定の確率で異なる属性値にランダム置換したりすること（例えば、非特許文献１の維持−置換撹乱）が匿名化に相当する。本形態の匿名化部１２７−ｔは、匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))が含む正しい属性値に対応する値を表現するためのデータ量の合計が所定値以下であるように秘匿化する（ただしm(j)≦M, 1≦M＜N）。言い換えると、本形態の匿名化部１２７−ｔは、匿名化属性値v(r,1),...,v(r,N)からどのような組み合わせのM個の匿名化属性値v(r,w(1)),...,v(r,w(M))が選択されたとしても、それらから得られる正しい属性値に対応する値を表現するためのデータ量の合計が所定値以下となるように秘匿化する。なお、正しい属性値に対応する値とは、正しい属性値そのものや正しい属性値の上位概念を意味する。例えば、属性「年齢」の正しい属性値「32歳」に対応する値は「32歳」や「30代」である。
【００２４】
秘匿化属性値μ(r,1),..., μ(r,N)の秘密計算が可能な場合、匿名化部１２７−ｔは、このような匿名化処理を秘密計算によって実行してもよい。すなわち、匿名化部１２７−ｔは、属性値ν(r,n(j,1)),..., ν(r,n(j,m(j)))を復元することなく、秘密計算による匿名化処理を秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))に施し、秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成してもよい。或いは、秘匿化属性値μ(r,1),..., μ(r,N)の秘密計算が可能であるか否かにかかわらず、匿名化部１２７−ｔが、秘匿化属性値μ(r,n(j,1)),...,μ(r,n(j,m(j)))から属性値ν(r,n(j,1)),..., ν(r,n(j,m(j)))を復元し、属性値ν(r,n(j,1)),..., ν(r,n(j,m(j)))を匿名化して匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))を生成し、匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))を再び秘匿化して秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))を生成してもよい（ステップＳ１２２）。
【００２５】
秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))は提供情報生成部１２６−ｔに入力される。提供情報生成部１２６−ｔは、秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))からなる集合SUB(r,j)={s(r,n(j,1)),...,s(r,n(j,m(j)))}を用い、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)に対応する提供情報D(n(j,1),...,n(j,m(j)))を生成する。以下に提供情報D(n(j,1),...,n(j,m(j)))を例示する。
【００２６】
[提供情報の例１（集計表）]
この例は、秘匿化匿名属性値s(r,1),...,s(r,N)の秘密計算が可能であることを前提とする。提供情報生成部１２６−ｔは、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)を秘密計算によって集計して得られる集計表を提供情報D(n(j,1),...,n(j,m(j)))とする。
集計表の具体例は、秘密計算によって行われるクロス集計によって得られる秘匿化されたクロス集計表である。クロス集計とはテーブルの複数の属性に着目し、着目したすべての属性の属性値が等しいレコードを集計する集計法である。クロス集計表は、着目された複数の属性の属性値の組と当該属性値の組に適合するレコードの個数とが対応付けられた表となる（例えば、参考文献４：永井彰，五十嵐大，濱田浩気，松林達史，“クロネッカー積を含む行列積演算の最適化による効率的なプライバシー保護データ公開技術”，SCIS2010, 2010.参照）。以下に、m(j)=2とし、２個の属性ATT(1)=「年齢」, ATT(2)=「性別」に着目した秘匿化されたクロス集計表を例示する。
【表３】
0005758315.tif 000004
【００２７】
集計表の他の具体例は、秘密計算によって行われる単純集計によって得られる秘匿化された単純集計表である。単純集計とはテーブルの一つの属性に着目し、着目した属性の属性値が等しいレコードを集計する集計法である。単純集計表は、着目された属性の属性値と当該属性値に適合するレコードの個数とが対応付けられた表となる。以下に、m(j)=1とし、属性ATT(1)=「年齢」に着目した秘匿化された単純集計表を例示する。
【表４】
0005758315.tif 000005
【００２８】
なお、提供情報生成部１２６−ｔは、秘匿化された集計表をそのまま提供情報D(n(j,1),...,n(j,m(j)))としてもよいし、秘匿化された集計表から秘匿化されていない集計表を復元し、それを提供情報D(n(j,1),...,n(j,m(j)))としてもよい。
【００２９】
[提供情報の例２（表形式のデータベース）]
提供情報生成部１２６−ｔは、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)をランダムに並び替えたR個の集合SUB(q(1),j),SUB(q(2),j),...,SUB(q(R),j)(ただしq(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})に対応するR個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)(ただしq(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})、又は当該R個の集合SUB’(q(1),j),SUB’(q(2),j),...,SUB’(q(R),j)を復元して得られる属性値の集合（表形式のデータベース）を提供情報D(n(j,1),...,n(j,m(j)))とする。例えば、提供情報生成部１２６−ｔは、R個の集合SUB(1,j),SUB(2,j),...,SUB(R,j)をランダムに並び替えたR個の集合SUB(5,j),SUB(3,j),...,SUB(6,j)に対応するR個の集合SUB’(5,j),SUB’(3,j),...,SUB’(6,j)、又はこれらを復元して得られる属性値の集合を提供情報D(n(j,1),...,n(j,m(j)))とする。なお、SUB(r,j)のそれぞれからrを特定することはできない。SUB(r,j)=SUB’(r,j)(r∈{1,...,R})であってもよいし、SUB(r,j)≠SUB’(r,j)であってもよい。SUB(r,j)≠SUB’(r,j)であり、SUB(r,j)及びSUB’(r,j)からSUB(r,j)とSUB’(r,j)との対応関係を知ることが困難なのであれば、匿名データ装置１２０−ｔや分析装置１３０に対して高い匿名性を維持できる。このような並び替え方法の一例は、「濱田造気，五十嵐大，千田浩司，高橋克巳，“３パーティ秘匿関数計算上のランダム置換プロトコル”，2010年10月12日，情報処理学会シンポジウム論文集，2010巻，9号，pp.561-566.（参考文献５）」に開示されている。提供情報生成部１２６−ｔは、提供情報の例１の集計表から生成した表形式のデータベースを提供情報D(n(j,1),...,n(j,m(j)))としてもよい。集計表から表形式のデータベースを生成するには、集計表の各集計値について、当該集計値に対応する属性値の組み合わせからなるレコードを、それぞれ当該集計値分ずつ生成していけばよい。或いは、提供情報生成部１２６−ｔが、「特開2011-145869号公報（参考文献６）」に開示された擬似データからなる擬似データベースを生成して出力してもよい。
【００３０】
提供情報生成部１２６−ｔは、生成した提供情報D(n(j,1),...,n(j,m(j)))を出力する（ステップＳ１２３）。提供情報D(n(j,1),...,n(j,m(j)))は出力部１２２−ｔに入力される。出力部１２２−ｔは提供情報D(n(j,1),...,n(j,m(j)))を出力する（ステップＳ１２４）。提供情報D(n(j,1),...,n(j,m(j)))は、ネットワーク等を介して分析装置１３０に送られ、図３Ｃに例示するように、分析装置１３０（図２Ｃ）の入力部１３１に入力され、記憶部１３３に格納される（ステップＳ１３２）。
【００３１】
分析部１１３は、記憶部１３３から提供情報D(n(j,1),...,n(j,m(j)))を抽出し、提供情報D(n(j,1),...,n(j,m(j)))を用いて所望のデータを生成して出力する。例えば提供情報D(n(j,1),...,n(j,m(j)))が秘匿化された情報であれば、分析部１１３は、例えば提供情報D(n(j,1),...,n(j,m(j)))を復元して得られる情報を出力する。例えば提供情報D(n(j,1),...,n(j,m(j)))が集計表であれば、分析部１１３は、例えば当該集計表から表形式のデータベースを生成する（ステップＳ１３３）。分析部１１３から出力されたデータは出力部１３２から出力される（ステップＳ１３４）。
【００３２】
なお、ステップＳ１２１〜Ｓ１２４，Ｓ１３１〜Ｓ１３３の処理は、すべてのj∈{1,...,J}について実行される。ステップＳ１２１〜Ｓ１２４，Ｓ１３１〜Ｓ１３３の処理がそれぞれ１回ずつ実行され、その際に各ステップですべてのj∈{1,...,J}についての処理がまとめて実行されてもよい。或いは、各j∈{1,...,J}についてのステップＳ１２１〜Ｓ１２４，Ｓ１３１〜Ｓ１３３の処理がjを更新しながら繰り返されてもよい。また、各j∈{1,...,J}についてのステップＳ１２１〜Ｓ１２４，Ｓ１３１，Ｓ１３２の処理がjを更新しながら繰り返され、すべてのj∈{1,...,J}についてステップＳ１２１〜Ｓ１２４，Ｓ１３１，Ｓ１３２の処理が実行された後、ステップＳ１３３，Ｓ１３４の処理が実行されてもよい。また好ましくは、J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である。
【００３３】
〔第２実施形態〕
第２実施形態は第１実施形態の具体例である。本形態では、データ提供装置で行われる匿名化処理として非特許文献１の５章に開示された維持-置換撹乱を用い、データ提供装置で行われる秘匿化や匿名データ装置で行われる秘密計算として参考文献２に開示された技術を用いる。参考文献２では、秘匿化情報を３者に秘密分散（加法的秘密分散）して秘密計算を行う。そのため、本形態の匿名データ装置の個数は３個（T=3）となる。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する部分については第１実施形態と同一の参照番号を用いて説明を簡略以下する。
【００３４】
＜構成＞
図１に例示するように、第２実施形態の匿名データ提供システム２は、データ提供装置２１０−１〜Ｒ（R≧2）、匿名データ装置２２０−１〜３（T=3）、及び分析装置２３０を有する。これらはネットワークや可搬型記録媒体などを介して情報のやり取りが可能である。説明の簡略化のため、本形態では１個の分析装置２３０のみを説明するが、分析装置が複数存在してもよい。
【００３５】
図２Ａに例示するように、第２実施形態のデータ提供装置２１０−ｒ（r∈{1,...,R}）は、入力部１１１−ｒ、出力部１１１−ｒ、記憶部１１３−ｒ、メモリ１１４−ｒ、制御部２１５−ｒ、及び秘匿化部２１７−ｒを有する。図２Ｂに例示するように、第２実施形態の匿名データ装置２２０−ｔ（t∈{1,2,3}）は、入力部１２１−ｔ、出力部１２２−ｔ、記憶部１２３−ｔ、メモリ１２４−ｔ、制御部２２５−ｔ、提供情報生成部２２６−ｔ、及び匿名化部２２７−ｔを有する。図２Ｃに例示するように、第２実施形態の分析装置２３０は、入力部１３１、出力部１３２、記憶部１３３、メモリ１３４、制御部２３５、及び分析部２３６を有する。
【００３６】
データ提供装置２１０−１〜Ｒ、匿名データ装置２２０−１〜３、及び分析装置２３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。データ提供装置２１０−１〜Ｒ、匿名データ装置２２０−１〜３、及び分析装置２３０は、それぞれが有する制御部２１５−ｒ，２２５−ｔ，２３５の制御のもとで各処理を実行する。各処理部から出力されたデータは、それぞれの装置が有するメモリ１１４−ｒ，１２４−ｔ，１３４に格納され、必要に応じて読み出されて他の処理に利用される。
【００３７】
＜事前処理＞
各属性ATT(n)(n∈{1,...,N})にそれぞれ対応する維持確率ρ(n)（0≦ρ(n)≦1）、及び各属性ATT(n)(n∈{1,...,N})にそれぞれ対応する属性値を正整数に変換するための対応表TAB(n)（属性値と整数との対応表）が何れかの匿名データ装置２２０−ｔから出力される。維持確率ρ(n)は匿名データ装置２２０−１〜３に入力及び設定され、対応表TAB(n)はデータ提供装置２１０−１〜Ｒに入力及び設定される。維持確率とは、維持-置換撹乱で属性値が維持される確率を表す。維持-置換撹乱で属性値が維持されない場合には本来の属性値がランダムな属性値に変更される。本来の属性値がランダムな属性値に変更された場合であっても、ランダムな属性値が本来の属性値に一致する場合もある。維持確率は、ランダムな属性値が本来の属性値に一致する場合にも属性値が維持されていないとみた確率である。好ましくは、維持確率ρ(n) (ただしn∈{1,...,N})は、秘密計算による維持-置換撹乱によって生成された秘匿化匿名属性値s(r,n(j,1)),...,s(r,n(j,m(j)))に対応する匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))が含む正しい属性値に対応する値を表現するためのデータ量の合計が、所定値以下となるような値である（ただしm(j)≦M, 1≦M＜N）。或いは、以下のσ値が閾値以上となる維持確率ρ(η)(η∈{1,...,N})が選択されることが望ましい。σ値は、直感的に「どのデータからもデータ提供者をσ個以下の候補に絞り込めない」ということを保証する指標である。
【数１】
0005758315.tif 000006
ただし、AS={w(1),...,w(M)}⊂{1,...,N}}であり、L(η)は属性ATT(η)の属性値の個数（要素の個数）である。例えば属性ATT(2)=「性別」である場合、L(2)=2である。また、参考文献２の秘密計算では正整数の属性値しか扱うことができず、属性値を整数として扱う必要性から対応表TAB(n)が必要となる。本形態の対応表TAB(n)は、属性ATT(n)に対応するL(n)個の属性値をL(n)個の整数0,...,L(n)-1に置換する。
【００３８】
維持確率ρ(n)でψ(n)を維持-置換撹乱して得られる値をζ(n)とすると、維持確率ρ(n)は、ψ(n)行ζ(n)列成分を遷移確率(A(n))ψ(n)ζ(n)とする以下遷の移確率行列A(n)で表現できる。
【数２】
0005758315.tif 000007
ただし、L(n)は属性ATT(n)の属性値の個数である。
【００３９】
＜秘匿データの保管処理＞
図３Ａに例示するように、各データ提供装置２１０−ｒ（図２Ａ）の入力部１１１−ｒに、レコードを構成するN個(N≧2)の属性ATT(1),...,ATT(N)それぞれの属性値ν(r,1),...,ν(r,N)が入力され、記憶部１１３−ｒに格納される（ステップＳ１１１）。
【００４０】
レコードを構成するN個の属性値ν(r,1),...,ν(r,N)は秘匿化部２１７−ｒに入力される。秘匿化部２１７−ｒは、属性値ν(r,1),...,ν(r,N)を以下のように秘匿化し、それによって得られたN個の秘匿化属性値μ(r,1),...,μ(r,N)を出力する。本形態では、３個の匿名データ装置２２０−t（t∈{1,2,3}）に対し、互いに同一とは限らない秘匿化属性値μ(r,1),...,μ(r,N)が出力される。以下では、匿名データ装置２２０−t（ただしt∈{1,2,3}）に対して出力される秘匿化属性値μ(r,n)(n∈{1,...,N})をμt(r,n)（ただしt∈{1,2,3}, n∈{1,...,N}）と表記する。
【００４１】
まず秘匿化部２１７−ｒは、対応表TAB(n)(ただしn∈{1,...,N})に従って、N個の属性値ν(r,1),...,ν(r,N)をN個の属性整数値υ(r,1),...,υ(r,N)に変換する。次に秘匿化部２１７−ｒは、N個の属性整数値υ(r,1),...,υ(r,N)に対する加法的秘密分散を行う。すなわち、まず秘匿化部２１７−ｒは、N個のランダムな整数υ0(r,1),...,υ0(r,N)とN個のランダムな整数υ1(r,1),...,υ1(r,N)を生成する。次に秘匿化部２１７−ｒは、υ2(r,n)=υ(r,n)-υ0(r,n)-υ1(r,n) mod p (ただしn∈{1,...,N}）を計算する。ただし、pは素数定数である。秘匿化部２１７−ｒは、以下のような秘匿化属性値μt(r,n)（ただしt∈{1,2,3}, n∈{1,...,N}）を生成する。
μ1(r,n)=(υ0(r,n), υ1(r,n))
μ2(r,n)=(υ1(r,n), υ2(r,n))
μ3(r,n)=(υ2(r,n), υ0(r,n))
すなわち、秘匿化部２１７−ｒは、以下のような秘匿化属性値μt(r,n)（ただしt∈{1,2,3}, n∈{1,...,N}）を生成する。
μt(r,n)=(υt-1(r,n), υt mod 3(r,n))
秘匿化属性値μt(r,1),...,μt(r,N)（ただしt∈{1,2,3}）は出力部１１２−ｒに入力される（ステップＳ２１３）。
【００４２】
出力部１１２−ｒは、秘匿化属性値μt(r,1),...,μt(r,N)（ただしt∈{1,2,3}）を出力する（ステップＳ２１４）。秘匿化属性値μt(r,1),...,μt(r,N)は、ネットワーク等を介して匿名データ装置２２０−ｔ（ただしt∈{1,2,3}）に送られる。秘匿化属性値μt(r,1),...,μt(r,N)は、匿名データ装置２２０−ｔ（図２Ｂ）のそれぞれの入力部１２１−ｔに入力され、記憶部１２３−ｔに格納される。これにより、記憶部１２３−ｔには、属性ATT(1),...,ATT(N)及びr={1,...,R}に秘匿化属性値μt(r,1),...,μt(r,N)が対応付けられたデータベースが格納される。
【００４３】
＜データの提供＞
図３Ｃに例示するように、分析装置２３０（図２Ｃ）の出力部１３２は、N個の属性ATT(1),...,ATT(N)から選択されたm(j)(ただしm(j)≦M, 1≦M＜N)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})を表す識別子である属性識別子を出力する（ステップＳ１３１）。なお、本形態のMは整数の定数である。属性識別子は、ネットワーク等を経由して匿名データ装置２２０−ｔ（ただしt∈{1,2,3}）のそれぞれに送られる。
【００４４】
図３Ｂに例示するように、属性識別子は匿名データ装置２２０−ｔ（図２Ｂ）の入力部１２１−ｔに入力され、記憶部１２３ｔに格納される（ステップＳ１２１）。属性識別子は匿名化部２２７−ｔに入力される。匿名化部２２７−ｔは、属性識別子が表すm(j)個の属性ATT(n(j,1)),...,ATT(n(j,m(j)))(ただし{n(j,1),...,n(j,m(j))}⊂{1,...,N})のそれぞれに対応する秘匿化属性値μt(r,n(j,1)),...,μt(r,n(j,m(j)))を記憶部１２３−ｔから抽出する。匿名化部２２７−ｔは、秘匿化属性値μt(r,n(j,1)),...,μt(r,n(j,m(j)))に対し、秘密計算による匿名化処理を行い、属性値ν(r,n(j,1)),...,ν(r,n(j,m(j)))を匿名化して得られる匿名化属性値v(r,n(j,1)),...,v(r,n(j,m(j)))の秘匿化値である秘匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))を生成する。以下に匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))の生成方法を例示する。
【００４５】
[匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))の生成方法の例]
匿名化部２２７−ｔは、各属性ATT(n’)(ただしn’∈{n(j,1),...,n(j,m(j))})に対し、一様乱数u(r,n’)(0≦u(r,n’)≦L(n’))の秘密分散値(u t-1(r,n’), u t mod 3(r,n’))を以下のステップＳ１１，Ｓ１２のように生成する。なおL(n’)は属性ATT(n’)の属性値の個数である。
【００４６】
まず匿名化部２２７−ｔ（ただしt∈{1,2,3}）が、log2L(n’)以上の最小の整数をλｔ(n’)とし、例えば「Takashi Nishide, Kazuo Ohta. Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol. PKC2007, 2007.（参考文献７）」の「3.3. Joint Random Bit Sharing」に記載された方法で、r(ただしr∈{1,...,R})及びn’(ただしn’∈{n(j,1),...,n(j,m(j))})のそれぞれについて、λｔ(n’)個の１ビットの一様乱数値の秘密分散値uｔ-1(r,n’,f)(ただしf∈{1,...,λｔ(n’)})を生成し、さらに以下に示すλｔ-1(n’)ビットの符号無整数uｔ-1(r,n’)を生成する。
【数３】
0005758315.tif 000008
なお、符号無整数uｔ-1(r,n’)（ただしt∈{1,2,3}）は秘密分散値であり、一様乱数u(r,n’)は匿名化部２２７−１，２，３でそれぞれ生成されるu0(r,n’)，u1(r,n’)，u2(r,n’)に対して、u(r,n’)=u0(r,n’)+u1(r,n’)+u2(r,n’) mod pを満たす。また、一様乱数値の代わりにハッシュ値などが用いられてもよい（ステップＳ１１）。
【００４７】
次に匿名化部２２７−ｔは、u(r,n’)＜L(n’)の比較を行ってその比較結果を出力する比較演算を符号無整数uｔ(r,n’)を用いた秘密計算によって行い、比較結果の秘密分散値CLｔ(r,n’)を出力する。匿名化部２２７−ｔは、他の匿名化部２２７−ｔ’（t’≠t, t’∈{1,2,3}）から秘密分散値CLｔ’(r,n’)を取得して比較結果を復元する。ここでu(r,n’)＜L(n’)を満たさない旨の比較結果が得られた場合、ステップＳ１１の処理に戻る。一方、u(r,n’)＜L(n’)を満たす旨の比較結果が得られた場合、匿名化部２２７−１は生成した符号無整数u0(r,n’)を匿名化部２２７−３に送り、匿名化部２２７−２は生成した符号無整数u1(r,n’)を匿名化部２２７−１に送り、匿名化部２２７−３は生成した符号無整数u2(r,n’)を匿名化部２２７−２に送る。これにより、各匿名化部２２７−ｔは、一様乱数値u(r,n’)=u0(r,n’)+u1(r,n’)+u2(r,n’) mod pの秘密分散値(ut-1(r,n’), ut mod 3(r,n’))を得る。なお、uｔ-1(r,n’)は加法的秘密分散の秘密分散値であるため、u(r,n’)＜L(n’)の比較を行ってその比較結果を出力する比較演算を加算及び乗算によって構成できれば、その秘密計算も可能である。g＜hの比較を行ってその比較結果zを出力する比較演算を加算及び乗算によって構成する方法については後述する（ステップＳ１２）。
【００４８】
次に匿名化部２２７−ｔは、r(r∈{1,...,R})及びn’(n’∈{n(j,1),...,n(j,m(j))})のそれぞれについて、0以上p-1以下の一様乱数値upt-1(r,n’)を生成する。匿名化部２２７−１は生成した一様乱数値up0(r,n’)を匿名化部２２７−３に送り、匿名化部２２７−２は生成した一様乱数値up1(r,n’)を匿名化部２２７−１に送り、匿名化部２２７−３は生成した一様乱数値up2(r,n’)を匿名化部２２７−２に送る。これにより、各匿名化部２２７−ｔは、一様乱数値up(r,n’)=up0(r,n’)+up2(r,n’)+up3(r,n’) mod pの秘密分散値(upt-1(r,n’), upt mod 3(r,n’))を得る。なお、一様乱数値の代わりにハッシュ値などが用いられてもよい（ステップＳ１３）。
【００４９】
次に匿名化部２２７−ｔは、秘匿化属性値(υt-1(r,n), υt mod 3(r,n))及び秘密分散値(upt-1(r,n’), upt mod 3(r,n’))，(ut-1(r,n’), ut mod 3(r,n’))を用い、r(ただしr∈{1,...,R})及びn’(n’∈{n(j,1),...,n(j,m(j))})のそれぞれについて、秘密計算によってπ(r,n’)=[IF up(r,n’)＞ρ(n)・p THEN u(r,n’) ELSE ν(r,n’)]を計算し（ただし「・」は乗算演算子）、π(r,n’)の秘密分散値である秘匿化匿名属性値st(r, n’)=(st-1(r,n’), st mod 3(r,n’)) (ただしr’∈{1,...,R}, n’∈{n(j,1),...,n(j,m(j))})を生成して出力する。なお、秘匿化属性値(υt-1(r,n), υt mod 3(r,n))及び秘密分散値(upt-1(r,n’), upt mod 3(r,n’))，(ut-1(r,n’), ut mod 3(r,n’))は加法的秘密分散の秘密分散値であるため、π(r,n’)=[IF up(r,n’)＞ρ(n)・p THEN u(r,n’) ELSE ν(r,n’)]を加算及び乗算によって構成できれば、その秘密計算も可能である。[IF g THEN h ELSE h’]を加算及び乗算によって構成する方法については後述する（ステップＳ１４）。
【００５０】
《g＜hの比較を行ってその比較結果zを出力する比較演算を加算及び乗算によって構成する方法の例示》
真を「1」，偽を「0」とする論理回路のAND素子及びNOT素子から他の任意の論理回路素子が構成できることは周知である。AND素子及びNOT素子は、加算及び乗算によって以下のように構成される。
AND素子は、α，β∈{0,1}を入力とし、α，βの両方が１であるときに１を出力し、そうでないときに0を出力する。よってα・βがAND素子である。
NOT素子は、α∈{0,1}を入力とし、αが１であるときに0を出力し、αが0であるときに1を出力する。よって1-αがNOT素子である。
【００５１】
ξビット（ξ≧1）の整数g=Σθ=0ξ-1 2θ・gθ，h=Σθ=0ξ-1 2θ・hθを入力とし、g＜hの比較を行い、g＜hであればz=1を出力し、そうでなければz=0を出力する論理演算子が以下のように構成される。
【００５２】
まず１ビットの大小比較gθ＜hθは、以下の真理値表を持つ論理演算子で演算できる。そのような論理演算子をAND及びNOTを用いて表現すると、例えば、(NOT gθ) AND hθとなる。
【表５】
0005758315.tif 000009
次に１ビット判定gθ=hθは、以下の真理値表を持つ論理演算子で演算できる。そのような論理演算子をAND及びNOTを用いて表現すると、例えば、(NOT (gθ＜hθ)) AND (NOT (hθ＜gθ))やNOT(gθ+hθ-2・gθ・hθ)となる。
【表６】
0005758315.tif 000010
【００５３】
CL0=(g0＜h0)及びCLΨ=(gΨ＜hΨ) OR ((gΨ=hΨ) AND CLΨ-1)（ただしΨ∈{1,...,ξ-1}）とし、最初にCL0を計算し、その後Ψ∈{1,...,ξ-1}の小さい方から順番にCLΨを計算し、CLξ-1の計算結果をzとして出力する論理演算子を定義する。この論理演算子は、g＜hの比較を行い、g＜hであればz=1を出力し、そうでなければz=0を出力するものとなる。このような論理演算子はAND素子及びNOT素子から構成され、前述のようにAND素子及びNOT素子は加算及び乗算によって構成される。よって、g＜hの比較を行ってその比較結果zを出力する比較演算が加算及び乗算によって構成される。
【００５４】
《[IF g THEN h ELSE h’]を加算及び乗算によって構成する方法の例示》
g∈{0,1}, h, h’∈{0,...,p-1}を入力とし、g=1ならばhを出力し、g=0ならばh’を出力する論理演算子は、g・h+(1-g)・h’によって構成できる（[匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))の生成方法の例]の説明終わり）。
【００５５】
以上のように生成された秘匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))は、提供情報生成部２２６−ｔに入力される。提供情報生成部２２６−ｔは、秘匿化匿名属性値st(r,n(j,1)),...,st(r,n(j,m(j)))からなる集合SUBt(r,j)={st(r,n(j,1)),...,st(r,n(j,m(j)))}を用い、R個の集合SUBt(1,j),SUBt(2,j),...,SUBt(R,j)に対応する提供情報Dt(n(j,1),...,n(j,m(j)))を生成する。本形態の提供情報生成部２２６−ｔは、R個の集合SUBt(1,j),SUBt(2,j),...,SUBt(R,j)をランダムに並び替えたR個の集合SUBt(q(1),j),SUBt(q(2),j),...,SUBt(q(R),j)(ただしq(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})に対応するR個の集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(ただしq(R),j)(q(r)∈{1,...,R}, {q(1),...,q(R)}={1,...,R})を生成し、当該R個の集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)に対応する提供情報Dt(n(j,1),...,n(j,m(j)))を生成する。以下に提供情報Dt(n(j,1),...,n(j,m(j)))の生成方法を例示する。
【００５６】
まず提供情報生成部２２６−ｔは、例えば参考文献５の2章「2.2.ランダム置換プロトコル」に開示された方法でR個の集合SUBt(1,j),SUBt(2,j),...,SUBt(R,j)をランダム置換してR個の集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)を生成する。この処理では、3個の匿名データ装置２２０−１〜３の提供情報生成部２２６−１〜３間でデータをやり取りし、R個の集合SUBt(1,j),SUBt(2,j),...,SUBt(R,j)の順序を並び替えながらそれらの各要素の加法的秘密分散を再び実行し、R個の集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)(ただしt=1,2,3)が生成される。
【００５７】
［集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)の生成方法の例］
集合SUBt(r,j)={st(r,n(j,1)),...,st(r,n(j,m(j)))}を構成する秘匿化匿名属性値st(r,n’)(n’∈{n(j,1),...,n(j,m(j))})のそれぞれはst(r, n’)=(st-1(r,n’), st mod 3(r,n’))と表現される。また、集合SUBt’(q(r),j)={st’(q(r),n(j,1)),...,st’(q(r),n(j,m(j)))}を構成する要素st’(q(r),n’)(ただしn’∈{n(j,1),...,n(j,m(j))})のそれぞれをst’(q(r), n’)=(st-1’(q(r),n’), st mod 3’(q(r),n’))と表現する。γ∈{1,...,R}をκ∈{1,...,R}に写すランダムな全単射写像：{1,...,R}→{1,...,R}をκ=BIJX(γ)(X=1,2,3)と表現する。全単射写像BIJ1(γ)は、匿名データ装置２２０−１，２に設定されるが匿名データ装置２２０−３に対して秘匿される。全単射写像BIJ2(γ)は、匿名データ装置２２０−２，３に設定されるが匿名データ装置２２０−１に対して秘匿される。全単射写像BIJ3(γ)は、匿名データ装置２２０−1，３に設定されるが匿名データ装置２２０−２に対して秘匿される。これらを前提にして以下の各ステップが実行される。
【００５８】
ステップＳ２１： X=1，Y=2，Z=3，γ=1とする。各r∈{1,...,R}及びn’∈{n(j,1),...,n(j,m(j))}について、a(Z,X)(r,n’)=s0(r,n’)，a(X,Y)(r,n’)=s1(r,n’)，a(Y,Z)(r,n’)=s2(r,n’)とする。
ステップＳ２２：提供情報生成部２２６−Ｘ，Ｙが、κ=BIJX(γ)を求める。
ステップＳ２３：提供情報生成部２２６−Ｘが、各n’∈{n(j,1),...,n(j,m(j))}について乱数b(Z,X)(κ,n’)∈Z/mZを生成し、乱数b(Z,X)(κ,n’)を提供情報生成部２２６−Ｚに送る。
ステップＳ２４：提供情報生成部２２６−Ｙが、各n’∈{n(j,1),...,n(j,m(j))}について乱数b(Y,Z)(κ,n’)∈Z/mZを生成し、乱数b(Y,Z)(κ,n’)を提供情報生成部２２６−Ｚに送る。
ステップＳ２５：提供情報生成部２２６−Ｘが、各n’∈{n(j,1),...,n(j,m(j))}についてθ(n’)=b(Z,X)(κ,n’)-a(Z,X)(γ,n’)を計算し、θ(n’)を提供情報生成部２２６−Ｙに送る。
ステップＳ２６：提供情報生成部２２６−Ｙが、各n’∈{n(j,1),...,n(j,m(j))}についてε(n’)=b(Y,Z)(κ,n’)-a(Y,Z)(γ,n’)を計算し、ε(n’)を提供情報生成部２２６−Ｘに送る。
ステップＳ２７：提供情報生成部２２６−Ｘ，Ｙが、各n’∈{n(j,1),...,n(j,m(j))}についてb(X,Y)(κ,n’)=a(X,Y)(γ,n’)-θ(n’)-ε(n’)を計算する。
ステップＳ２８：提供情報生成部２２６−Ｘが、各n’∈{n(j,1),...,n(j,m(j))}について、乱数b(Z,X)(κ,n’)を新たなa(Z,X)(κ,n’)とし、提供情報生成部２２６−Ｙが乱数b(Y,Z)(κ,n’)を新たなa(Y,Z)(κ,n’)とし、提供情報生成部２２６−Ｘ，Ｙが、各n’∈{n(j,1),...,n(j,m(j))}についてb(X,Y)(κ,n’)を新たなa(X,Y)(κ,n’)とする。
ステップＳ２９：γ＜Rであれば、γ+1を新たなγとしてステップＳ２２に戻る。γ=Rであれば、ステップＳ３０に進む。
ステップＳ３０：X＜3であれば、X+1を新たなXとし、Y=(X mod 3)+1，Z=(X+1 mod 3)+1とし、γ=1とし、ステップＳ２２に進む。X=3であれば、提供情報生成部２２６−ｔ（t∈{1,2,3}）が、各κ=BIJ3(γ)∈{1,...,R}及びn’∈{n(j,1),...,n(j,m(j))}について以下のようにst’(κ, n’)=(st-1’(κ,n’), st mod 3’(κ,n’))を設定する。
s1’(κ, n’)=(s0’(κ,n’), s1’(κ,n’))=(a(Z,X)(κ,n’), a(X,Y)(κ,n’))
s2’(κ, n’)=(s1’(κ,n’), s2’(κ,n’))=(a(X,Y)(κ,n’), a(Y,Z)(κ,n’))
s3’(κ, n’)=(s2’(v,n’), s0’(κ,n’)=(a(Y,Z)(κ,n’), a(Z,X)(κ,n’))
提供情報生成部２２６−ｔは、集合SUBt’(κ,j)={st’(κ,n(j,1)),...,st’(κ,n(j,m(j)))}（κ=BIJ3(γ)∈{1,...,R}）とし、R個の集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)を生成する（［集合SUBt’(q(1),j),SUBt’(q(2),j),...,SUBt’(q(R),j)の生成方法の例］の説明終わり）。
【００５９】
次に例えば提供情報生成部２２６−１が、匿名データ装置２２０−２から集合SUB2’(q(1),j),SUB2’(q(2),j),...,SUB2’(q(R),j)を受け取り、集合SUB1’(q(1),j),SUB1’(q(2),j),...,SUB1’(q(R),j)と集合SUB2’(q(1),j),SUB2’(q(2),j),...,SUB3’(q(R),j)とを用い、加法的秘密分散の復元処理を行って、撹乱レコード群DR(q(1),j),DR(q(2),j),...,DR(q(R),j)を生成して出力する。なお、DR(q(r),j)={DR(q(r),n(j,1)),..., DR(q(r),n(j,m(j)))}であり、DR(q(r),n’)=s0’(q(r),n’)+s1’(q(r),n’)+s2’(q(r),n’) mod p (n’∈{n(j,1),...,n(j,m(j))})を満たす。
【００６０】
次に提供情報生成部２２６−１が、撹乱レコード群DR(q(1),j),DR(q(2),j),...,DR(q(R),j)に対し、属性ATT(n(j,1)),...,ATT(n(j,m(j)))に着目したクロス集計を行って各属性値の組み合わせに対する集計値E(c)(c∈{1,...,MAX})を求め、クロス集計表を作成する。提供情報生成部２２６−１は、さらに参考文献４の3章の「3.3.3 反復ベイズ手法を用いた再構築処理」に記載された反復ベイズ手法を施し、それによって得られた再構築値からなる再構築クロス集計表を生成する。すなわち、提供情報生成部２２６−１は、遷移確率行列A(n(j,1)),...,A(n(j,m(j)))のクロネッカー積A(j)とy→=(E(1),...,E(MAX))とを「Input」として、参考文献４の3章の「Algorithm 1 Reconstruction」を実行し、それによって出力される再構築値x→=(E’(1),...,E’(MAX))の要素E’(1),...,E’(MAX)からなる再構築クロス集計表を生成する。例えば提供情報生成部２２６−１は、ιを1ずつ増加させながらx→ι+1=x→ι・(A(j)・(y→/(x→ι・A))t)tを繰り返し、x→ι+1とx→ιとの距離が閾値以下となった時点でのx→ιをx→とする。ただし、(α)tはαの転置を表す。
【００６１】
さらに提供情報生成部２２６−１は、再構築クロス集計表を表形式のデータベースに変換した擬似データベースを生成し、それを提供情報D(n(j,1),...,n(j,m(j)))として出力する。なお、各セルCELL(c)の再構築値E’(c)(ただしc∈{1,...,MAX})は整数とは限らず、一般に実数である。しかしながら、再構築値E’(c)(ただしc∈{1,...,MAX})の合計値はレコードの総数Rと等しい。このような再構築クロス集計表を表形式のデータベースに変換する方法として前述した参考文献６の方法を用いる場合、提供情報生成部２２６−１は、再構築クロス集計表の各再構築値E’(c)について、当該再構築値E’(c)に対応する属性値の組み合わせからなるレコードを、それぞれ当該再構築値E’(c)の整数部の値ずつ生成する。さらに提供情報生成部２２６−１は、各再構築値E’(c) (ただしc∈{1,...,MAX})の小数部を加算していき、その加算値SUMが１となった時点での再構築値E’(c)に対応する属性値の組み合わせからなるレコードをさらに１個生成し、かつ、加算値SUMから１を減じた値を新たな加算値SUMとしていく処理を、すべての再構築値E’(c) (ただしc∈{1,...,MAX})の小数部の加算が終了するまで実行する（ステップＳ２２３）。提供情報D(n(j,1),...,n(j,m(j)))は出力部１２２−１に入力されて出力される（ステップＳ２２４）。
【００６２】
提供情報D(n(j,1),...,n(j,m(j)))は、ネットワーク等を介して分析装置２３０に送られ、図３Ｃに例示するように、分析装置２３０（図２Ｃ）の入力部１３１に入力され、記憶部１３３に格納される（ステップＳ２３２）。
【００６３】
分析部２１３は、記憶部１３３から提供情報D(n(j,1),...,n(j,m(j)))を抽出し、提供情報D(n(j,1),...,n(j,m(j)))を用いて所望のデータを生成して出力する（ステップＳ２３３）。分析部２１３から出力されたデータは出力部１３２から出力される（ステップＳ２３４）。
【００６４】
なお、ステップＳ１２１，Ｓ２２２〜Ｓ２２４，Ｓ１３１，Ｓ２３２，Ｓ２３３の処理は、すべてのj∈{1,...,J}について実行される。ステップＳ１２１，Ｓ２２２〜Ｓ２２４，Ｓ１３１，Ｓ２３２，Ｓ２３３の処理がそれぞれ１回ずつ実行され、その際に各ステップですべてのj∈{1,...,J}についての処理がまとめて実行されてもよい。或いは、各j∈{1,...,J}についてのステップＳ１２１，Ｓ２２２〜Ｓ２２４，Ｓ１３１，Ｓ２３２，Ｓ２３３の処理がjを更新しながら繰り返されてもよい。また、各j∈{1,...,J}についてのステップＳ１２１，Ｓ２２２〜Ｓ２２４，Ｓ１３１，Ｓ２３２の処理がjを更新しながら繰り返され、すべてのj∈{1,...,J}についてステップＳ１２１，Ｓ２２２〜Ｓ２２４，Ｓ１３１，Ｓ２３２，Ｓ２３３の処理が実行された後、ステップＳ２３３，Ｓ２３４の処理が実行されてもよい。また好ましくは、J≧2であり、j1,j2∈{1,...,J}, j1≠j2について、{n(j1,1),...,n(j1,m(j1))}∩{n(j2,1),...,n(j2,m(j2))}が空集合である。
【００６５】
本形態で匿名化に用いた維持-置換撹乱はk-匿名化などに比べ処理コストが非常に小さく、秘密計算上でも現実的な時間で実行可能である。秘匿された撹乱レコード群は匿名化されているため、復元された値も匿名性が保たれている。そのため、匿名データ装置で擬似データベースを生成したとしても、匿名データ装置に対する匿名性が保たれる。
【００６６】
〔その他の変形例〕
本発明は上述の各実施形態に限定されるものではない。例えば、各実施形態では、各データ提供装置が各rに対応する秘匿化匿名属性値を出力することとしたが、少なくとも一部のデータ提供装置が複数のrに対応する秘匿化匿名属性値を出力してもよい。また、データ提供装置の個数とRとが一致していなくてもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６９】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７１】
各実施形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７２】
１１０，２１０  データ提供装置
１２０，２２０  匿名データ装置
１３０，２３０  分析装置
【図１】
0005758315.tif 000011
【図２】
0005758315.tif 000012
【図３】
0005758315.tif 000013