(57)【要約】  要素に重複があるベクトルと結合対象の行列を、重複がないベクトルとそのベクトルに対応した行列に変換する。行列・キー生成装置は、ベクトル生成部、集合生成部、行列生成部、キー生成部を備える。ベクトル生成部は、ベクトルｘｎをｉ≠ｊのときにｋｎ［ｉ］＝ｋｎ［ｊ］ならばｘｎ［ｉ］≠ｘｎ［ｊ］となるように生成する。集合生成部は、集合Ｂｎ，ｊを集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する。行列生成部は、行列Ｔｎ’をＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する。キー生成部は、ベクトルｋｎ’を行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する。
2016114309.tif 000002
【特許請求の範囲】
【請求項１】
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、Ｍｎを互いに異なるｍｎ個の元からなる集合、Ｍｎ［ｉ］を集合Ｍｎのｉ番目の元とし、
ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素であり、
行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を入力とし、
ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり、各要素が集合Ｍｎの元であるベクトルｘｎを、ｉ≠ｊのときにｋｎ［ｉ］＝ｋｎ［ｊ］ならばｘｎ［ｉ］≠ｘｎ［ｊ］となるように生成するベクトル生成部と、
ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成部と、
ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する行列生成部と、
ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成するキー生成部と
を備える行列・キー生成装置。
【請求項２】
請求項１記載の行列・キー生成装置であって、
Ｍｎ［ｉ］＝ｉであり、
ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新するソート部
も備え、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソート部が更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行い、
前記ベクトル生成部は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｘｎを、ｘｎ［ｉ］＝１とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝ｘｎ［ｉ−１］＋１、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝１のように生成する
ことを特徴とする行列・キー生成装置。
【請求項３】
ネットワークで接続された３つ以上の行列・キー生成装置で秘匿計算を行う行列・キー生成システムを構成する行列・キー生成装置であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、Ｍｎを１，…，ｍｎを元とする集合、‖‖を秘匿化されたデータであることを示す記号とし、
ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素であり、
行列Ｔｎの行と列の数、ベクトルｋｎの要素の数、値ｍｎは秘匿化されていない情報であり、
行列Ｔｎの要素のそれぞれ、ベクトルｋｎの要素のそれぞれは前記行列・キー生成装置の間で秘匿化されており、
当該行列・キー生成装置は、ソート部、ベクトル生成部、集合生成部、行列生成部、キー生成部を備え、
前記ソート部は、他の行列・キー生成装置のソート部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新し、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソート部が更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行うものであり、
前記ベクトル生成部は、他の行列・キー生成装置のベクトル生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり要素のそれぞれを秘匿化したベクトルｘｎを、ｘｎ［１］＝‖１‖とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖ｘｎ［ｉ−１］＋１‖、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖１‖のように生成し、
前記集合生成部は、他の行列・キー生成装置の集合生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成し、
前記行列生成部は、他の行列・キー生成装置の行列生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成し、
前記キー生成部は、他の行列・キー生成装置のキー生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する
ことを特徴とする行列・キー生成装置。
【請求項４】
ネットワークで接続された３つ以上の行列結合装置で秘匿計算を行う行列結合システムを構成する行列結合装置であって、
当該行列結合装置は、
請求項３記載の行列・キー生成装置と結合部を備えており、
前記結合部は、他の行列結合装置の結合部との秘匿計算によって、ベクトルｋ０’，…，ｋＮ−１’のすべてに共通する要素がある場合は、共通する要素ごとに対応する行列Ｔ０’，…，ＴＮ−１’の行を結合して１つの行とし、要素のそれぞれを秘匿化した行列を生成する
ことを特徴とする行列結合装置。
【請求項５】
請求項３記載の行列・キー生成装置を３つ以上有する行列・キー生成システム。
【請求項６】
ベクトル生成部、集合生成部、行列生成部、キー生成部を備える行列・キー生成装置に処理を実行させる行列・キー生成方法であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、Ｍｎを互いに異なるｍｎ個の元からなる集合、Ｍｎ［ｉ］を集合Ｍｎのｉ番目の元とし、
ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素であり、
行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を入力とし、
前記ベクトル生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり、各要素が集合Ｍｎの元であるベクトルｘｎを、ｉ≠ｊのときにｋｎ［ｉ］＝ｋｎ［ｊ］ならばｘｎ［ｉ］≠ｘｎ［ｊ］となるように生成するベクトル生成ステップと、
前記集合生成部が、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成ステップと、
前記行列生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する行列生成ステップと、
前記キー生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成するキー生成ステップと
を実行する行列・キー生成方法。
【請求項７】
ネットワークで接続された３つ以上の行列・キー生成装置を有し、行列・キー生成装置間で秘匿計算ができる行列・キー生成システムに処理を実行させる行列・キー生成方法であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、Ｍｎを１，…，ｍｎを元とする集合、‖‖を秘匿化されたデータであることを示す記号とし、
ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素であり、
行列Ｔｎの行と列の数、ベクトルｋｎの要素の数、値ｍｎは秘匿化されていない情報であり、
行列Ｔｎの要素のそれぞれ、ベクトルｋｎの要素のそれぞれは前記行列・キー生成装置の間で秘匿化されており、
それぞれの行列・キー生成装置は、ソート部、ベクトル生成部、集合生成部、行列生成部、キー生成部を備え、
前記ソート部が、他の行列・キー生成装置のソート部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新するソートステップと、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソートステップで更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行うものであり、
それぞれの前記ベクトル生成部が、他の行列・キー生成装置のベクトル生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり要素のそれぞれを秘匿化したベクトルｘｎを、ｘｎ［１］＝‖１‖とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖ｘｎ［ｉ−１］＋１‖、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖１‖のように生成するベクトル生成ステップと、
それぞれの前記集合生成部が、他の行列・キー生成装置の集合生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成ステップと、
それぞれの前記行列生成部が、他の行列・キー生成装置の行列生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する行列生成ステップと、
それぞれの前記キー生成部が、他の行列・キー生成装置のキー生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成するキー生成ステップと
を実行する行列・キー生成方法。
【請求項８】
請求項１から３のいずれかに記載の行列・キー生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、表などの行と列で構成されたデータを処理するための行列・キー生成装置、行列・キー生成システム、行列結合装置、行列・キー生成方法、プログラムに関する。
【背景技術】
【０００２】
非特許文献１には、要素が秘匿化された行列と、その行列の行ごとに対応している秘匿化された要素を持つベクトルに対し、行列の行の順番とベクトルの要素の順番を、秘匿計算によって要素を秘匿化したままで、ベクトルの要素にしたがってソートする技術が示されている。非特許文献２には、同じ要素が出現した回数（重複している個数）をカウントする計算（以下、「階段計算」と呼ぶ）を、要素を秘匿化したままで行い、秘匿化した結果を出力する技術が示されている。図１は階段計算の概要を説明するための図である。なお、‖‖は秘匿化されたことを示す記号である。入力の第１の要素の‖１‖は１回目の出現なので、出力の第１の要素は‖１‖である。入力の第２の要素の‖２‖は１回目の出現なので、出力の第２の要素は‖１‖である。入力の第３の要素の‖２‖は２回目の出現なので、出力の第３の要素は‖２‖である。入力の第６の要素の‖３‖は３回目の出現なので、出力の第６の要素は‖３‖である。このように、階段計算を行うと同じ要素が出現した回数（重複している個数）をカウントし、その結果が出力される。非特許文献３には、要素が秘匿化された複数の行列を、少ない通信量で、それぞれの行列に対応するベクトルの秘匿化された要素に基づいて結合する技術が示されている。非特許文献４には、データを秘匿化する技術（分散処理）、秘匿化されたデータを復元する技術（復元処理）、秘匿化されたデータを秘匿化した状態で加算，乗算，検証（２つの秘匿化したデータが等しいかの検証）を行い、秘匿化された結果を得る技術などが示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Koki Hamada, Dai Ikarashi, Koji Chida, and Katsumi Takahashi, “Oblivious radix sort: An efficient sorting algorithm for practical secure multi-party computation”, IACR Cryptology ePrint Archive, Vol. 2014, p. 121, 2014.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司， “秘匿計算上の集約関数中央値計算アルゴリズム”, In CSS, 2012.
【非特許文献３】濱田浩気, 菊池亮, 五十嵐大, 千田浩司， “秘匿計算上の結合アルゴリズム”,人工知能学会全国大会(第26 回) 論文集, June 2012.
【非特許文献４】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳， “軽量検証可能3 パーティ秘匿関数計算の再考”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献３に示された行列を結合する技術は、結合のキーとなるベクトルの要素に重複がないことを前提にし、少ない通信量で秘匿計算によって行列の結合を実現している。しかし、ベクトルの要素に重複がある場合には利用できないという課題がある。非特許文献３の行列を結合する技術を利用できるようにするためには、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換する必要がある。【０００５】
そこで本発明は、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換する技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
まず、Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数とする。ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素とする。【０００７】
本発明の第１の発明は、秘匿計算に限定し、非特許文献３に示された行列結合と組み合わせることができる技術である。第１の発明では、‖‖を秘匿化されたデータであることを示す記号、Ｍｎを‖１‖，…，‖ｍｎ‖を元とする集合とする。第１の発明の行列・キー生成装置は、ネットワークで接続された３つ以上の行列・キー生成装置で行列・キー生成システムを構成する。行列・キー生成システムは、行列・キー生成装置間でデータ通信を行いながら秘匿計算ができる。また、行列Ｔｎの行と列の数、ベクトルｋｎの要素の数、値ｍｎは秘匿化されていない情報であり、行列Ｔｎの要素のそれぞれ、ベクトルｋｎの要素のそれぞれは行列・キー生成装置の間で秘匿化された情報である。行列・キー生成装置は、ソート部、ベクトル生成部、集合生成部、行列生成部、キー生成部を備える。【０００８】
ソート部は、他の行列・キー生成装置のソート部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新する。ベクトル生成部、集合生成部、行列生成部、キー生成部は、ソート部が更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行う。ベクトル生成部は、他の行列・キー生成装置のベクトル生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり要素のそれぞれを秘匿化したベクトルｘｎを、ｘｎ［１］＝‖１‖とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖ｘｎ［ｉ−１］＋１‖、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖１‖のように生成する。集合生成部は、他の行列・キー生成装置の集合生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する。行列生成部は、他の行列・キー生成装置の行列生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する。キー生成部は、他の行列・キー生成装置のキー生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する。【０００９】
本発明の第２の発明は、秘匿計算は行わないで、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換する技術である。第２の発明では、Ｍｎを互いに異なるｍｎ個の元からなる集合、Ｍｎ［ｉ］を集合Ｍｎのｉ番目の元とする。また、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を入力とする。第２の発明の行列・キー生成装置は、ベクトル生成部、集合生成部、行列生成部、キー生成部を備える。ベクトル生成部は、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり、各要素が集合Ｍｎの元であるベクトルｘｎを、ｉ≠ｊのときにｋｎ［ｉ］＝ｋｎ［ｊ］ならばｘｎ［ｉ］≠ｘｎ［ｊ］となるように生成する。集合生成部は、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する。行列生成部は、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する。キー生成部は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する。
【発明の効果】
【００１０】
本発明の行列・キー生成システム、行列・キー生成装置によれば、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換することができる。
【図面の簡単な説明】
【００１１】
【図１】階段計算の概要を説明するための図。
【図２】行列の結合の具体例を示す図。
【図３】実施例１の行列・キー生成システムの構成例を示す図。
【図４】実施例１の行列・キー生成システム、および実施例２の行列・キー生成装置の処理フローを示す図。
【図５】秘匿計算で図２に示した行列Ｔ０の行の順番とベクトルｋ０の要素の順番を、ベクトルｋ０の要素にしたがって対応を維持したままソートした様子を示す図。
【図６】要素が秘匿化された状態の図２に示したベクトルｋ０，ｋ１，ｋ２に対して階段計算を行った結果であるベクトルｘ０，ｘ１，ｘ２を示す図。
【図７】要素が秘匿化された状態の図２に示した行列Ｔ０と行列Ｔ１とを結合する場合の行列Ｔ０’，ベクトルｋ０’と行列Ｔ１’，ベクトルｋ１’の例を示す図。
【図８】実施例１変形例の行列結合システムの構成例を示す図。
【図９】実施例１変形例の行列結合システムの処理フローを示す図。
【図１０】図７に示した行列Ｔ０’と行列Ｔ１’とを結合して得られる行列を示す図。
【図１１】実施例２、実施例２変形例の行列・キー生成装置の構成例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１３】
実施例１の説明では、Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、Ｍｎを１，…，ｍｎを元とする集合、‖‖を秘匿化されたデータであることを示す記号とする。ベクトルｋｎのｊ番目の要素は行列Ｔｎの第ｊ行と対応する要素である。なお、上限数ｍｎは、ベクトルｋｎの要素が実際に重複している数でなくてもよく、重複する可能性がある最大値に設定すればよい。【００１４】
＜行列の結合＞
まず、表を表現する行列とその行列の各行のキーを表現する列ベクトル、および行列の結合について説明する。行列の結合では、ベクトルｋ０，…，ｋＮ−１のすべてに共通する要素がある場合は、共通する要素に対応する行列Ｔ０，…，ＴＮ−１の行を結合して１つの行とする。図２に、行列の結合の具体例を示す。行列Ｔ０，Ｔ１，Ｔ２が結合の対象となる行列である。ベクトルｋ０，ｋ１，ｋ２がキーを示す列ベクトルである。なお、本明細書では、「行列」とは表を表現する形式、「ベクトル」とはキーを表現する形式を意味しているので、行列Ｔｎとベクトルｋｎの各要素は１つの数値に限る必要はなく、数値の組合せ、文字列などでも構わない。【００１５】
ここで、行列Ｔ０と行列Ｔ１との結合を考える。行列Ｔ０のキーを示すベクトルｋ０の１番目と４番目の要素と、行列Ｔ１のキーを示すベクトルｋ１の１番目と２番目の要素が「１」であり、共通している。つまり、行列Ｔ０の第１行と第４行のキー、行列Ｔ１の第１行と第２行のキーが「１」であり、共通している。また、行列Ｔ０の第３行のキー（ベクトルｋ０の３番目の要素）、行列Ｔ１の第３行と第４行のキー（ベクトルｋ１の３番目と４番目の要素）が「３」であり、共通している。したがって、行列Ｔ０と行列Ｔ１とを結合した行列では、行列Ｔ０の第１行と行列Ｔ１の第１行を結合した結果を第１行、行列Ｔ０の第１行と行列Ｔ１の第２行を結合した結果を第２行、行列Ｔ０の第４行と行列Ｔ１の第１行を結合した結果を第３行、行列Ｔ０の第４行と行列Ｔ１の第２行を結合した結果を第４行、行列Ｔ０の第３行と行列Ｔ１の第３行を結合した結果を第５行、行列Ｔ０の第３行と行列Ｔ１の第４行を結合した結果を第６行としている。【００１６】
次に、行列Ｔ０と行列Ｔ１と行列Ｔ２との結合を考える。キーを示しているベクトルｋ０の要素、ベクトルｋ１の要素、ベクトルｋ２の要素が共通するのは、要素が「１」のベクトルｋ０の１番目と４番目の要素、ベクトルｋ１の１番目と２番目の要素、ベクトルｋ２の１番目の要素である。つまり、キーが共通するのは、キーが「１」の行列Ｔ０の第１行と第４行、行列Ｔ１の第１行と第２行、行列Ｔ２の第１行である。したがって、行列Ｔ０と行列Ｔ１と行列Ｔ２とを結合した行列では、行列Ｔ０の第１行と行列Ｔ１の第１行と行列Ｔ２の第１行とを結合した結果を第１行、行列Ｔ０の第１行と行列Ｔ１の第２行と行列Ｔ２の第１行とを結合した結果を第２行、行列Ｔ０の第４行と行列Ｔ１の第１行と行列Ｔ２の第１行とを結合した結果を第３行、行列Ｔ０の第４行と行列Ｔ１の第２行と行列Ｔ２の第１行とを結合した結果を第４行としている。【００１７】
＜構成とアルゴリズム＞
図３に行列・キー生成システムの構成例を、図４に行列・キー生成システムの処理フローを示す。行列・キー生成システムは、ネットワーク８００で接続された３つ以上の行列・キー生成装置１６０を有し、行列・キー生成装置１６０間で秘匿計算ができる。それぞれの行列・キー生成装置１６０は、ソート部１１０、ベクトル生成部１２０、集合生成部１３０、行列生成部１４０、キー生成部１５０、記録部１９０を備える。本実施例では、行列Ｔｎの行と列の数、ベクトルｋｎの要素の数、値ｍｎは秘匿化されていない情報であり、行列Ｔｎの要素のそれぞれ、ベクトルｋｎの要素のそれぞれは行列・キー生成装置１６０の間で秘匿化された情報である。つまり、行列Ｔｎの要素のそれぞれ、ベクトルｋｎの要素のそれぞれの断片が、複数の行列・キー生成装置の記録部１９０に分散されて記録されている。なお、「断片」とは、所定の数の断片が分かれば元の値を復元できるデータであり、非特許文献４では「分散データ」と呼ばれている。【００１８】
ソート部１１０は、他の行列・キー生成装置１６０のソート部１１０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新する（Ｓ１１０）。なお、秘匿計算でソート処理を行う方法については非特許文献１に、具体的に示されている。また、ソートは昇順でも降順でもよい。図５に、秘匿計算で図２に示した行列Ｔ０の行の順番とベクトルｋ０の要素の順番を、ベクトルｋ０の要素にしたがって対応を維持したままソートした様子を示す。この例では、値が小さいキー（ベクトルｋ０の要素）ほど早い順番（上）になっている。ベクトル生成部１２０、集合生成部１３０、行列生成部１４０、キー生成部１５０は、ソート部１１０が更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行う。【００１９】
ベクトル生成部１２０は、他の行列・キー生成装置１６０のベクトル生成部１２０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり要素のそれぞれを秘匿化したベクトルｘｎを、ｘｎ［１］＝‖１‖とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖ｘｎ［ｉ−１］＋１‖、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝‖１‖のように生成する（Ｓ１２０）。この処理は、非特許文献２に示された階段計算と同じである。また、値を秘匿化する技術は非特許文献４などに示されている。図６に、ソート部１１０が、要素が秘匿化された状態の図２に示したベクトルｋ０，ｋ１，ｋ２をソートした後のベクトルｋ０，ｋ１，ｋ２と、ベクトル生成部１２０が、ソート後のベクトルｋ０，ｋ１，ｋ２に対して階段計算を行った結果であるベクトルｘ０，ｘ１，ｘ２を示す。【００２０】
集合生成部１３０は、他の行列・キー生成装置１６０の集合生成部１３０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する（Ｓ１３０）。例えば、組合せを（Ｍ０の元，…，Ｍｎ−１の元，ｘｎ［ｊ］，Ｍｎ＋１の元，…，ＭＮ−１の元）のように作り、１つの元とすればよい。また、組合せから決定的に計算される値（組合せと１対１に対応している値、言い換えると異なる組合せのときには必ず異なる計算値となるように求められた値）を元としてもよい。上記の「組合せに対応」とは、組合せ自体だけでなく、組合せから決定的に計算される値を含むことを示すための表現である。【００２１】
例えば、図６に示したベクトルｋ０、ベクトルｋ１、ベクトルｋ２を用いて集合生成部１３０の処理を説明する。ベクトルｋ０では要素に‖１‖が２つあり、他の要素はそれぞれ１つずつなので、ベクトルｋ０で要素が重複する上限数ｍ０は２である。同様に要素が重複する上限数を調べると、ベクトルｋ１で要素が重複する上限数ｍ１は２、ベクトルｋ２で要素が重複する上限数ｍ２は３である。よって、集合Ｍ０＝｛‖１‖，‖２‖｝、集合Ｍ１＝｛‖１‖，‖２‖｝、集合Ｍ２＝｛‖１‖，‖２‖，‖３‖｝である。まず、行列Ｔ０と行列Ｔ１とを結合する処理の例を示す。ｘ０［１］＝‖１‖、集合Ｍ１＝｛‖１‖，‖２‖｝なので、ｘ０［１］と集合Ｍ１の元の組合せは、（‖１‖，‖１‖）と（‖１‖，‖２‖）となる。よって、集合Ｂ０，１＝｛（‖１‖，‖１‖），（‖１‖，‖２‖）｝となる。また、例えば、ｘ０［２］＝‖２‖、集合Ｍ１＝｛‖１‖，‖２‖｝なので、ｘ０［２］と集合Ｍ１の元の組合せは、（‖２‖，‖１‖）と（‖２‖，‖２‖）であり、集合Ｍ０の元とｘ１［４］の組合せは、（‖１‖，‖２‖）と（‖２‖，‖２‖）である。他の組合せについても同様に行えばよい。行列Ｔ０と行列Ｔ１と行列Ｔ２とを結合する処理の場合は、３つの組合せになる。ｘ０［１］＝‖１‖、集合Ｍ１＝｛‖１‖，‖２‖｝、集合Ｍ２＝｛‖１‖，‖２‖，‖３‖｝なので、ｘ０［１］と集合Ｍ１の元と集合Ｍ２の元の組合せは、（‖１‖，‖１‖，‖１‖），（‖１‖，‖１‖，‖２‖），（‖１‖，‖１‖，‖３‖），（‖１‖，‖２‖，‖１‖），（‖１‖，‖２‖，‖２‖），（‖１‖，‖２‖，‖３‖）となる。よって、集合Ｂ０，１＝｛｛（‖１‖，‖１‖，‖１‖），（‖１‖，‖１‖，‖２‖），（‖１‖，‖１‖，‖３‖），（‖１‖，‖２‖，‖１‖），（‖１‖，‖２‖，‖２‖），（‖１‖，‖２‖，‖３‖）｝｝となる。【００２２】
行列生成部１４０は、他の行列・キー生成装置１６０の行列生成部１４０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する（Ｓ１４０）。図７に要素が秘匿化された状態の図２に示した行列Ｔ０と行列Ｔ１とを結合する場合の行列Ｔ０’，ベクトルｋ０’と行列Ｔ１’，ベクトルｋ１’の例を示す。行列Ｔ０と行列Ｔ１とを結合する処理の場合、集合Ｂ０，１の元の数は２なのでＴ０［１］と同一の行を２行作る。同様に、集合Ｂ０，２，Ｂ０，３，Ｂ０，４，Ｂ０，５の元の数も２なので、それぞれ同じ行を２つずつ作る。したがって、行列Ｔ０’は同じ行が２つずつ存在する１０行の行列になる。また、行列Ｔ１’も同じ行が２つずつ存在する８行の行列になる。【００２３】
キー生成部１５０は、他の行列・キー生成装置１６０のキー生成部１５０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する（Ｓ１５０）。行列Ｔ０’が１０行、行列Ｔ１’が８行なので、ベクトルｋ０’の要素は１０個、ベクトルｋ１’の要素は８個である。Ｔ０’［１］とＴ０’［２］はともにＴ０［１］なので、ｋ０’［１］は（ｋ０［１］，Ｂ０，１の１つの元）、ｋ０’［２］は（ｋ０［１］，Ｂ０，１の別の元）となる。図７ではｋ０’［１］＝（‖１‖，（‖１‖，‖１‖））、ｋ０’［２］＝（‖１‖，（‖１‖，‖２‖））となっている。つまり、行列Ｔ０’のＴ０［１］と同一の行に対応する要素（ｋ０’［１］とｋ０’［２］）がｋ０［１］と集合Ｂ０，１の元との組合せに対応している。さらに、Ｔ０［１］と同一の行が複数あるので、集合Ｂ０，１の元は互いに異なるように選ばれている。【００２４】
なお、キー生成部１５０の説明中の「組合せに対応」も、組合せ自体だけでなく、組合せから決定的に計算される値（組合せと１対１に対応している値）を含むことを示すための表現である。例えば、ｆを組合せから決定的に値を計算する関数として、ｋ０’［１］＝‖ｆ（‖１‖，（‖１‖，‖１‖））‖としてもよい。ただし、ｆは秘匿計算が可能な関数である。【００２５】
図７から分かるように、ベクトルｋ０’にもベクトルｋ１’にも、ベクトル内で要素の重複がない。したがって、実施例１の行列・キー生成装置によれば、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換することができる。【００２６】
［変形例］
図８に行列結合システムの構成例を、図９に行列結合システムの処理フローを示す。行列結合システムは、ネットワーク８００で接続された３つ以上の行列結合装置１００を有し、行列結合装置１００同士の間で秘匿計算ができる。行列結合装置１００は、行列・キー生成装置１６０と結合部１７０を備えている。行列・キー生成装置１６０及び行列・キー生成ステップＳ１６０は、実施例１で説明した内容と同じである。【００２７】
結合部１７０は、他の行列結合装置１００の結合部１７０との秘匿計算によって、ベクトルｋ０’，…，ｋＮ−１’のすべてに共通する要素がある場合は、共通する要素ごとに対応する行列Ｔ０’，…，ＴＮ−１’の行を結合して１つの行とし、要素のそれぞれを秘匿化した行列を生成する（Ｓ１７０）。この処理は、非特許文献３に記載された行列結合の技術を用いればよい。図１０に、図７に示した行列Ｔ０’と行列Ｔ１’とを結合して得られる行列を示す。図１０に示された行列は、図２に示した行列Ｔ０と行列Ｔ１とを結合した行列の各要素を秘匿化した行列になっていることが分かる。なお、行列Ｔ０’，…，ＴＮ−１’とベクトルｋ０’，…，ｋＮ−１’を求めるまでの処理では、行間の対応関係を知られてしまう可能性があるが、秘匿計算での行列の結合のときに行をランダムに置換すれば、行間の対応関係を分からなくできる。【００２８】
非特許文献３の行列結合の技術は、入力の表のレコード数の総和（行列形式で表現した場合は行数の総和）をＱとすると、通信量がＯ（Ｑ・ｌｏｇＱ）である。本発明の行列・行列結合システムの場合、行数の総和をＱ、重複数の上限をＰとすると、通信量をＯ（ＰＱ・ｌｏｇＱ）にできる。キーに重複がある場合、一般的には処理はＰの２乗のオーダーで増加するが、本発明の場合はＰの１乗のオーダーなので、非特許文献３の通信量を少なくできるという長所を生かすことができる。
【実施例２】
【００２９】
実施例１では秘匿計算の場合を検討したが、本発明の考え方は秘匿計算に限定しなくても利用できる。秘匿計算でなければ複数の行列・キー生成装置を使う必要はない。１台の行列・キー生成装置で、要素に重複があるキーを示すベクトルと結合対象の行列を、要素に重複がないキーを示すベクトルとそのベクトルに対応した行列に変換できる。そこで、実施例２では秘匿化しない場合を説明する。【００３０】
実施例２では、Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋｎを１以上の整数、ｉとｊを整数、ＴｎをＫｎ行の行列、ｋｎを要素の数がＫｎ個のベクトル、Ｔｎ［ｊ］を行列Ｔｎの第ｊ行、ｋｎ［ｊ］をベクトルｋｎのｊ番目の要素、ｍｎをベクトルｋｎの要素が重複する上限数、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を入力とする。また、ＭｎをＭｎ［ｉ］＝ｉであるｍｎ個の元からなる集合とする。【００３１】
図１１に実施例２の行列・キー生成装置の構成例を、図４に実施例２の行列・キー生成装置の処理フローの例を示す。行列・キー生成装置２６０は、ソート部２１０、ベクトル生成部２２０、集合生成部２３０、行列生成部２４０、キー生成部２５０を備える。ソート部２１０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎの行の順番とベクトルｋｎの要素の順番を、ベクトルｋｎの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１を更新する（Ｓ２１０）。ベクトル生成部２２０、集合生成部２３０、行列生成部２４０、キー生成部２５０は、ソート部２１０が更新した行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行う。【００３２】
ベクトル生成部２２０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｘｎを、ｘｎ［ｉ］＝１とし、２≦ｉ≦Ｋｎに対してｋｎ［ｉ−１］＝ｋｎ［ｉ］ならばｘｎ［ｉ］＝ｘｎ［ｉ−１］＋１、ｋｎ［ｉ−１］≠ｋｎ［ｉ］ならばｘｎ［ｉ］＝１のように生成する（Ｓ２２０）。集合生成部２３０は、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋｎのそれぞれに対して、集合Ｂｎ，ｊを、それぞれの元が、集合Ｍｎ以外の集合Ｍ０，…，ＭＮ−１から１つずつ選んだＮ−１個の元とｘｎ［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する（Ｓ２３０）。行列生成部２４０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔｎ’を、ｊ＝１，…，ＫｎのすべてについてＴｎ［ｊ］と同一の行を集合Ｂｎ，ｊの元の数だけ有するように生成する（Ｓ２４０）。キー生成部２５０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋｎ’を、行列Ｔｎ’のＴｎ［ｊ］と同一の行に対応する要素がｋｎ［ｊ］と集合Ｂｎ，ｊの元との組合せに対応し、かつＴｎ［ｊ］と同一の行が複数ある場合は集合Ｂｎ，ｊの元は互いに異なるように生成する（Ｓ２５０）。【００３３】
それぞれの処理は、秘匿計算ではないという点が実施例１と異なるだけなので、図２に示された行列Ｔ０，Ｔ１とベクトルｋ０，ｋ１が入力された場合、出力される行列Ｔ０’，Ｔ１’とベクトルｋ０’，ｋ１’は図７の各要素が秘匿化されていない行列とベクトルになる。したがって、実施例２の行列・キー生成装置によれば、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換することができる。【００３４】
［変形例］
本変形例では、実施例２の上位概念を導く。本変形例では、ソート部２１０を省略し、ベクトル生成部２２０をベクトル生成部２２０’に変更する。また、本変形例では、ＭｎをＭｎ［ｉ］＝ｉの集合に限定しないで、Ｍｎを互いに異なるｍｎ個の元からなる集合、Ｍｎ［ｉ］を集合Ｍｎのｉ番目の元とする。本変形例の行列・キー生成装置の機能構成は図１１、処理フローは図４に示す。本変形例では、ベクトル生成部２２０’、集合生成部２３０、行列生成部２４０、キー生成部２５０は、入力された行列Ｔ０，…，ＴＮ−１とベクトルｋ０，…，ｋＮ−１に対して処理を行う（ソートステップＳ２１０は行わない）。【００３５】
ベクトル生成部２２０’は、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫｎ個であり、各要素が集合Ｍｎの元であるベクトルｘｎを、ｉ≠ｊのときにｋｎ［ｉ］＝ｋｎ［ｊ］ならばｘｎ［ｉ］≠ｘｎ［ｊ］となるように生成する。変形例２のベクトル生成部２２０の処理は、ベクトルｋｎがあらかじめソートされている場合に利用できるベクトル生成部２２０’の処理の条件を満たす１つの処理である。よって、本変形例の発明は、実施例２の発明の上位概念である。【００３６】
このようにベクトルｘｎを生成すれば、集合生成部２３０、行列生成部２４０、キー生成部２５０の処理はソートされているか否かによる違いはないので、本変形例の行列・キー生成装置も、要素に重複があるベクトルと結合対象の行列を、要素に重複がないベクトルとそのベクトルに対応した行列に変換することができる。【００３７】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。【００３８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。【００３９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。【００４０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。【００４１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。【００４２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００４３】
本発明は、コンピュータを利用した統計的なデータの処理や分析に利用することができる。
【符号の説明】
【００４４】
１００  行列結合装置                      １１０，２１０  ソート部
１２０，２２０  ベクトル生成部            １３０，２３０  集合生成部
１４０，２４０  行列生成部                １５０，２５０  キー生成部
１６０，２６０  行列・キー生成装置        １７０  結合部
１９０  記録部                            ８００  ネットワーク
【図１】
2016114309.tif 000003
【図２】
2016114309.tif 000004
【図３】
2016114309.tif 000005
【図４】
2016114309.tif 000006
【図５】
2016114309.tif 000007
【図６】
2016114309.tif 000008
【図７】
2016114309.tif 000009
【図８】
2016114309.tif 000010
【図９】
2016114309.tif 000011
【図１０】
2016114309.tif 000012
【図１１】
2016114309.tif 000013
【手続補正書】
【提出日】平成29年6月7日(2017.6.7)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
キー生成部１５０は、他の行列・キー生成装置１６０のキー生成部１５０との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成する（Ｓ１５０）。行列Ｔ0'が１０行、行列Ｔ1'が８行なので、ベクトルｋ0'の要素は１０個、ベクトルｋ1'の要素は８個である。Ｔ0'［１］とＴ0'［２］はともにＴ0［１］なので、ｋ0'［１］は（ｋ0［１］，Ｂ0,1の１つの元）、ｋ0'［２］は（ｋ0［１］，Ｂ0,1の別の元）となる。図７ではｋ0'［１］＝（‖１‖，（‖１‖，‖１‖））、ｋ0'［２］＝（‖１‖，（‖１‖，‖２‖））となっている。つまり、行列Ｔ0'のＴ0［１］と同一の行に対応する要素がｋ0［１］と集合Ｂ0,1の元との組合せ（ｋ0'［１］とｋ0'［２］）に対応している。さらに、Ｔ0［１］と同一の行が複数あるので、集合Ｂ0,1の元は互いに異なるように選ばれている。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
非特許文献３の行列結合の技術は、入力の表のレコード数の総和（行列形式で表現した場合は行数の総和）をＱとすると、通信量がＯ（Ｑ・ｌｏｇＱ）である。本発明の行列結合システムの場合、行数の総和をＱ、重複数の上限をＰとすると、通信量をＯ（ＰＱ・ｌｏｇＱ）にできる。キーに重複がある場合、一般的には処理はＰの２乗のオーダーで増加するが、本発明の場合はＰの１乗のオーダーなので、非特許文献３の通信量を少なくできるという長所を生かすことができる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
ベクトル生成部２２０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｘnを、ｘn［１］＝１とし、２≦ｉ≦Ｋnに対してｋn［ｉ−１］＝ｋn［ｉ］ならばｘn［ｉ］＝ｘn［ｉ−１］＋１、ｋn［ｉ−１］≠ｋn［ｉ］ならばｘn［ｉ］＝１のように生成する（Ｓ２２０）。集合生成部２３０は、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋnのそれぞれに対して、集合Ｂn,jを、それぞれの元が、集合Ｍn以外の集合Ｍ0，…，ＭN-1から１つずつ選んだＮ−１個の元とｘn［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する（Ｓ２３０）。行列生成部２４０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔn'を、ｊ＝１，…，ＫnのすべてについてＴn［ｊ］と同一の行を集合Ｂn,jの元の数だけ有するように生成する（Ｓ２４０）。キー生成部２５０は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成する（Ｓ２５０）。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
ベクトル生成部２２０'は、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫn個であり、各要素が集合Ｍnの元であるベクトルｘnを、ｉ≠ｊのときにｋn［ｉ］＝ｋn［ｊ］ならばｘn［ｉ］≠ｘn［ｊ］となるように生成する。本変形例のベクトル生成部２２０の処理は、ベクトルｋnがあらかじめソートされている場合に利用できるベクトル生成部２２０'の処理の条件を満たす１つの処理である。よって、本変形例の発明は、実施例２の発明の上位概念である。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋnを１以上の整数、ｉとｊを整数、ＴnをＫn行の行列、ｋnを要素の数がＫn個のベクトル、Ｔn［ｊ］を行列Ｔnの第ｊ行、ｋn［ｊ］をベクトルｋnのｊ番目の要素、ｍnをベクトルｋnの要素が重複する上限数、Ｍnを互いに異なるｍn個の元からなる集合、Ｍn［ｉ］を集合Ｍnのｉ番目の元とし、
ベクトルｋnのｊ番目の要素は行列Ｔnの第ｊ行と対応する要素であり、
行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1を入力とし、
ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫn個であり、各要素が集合Ｍnの元であるベクトルｘnを、ｉ≠ｊのときにｋn［ｉ］＝ｋn［ｊ］ならばｘn［ｉ］≠ｘn［ｊ］となるように生成するベクトル生成部と、
ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋnのそれぞれに対して、集合Ｂn,jを、それぞれの元が、集合Ｍn以外の集合Ｍ0，…，ＭN-1から１つずつ選んだＮ−１個の元とｘn［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成部と、
ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔn'を、ｊ＝１，…，ＫnのすべてについてＴn［ｊ］と同一の行を集合Ｂn,jの元の数だけ有するように生成する行列生成部と、
ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成するキー生成部と
を備える行列・キー生成装置。
【請求項２】
請求項１記載の行列・キー生成装置であって、
Ｍn［ｉ］＝ｉであり、
ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔnの行の順番とベクトルｋnの要素の順番を、ベクトルｋnの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1を更新するソート部
も備え、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソート部が更新した行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1に対して処理を行い、
前記ベクトル生成部は、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｘnを、ｘn［１］＝１とし、２≦ｉ≦Ｋnに対してｋn［ｉ−１］＝ｋn［ｉ］ならばｘn［ｉ］＝ｘn［ｉ−１］＋１、ｋn［ｉ−１］≠ｋn［ｉ］ならばｘn［ｉ］＝１のように生成する
ことを特徴とする行列・キー生成装置。
【請求項３】
ネットワークで接続された３つ以上の行列・キー生成装置で秘匿計算を行う行列・キー生成システムを構成する行列・キー生成装置であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋnを１以上の整数、ｉとｊを整数、ＴnをＫn行の行列、ｋnを要素の数がＫn個のベクトル、Ｔn［ｊ］を行列Ｔnの第ｊ行、ｋn［ｊ］をベクトルｋnのｊ番目の要素、ｍnをベクトルｋnの要素が重複する上限数、Ｍnを１，…，ｍnを元とする集合、‖‖を秘匿化されたデータであることを示す記号とし、
ベクトルｋnのｊ番目の要素は行列Ｔnの第ｊ行と対応する要素であり、
行列Ｔnの行と列の数、ベクトルｋnの要素の数、値ｍnは秘匿化されていない情報であり、
行列Ｔnの要素のそれぞれ、ベクトルｋnの要素のそれぞれは前記行列・キー生成装置の間で秘匿化されており、
当該行列・キー生成装置は、ソート部、ベクトル生成部、集合生成部、行列生成部、キー生成部を備え、
前記ソート部は、他の行列・キー生成装置のソート部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔnの行の順番とベクトルｋnの要素の順番を、ベクトルｋnの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1を更新し、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソート部が更新した行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1に対して処理を行うものであり、
前記ベクトル生成部は、他の行列・キー生成装置のベクトル生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫn個であり要素のそれぞれを秘匿化したベクトルｘnを、ｘn［１］＝‖１‖とし、２≦ｉ≦Ｋnに対してｋn［ｉ−１］＝ｋn［ｉ］ならばｘn［ｉ］＝‖ｘn［ｉ−１］＋１‖、ｋn［ｉ−１］≠ｋn［ｉ］ならばｘn［ｉ］＝‖１‖のように生成し、
前記集合生成部は、他の行列・キー生成装置の集合生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋnのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂn,jを、それぞれの元が、集合Ｍn以外の集合Ｍ0，…，ＭN-1から１つずつ選んだＮ−１個の元とｘn［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成し、
前記行列生成部は、他の行列・キー生成装置の行列生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔn'を、ｊ＝１，…，ＫnのすべてについてＴn［ｊ］と同一の行を集合Ｂn,jの元の数だけ有するように生成し、
前記キー生成部は、他の行列・キー生成装置のキー生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成する
ことを特徴とする行列・キー生成装置。
【請求項４】
ネットワークで接続された３つ以上の行列結合装置で秘匿計算を行う行列結合システムを構成する行列結合装置であって、
当該行列結合装置は、
請求項３記載の行列・キー生成装置と結合部を備えており、
前記結合部は、他の行列結合装置の結合部との秘匿計算によって、ベクトルｋ0'，…，ｋN-1'のすべてに共通する要素がある場合は、共通する要素ごとに対応する行列Ｔ0'，…，ＴN-1'の行を結合して１つの行とし、要素のそれぞれを秘匿化した行列を生成する
ことを特徴とする行列結合装置。
【請求項５】
請求項３記載の行列・キー生成装置を３つ以上有する行列・キー生成システム。
【請求項６】
ベクトル生成部、集合生成部、行列生成部、キー生成部を備える行列・キー生成装置に処理を実行させる行列・キー生成方法であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋnを１以上の整数、ｉとｊを整数、ＴnをＫn行の行列、ｋnを要素の数がＫn個のベクトル、Ｔn［ｊ］を行列Ｔnの第ｊ行、ｋn［ｊ］をベクトルｋnのｊ番目の要素、ｍnをベクトルｋnの要素が重複する上限数、Ｍnを互いに異なるｍn個の元からなる集合、Ｍn［ｉ］を集合Ｍnのｉ番目の元とし、
ベクトルｋnのｊ番目の要素は行列Ｔnの第ｊ行と対応する要素であり、
行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1を入力とし、
前記ベクトル生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫn個であり、各要素が集合Ｍnの元であるベクトルｘnを、ｉ≠ｊのときにｋn［ｉ］＝ｋn［ｊ］ならばｘn［ｉ］≠ｘn［ｊ］となるように生成するベクトル生成ステップと、
前記集合生成部が、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋnのそれぞれに対して、集合Ｂn,jを、それぞれの元が、集合Ｍn以外の集合Ｍ0，…，ＭN-1から１つずつ選んだＮ−１個の元とｘn［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成ステップと、
前記行列生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔn'を、ｊ＝１，…，ＫnのすべてについてＴn［ｊ］と同一の行を集合Ｂn,jの元の数だけ有するように生成する行列生成ステップと、
前記キー生成部が、ｎ＝０，…，Ｎ−１のそれぞれに対して、ベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成するキー生成ステップと
を実行する行列・キー生成方法。
【請求項７】
ネットワークで接続された３つ以上の行列・キー生成装置を有し、行列・キー生成装置間で秘匿計算ができる行列・キー生成システムに処理を実行させる行列・キー生成方法であって、
Ｎを１以上の整数、ｎを０以上Ｎ−１以下の整数、Ｋnを１以上の整数、ｉとｊを整数、ＴnをＫn行の行列、ｋnを要素の数がＫn個のベクトル、Ｔn［ｊ］を行列Ｔnの第ｊ行、ｋn［ｊ］をベクトルｋnのｊ番目の要素、ｍnをベクトルｋnの要素が重複する上限数、Ｍnを１，…，ｍnを元とする集合、‖‖を秘匿化されたデータであることを示す記号とし、
ベクトルｋnのｊ番目の要素は行列Ｔnの第ｊ行と対応する要素であり、
行列Ｔnの行と列の数、ベクトルｋnの要素の数、値ｍnは秘匿化されていない情報であり、
行列Ｔnの要素のそれぞれ、ベクトルｋnの要素のそれぞれは前記行列・キー生成装置の間で秘匿化されており、
それぞれの行列・キー生成装置は、ソート部、ベクトル生成部、集合生成部、行列生成部、キー生成部を備え、
前記ソート部が、他の行列・キー生成装置のソート部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、行列Ｔnの行の順番とベクトルｋnの要素の順番を、ベクトルｋnの要素にしたがって対応を維持したままソートし、ソート後の行列とベクトルで、行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1を更新するソートステップと、
前記ベクトル生成部、前記集合生成部、前記行列生成部、前記キー生成部は、前記ソートステップで更新した行列Ｔ0，…，ＴN-1とベクトルｋ0，…，ｋN-1に対して処理を行うものであり、
それぞれの前記ベクトル生成部が、他の行列・キー生成装置のベクトル生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素の数がＫn個であり要素のそれぞれを秘匿化したベクトルｘnを、ｘn［１］＝‖１‖とし、２≦ｉ≦Ｋnに対してｋn［ｉ−１］＝ｋn［ｉ］ならばｘn［ｉ］＝‖ｘn［ｉ−１］＋１‖、ｋn［ｉ−１］≠ｋn［ｉ］ならばｘn［ｉ］＝‖１‖のように生成するベクトル生成ステップと、
それぞれの前記集合生成部が、他の行列・キー生成装置の集合生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれ、かつｊ＝１，…，Ｋnのそれぞれに対して、元のそれぞれを秘匿化した集合Ｂn,jを、それぞれの元が、集合Ｍn以外の集合Ｍ0，…，ＭN-1から１つずつ選んだＮ−１個の元とｘn［ｊ］の組合せに対応し、すべての組合せ分の元を含むように生成する集合生成ステップと、
それぞれの前記行列生成部が、他の行列・キー生成装置の行列生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化した行列Ｔn'を、ｊ＝１，…，ＫnのすべてについてＴn［ｊ］と同一の行を集合Ｂn,jの元の数だけ有するように生成する行列生成ステップと、
それぞれの前記キー生成部が、他の行列・キー生成装置のキー生成部との秘匿計算によって、ｎ＝０，…，Ｎ−１のそれぞれに対して、要素のそれぞれを秘匿化したベクトルｋn'を、行列Ｔn'のＴn［ｊ］と同一の行に対応する要素がｋn［ｊ］と集合Ｂn,jの元との組合せに対応し、かつＴn［ｊ］と同一の行が複数ある場合は集合Ｂn,jの元は互いに異なるように生成するキー生成ステップと
を実行する行列・キー生成方法。
【請求項８】
請求項１から３のいずれかに記載の行列・キー生成装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2016114309.tif 000014
2016114309.tif 000015
2016114309.tif 000016
2016114309.tif 000017