秘密計算システム、秘密計算方法
【課題】条件式の演算を含む秘匿関数計算を効率よく処理する。
【解決手段】本発明の秘密計算システムは、通信手段で接続された計算装置Ｘと計算装置Ｙを有する。計算装置Ｘはランダム置換部と条件式演算部とを備え、計算装置Ｙは、計算逆変換部を備える。計算装置Ｘのランダム置換部は、秘匿関数計算により、秘匿した入力データをランダム置換して置換入力データを求める。条件式演算部は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める。計算装置Ｙの計算逆変換部は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う。
【解決手段】本発明の秘密計算システムは、通信手段で接続された計算装置Ｘと計算装置Ｙを有する。計算装置Ｘはランダム置換部と条件式演算部とを備え、計算装置Ｙは、計算逆変換部を備える。計算装置Ｘのランダム置換部は、秘匿関数計算により、秘匿した入力データをランダム置換して置換入力データを求める。条件式演算部は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める。計算装置Ｙの計算逆変換部は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、条件式の演算と、計算とを含んだ処理を行う秘密計算システム、秘密計算方法に関する。
【背景技術】
【０００２】
入力データを秘匿したまま計算結果を求める方法として、例えば非特許文献１に記載された方法が知られている。当該方法は、論理回路の入出力ビットを乱数に置き換える操作により、置き換え後の演算の実行者は入出力の値を知ることなく演算結果に対応する乱数を得ることを可能とする。つまり、任意の論理回路演算について入力データを秘匿したまま計算結果を求めることができるため、高い汎用性を持つ。入力データを秘匿したまま計算結果を求める方法は総称して秘匿関数計算（Secure Function Evaluation）と呼ばれる場合がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Andrew Chi-Chih Yao, “How to Generate and Exchange Secrets (Extended Abstract)”, Proc. of FOCS 1986, pp.162-167.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、秘匿関数計算は通常の計算に比べ一般的に膨大な処理時間を必要とする。特に条件式の計算は処理時間が著しく増加する可能性がある。例として、売上商品データ（例えば、Ｍ種類の商品名があり、合計Ｎ個の商品が売れたときに、Ｎ個の売れた商品名を特定するデータ）を秘匿したまま一番売れた商品を求めることを考える。このとき、以下の処理手順が考えられる。
【０００５】
［処理Ａ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）を入力する。なお、ｇｎは、ｎ番目の売上げた商品名のデータであって、販売しているＭ種類の商品名の中の１つを特定するデータである。
２．ｇ１を登録してｃ１＝１とし、ｎ＝２〜Ｎについて、１≦ｋ＜ｎの範囲でｇｋ＝ｇｎが成り立つかを調べ、ｇｋ＝ｇｎが成り立つｋに対してはｃｋに１を加算し、１≦ｋ＜ｎの範囲ですべてのｇｋについてｇｋ≠ｇｎならばｇｎを登録し、ｃｎ＝１とする。
３．最大のｃｎを求め、ｃｎのインデックスｎを出力する（ｎは複数あってもよい）。インデックスｎに対応する商品ｇｎが一番売れた商品である。
【０００６】
上記処理Ａの手続き２について、ｇｎ＝ｇｋとなるｇｋ（１≦ｋ＜ｎ）があるかどうか効率良く判定する方法はいくつか知られている。単純にはｋ＝１から昇順にｇｋ＝ｇｎとなるかどうか判定すれば良いが、この場合、最悪でｎ−１回の判定が必要となる（方法ａ）。しかし、ｇｋを昇順に並べておけばおよそｌｏｇ２ｎ回の判定で済む方法が知られている（方法ｂ）。
【０００７】
しかし方法ｂはおろか、方法ａについても秘匿関数計算への置き換えは自明でないと考えられる。その理由は、方法ａや方法ｂは条件式の真偽の結果に基づき次の計算が決定されるが、当該真偽結果から入力データを推定できる可能性があり（方法ａではｇｋ＝ｇｎが成り立てば真、成り立たなければ偽）、一方で真偽結果を秘匿すると次の計算を決定できない場合があるためである（方法ａではｇｋ＝ｇｎが成り立てばｃｋに１を加算、成りたたなければｃｎ＝１）。
【０００８】
このような問題を回避するためには、単純には下記の処理Ｂのように処理を行えばよい。しかし、この方法の場合、常にｎ−１回の判定を行う必要があり、処理Ａと比べて明らかに効率が悪い。
【０００９】
［処理Ｂ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）を入力する。
２．ｎ＝２〜Ｎ、およびｋ＝１〜Ｎ−１について、
【００１０】
【数１】
【００１１】
を計算する。
３．ｎ＝１〜Ｎについて、
【００１２】
【数２】
【００１３】
を計算する。
４．最大のｃｎを求め、ｃｎのインデックスｎを出力する（ｎは複数あっても良い）。ｎに対応する商品ｇｎを一番売れた商品とする。
【００１４】
上記処理Ｂの計算量はＯ（Ｎ２）となる。別の方法として、売上商品データｇｎをＭ種類の販売商品データ（販売しているＭ種類の商品名の中の１つを特定するデータ）の集合Ｈ＝｛ｈ１，…，ｈＭ｝の要素としたとき、以下のような処理手順も考えられる。
【００１５】
［処理Ｃ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）および販売商品データｈｍ（ｍ＝１，…，Ｍ）を入力する。
２．ｍ＝１〜Ｍ、およびｎ＝１〜Ｎについて、
【００１６】
【数３】
【００１７】
を計算する。
３．ｍ＝１〜Ｍについて、
【００１８】
【数４】
【００１９】
を計算する。
４．最大のｃｍを求め、ｃｍのインデックスｍを出力する（ｍは複数あっても良い）。ｍに対応する商品ｈｍを一番売れた商品とする。
【００２０】
上記処理Ｃは計算量がＯ（ＭＮ）となり、Ｍ＜Ｎであれば処理Ｂと比べ処理時間の短縮が期待できるが、処理Ａと比べ効率が良いとは言えない。このように、条件式を含む演算の場合、秘匿関数計算への置き換えが自明でない処理や、置き換えは可能であっても著しく効率が悪い処理となってしまう。
【００２１】
本発明は、このような状況に鑑みてなされたものであり、条件式の演算を含む秘匿関数計算を効率よく処理することを目的とする。
【課題を解決するための手段】
【００２２】
本発明の秘密計算システムは、通信手段で接続された計算装置Ｘと計算装置Ｙを有する。計算装置Ｘはランダム置換部と条件式演算部とを備え、計算装置Ｙは、計算逆変換部を備える。計算装置Ｘのランダム置換部は、秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求める。条件式演算部は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める。計算装置Ｙの計算逆変換部は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う。
【発明の効果】
【００２３】
本発明の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘは置換条件結果データを知るが、ランダム置換の演算ロジックを秘匿しているので、置換条件結果データの逆像を知ることができない。つまり、計算装置Ｘが置換条件結果データを知っていることは、秘匿性を損ねない。
【図面の簡単な説明】
【００２４】
【図１】本発明の秘密計算システムの構成例を示す図。
【図２】本発明の秘密計算方法の処理フローを示す図。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００２６】
図１に本発明の秘密計算システムの構成例を示す。また、図２に本発明の秘密計算方法の処理フローを示す。秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００２７】
計算装置Ｘ１００のランダム置換部１１０は、秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求める（Ｓ１１０）。なお、演算ロジックを秘匿しているので、計算装置Ｘ１００は、ランダム置換の逆変換は行えない。条件式演算部１２０は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求め、計算装置Ｙ２００に送る（Ｓ１２０）。「あらかじめ定めた条件式」は、求めたい出力データに応じて定めればよく、特定の条件式に限定するものではない。
【００２８】
計算装置Ｙ２００の計算逆変換部２２０は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う（Ｓ２２０）。「あらかじめ定めた計算」は、求めたい出力データに応じて定めればよく、特定の計算に限定する必要はない。
【００２９】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘは置換条件結果データを知るが、ランダム置換の演算ロジックを秘匿しているので、置換条件結果データの逆像を知ることができない。つまり、計算装置Ｘが置換条件結果データを知っていることは、秘匿性を損ねない。
【００３０】
実施例１では、条件式演算部１２０が演算する「条件式」は「あらかじめ定めた条件式」としただけであり限定していない、計算逆変換部２２０が計算する「計算」も「あらかじめ定めた計算」としただけで限定していない。本発明の効果は特定の「条件式」や特定の「計算」に対してのみ得られるものではないので、本実施例ではこれらを限定していない。実施例２以下では、実施例１で示した秘密計算システムの具体例を示していく。
【実施例２】
【００３１】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とする。本実施例の秘密計算システムは、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算システムである。
【００３２】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００３３】
計算装置Ｘ１００のランダム置換部１１０が、Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求める（Ｓ１１０）。
【００３４】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、置換入力データｈｎ’に対する条件式
【００３５】
【数５】
【００３６】
の演算を行い、置換条件結果データｄｍ，ｎを求め、計算装置Ｙ２００に送る（Ｓ１２０）。上記の式が、「あらかじめ定めた条件式」である。
【００３７】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【００３８】
【数６】
【００３９】
を行う（Ｓ２２０）。本実施例の秘密計算システムでは、上記の式が、「あらかじめ定めた計算」である。このような処理により、秘匿した入力データの中に含まれる集合Ｈの各要素の数を求めることができる。
【００４０】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｎを知るが、ランダム置換πｎの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｎの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｎを知っていることは、秘匿性を損ねない。
【００４１】
［変形例］
実施例２では、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求めた。本変形例では、実施例２の秘密計算装置Ｙ２００の処理に別の処理を付加することで、秘密計算システムを、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算システムにする。具体的には、計算逆変換部２２０が、さらに、秘匿計算により、最大値となるｃｍを求め、最大値となるｃｍに対応するｍを求める（Ｓ２２０）。本変形例の秘密計算システムでは、
【００４２】
【数７】
【００４３】
と、最大値となるｃｍに対応するｍを求めることが、「あらかじめ定めた計算」である。
【００４４】
このような処理なので、本変形例は実施例２と同様の効果がある。なお、この処理は、Ｎ個の入力データｇｎの中で最も多いデータｈｍを求める処理なので、「発明が解決しようとする課題」で説明した一番売れた商品を求める処理にそのまま適用できる。
【実施例３】
【００４５】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算システムである。
【００４６】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００４７】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００４８】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００４９】
【数８】
【００５０】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。二進数表記での同じ桁同士の排他的論理和とは、次のような計算である。例えば、Ｘ＝９、Ｙ＝５としたとき、Ｘ、Ｙを二進数表記すると１００１、０１０１となる。そして、同じ桁同士の排他的論理和の結果は、１１００またはそれを十進数表記した１２となる。また、計算装置Ｘ１００は乱数ｒｋを知らないので、この処理によって、計算装置Ｘ１００が置換入力データｈｋ’から２ｖａｋ＋ｂｋを推定できなくなっている。なお、本実施例では、乱数と二進数表記での同じ桁同士の排他的論理和を用いて２ｖａｋ＋ｂｋを推定できなくしたが、他の方法を用いてもよい。
【００５１】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００５２】
【数９】
【００５３】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００５４】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【００５５】
【数１０】
【００５６】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、ｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める（Ｓ２２０）。本実施例では、上記の式とｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、ｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求めることが、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００５７】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｈ，ｋを知るが、ランダム置換の演算ロジック（乱数ｒＫ）を秘匿しているので、置換条件結果データｄｈ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｈ，ｋを知っていることは、秘匿性を損ねない。
【００５８】
例えば、集合Ａ，Ｂは商品カテゴリ、（ｍ，ｎ）はＡ，Ｂをの購入商品とするときに、分析者は、購入商品データを知ることなくバスケット分析を行うことができる。
【実施例４】
【００５９】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムである。つまり、Ａを条件とし、条件ごとにＢのデータをグループ分けする秘密計算システムである。例えば、入力データが［［（０，１），（２，１），（０，３），（０，１），（１，１），（１，４）］］であれば、出力データは［［（０，｛１，３，１｝），（１，｛１，４｝），（２，｛１｝）］］となる。
【００６０】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００６１】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００６２】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００６３】
【数１１】
【００６４】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。なお、本実施例では、乱数と二進数表記での同じ桁同士の排他的論理和を用いてａｋを推定できなくしたが、他の方法を用いてもよい。
【００６５】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００６６】
【数１２】
【００６７】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。なお、集合Ｂが０を要素に含まないのであれば、φの代わりに０を用いてもよい。
【００６８】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００６９】
【数１３】
【００７０】
を行い、Ｍ個の集合Ｇｍを求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００７１】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換の演算ロジック（乱数ｒＫ）を秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【実施例５】
【００７２】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムである。
【００７３】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００７４】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を計算装置Ｘに送信する（Ｓ２１０）。なお、［［πｋ］］の例として、πｋのブール関数の定数を秘匿したデータとする方法がある。
【００７５】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００７６】
【数１４】
【００７７】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。この処理によって、計算装置Ｘ１００は、置換入力データｈｋ’は知っていても（ａｋ，ｂｋ）は知らない状態が維持される。
【００７８】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００７９】
【数１５】
【００８０】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００８１】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００８２】
【数１６】
【００８３】
を行い、Ｍ個の集合Ｇｍを求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００８４】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換πｋの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【実施例６】
【００８５】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算システムである。
【００８６】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００８７】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００８８】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００８９】
【数１７】
【００９０】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。この処理によって、計算装置Ｘ１００は、置換入力データｈｋ’は知っていても（ａｋ，ｂｋ）は知らない状態が維持される。
【００９１】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００９２】
【数１８】
【００９３】
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００９４】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００９５】
【数１９】
【００９６】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００９７】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換πｋの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【００９８】
［変形例］
実施例６では、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの要素数［［ｇｍ］］を求めた。本変形例では、実施例６の秘密計算装置Ｙ２００の処理に別の処理を付加することで、秘密計算システムを、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算システムにする。具体的には、計算逆変換部２２０が、さらに、秘匿計算により、秘匿計算により、最大値となるｇｍを求める（Ｓ２２０）。本変形例の秘密計算システムでは、
【００９９】
【数２０】
【０１００】
と最大値となるｇｍを求めることが、あらかじめ定めた計算である。
【０１０１】
このような処理なので、本変形例は実施例２と同様の効果がある。
【産業上の利用可能性】
【０１０２】
本発明は、入力データを秘匿したまま計算結果を求めるような分析技術に利用することができる。例えば、顧客情報を含んだ商品の販売データのように個々の情報は秘匿しておきながら、何らかの集計データ（一番売れた商品を求める、商品をカテゴリごとにグループ分けするなど）を求める場合に利用できる。
【符号の説明】
【０１０３】
１００ 計算装置Ｘ １１０ ランダム置換部
１２０ 条件式演算部 １８０ 入出力部Ｘ
１９０ 記録部Ｘ ２００ 計算装置Ｙ
２１０ 置換生成部 ２２０ 計算逆変換部
２８０ 入出力部Ｙ ２９０ 記録部Ｙ
【技術分野】
【０００１】
本発明は、条件式の演算と、計算とを含んだ処理を行う秘密計算システム、秘密計算方法に関する。
【背景技術】
【０００２】
入力データを秘匿したまま計算結果を求める方法として、例えば非特許文献１に記載された方法が知られている。当該方法は、論理回路の入出力ビットを乱数に置き換える操作により、置き換え後の演算の実行者は入出力の値を知ることなく演算結果に対応する乱数を得ることを可能とする。つまり、任意の論理回路演算について入力データを秘匿したまま計算結果を求めることができるため、高い汎用性を持つ。入力データを秘匿したまま計算結果を求める方法は総称して秘匿関数計算（Secure Function Evaluation）と呼ばれる場合がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Andrew Chi-Chih Yao, “How to Generate and Exchange Secrets (Extended Abstract)”, Proc. of FOCS 1986, pp.162-167.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、秘匿関数計算は通常の計算に比べ一般的に膨大な処理時間を必要とする。特に条件式の計算は処理時間が著しく増加する可能性がある。例として、売上商品データ（例えば、Ｍ種類の商品名があり、合計Ｎ個の商品が売れたときに、Ｎ個の売れた商品名を特定するデータ）を秘匿したまま一番売れた商品を求めることを考える。このとき、以下の処理手順が考えられる。
【０００５】
［処理Ａ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）を入力する。なお、ｇｎは、ｎ番目の売上げた商品名のデータであって、販売しているＭ種類の商品名の中の１つを特定するデータである。
２．ｇ１を登録してｃ１＝１とし、ｎ＝２〜Ｎについて、１≦ｋ＜ｎの範囲でｇｋ＝ｇｎが成り立つかを調べ、ｇｋ＝ｇｎが成り立つｋに対してはｃｋに１を加算し、１≦ｋ＜ｎの範囲ですべてのｇｋについてｇｋ≠ｇｎならばｇｎを登録し、ｃｎ＝１とする。
３．最大のｃｎを求め、ｃｎのインデックスｎを出力する（ｎは複数あってもよい）。インデックスｎに対応する商品ｇｎが一番売れた商品である。
【０００６】
上記処理Ａの手続き２について、ｇｎ＝ｇｋとなるｇｋ（１≦ｋ＜ｎ）があるかどうか効率良く判定する方法はいくつか知られている。単純にはｋ＝１から昇順にｇｋ＝ｇｎとなるかどうか判定すれば良いが、この場合、最悪でｎ−１回の判定が必要となる（方法ａ）。しかし、ｇｋを昇順に並べておけばおよそｌｏｇ２ｎ回の判定で済む方法が知られている（方法ｂ）。
【０００７】
しかし方法ｂはおろか、方法ａについても秘匿関数計算への置き換えは自明でないと考えられる。その理由は、方法ａや方法ｂは条件式の真偽の結果に基づき次の計算が決定されるが、当該真偽結果から入力データを推定できる可能性があり（方法ａではｇｋ＝ｇｎが成り立てば真、成り立たなければ偽）、一方で真偽結果を秘匿すると次の計算を決定できない場合があるためである（方法ａではｇｋ＝ｇｎが成り立てばｃｋに１を加算、成りたたなければｃｎ＝１）。
【０００８】
このような問題を回避するためには、単純には下記の処理Ｂのように処理を行えばよい。しかし、この方法の場合、常にｎ−１回の判定を行う必要があり、処理Ａと比べて明らかに効率が悪い。
【０００９】
［処理Ｂ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）を入力する。
２．ｎ＝２〜Ｎ、およびｋ＝１〜Ｎ−１について、
【００１０】
【数１】
【００１１】
を計算する。
３．ｎ＝１〜Ｎについて、
【００１２】
【数２】
【００１３】
を計算する。
４．最大のｃｎを求め、ｃｎのインデックスｎを出力する（ｎは複数あっても良い）。ｎに対応する商品ｇｎを一番売れた商品とする。
【００１４】
上記処理Ｂの計算量はＯ（Ｎ２）となる。別の方法として、売上商品データｇｎをＭ種類の販売商品データ（販売しているＭ種類の商品名の中の１つを特定するデータ）の集合Ｈ＝｛ｈ１，…，ｈＭ｝の要素としたとき、以下のような処理手順も考えられる。
【００１５】
［処理Ｃ］
１．Ｎ個の売上商品データｇｎ（ｎ＝１，…，Ｎ）および販売商品データｈｍ（ｍ＝１，…，Ｍ）を入力する。
２．ｍ＝１〜Ｍ、およびｎ＝１〜Ｎについて、
【００１６】
【数３】
【００１７】
を計算する。
３．ｍ＝１〜Ｍについて、
【００１８】
【数４】
【００１９】
を計算する。
４．最大のｃｍを求め、ｃｍのインデックスｍを出力する（ｍは複数あっても良い）。ｍに対応する商品ｈｍを一番売れた商品とする。
【００２０】
上記処理Ｃは計算量がＯ（ＭＮ）となり、Ｍ＜Ｎであれば処理Ｂと比べ処理時間の短縮が期待できるが、処理Ａと比べ効率が良いとは言えない。このように、条件式を含む演算の場合、秘匿関数計算への置き換えが自明でない処理や、置き換えは可能であっても著しく効率が悪い処理となってしまう。
【００２１】
本発明は、このような状況に鑑みてなされたものであり、条件式の演算を含む秘匿関数計算を効率よく処理することを目的とする。
【課題を解決するための手段】
【００２２】
本発明の秘密計算システムは、通信手段で接続された計算装置Ｘと計算装置Ｙを有する。計算装置Ｘはランダム置換部と条件式演算部とを備え、計算装置Ｙは、計算逆変換部を備える。計算装置Ｘのランダム置換部は、秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求める。条件式演算部は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める。計算装置Ｙの計算逆変換部は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う。
【発明の効果】
【００２３】
本発明の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘは置換条件結果データを知るが、ランダム置換の演算ロジックを秘匿しているので、置換条件結果データの逆像を知ることができない。つまり、計算装置Ｘが置換条件結果データを知っていることは、秘匿性を損ねない。
【図面の簡単な説明】
【００２４】
【図１】本発明の秘密計算システムの構成例を示す図。
【図２】本発明の秘密計算方法の処理フローを示す図。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００２６】
図１に本発明の秘密計算システムの構成例を示す。また、図２に本発明の秘密計算方法の処理フローを示す。秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００２７】
計算装置Ｘ１００のランダム置換部１１０は、秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求める（Ｓ１１０）。なお、演算ロジックを秘匿しているので、計算装置Ｘ１００は、ランダム置換の逆変換は行えない。条件式演算部１２０は、置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求め、計算装置Ｙ２００に送る（Ｓ１２０）。「あらかじめ定めた条件式」は、求めたい出力データに応じて定めればよく、特定の条件式に限定するものではない。
【００２８】
計算装置Ｙ２００の計算逆変換部２２０は、秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、ランダム置換の逆変換を行う（Ｓ２２０）。「あらかじめ定めた計算」は、求めたい出力データに応じて定めればよく、特定の計算に限定する必要はない。
【００２９】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘは置換条件結果データを知るが、ランダム置換の演算ロジックを秘匿しているので、置換条件結果データの逆像を知ることができない。つまり、計算装置Ｘが置換条件結果データを知っていることは、秘匿性を損ねない。
【００３０】
実施例１では、条件式演算部１２０が演算する「条件式」は「あらかじめ定めた条件式」としただけであり限定していない、計算逆変換部２２０が計算する「計算」も「あらかじめ定めた計算」としただけで限定していない。本発明の効果は特定の「条件式」や特定の「計算」に対してのみ得られるものではないので、本実施例ではこれらを限定していない。実施例２以下では、実施例１で示した秘密計算システムの具体例を示していく。
【実施例２】
【００３１】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とする。本実施例の秘密計算システムは、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算システムである。
【００３２】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００３３】
計算装置Ｘ１００のランダム置換部１１０が、Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求める（Ｓ１１０）。
【００３４】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、置換入力データｈｎ’に対する条件式
【００３５】
【数５】
【００３６】
の演算を行い、置換条件結果データｄｍ，ｎを求め、計算装置Ｙ２００に送る（Ｓ１２０）。上記の式が、「あらかじめ定めた条件式」である。
【００３７】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【００３８】
【数６】
【００３９】
を行う（Ｓ２２０）。本実施例の秘密計算システムでは、上記の式が、「あらかじめ定めた計算」である。このような処理により、秘匿した入力データの中に含まれる集合Ｈの各要素の数を求めることができる。
【００４０】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｎを知るが、ランダム置換πｎの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｎの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｎを知っていることは、秘匿性を損ねない。
【００４１】
［変形例］
実施例２では、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求めた。本変形例では、実施例２の秘密計算装置Ｙ２００の処理に別の処理を付加することで、秘密計算システムを、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算システムにする。具体的には、計算逆変換部２２０が、さらに、秘匿計算により、最大値となるｃｍを求め、最大値となるｃｍに対応するｍを求める（Ｓ２２０）。本変形例の秘密計算システムでは、
【００４２】
【数７】
【００４３】
と、最大値となるｃｍに対応するｍを求めることが、「あらかじめ定めた計算」である。
【００４４】
このような処理なので、本変形例は実施例２と同様の効果がある。なお、この処理は、Ｎ個の入力データｇｎの中で最も多いデータｈｍを求める処理なので、「発明が解決しようとする課題」で説明した一番売れた商品を求める処理にそのまま適用できる。
【実施例３】
【００４５】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算システムである。
【００４６】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００４７】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００４８】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００４９】
【数８】
【００５０】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。二進数表記での同じ桁同士の排他的論理和とは、次のような計算である。例えば、Ｘ＝９、Ｙ＝５としたとき、Ｘ、Ｙを二進数表記すると１００１、０１０１となる。そして、同じ桁同士の排他的論理和の結果は、１１００またはそれを十進数表記した１２となる。また、計算装置Ｘ１００は乱数ｒｋを知らないので、この処理によって、計算装置Ｘ１００が置換入力データｈｋ’から２ｖａｋ＋ｂｋを推定できなくなっている。なお、本実施例では、乱数と二進数表記での同じ桁同士の排他的論理和を用いて２ｖａｋ＋ｂｋを推定できなくしたが、他の方法を用いてもよい。
【００５１】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００５２】
【数９】
【００５３】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００５４】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【００５５】
【数１０】
【００５６】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、ｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める（Ｓ２２０）。本実施例では、上記の式とｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、ｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求めることが、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００５７】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｈ，ｋを知るが、ランダム置換の演算ロジック（乱数ｒＫ）を秘匿しているので、置換条件結果データｄｈ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｈ，ｋを知っていることは、秘匿性を損ねない。
【００５８】
例えば、集合Ａ，Ｂは商品カテゴリ、（ｍ，ｎ）はＡ，Ｂをの購入商品とするときに、分析者は、購入商品データを知ることなくバスケット分析を行うことができる。
【実施例４】
【００５９】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムである。つまり、Ａを条件とし、条件ごとにＢのデータをグループ分けする秘密計算システムである。例えば、入力データが［［（０，１），（２，１），（０，３），（０，１），（１，１），（１，４）］］であれば、出力データは［［（０，｛１，３，１｝），（１，｛１，４｝），（２，｛１｝）］］となる。
【００６０】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００６１】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００６２】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００６３】
【数１１】
【００６４】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。なお、本実施例では、乱数と二進数表記での同じ桁同士の排他的論理和を用いてａｋを推定できなくしたが、他の方法を用いてもよい。
【００６５】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００６６】
【数１２】
【００６７】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。なお、集合Ｂが０を要素に含まないのであれば、φの代わりに０を用いてもよい。
【００６８】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００６９】
【数１３】
【００７０】
を行い、Ｍ個の集合Ｇｍを求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００７１】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換の演算ロジック（乱数ｒＫ）を秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【実施例５】
【００７２】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムである。
【００７３】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００７４】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を計算装置Ｘに送信する（Ｓ２１０）。なお、［［πｋ］］の例として、πｋのブール関数の定数を秘匿したデータとする方法がある。
【００７５】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００７６】
【数１４】
【００７７】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。この処理によって、計算装置Ｘ１００は、置換入力データｈｋ’は知っていても（ａｋ，ｂｋ）は知らない状態が維持される。
【００７８】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００７９】
【数１５】
【００８０】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００８１】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００８２】
【数１６】
【００８３】
を行い、Ｍ個の集合Ｇｍを求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００８４】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換πｋの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【実施例６】
【００８５】
秘密計算システムの構成を示す図は図１、処理フローを示す図は図２である。本実施例の説明では、［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとする。本実施例の秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算システムである。
【００８６】
本実施例の秘密計算システムは、計算装置Ｘ１００と計算装置Ｙ２００を有し、計算装置Ｘ１００と計算装置Ｙ２００は、ネットワーク１０００（通信手段）で接続されている。計算装置Ｘ１００は、ランダム置換部１１０、条件式演算部１２０、入出力部Ｘ１８０、記録部Ｘ１９０を備える。計算装置Ｙ２００は、置換生成部２１０、計算逆変換部２２０、入出力部Ｙ２８０、記録部Ｙ２９０を備える。入出力部Ｘ１８０は、ネットワーク１０００を介して計算装置Ｙ２００とデータ通信を行う。記録部Ｘ１９０は、計算装置Ｘ１００の処理に必要なデータを記録する。入出力部Ｙ２８０は、ネットワーク１０００を介して計算装置Ｘ１００とデータ通信を行う。記録部Ｙ２９０は、計算装置Ｙ２００の処理に必要なデータを記録する。
【００８７】
計算装置Ｙ２００の置換生成部２１０は、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を計算装置Ｘ１００に送信する（Ｓ２１０）。
【００８８】
計算装置Ｘ１００のランダム置換部１１０は、Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【００８９】
【数１７】
【００９０】
の計算を行って、置換入力データｈｋ’を求める（Ｓ１１０）。この処理によって、計算装置Ｘ１００は、置換入力データｈｋ’は知っていても（ａｋ，ｂｋ）は知らない状態が維持される。
【００９１】
計算装置Ｘ１００の条件式演算部１２０は、ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、置換入力データｈｋ’に対する条件式
【００９２】
【数１８】
【００９３】
の演算を行い、置換条件結果データｄｍ，ｋを求め、計算装置Ｙ２００に送る（Ｓ１２０）。本実施例では、上記の式があらかじめ定めた条件式である。
【００９４】
計算装置Ｙ２００の計算逆変換部２２０は、ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【００９５】
【数１９】
【００９６】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める（Ｓ２２０）。本実施例では、上記の式が、あらかじめ定めた計算である。また、上記の式でＳ１１０が行ったランダム置換を元に戻しているので、計算結果は正しく得られる。
【００９７】
このような構成と処理なので、本実施例の秘密計算システムによれば、条件式の演算を平文で処理できる。したがって、条件式の演算を含む秘匿関数計算を効率よく処理できる。また、計算装置Ｘ１００は置換条件結果データｄｍ，ｋを知るが、ランダム置換πｋの演算ロジックを秘匿しているので、置換条件結果データｄｍ，ｋの逆像を知ることができない。つまり、計算装置Ｘ１００が置換条件結果データｄｍ，ｋを知っていることは、秘匿性を損ねない。
【００９８】
［変形例］
実施例６では、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの要素数［［ｇｍ］］を求めた。本変形例では、実施例６の秘密計算装置Ｙ２００の処理に別の処理を付加することで、秘密計算システムを、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算システムにする。具体的には、計算逆変換部２２０が、さらに、秘匿計算により、秘匿計算により、最大値となるｇｍを求める（Ｓ２２０）。本変形例の秘密計算システムでは、
【００９９】
【数２０】
【０１００】
と最大値となるｇｍを求めることが、あらかじめ定めた計算である。
【０１０１】
このような処理なので、本変形例は実施例２と同様の効果がある。
【産業上の利用可能性】
【０１０２】
本発明は、入力データを秘匿したまま計算結果を求めるような分析技術に利用することができる。例えば、顧客情報を含んだ商品の販売データのように個々の情報は秘匿しておきながら、何らかの集計データ（一番売れた商品を求める、商品をカテゴリごとにグループ分けするなど）を求める場合に利用できる。
【符号の説明】
【０１０３】
１００ 計算装置Ｘ １１０ ランダム置換部
１２０ 条件式演算部 １８０ 入出力部Ｘ
１９０ 記録部Ｘ ２００ 計算装置Ｙ
２１０ 置換生成部 ２２０ 計算逆変換部
２８０ 入出力部Ｙ ２９０ 記録部Ｙ
【特許請求の範囲】
【請求項１】
通信手段で接続された計算装置Ｘと計算装置Ｙを有する秘密計算システムであって、
前記計算装置Ｘは、
秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求めるランダム置換部と、
前記置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める条件式演算部と
を備え、
前記計算装置Ｙは、
秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、前記ランダム置換の逆変換を行う計算逆変換部
を備える
ことを特徴とする秘密計算システム。
【請求項２】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とするときに、
当該秘密計算システムは、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算システムであって、
前記計算装置Ｘの前記ランダム置換部は、
Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、前記置換入力データｈｎ’に対する条件式
【数２１】
の演算を行い、置換条件結果データｄｍ，ｎを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【数２２】
を行う
ことを特徴とする秘密計算システム。
【請求項３】
請求項２記載の秘密計算システムを用いて、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算システムであって、
前記計算装置Ｙの前記計算逆変換部は、
さらに、
秘匿計算により、最大値となるｃｍを求め、前記の最大値となるｃｍに対応するｍを求める
ことを特徴とする秘密計算システム。
【請求項４】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２３】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数２４】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【数２５】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、前記のｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める
ことを特徴とする秘密計算システム。
【請求項５】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２６】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数２７】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数２８】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算システム。
【請求項６】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２９】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３０】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数３１】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算システム。
【請求項７】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数３２】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３３】
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数３４】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める
ことを特徴とする秘密計算システム。
【請求項８】
請求項７記載の秘密計算システムを用いて、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算システムであって、
前記計算装置Ｙの前記計算逆変換部は、
さらに、
秘匿計算により、最大値となるｇｍを求める
ことを特徴とする秘密計算システム。
【請求項９】
通信手段で接続された計算装置Ｘと計算装置Ｙを用いる秘密計算方法であって、
前記計算装置Ｘが、
秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求めるランダム置換ステップと、
前記置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める条件式演算ステップと
を実行し、
前記計算装置Ｙが、
秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、前記ランダム置換の逆変換を行う計算逆変換ステップ
を行う
ことを特徴とする秘密計算方法。
【請求項１０】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とするときに、
当該秘密計算方法は、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算方法であって、
前記計算装置Ｘの前記ランダム置換ステップは、
Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求め、
前記計算装置Ｘの前記条件式演算ステップは、
ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、前記置換入力データｈｎ’に対する条件式
【数３５】
の演算を行い、置換条件結果データｄｍ，ｎを求め、
前記計算装置Ｙの前記計算逆変換ステップは、
ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【数３６】
を行う
ことを特徴とする秘密計算方法。
【請求項１１】
請求項１０記載の秘密計算方法を用いて、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算方法であって、
前記計算装置Ｙの前記計算逆変換ステップは、
前記の処理を行った上で、さらに、
秘匿計算により、最大値となるｃｍを求め、前記の最大値となるｃｍに対応するｍを求める
ことを特徴とする秘密計算方法。
【請求項１２】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成ステップ
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数３７】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３８】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【数３９】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、前記のｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める
ことを特徴とする秘密計算方法。
【請求項１３】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４０】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４１】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４２】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算方法。
【請求項１４】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４３】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４４】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４５】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算方法。
【請求項１５】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４６】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４７】
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４８】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める
ことを特徴とする秘密計算方法。
【請求項１６】
請求項１５記載の秘密計算方法を用いて、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算方法であって、
前記計算装置Ｙの前記計算逆変換ステップは、
前記の処理を行った上で、さらに、
秘匿計算により、最大値となるｇｍを求める
ことを特徴とする秘密計算方法。
【請求項１】
通信手段で接続された計算装置Ｘと計算装置Ｙを有する秘密計算システムであって、
前記計算装置Ｘは、
秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求めるランダム置換部と、
前記置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める条件式演算部と
を備え、
前記計算装置Ｙは、
秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、前記ランダム置換の逆変換を行う計算逆変換部
を備える
ことを特徴とする秘密計算システム。
【請求項２】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とするときに、
当該秘密計算システムは、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算システムであって、
前記計算装置Ｘの前記ランダム置換部は、
Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、前記置換入力データｈｎ’に対する条件式
【数２１】
の演算を行い、置換条件結果データｄｍ，ｎを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【数２２】
を行う
ことを特徴とする秘密計算システム。
【請求項３】
請求項２記載の秘密計算システムを用いて、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算システムであって、
前記計算装置Ｙの前記計算逆変換部は、
さらに、
秘匿計算により、最大値となるｃｍを求め、前記の最大値となるｃｍに対応するｍを求める
ことを特徴とする秘密計算システム。
【請求項４】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２３】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数２４】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【数２５】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、前記のｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める
ことを特徴とする秘密計算システム。
【請求項５】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２６】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数２７】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数２８】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算システム。
【請求項６】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数２９】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３０】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数３１】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算システム。
【請求項７】
請求項１記載の秘密計算システムであって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算システムは、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算システムであって、
前記計算装置Ｙは、
さらに、Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成部も備えており、
前記計算装置Ｘの前記ランダム置換部は、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数３２】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算部は、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３３】
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換部は、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数３４】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める
ことを特徴とする秘密計算システム。
【請求項８】
請求項７記載の秘密計算システムを用いて、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算システムであって、
前記計算装置Ｙの前記計算逆変換部は、
さらに、
秘匿計算により、最大値となるｇｍを求める
ことを特徴とする秘密計算システム。
【請求項９】
通信手段で接続された計算装置Ｘと計算装置Ｙを用いる秘密計算方法であって、
前記計算装置Ｘが、
秘匿関数計算により、秘匿した入力データを、演算ロジックを秘匿したランダム置換によって置換し、置換入力データを求めるランダム置換ステップと、
前記置換入力データに対してあらかじめ定めた条件式を用いた演算を行い、置換条件結果データを求める条件式演算ステップと
を実行し、
前記計算装置Ｙが、
秘匿関数計算により、置換条件結果データに対してあらかじめ定めた計算を行うとともに、前記ランダム置換の逆変換を行う計算逆変換ステップ
を行う
ことを特徴とする秘密計算方法。
【請求項１０】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎを正の整数、ｋを１〜Ｋの整数、ｍを１〜Ｍの整数、ｎを１〜Ｎの整数、集合ＨをＭ個の要素を持つ集合、ｈｍを集合Ｈのｍ番目の要素、［［ｇｎ］］を集合Ｈの要素の１つを秘匿したｎ番目の入力データ、πｎを集合Ｈの要素を集合Ｈの要素にランダムに置換する可逆な関数、πｎ−１をπｎの逆関数とするときに、
当該秘密計算方法は、Ｎ個の入力データの中に含まれる集合Ｈの各要素の数を求める秘密計算方法であって、
前記計算装置Ｘの前記ランダム置換ステップは、
Ｎ個の秘匿した入力データ［［ｇｎ］］に対して、秘匿関数計算により
ｈｎ’＝πｎ（ｇｎ）
の計算を行って、置換入力データｈｎ’を求め、
前記計算装置Ｘの前記条件式演算ステップは、
ｍ＝１〜Ｍ，ｎ＝１〜Ｎのすべてについて、前記置換入力データｈｎ’に対する条件式
【数３５】
の演算を行い、置換条件結果データｄｍ，ｎを求め、
前記計算装置Ｙの前記計算逆変換ステップは、
ｍ＝１〜Ｍについて、置換条件結果データｄｍ，ｎに対して秘匿関数計算により、
【数３６】
を行う
ことを特徴とする秘密計算方法。
【請求項１１】
請求項１０記載の秘密計算方法を用いて、Ｎ個の入力データの中に最も多く含まれる集合Ｈの要素を特定する秘密計算方法であって、
前記計算装置Ｙの前記計算逆変換ステップは、
前記の処理を行った上で、さらに、
秘匿計算により、最大値となるｃｍを求め、前記の最大値となるｃｍに対応するｍを求める
ことを特徴とする秘密計算方法。
【請求項１２】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，Ｎ，ｕ，ｖ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、ｎを０〜Ｎ−１の整数、Ｍ＝２ｕ、Ｎ＝２ｖ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂを｛０，…，Ｎ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データの中に閾値ｔよりも多く含まれていた集合Ａの要素と集合Ｂの要素の組合せに対して、組合せと含まれていた数を出力する秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個のｕ＋ｖビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成ステップ
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数３７】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｎ＝０〜Ｎ−１、ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数３８】
の演算を行い、置換条件結果データｄｈ，ｋ（ただし、ｈ＝２ｖｍ＋ｎ）を求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、置換条件結果データｄｈ，ｋに対して秘匿関数計算により、
【数３９】
を行い、さらに
ｍ＝０〜Ｍ−１、ｎ＝０〜Ｎ−１のすべてについて、秘匿計算により、
ｃｍ，ｎ＞ｔであるｃｍ，ｎを求め、前記のｃｍ，ｎ＞ｔであるｃｍ，ｎに対応する（（ｍ，ｎ），ｃｍ，ｎ）を求める
ことを特徴とする秘密計算方法。
【請求項１３】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個のｕビットの乱数ｒｋを生成し、［［ｒ１］］，…，［［ｒＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４０】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４１】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４２】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算方法。
【請求項１４】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍを求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４３】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４４】
ただし、φは空であることを示す記号
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４５】
を行い、Ｍ個の集合Ｇｍを求める
ことを特徴とする秘密計算方法。
【請求項１５】
請求項９記載の秘密計算方法であって、
［［ｘ］］はデータｘが秘匿した状態を表わすものとし、Ｋ，Ｍ，ｕ，ｔを正の整数、ｋを１〜Ｋの整数、ｍを０〜Ｍ−１の整数、Ｍ＝２ｕ、集合Ａを｛０，…，Ｍ−１｝を要素とする集合、集合Ｂは０を要素として含まない集合、［［（ａｋ，ｂｋ）］］を集合Ａの要素の１つであるａｋと集合Ｂの要素の１つであるｂｋとの組合せを秘匿したｋ番目の入力データとするときに、
当該秘密計算方法は、Ｋ個の入力データを集合Ａの要素であるａｋによってグループ分けしたＭ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める秘密計算方法であって、
まず、前記計算装置Ｙが、
Ｋ個の集合Ａの置換関数πｋを生成し、置換関数πｋの演算ロジックを秘匿したデータ［［π１］］，…，［［πＫ］］を前記計算装置Ｘに送信する置換生成ステップ、
を行い、その後、
前記計算装置Ｘの前記ランダム置換ステップが、
Ｋ個の秘匿した入力データ［［（ａｋ，ｂｋ）］］に対して、秘匿関数計算により
【数４６】
の計算を行って、置換入力データｈｋ’を求め、
前記計算装置Ｘの前記条件式演算ステップが、
ｍ＝０〜Ｍ−１，ｋ＝１〜Ｋのすべてについて、前記置換入力データｈｋ’に対する条件式
【数４７】
の演算を行い、置換条件結果データｄｍ，ｋを求め、
前記計算装置Ｙの前記計算逆変換ステップが、
ｍ＝０〜Ｍ−１について、置換条件結果データｄｍ，ｋに対して秘匿関数計算により、
【数４８】
を行い、Ｍ個の集合Ｇｍそれぞれの秘匿した要素数［［ｇｍ］］を求める
ことを特徴とする秘密計算方法。
【請求項１６】
請求項１５記載の秘密計算方法を用いて、Ｍ個の集合Ｇｍの中の最大の要素数を求める秘密計算方法であって、
前記計算装置Ｙの前記計算逆変換ステップは、
前記の処理を行った上で、さらに、
秘匿計算により、最大値となるｇｍを求める
ことを特徴とする秘密計算方法。
【図１】
【図２】
【図２】
【公開番号】特開２０１１−２４８０６６（Ｐ２０１１−２４８０６６Ａ）
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願番号】特願２０１０−１２０７０４（Ｐ２０１０−１２０７０４）
【出願日】平成２２年５月２６日（２０１０．５．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１２月８日（２０１１．１２．８）
【国際特許分類】
【出願日】平成２２年５月２６日（２０１０．５．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]