(57)【要約】【課題】個別情報を秘匿したまま効率よくクロス集計を行うようにする。【解決手段】数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として、数値ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるｉの個数を以下のように求める。１．乱数ｔi，ｒjを生成する。２．Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（ａi）＝Ｅ（Σj=1mｒjａij），Ｅ（ｗ）＝Ｅ（Σj=1mｒjｗj）を計算する。３．Ｅ（ａi），Ｅ（ｗ）から、Ｅ（αi）＝Ｅ（ｔj（ａi−ｗ））を計算する。４．Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化し、順序を撹乱する。５．再暗号化した暗号文を復号し、復号結果が０となるものの個数を求める。【選択図】図７
2008109308.tif 000002
【特許請求の範囲】
【請求項１】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、数値ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計方法であって、
乱数ｔi，ｒj（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（ａi）＝Ｅ（Σj=1mｒjａij），Ｅ（ｗ）＝Ｅ（Σj=1mｒjｗj）を計算するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi），Ｅ（ｗ）から、Ｅ（αi）＝Ｅ（ｔi（ａi−ｗ））を計算するステップと、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化するステップと、
前記再暗号化した暗号文の順序をランダムに入れ替えるステップと、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号するステップと、
復号結果が０となるものの個数を求めるステップと、
を含むことを特徴とする個別情報を秘匿するクロス集計方法。
【請求項２】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計方法であって、
乱数ｔi，ｒj（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（ａi）＝Ｅ（Πj=1mａijｒj），Ｅ（ｗ）＝Ｅ（Πj=1mｗjｒj）を計算するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi），Ｅ（ｗ）から、Ｅ（αi）＝Ｅ（（ａi／ｗ）ｔi）を計算するステップと、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化するステップと、
前記再暗号化した暗号文の順序をランダムに入れ替えるステップと、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号するステップと、
復号結果が１となるものの個数を求めるステップと、
を含むことを特徴とする個別情報を秘匿するクロス集計方法。
【請求項３】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計方法であって、
乱数ｒj（ｊ＝１，…，ｍ）を生成するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（αi）＝Ｅ（Σj=1mｒjａij），ｗ＝Σj=1mｒjｗjを計算するステップと、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化するステップと、
前記再暗号化した暗号文の順序をランダムに入れ替えるステップと、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号するステップと、
前記の復号結果がｗと一致するものの個数をそれぞれ求めるステップと、
を含むことを特徴とする個別情報を秘匿するクロス集計方法。
【請求項４】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計方法であって、
乱数ｒj（ｊ＝１，…，ｍ）を生成するステップと、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（αi）＝Ｅ（Πj=1mａijｒj），ｗ＝Πj=1mｗjｒjを計算するステップと、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化するステップと、
前記再暗号化した暗号文の順序をランダムに入れ替えるステップと、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号するステップと、
前記の復号結果がｗとなるものの個数を求めるステップと、
を含むことを特徴とする個別情報を秘匿するクロス集計方法。
【請求項５】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）のビット毎の暗号文Ｅ（ａijk）入力として（Ｅは暗号化関数、ａijkはａijを２進標記した時の下位ビットｋビットとし、ビット長をｌ（エル）とする）、数値ａijkを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計方法であって、
ｉ＝１，…，ｎ、ｊ＝１，…，ｍ、ｋ＝１，…，ｌについて、ｗjとＥ（ａijk）を入力として、Ｅ（ｂijk）＝Ｅ（ｗjk＋ａijk）（ここで、＋は排他的論理和）を計算するステップと、
ｉ＝１，…，ｎ、ｊ＝１，…，ｍについて、Ｅ（ｂijk）を入力として、Ｅ（ｂij）＝Ｅ（１−（ｂik1∨…∨ｂijl））を計算するステップと、
ｉ＝１，…，ｎについて、Ｅ（ｂij）を入力として、Ｅ（ｂi）＝Ｅ（ｂi1∧…∧ｂim）を計算するステップと、
Ｅ（ｂi）を入力として、Ｅ（ｄ）＝Ｅ（Σi=1nｂi）を計算するステップと、
Ｅ（ｄ）を復号するステップと、
を含むことを特徴とする個別情報を秘匿するクロス集計方法。
【請求項６】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、数値ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計装置であって、
乱数ｔi，ｒj（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（ａi）＝Ｅ（Σj=1mｒjａij），Ｅ（ｗ）＝Ｅ（Σj=1mｒjｗj）を計算する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi），Ｅ（ｗ）から、Ｅ（αi）＝Ｅ（ｔi（ａi−ｗ））を計算する手段と、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化する手段と、
前記再暗号化した暗号文の順序をランダムに入れ替える手段と、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号する手段と、
復号結果が０となるものの個数を求める手段と、
を含むことを特徴とする個別情報を秘匿するクロス集計装置。
【請求項７】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計装置であって、
乱数ｔi，ｒj（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（ａi）＝Ｅ（Πj=1mａijｒj），Ｅ（ｗ）＝Ｅ（Πj=1mｗjｒj）を計算する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi），Ｅ（ｗ）から、Ｅ（αi）＝Ｅ（（ａi／ｗ）ｔi）を計算する手段と、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化する手段と、
前記再暗号化した暗号文の順序をランダムに入れ替える手段と、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号する手段と、
復号結果が１となるものの個数を求める手段と、
を含むことを特徴とする個別情報を秘匿するクロス集計装置。
【請求項８】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として（Ｅは暗号化関数）、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計装置であって、
乱数ｒj（ｊ＝１，…，ｍ）を生成する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（αi）＝Ｅ（Σj=1mｒjａij），ｗ＝Σj=1mｒjｗjを計算する手段と、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化する手段と、
前記再暗号化した暗号文の順序をランダムに入れ替える手段と、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号する手段と、
前記の復号結果がｗと一致するものの個数をそれぞれ求める手段と、
を含むことを特徴とする個別情報を秘匿するクロス集計装置。
【請求項９】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計装置であって、
乱数ｒj（ｊ＝１，…，ｍ）を生成する手段と、
ｉ＝１，…，ｎについて、Ｅ（ａi1），…，Ｅ（ａim）、ｗjから、Ｅ（αi）＝Ｅ（Πj=1mａijｒj），ｗ＝Πj=1mｗjｒjを計算する手段と、
暗号文Ｅ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化する手段と、
前記再暗号化した暗号文の順序をランダムに入れ替える手段と、
前記ランダムに入れ替えられた前記再暗号化した暗号文を復号する手段と、
前記の復号結果がｗとなるものの個数を求める手段と、
を含むことを特徴とする個別情報を秘匿するクロス集計装置。
【請求項１０】
数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）のビット毎の暗号文Ｅ（ａijk）入力として（Ｅは暗号化関数、ａijkはａijを２進標記した時の下位ビットｋビットとし、ビット長をｌ（エル）とする）、数値ａijkを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるクロス集計装置であって、
ｉ＝１，…，ｎ、ｊ＝１，…，ｍ、ｋ＝１，…，ｌについて、ｗjとＥ（ａijk）を入力として、Ｅ（ｂijk）＝Ｅ（ｗjk＋ａijk）（ここで、＋は排他的論理和）を計算する手段と、
ｉ＝１，…，ｎ、ｊ＝１，…，ｍについて、Ｅ（ｂijk）を入力として、Ｅ（ｂij）＝Ｅ（１−（ｂik1∨…∨ｂijl））を計算する手段と、
ｉ＝１，…，ｎについて、Ｅ（ｂij）を入力として、Ｅ（ｂi）＝Ｅ（ｂi1∧…∧ｂim）を計算する手段と、
Ｅ（ｂi）を入力として、Ｅ（ｄ）＝Ｅ（Σi=1nｂi）を計算する手段と、
Ｅ（ｄ）を復号する手段と、
を含むことを特徴とする個別情報を秘匿するクロス集計装置。
【請求項１１】
請求項１乃至５のいずれか１項に記載の個別情報を秘匿するクロス集計方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関するものであり、特に個別情報を秘匿したままクロス集計を行う技術に関する。クロス集計とは複数の項目に注目して集計する方法である。
【背景技術】
【０００２】
消費者情報の活用がマーケティングなどに有効とされる一方で、近年は特に消費者に対するプライバシ保護の配慮が重要なテーマとなっている。これに関連して従来、準同型暗号の性質を利用して、各消費者の属性（年齢、性別など）やアンケート回答といった個別情報を秘匿したまま集計処理可能な方式がいくつか提案されている（例えば、非特許文献１、非特許文献２等）。
【０００３】
しかし、それらは基本的に単純集計を対象としており、アンケートを通じた社会調査などでしばしば用いられるクロス集計に対して適用することは難しい。この問題に対する自明な対応策として、クロス集計における複数の個別情報をあらかじめ組合せて単純集計の問題に置き換える方法が挙げられる。これは例えば「年代」と「性別」という二つの属性（個別情報）を「年代＋性別」という属性の組合せに置き換える方法であり、「年代＝２０代」、「性別＝男性」と属性毎に個別に回答していたものを「年代＋性別＝２０代の男性」という属性の組合せの回答に置き換えることで、「○○代の男性（女性）の利用者が何人いるか？」という問題が、クロス集計ではなく単純集計で十分となる。
【０００４】
しかしこの置き換えによって、今度は「２０代の利用者が何人いるか？」や「男性の利用者が何人いるか？」といった設問に対する集計が既存の準同型暗号利用方式では困難となってしまい、本質的な問題解決にはなっていない。また、全ての個別情報の組合せ、即ち先の例で言えば「年代」、「性別」、「年代＋性別」の３パターンの項目があれば全ての設問パターンが単純集計で十分となるが、個別情報が多くなるにつれ項目数が飛躍的に増大するため、個別情報が多い場合はやはり既存の準同型暗号利用方式では実現が困難であると考えられる。
【０００５】
【非特許文献１】K.Sako：“Generating  Statistical  Information  in  Anonymous  Survey,”IEICE  Trans.Fundamentals.，E79-A，No.4，pp.507-512，Apr.1996.
【非特許文献２】中里純二，藤本賢司，菊池浩明：“個人情報漏洩を防止するWebアンケートのセキュリティ強化”，情処学論，Vol．46，No．8，pp．2068-2077，Aug．2005.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、個別情報を秘匿したまま効率良くクロス集計を行う事が可能な方法及び装置、並びにプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
アンケートを例に説明する。アンケート集約サーバＡ、ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu、ｎ人のアンケート回答者Ｕi（ｉ＝１，…，ｎ）およびその端末Ｔiが存在するとする。また、設問ｊの数はｍ個とする（ｊ＝１，…，ｍ）。
【０００８】
アンケート回答者ｉ（１≦ｉ≦ｎ）は端末Ｔiを用いて、各設問ｊ（ｊ＝１，…，ｍ）に対して、ｋj個の選択肢の中から一つだけ回答を選ぶものとする。これをａijとする。ａijについて、回答者ｉが端末Ｔiを通じて設問ｊに対してｗ（１≦ｗ≦ｋj）番目の選択肢を選んだとき、Ｔiはａij＝ｗとして、準同型暗号関数Ｅを用いてａijの暗号文Ｅ（ａij）を計算する。複数の設問ｊ1，…，ｊm’について、それぞれある選択肢ｗ1，…，ｗm’の組合せｗ1∧…∧ｗm’を選んだ回答者の総数を以下のようにして求める。なお、簡単のためｍ’＝ｍ，ｊu＝ｕとする。
１．全てのＳuが協力して乱数ｔi，ｒj（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成する。このｔi，ｒjは公開とする。
２．ＡはＥ（ａi1），…，Ｅ（ａim）、ｗjを入力し、ｉ＝１，…，ｎについてＥ（ａi）：＝Ｅ（Σj=1mｒjａij），Ｅ（ｗ）：＝Ｅ（Σj=1mｒjｗj）を計算する。ここで、Ｅ（ａi）はＥの準同型性を利用して入力の暗号文を復号することなく計算できる。なお、Ｅ（ａi），Ｅ（ｗ）は、あるＳuが計算してもよく、また、各Ｓuが分担して計算することでもよい。
３．ｉ＝１，…，ｎについて、Ａはステップ２で求めた値Ｅ（ａi）、Ｅ（ｗ）を用いてＥ（αi）：＝Ｅ（ｔi（ａi−ｗ））を計算する。ここでステップ２同様、Ｅ（αi）はＥ（ａi）、Ｅ（ｗ）を復号することなく計算できる。Ｅ（αi）も、あるＳuが代表して、あるいは各Ｓuが分担して計算することでもよい。
４．全てのＳuが協力してＥ（α1），Ｅ（α2），…，Ｅ（αn）を再暗号化して順序を撹乱したｎ個の暗号文
【０００９】
【数１】
2008109308.tif 000003
を求める。ここでφは1からｎまでの整数に対する置換関数である。
５．全てのＳuが協力して
【００１０】
【数２】
2008109308.tif 000004
を復号し、復号結果が０となっているものの個数を求め、その個数を出力する。
【００１１】
ステップ３で、乱数ｔiを用いてａi≠ｗであれば、復号結果αφ（1）はＺ／ｑＺで一様に分散するような操作を加えているため、ステップ５で復号後、０でない値から回答に関する情報を得ることは難しい。また、復号する前にステップ４で撹乱を行っているため、回答者と復号後の値との関係についての情報を得ることも難しい。
【００１２】
なお、ステップ２では、Ｅ（ａi1），…，Ｅ（ａim）、ｗjからＥ（ａi）＝Ｅ（Πj=1mａijｒj），Ｅ（ｗ）＝Ｅ（Πj=1mｗjｒj）を計算し、ステップ３では、Ｅ（ａi），Ｅ（ｗ）からＥ（αi）＝Ｅ（（ａi／ｗ）ｔi）を計算することでもよい。この場合、ステップ５では、復号結果が１となるものの個数を求める。
また、復号サーバＤを別に備えて、ステップ５の復号処理をＤが実施することでもよい。その他の本発明の特徴については、後の実施形態の説明で詳述する。
【発明の効果】
【００１３】
本発明によれば、管理者（集計者）であっても消費者の個別情報が復元できないクロス集計が容易に実現でき、アンケート回答者のプライバシ保護、情報漏えい対策に効果的である。
【００１４】
また、本発明はアンケートへの適用に限らず、例えば各種ウェブサービスのユーザ分析に対するプライバシ保護、情報漏えい対策としても活用できる。即ち、ネットユーザはウェブサイトへのアクセス時に属性情報や趣味嗜好情報等の個別情報をそれぞれ暗号化して当該ウェブサイトに提供し、その後各ウェブサービス事業者は協力して、当該個別情報を復元することなく、クロス集計による統計情報を得ることができるようにする。
【００１５】
更にセンサネットワークにおけるプライバシ保護、情報漏えい対策としての活用も考えられる。即ち、センサが行動履歴や身体情報（体温など）といった人々のプライバシにかかわる個別情報を収集して活用する際、センサと連動したサーバには当該個別情報が暗号化されてから送信されるようにし、複数の管理者が合意したときのみ、当該個別情報を復元することなく、クロス集計による当該個別情報のデータ分析を行うことができるようにする。
【発明を実施するための最良の形態】
【００１６】
以下、本発明のいくつかの実施の形態について図面を用いて詳細に説明する。以下でも、インターネットを通じてアンケートを実施して、アンケート回答内容を秘匿したままクロス集計する場合について説明する。
【００１７】
［第１の実施の形態］
本実施例では、図１に示すように、アンケート集約サーバＡ、ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu、ｎ人のアンケート回答者Ｕi（１≦ｉ≦ｎ）およびＵiの端末Ｔi、および復号サーバＤからなり、Ｓu，Ｔi，Ｄはインターネットを介してＡにアクセスできるものとする。なお、ここではｎ人のアンケート回答者が事前に存在するものと仮定しているが、不特定多数が不定期にＡにアクセスしてアンケートに回答するとしても良い。
【００１８】
図２はアンケート集約サーバＡのブロック図を示し、本アンケート集約サーバＡは乱数計算手段１１０、暗号計算手段１２０、公開鍵保持手段１３０、アンケートファイルＱＦおよび暗号処理プログラムＥＰの保持手段１４０等を具備する。
【００１９】
図３はアンケート集計管理者端末Ｓuのブロック図を示し、本アンケート集計管理者端末Ｓuは乱数生成手段２２０、再暗号化・撹乱手段２３０等を具備する。なお、実際には、これら手段２２０、２３０はすべてのＳuの協力によって機能する。
【００２０】
図４はアンケート回答者端末Ｔiのブロック図を示し、本アンケート数回答者端末Ｔiは乱数生成手段３１０、暗号手段３２０等を具備する。
【００２１】
図５は復号サーバＤのブロック図を示し、本復号サーバＤは暗号鍵対生成手段４１０、復号手段４２０、鍵保持手段４３０等を具備する。
【００２２】
はじめに、復号サーバＤは暗号鍵対生成手段４１０にて準同型暗号の暗号鍵対である公開鍵ｐｋおよび秘密鍵ｓｋを生成し、ｐｋをアンケート集約サーバＡに送信し、ｓｋを安全に保持する。以下に準同型暗号をＰaillier暗号としたときの暗号鍵対の生成手続について一例を示す。
１．大きな素数ｐ，ｑを生成し、ｐ，ｑを秘密鍵ｓｋとする。
２．ｙ＝ｐ×ｑを計算し、ｙを公開鍵ｐｋとする。
【００２３】
次に、アンケート回答の暗号化方法について説明する。各アンケート回答者Ｕiは端末Ｔiを通じてアンケート集約サーバＡにアクセスすると、アンケートファイルＱＦおよび暗号処理プログラムＥＰが端末Ｔiにダウンロードされる。ＥＰには公開鍵ｐｋ（＝ｙ）が含まれている。ＱＦにはｍ個の設問が記載され、各設問ｊ（ｊ＝１，…，ｍ）に対してｋj個の選択肢があり、その中から一つだけ回答を選択できるようになっているものとする。なお、複数の回答を選択できるようにしてもよい。
【００２４】
アンケート回答者Ｕiが設問ｊに対してｗ番目の選択肢を回答として選択したとき、当該端末ＴiはＥＰを実行することで回答ａij＝ｗの暗号文Ｅ（ａij）を計算する。図６にＥがＰaillier暗号である場合における、Ｔiによる暗号化処理フローの一例を示す。
１．回答ａij（ｊ＝１，…，ｍ）を入力する。
２．乱数生成手段３１０は、１以上ｙ未満の整数からなる乱数ｘj（ｊ＝１，…，ｍ）を生成する。
３．暗号化手段３２０は暗号文Ｅ（ａij）＝ｇaij×ｘjy（modｙ2）を計算する。ここでｇ＝ｙ＋１である。
【００２５】
アンケート回答者端末Ｔiは自身が計算したｍ個の暗号文Ｅ（ａij）をアンケート集約サーバＡに送信する。すなわち、ＴiはＥ（ａi，1），…，Ｅ（ａi，m）をＡに送信する。他のアンケート回答者端末においても同様である。
【００２６】
次に、複数の設問ｊ1，…，ｊm’について、それぞれある選択肢ｗ1，…，ｗm’の組合せｗ1∧…∧ｗm’を選んだ回答者の総数を求める方法について説明する。なお、簡単のためｍ’＝ｍ、ｊu＝ｕとする。図7にその処理フローの一例を示す。
１．各アンケート集計管理者端末Ｓuは、乱数生成手段２２０にて１以上ｙ未満の整数からなる乱数ｔi，u，ｒj，u（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）を生成し、それらをアンケート集約サーバＡに送信する。
２．アンケート集約サーバＡは、乱数計算手段１１０にて、ｔi＝Σu=1pｔi，u（modｙ），ｒj＝Σu=1pｒj，u（modｙ）を計算して、それらについて各Ｓuが受信できるようにする。また、ＡはＳuから受信した全ての乱数ｔi，u，ｒj，uも各Ｓuが受信できるようにする。
３．アンケート集約サーバＡは、暗号計算手段１２０にて、各アンケート回答者端末Ｔiから送信されたＥ（ａi，1），…，Ｅ（ａi，m）を用いて、ｉ＝１，…，ｎについてＥ（ａi）＝Ｅ（Σj=1mｒjａij）を計算し、また、Ｅ（ｗ）＝Ｅ（Σj=1mｒjｗj）を計算する。
４．アンケート集約サーバＡは、暗号計算手段１２０にて、ステップ３で生成した暗号文Ｅ（ａi），Ｅ（ｗ）を用いて、ｉ＝１，…，ｎについてＥ（αi）＝Ｅ（ti（ａi−ｗ））を計算する。
【００２７】
なお、アンケート集計管理者端末Ｓuが暗号計算手段を備え、任意のＳuがアンケート集約サーバＡからｗjおよびＥ（ａi，j）を受信してステップ３、４を実行し、計算結果のＥ（αi）をＡに送信することでもよい。また、複数のＳuが分担してステップ３、４を実行し、計算結果のＥ（αi）をＡに送信することでもよい。
【００２８】
５．Ｃi，0＝Ｅ（αi）として、ｕ＝１，…，ｐの順に、アンケート集計管理者端末Ｓuは再暗号化撹乱手段２３０にて以下の処理を行う。
（ａ）ｉ＝１，…，ｎについて、Ｃi，u-1をＡから受信して再暗号化する。再暗号化した結果をＣi，uとする。
（ｂ）１以上ｎ以下の整数に対する置換関数φuを選び、φu（１），φu（２），…，φu（ｎ）の順にＣi，uをＡに送信する。
図８はステップ５の処理イメージを示したものである。
６．アンケート集約サーバＡはＣi，uを復号サーバＤが受信できるようにする。
７．復号サーバＤはアンケート集約サーバＡからアンケート集計管理者端末Ｓpの出力
【００２９】
【数３】
2008109308.tif 000005
を受信し、すなわち
【００３０】
【数４】
2008109308.tif 000006
を受信し、復号手段４２０にてそれら全てを復号し、復号結果
【００３１】
【数５】
2008109308.tif 000007
をアンケート集約サーバＡに送信する。
８．アンケート集約サーバＡは、復号結果が０であるものの個数ｄを求め、ｄを、ｗ1∧…∧ｗmを選んだ回答者の総数として公開する。
【００３２】
以上の手続きにより、アンケート回答者の個別情報ａijについて，アンケート回答者に知られることなく、かつアンケート集計に係わった計算機Ａ，Ｔiの内部で復元されることなく、ａijに対するクロス集計結果を得ることができる。上記の手続きのうちステップ３、７の詳細について以下に示す。
【００３３】
［ステップ３の詳細］
Ｅ（ａij）＝ｇaij×ｘyj（modｙ2）に対して、Ｘ＝Πj=1mＥ（ａij）rjを計算し、Ｅ（ａi）＝Ｘとする。すると
【００３４】
【数６】
2008109308.tif 000008
であるから、Ｅ（ａi）はａi＝Σj=1mｒjａijの暗号文であることが分かる。
Ｅ（ｗ）についても同様の方法で計算できる。
【００３５】
［ステップ７の詳細］
Ｄの復号手順について現明する。ここではａに対してＰaillier暗号を用いた暗号文Ｅ（ａ）＝ｇa×ｘy（modｙ2）の復号について説明する。ここでｒは１以上ｑ未満の整数からなる乱数とし、Ｅ（ａ）はＡ上にあるものとする。
１．ＡからＥ（ａ）を受信し、秘密鍵ｐ，ｑを用いてＸ’＝（Ｅ（ａ）(p-1)(q-1)−１（modｙ））／ｙを計算してそれをＡに送信する。
２．ＡはＸ’を復号結果として公開する。
【００３６】
なお、本実施例の変形例として、次の第２の実施例と同様に閾値準同型暗号を利用し、暗号鍵対生成および復号処理をアンケート集計管理者端末Ｓuが行うようにすることもできる。この場合、復号サーバＤが不要となる。そのかわりにＳuが暗号鍵対生成手段と復号手段を備えて、各Ｓuの協力によって暗号鍵対生成、復号処理が行われることになる。Ｐaillier暗号について、閾値準同型暗号に拡張する方法は例えば非特許文献３に示されている。
【００３７】
【非特許文献３】Ｉ.Damgard  and  M.Koprowski，“Practical  threshold  RSA  signatures  without  a  trusted  dealer,”EUROCRYPT  ’01，LNCS  2045，Springer-Verlag，pp.152-165，2001.
【００３８】
［第２の実施の形態］
本実施例は、暗号応用技術は第１の実施の形態と同様であるが、数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるものである。
【００３９】
本実施例でも、図１に示すように、アンケート集約サーバＡ、ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu、ｎ人のアンケート回答者Ｕi（１≦ｉ≦ｎ）およびＵiの端末Ｔi、および復号サーバＤからなり、Ｓu，Ｔi，Ｄはインターネットを介してＡにアクセスできるものとする。なお、ここではｎ人のアンケート回答者が事前に存在するものと仮定しているが、不特定多数が不定期にＡにアクセスしてアンケートに回答するとしても良い。
【００４０】
アンケート集約サーバＡ、アンケート集計管理者端末Ｓu、アンケート回答者端末Ｔi、復号サーバＤの構成は、第１の実施の形態と同様であるので省略する（図２、図３、図４、図５）。また、暗号鍵対の生成方法、アンケート回答の暗号化方法も第１の実施の形態で示した方法と同様であるため、ここでは説明を省略する。
【００４１】
以下に、複数の設問ｊ1，…，ｊm’について、任意の選択肢ｗ1，…，ｗm’の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim’＝ｗm’）となるような回答者の個数を求める方法について説明する。ここでも、簡単のためｍ’＝ｍ、ｊu＝ｕとする。図９にその処理フローの一例を示す。
１．各アンケート集計管理者端末Ｓuは、乱数生成手段２２０にて１以上ｙ未満の整数からなる乱数ｒj，u（ｊ＝１，…，ｍ）を生成し、それらをアンケート集約サーバＡに送信する。
２．アンケート集約サーバＡは、乱数計算手段１１０にて、ｒj＝Σu=1pｒj，u（modｙ）を計算して、それらについて各Ｓuが受信できるようにする。また、ＡはＳuから受信した全ての乱数ｒj，uも各Ｓuが受信できるようにする。
３．アンケート集約サーバＡは、暗号計算手段１２０にて、各アンケート回答者端末Ｔiから送信されたＥ（ａi，1），…，Ｅ（ａi，m）を用いて、ｉ＝１，…，ｎについてＥ（αi）＝Ｅ（Σj=1mｒjａij）を計算し、また、ｗ＝Σj=1mｒjｗjを計算する。
【００４２】
なお、アンケート集計管理者端末Ｓuが暗号計算手段を備え、任意のＳuがアンケート集約サーバＡからＥ（ａi，j）を受信してステップ３を実行し、計算結果のＥ（αi）をＡに送信することでもよい。また、複数のＳuが分担してステップ３を実行し、計算結果のＥ（αi）をＡに送信することでもよい。
【００４３】
４．Ｃi，0＝Ｅ（αi）として、ｕ＝１，…，ｐの順に、アンケート集計管理者端末Ｓuは再暗号化撹乱手段２３０にて以下の処理を行う（図８）。
（ａ）ｉ＝１，…，ｎについて、Ｃi，u-1をＡから受信して再暗号化する。再暗号化した結果をＣi，uとする。
（ｂ）１以上ｎ以下の整数に対する置換関数φuを選び、φu（１），φu（２），…，φu（ｎ）の順にＣi，uをＡに送信する。
５．アンケート集約サーバＡはＣi，uを復号サーバＤが受信できるようにする。
６．復号サーバＤはアンケート集約サーバＡからアンケート集計管理者端末Ｓpの出力
【００４４】
【数７】
2008109308.tif 000009
を受信し、すなわち
【００４５】
【数８】
2008109308.tif 000010
を受信し、復号手段４２０にてそれら全てを復号し、復号結果
【００４６】
【数９】
2008109308.tif 000011
をアンケート集約サーバＡに送信する。
７．アンケート集約サーバＡは、復号結果がｗと一致するものの個数ｄを求めて公開する。
【００４７】
以上の手続きにより、アンケート回答者の個別情報ａijについて，アンケート回答者に知られることなく、任意のｗ1，…，ｗmの組合せについて（ａij＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めることができる。しかも、Ｅ（αi）の計算は１回でよい。
【００４８】
なお、本実施例の変形例として、次の第３の実施例と同様に閾値準同型暗号を利用し、暗号鍵対生成および復号処理をアンケート集計管理者端末Ｓuが行うようにすることもできる。この場合、復号サーバＤが不要となる。
【００４９】
［第３の実施の形態］
本実施例では、図１０に示すように、アンケート集約サーバＡ，ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu、ｎ人のアンケート回答者Ｕi（１≦ｉ≦ｎ）およびＵiの端末Ｔiからなり、Ｓu，Ｔiはインターネットを介してＡにアクセスできるものとする。ここでもｎ人のアンケート回答者が事前に存在するものと仮定しているが、不特定多数が不定期にＡにアクセスしてアンケートに回答するとしても良い。
【００５０】
図１１はアンケート集計管理者端末Ｓuのブロック図を示し、本アンケート集計管理者端末は暗号鍵対生成手段２１０、乱数生成手段２２０、再暗号化・撹乱手段２３０、復号手段２４０、鍵保持手段２５０を具備している。実際には、手段２１０〜２４０はすべてのＳuの協力によって機能する。
【００５１】
なお、アンケート集約サーバＡ、アンケート回答者端末Ｔiは、先の第１の実施の形態と同様であるので省略する（図２、図４）。
【００５２】
はじめに、各アンケート集計管理者端末Ｍu（ｕ＝１，…，ｐ）の暗号鍵対生成手段２１０が協力して閾値準同型暗号の暗号鍵対を生成する。そして、Ｓuは秘密鍵ｓｋuを鍵保持手段２４０に保持し、Ａは公開鍵ｐｋを公開鍵保持手段１３０に保持する。これにより、全てのｓｋuを用いない限りは、ｐｋにより暗号化された暗号文を復号できない。以下に閾値準同型暗号をＥlＧamal暗号としたときの暗号鍵対の生成手続きについて一例を示す。
１．位数ｑの可換群Ｇについて、Ｇの生成元ｇおよび位数ｑがＡ上で公開されている。
２．各Ｓuは１以上ｑ未満の整数からなる乱数ｓｋuを生成し、その後、
【００５３】
【数１０】
2008109308.tif 000012
を計算して、ｐｋuをＡに送信する。ここでｓｋuはＭuの秘密鍵となる。
３．Ａはｐｋ＝Πu=1pｐｋuを計算し、ｐｋを公開鍵としてｇ，ｑとともに公開する。
【００５４】
上記の方法はｐ人全てのアンケート管理者が協力しない限り復号できないような暗号鍵対を作成するものであるが、いわゆる閾値秘密鍵分散法を利用すれば（例えば、非特許文献４）、ｐ人のうちｐ’（＜ｐ）人のアンケート管理者が協力することで復号できるように拡張することもできる
【非特許文献４】Y.Desmedt  and  Y.Frankel：“Threshold  cryptosystems,”CRYPTO  ’89，LNCS  435，pp.307-315，Springer-Verlag，1990.
【００５５】
次にアンケート回答の暗号化方法について説明する。これは先の第１の実施の形態と基本的に同じである。各アンケート回答者Ｕiは端末Ｔiを通じてアンケート集約サーバＡにアクセスすると、アンケートファイルＱＦおよび暗号処理プログラムＥＰがＴiにダウンロードされる。ＥＰには公開鍵ｐｋが含まれている。ＱＦにはｍ個の設問が記載され、各設問ｊ（ｊ＝１，…，ｍ）に対してｋj個の選択肢があり，その中から一つだけ回答を選択できるようになっているものとする。なお、複数の回答を選択できるようにしてもよい。
【００５６】
アンケート回答者Ｕiが設問ｊに対してｗ番目の選択肢を回答として選択したとき、当該端末ＴiはＥＰを実行することで、回答ａij＝ｗの暗号文Ｅ（ａij）を計算する。図１２にＥがＥlＧamal暗号である場合における、Ｔiによる暗号化処理フローの一例を示す。
１．回答ａij（ｊ＝１，…，ｍ）を入力する。
２．乱数生成手段３１０は、１以上ｑ未満の整数からなる乱数ｘj（ｊ＝１，…，ｍ）を生成する。
３．暗号化手段３２０は暗号文Ｅ（ａij）＝（ｇxj，ａij×ｐｋxj）を計算する。
【００５７】
アンケート回答者端末Ｔiは自身が計算したｍ個の暗号文Ｅ（ａij）をアンケート集約サーバＡに送信する。すなわち、ＴiはＥ（ａi，1），…，Ｅ（ａi，m）をＡに送信する。他のアンケート回答者端末においても同様である。
【００５８】
次に、複数の設問ｊ1，…，ｊm’について、それぞれある選択肢ｗ1，…，ｗm’の組合せｗ1∧…∧ｗm’を選んだ回答者の総数を求める方法について説明する。ここでも、簡単のためｍ′＝ｍ，ju＝ｕとする。図１３にその処理フローの一例を示す。
１．各アンケート集計管理者端末Ｓuは、乱数生成手段２２０にて１以上ｑ未満の整数からなる乱数ｔi,u，ｒj,u（ｉ＝１，…，ｎ，ｊ＝１，…，ｍ）を生成し、それらをアンケート集約サーバＡに送信する。
２．アンケート集約サーバＡは、乱数計算手段１１０にてｔi＝Σu=1pｔi，u（modｑ），ｒj＝Σu=1pｒj，u（modｑ）を計算して、それらを公開する。また、ＡはＳuから受信した全ての乱数も公開する。
３．アンケート集約サーバＡは、暗号計算手段１２０にて、各アンケート回答者端末Ｔiから送信されたＥ（ａi1），…，Ｅ（ａim）を用いて、ｉ＝１，…，ｎについてＥ（ａi）＝Ｅ（Πj=1mａijrj）を計算し、また、Ｅ（ｗ）＝Ｅ（Πj=1mｗjrj）を計算する。
４．アンケート集約サーバＡは、暗号計算手段１２０にて、ステップ３で生成した暗号文Ｅ（ａi），Ｅ（ｗ）を用いて、ｉ＝１，…，ｎについて、Ｅ（αi）＝Ｅ（（ａi/ｗ）ｔi）を計算する。
【００５９】
なお、本実施例でも、アンケート集計管理者端末Ｓuが暗号計算手段を備えて、任意のＳuがアンケート集約サーバＡからｗjおよびＥ（ａi，j）を受信してステップ３、４を実行し、計算結果Ｅ（αi）をＡに送信することでもよい。また、複数のＳuが分担してステップ３、４を実行し、計算結果Ｅ（αi）をＡに送信することでもよい。
【００６０】
５．Ｃｉ，0＝Ｅ（αi）として、ｕ＝１，…，ｐの順に、アンケート集計管理者端末Ｓuは、再暗号化・撹乱手段２３０にて以下の処理を行う（図８）。
（ａ）ｉ＝１，…，ｎについて、Ｃi,u-1をＡから受信して再暗号化する。再暗号化した結果をＣi,uとする。
（ｂ）１以上ｎ以下の整数に対する置換関数φuを選び、φu（１），φu（２），…，φu（ｎ）の順にＣi,uをＡに送信する。
６．アンケート集計管理者端末Ｓpの出力
【００６１】
【数１１】
2008109308.tif 000013
について、全てのアンケート集計管理者端末Ｓuの復号手段２４０が協力して復号処理を行う。復号結果はアンケート集約サーバＡに送信される。
７．アンケート集約サーバＡは、復号結果が１であるものの個数ｄを求め，ｄを，ｗ1∧…∧ｗmを選んだ回答者の総数として公開する。
【００６２】
以上の手続きにより、アンケート回答者の個別情報ａijについて，アンケート回答者に知られることなく、かつアンケート集計に係わった計算機Ａ，Ｔiの内部で復元されることなく，ａijに対するクロス集計結果を得ることができる。上記の手続きのうちステップ３、４、５、６の詳細を以下に示す。
［ステップ３の詳細］
Ｅ（ａij）＝（ｇxj，ａij×ｐｋxj）に対して，Ｘ＝Πj=1m（ｇxj）rj，Ｙ＝Πmj=1（ａij×ｐｋxj）rjを計算し、Ｅ（ａi）＝（Ｘ，Ｙ）とする。すると
【００６３】
【数１２】
2008109308.tif 000014
であるから、Ｅ（ａi）はａi＝Πj=1mａijrjの暗号文であることが分かる。Ｅ（ｗ）についても同様の方法で計算できる。
【００６４】
［ステップ４の詳細］
【００６５】
【数１３】
2008109308.tif 000015
について、Ｘ’＝Ｘti，Ｙ’＝（Ｙ／ｗ）tiを計算し、Ｅ（αi）＝（Ｘ’，Ｙ’）とする。するとステップ３の詳細と同様な議論により、Ｅ（αi）はαi＝（ａi／ｗ）tiの暗号文であることが分かる。
【００６６】
［ステップ５の詳細］
再暗号化の手順について説明する。ここではａに対してＥlＧamal暗号を用いた暗号文Ｅ（ａ）＝（Ｘ，Ｙ）＝（ｇr，ａ×ｐｋr）の再暗号化について説明する。ここでｒは１以上ｑ未満の整数からなる乱数とする。
１．ｇ，ｑ，ｐｋ，（Ｘ，Ｙ）を入力する。
２．１以上ｑ未満の整数からなる乱数ｚを生成する。
３．Ｘ’＝Ｘ×ｇz，Ｙ’＝Ｙ×ｐｋzを計算し、（Ｘ’，Ｙ’）を再暗号化データとして出力する。
【００６７】
いまＸ’＝ｇr+z，Ｙ’＝ａ×ｐｋr+zであるから（Ｘ’，Ｙ’）は（Ｘ，Ｙ）同様ａの暗号文である。このように、平文を変えず、かつ復元することなく、ａの暗号文のデータを変換する処理を再暗号化と呼ぶ。
【００６８】
［ステップ６の詳細］
復号の手順について説明する。ここではａに対してＥlＧamal暗号を用いた暗号文Ｅ（ａ）＝（Ｘ，Ｙ）＝（ｇr，ａ×ｐｋr）の復号について説明する。ここでｒは１以上ｑ未満の整数からなる乱数とし、（Ｘ，Ｙ）はＡ上で公開されているものとする。
１．各ＳuはＡからＸを受信し、秘密鍵ｓｋuを用いて
【００６９】
【数１４】
2008109308.tif 000016
を計算してそれをＡに送信する。
２．ＡはＸ’＝Πu=1pＸu，Ｙ’＝Ｙ／Ｘ’を計算し、Ｙ’を復号結果として公開する。
いま
【００７０】
【数１５】
2008109308.tif 000017
であるから、Ｙ’＝ａとなり上記処理は正しくａを復元できていることが分かる。
【００７１】
なお、本実施例の変形例として、先の第１の実施の形態と同様に復号サーバを備えて、暗号鍵対生成および復号処理を復号サーバが行うようにすることもできる。
【００７２】
［第４の実施の形態］
本実施例は、暗号応用技術は第３の実施の形態と同様であるが、先の第２の実施の形態と同様に、数値ｗj（ｊ＝１，…，ｍ）、および数値ａij（ｉ＝１，…，ｎ）の暗号文Ｅ（ａij）を入力として、任意のｗ1，…，ｗm（１≦ｗj≦ｋj）の組合せについて、ａijを復元することなく（ａi1＝ｗ1）∧…∧（ａim＝ｗm）となるようなｉの個数を求めるものである。
【００７３】
本実施例でも、図１０に示すように、アンケート集約サーバＡ，ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu、ｎ人のアンケート回答者Ｕi（１≦ｉ≦ｎ）およびＵiの端末Ｔiからなり、Ｓu，Ｔiはインターネットを介してＡにアクセスできるものとする。ここでもｎ人のアンケート回答者が事前に存在するものと仮定しているが、不特定多数が不定期にＡにアクセスしてアンケートに回答するとしても良い。
【００７４】
アンケート集約サーバＡ、アンケート集計管理者端末Ｓu、アンケート回答者端末Ｔiの構成は、第３の実施の形態と同様であるので省略する。また、暗号鍵対の生成方法、アンケート回答の暗号化方法も第３の実施の形態で示した方法と同様であるため、ここでは説明を省略する。
【００７５】
以下に、複数の設問ｊ1，…，ｊm’について、任意の選択肢ｗ1，…，ｗm’の組合せについて、ａijを復元することなく（ａj1＝ｗ1）∧…∧（ａjm’＝ｗm’）となるような回答者の個数を求める方法について説明する。ここでも、簡単のためｍ′＝ｍ，ju＝ｕとする。図１４にその処理フローの一例を示す。
１．各アンケート集計管理者端末Ｓuは、乱数生成手段２２０にて１以上ｑ未満の整数からなる乱数ｒj,u（ｊ＝１，…，ｍ）を生成し、それらをアンケート集約サーバＡに送信する。
２．アンケート集約サーバＡは、乱数計算手段１１０にてｒj＝Σu=1pｒj，u（modｑ）を計算して、それらを公開する。また、ＡはＳuから受信した全ての乱数も公開する。
３．アンケート集約サーバＡは、暗号計算手段１２０にて、各アンケート回答者端末Ｔiから送信されたＥ（ａi1），…，Ｅ（ａim）を用いて、ｉ＝１，…，ｎについてＥ（αi）＝Ｅ（Πj=1mａijrj）を計算し、また、ｗ＝Πj=1mｗjrjを計算する。
【００７６】
なお、本実施例でも、アンケート集計管理者端末Ｓuが暗号計算手段を備えて、任意のＳuがアンケート集約サーバＡからＥ（ａi，j）を受信してステップ３を実行し、計算結果Ｅ（αi）をＡに送信することでもよい。また、複数のＳuが分担してステップ３を実行し、計算結果Ｅ（αi）をＡに送信することでもよい。
【００７７】
４．Ｃｉ，0＝Ｅ（αi）として、ｕ＝１，…，ｐの順に、アンケート集計管理者端末Ｓuは、再暗号化・撹乱手段２３０にて以下の処理を行う（図８）。
（ａ）ｉ＝１，…，ｎについて、Ｃi,u-1をＡから受信して再暗号化する。再暗号化した結果をＣi,uとする。
（ｂ）１以上ｎ以下の整数に対する置換関数φuを選び、φu（１），φu（２），…，φu（ｎ）の順にＣi,uをＡに送信する。
５．アンケート集計管理者端末Ｓpの出力
【００７８】
【数１６】
2008109308.tif 000018
について、全てのアンケート集計管理者端末Ｓuの復号手段２４０が協力して復号処理を行う。復号結果はアンケート集約サーバＡに送信される。
６．アンケート集約サーバＡは、復号結果がｗと一致するものの個数を求めて公開する。
【００７９】
なお、本実施例の変形例として、先の第１や第２の実施の形態と同様に復号サーバを備えて、暗号鍵対生成および復号処理を復号サーバが行うようにすることもできる。
【００８０】
［第５の実施の形態］
本実施例は、入力データを秘匿したまま排他的論理等の任意の論理回路演算を行うことが可能な秘匿回路計算（Secure  Circuit  Evaluation；ＳＣＥ）という技術（例えば非特許文献５）を利用するものである。
【００８１】
【非特許文献５】Go  Yamamoto，et  al.：Efficient，Non-optimistic  Secure  Circuit  Evaluation  Based  on  the  ElGamal  Encryption.Proc.of  WISA  2005：pp.328-342，2005.
【００８２】
本実施例でも図１０と同様に、アンケート集約サーバＡ，ｐ人のアンケート集計管理者Ｍu（ｕ＝１，…，ｐ）およびＭuが管理する端末Ｓu，ｎ人のアンケート回答者Ｕi（１≦ｉ≦ｎ）およびＵiの端末Ｔiからなり、Ｓu，Ｔiはインターネットを介してＡにアクセスできるものとする。
【００８３】
はじめに、Ｓu（ｕ＝１，…，ｐ）は協力して閾値準同型暗号の暗号鍵対を生成する。そして、Ｓuは秘匿鍵ｓｋuを保持し、Ａは公開鍵、ｐｋを保持する。これにより、全てのｓｋuを用いない限りは、ｐｋにより暗号化された暗号文を復号できない。本実施例では、閾値準同型暗号を非特許文献５等で用いられている変形ＥlＧamal暗号とする。暗号鍵対の生成手続きは第３の実施の形態で示した方法と同様であるため、ここでは説明を省略する。
【００８４】
次にアンケート回答の暗号化方法について説明する。これは、第１および第３の実施の形態と基本的に同様である。各アンケート回答者Ｕiは端末Ｔiを通じてアンケート集約サーバＡにアクセスすると、アンケートファイルＱＦおよび暗号処理プログラムＥＰが端末Ｔiにダウンロードされる。ＥＰには公開鍵ｐｋが含まれている。ＱＦにはｍ個の設問が記載されている。ここでは、各設問ｊ（ｊ＝１，…，ｍ）に対してｋj個の選択肢があり、その中から一つだけ回答を選択できるようになっているものとする。なお、複数の回答を選択できるようにしてもよい。
【００８５】
アンケート回答者Ｕiが設問ｊに対してｗ番目の選択肢を回答として選択したとき、当該端末ＴiはＥＰを実行することで、回答ａij＝ｗ＝（ｂl-1(ij)…ｂ0(ij)）2の暗号文Ｅ（ｂl-1(ij)），…，Ｅ（ｂ(0ij)）を計算する。ここで（ｂl-1(ij)…ｂ0(ij)）2はｗの２進数表記を意味する。即ち、ｗを２進数表記したときの最下位ビットがｂ0(ij)，下位２番目のビットがｂ1(ij)、最上位ビット（＝下位ｌ（エル）番目のビット）がｂl-1(ij)となる。
【００８６】
図１５にＥが非特許文献５で用いられている変形ＥlＧamal暗号である場合における、Ｔiによる暗号化処理の一例を示す。
１．回答ｂl-1(ij)，…，ｂ0(ij)（ｊ＝１，…，ｍ）を入力する。
２．１以上ｑ未満の整数からなる乱数ｘjk（ｊ＝１，…，ｍ；ｋ＝０，１，…，ｌ−１）を生成する。
３.暗号文
【００８７】
【数１７】
2008109308.tif 000019
を計算する。
【００８８】
アンケート回答者端末Ｔiは自身が計算したｍ×ｌ（エル）個の暗号文Ｅ（ｂk(ij)）をアンケート集約サーバＡに送信する。他のアンケート回答者端末も同様に、それぞれ回答暗号文をＡに送信する。
【００８９】
次に、ＳＣＥ技術を用いて、複数の設問ｊ1，…，ｊm’について、それぞれある選択肢ｗ1＝（ｚl-1(1)…ｚ0(1)）2，…，ｗm’＝（ｚl-1(m’)…ｚ0(m’)）2の組合せｗ1∧…∧ｗｍ’を選んだ回答者の総数を求める方法について説明する。なお、ここでも簡単のためｍ’＝ｍ，ｊu＝ｕとする。図１６にその処理フローの一例を示す。
１．ＡはＥ（ｂk(ij)）について（ｉ＝１，…，ｎ；ｊ＝１，…，ｍ），ｚkj＝０であればそのまま返し、ｚkj＝1であればＥ（１−ｂk(ij)）を計算して返す。返した結果をＥ（ｂ’k(ij)）とする。
２．各ＳuはＡが持つＥ（ｂ’k(ij)）を元に、協力して（ｂ’(ij)）＝Ｅ（１−（ｂ’0(ij)∨…∨ｂ’l-1(ij)）を計算する。
３．各ＳuはＥ（ｂ’(ij)）を元に、協力してＥ（ｂ’(i)）＝Ｅ（ｂ’(i1)∧…∧ｂ’(im)）を計算し、結果をＡに送信する。
４．ＡはＥ（ｂ’(i)）からＥ（ｄ）＝Ｅ（Σi=1nｂ’(i)）を計算する。
５．各Ｓuは協力してＥ（ｄ）の復号処理を行う。復号結果ｄはＡに送信される。
６．Ａは当該復号結果ｄを、ｗ1∧…∧ｗmを選んだ回答者の総数として公開する。
【００９０】
以上の手続きにより、アンケート回答者の個別情報ａijについて、アンケート回答者に知られることなく、かつアンケート集計に係わった計算機Ａ，Ｔiの内部で復元されることなく、ａijに対するクロス集計結果を得ることができる。
【００９１】
上記の手続きについて詳しく説明すると、先ずステップ１，２により、ｉ＝１，…，ｎ；ｊ＝１，…，ｍについて、ａij＝ｗjであればｂ’(ij)＝１、そうでなければｂ’(ij)＝０となることは明らかである。したがってステップ３により、ｉ＝１，…，ｎについて、（ａi1＝ｗ1）∧…∧（ａim＝ｗm）であれば、ｂ’(i)＝１、そうでなければｂ’(i)＝０となる。以上から、ステップ５の復号結果ｄ＝Σi=1nｂ’(i)はｗ1∧…∧ｗmを選んだ回答者の総数であることが分かる。ステップ１，２，３の計算については、例えば非特許文献５の方法をそのまま用いれば良く、ここでは説明を省略する。ステップ４については、全ての暗号文を成分ごとに掛け合わせれば良い。ステップ５について以下に詳細な処理手順を示す。
【００９２】
［ステップ５の詳細］
復号の手順について説明する。ここではａに対して変形ＥlＧamal暗号を用いた暗号文Ｅ（ａ）＝（Ｘ，Ｙ）＝（ｇr，ｐｋa+r）の復号について説明する。ここでｒは１以上ｑ未満の整数からなる乱数とし、（Ｘ，Ｙ）はＡ上で公開されているものとする。
１．各ＳuはＡからＸを受信し、秘密鍵ｓｋuを用いてＸu＝Ｘskuを計算してそれをＡに送信する。
２．ＡはＸ’＝Πu=1pＸu，Ｙ’＝Ｙ／Ｘ’を計算する。このときＹ’＝ｐｋaとなる。
３．Ｙ’からａを求める。例えばｐｋ，ｐｋ2，ｐｋ3，ｐｋ4，…，ｐｋi，…，と順に計算していき、逐次Ｙ’＝ｐｋiかどうか判定し、Ｙ’＝ｐｋiであればｉ＝ａとすれば良い。
【００９３】
以上、実施例では、インターネットを通じてアンケートを実施し、アンケート回答内容を秘匿したままクロス集計する例を説明したが、本発明は、アンケートへの適用に限らず、マーケティングその他、個別情報を秘匿する必要のある種々のクロス集計に適用することができる。
【００９４】
なお、実施例で示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、実施例で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００９５】
【図１】本発明の一実施の形態のシステム構成図。
【図２】アンケート集約サーバのブロック図。
【図３】アンケート集計管理者端末のブロック図。
【図４】アンケート回答者端末のブロック図。
【図５】復号サーバのブロック図。
【図６】アンケート回答の暗号化処理フローの第１の例。
【図７】所定の選択肢の組合せを選んだ回答者の総数を求める処理フローの第１の例。
【図８】再暗号化・撹乱処理の概念図。
【図９】任意の選択肢の組合せを選んだ回答者の個数を求める処理フローの第１の例。
【図１０】本発明の別の実施の形態のシステム構成図。
【図１１】アンケート集計管理者端末の別のブロック図。
【図１２】アンケート回答の暗号化処理フローの第２の例。
【図１３】所定の選択肢の組合せを選んだ回答者の総数を求める処理フローの第２の例。
【図１４】任意の選択肢の組合せを選んだ回答者の個数を求める処理フローの第２の例。
【図１５】アンケート回答の暗号化処理フローの第３の例。
【図１６】所定の選択肢の組合せを選んだ回答者の総数を求める処理フローの第３の例。
【符号の説明】
【００９６】
Ａ    アンケート集約サーバ
Ｓ1〜Ｓp  アンケート集計管理者端末
Ｔ1〜Ｔn  アンケート回答者端末
Ｄ    復号サーバ
【図１】
2008109308.tif 000020
【図２】
2008109308.tif 000021
【図３】
2008109308.tif 000022
【図４】
2008109308.tif 000023
【図５】
2008109308.tif 000024
【図６】
2008109308.tif 000025
【図７】
2008109308.tif 000026
【図８】
2008109308.tif 000027
【図９】
2008109308.tif 000028
【図１０】
2008109308.tif 000029
【図１１】
2008109308.tif 000030
【図１２】
2008109308.tif 000031
【図１３】
2008109308.tif 000032
【図１４】
2008109308.tif 000033
【図１５】
2008109308.tif 000034
【図１６】
2008109308.tif 000035