(57)【要約】【課題】従来の秘匿回路計算の実行回数を削減すること。【解決手段】本発明は、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムに適用される。本発明の秘密計算システムは、ＡＮＤ演算を行う場合、まず、［ｂi］及びｎを基に、［ｎ−Σｂi］を計算する。次に、当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、［ｗj］が全て０であれば［１］を、そうでなければ［０］を論理演算結果として出力する。【選択図】図１
2010164899.tif 000002
【特許請求の範囲】
【請求項１】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１】
2010164899.tif 000037
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数２】
2010164899.tif 000038
を、そうでなければ、
【数３】
2010164899.tif 000039
を論理演算結果として出力する、秘密計算システム。
【請求項２】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数４】
2010164899.tif 000040
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
ｗ1を論理演算結果として出力する、請求項１に記載の秘密計算システム。
【請求項３】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数５】
2010164899.tif 000041
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数６】
2010164899.tif 000042
を、そうでなければ、
【数７】
2010164899.tif 000043
を論理演算結果として出力する、請求項１または２に秘密計算システム。
【請求項４】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数８】
2010164899.tif 000044
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数９】
2010164899.tif 000045
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１０】
2010164899.tif 000046
を、そうでなければ、
【数１１】
2010164899.tif 000047
を論理演算結果として出力する、秘密計算システム。
【請求項５】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１２】
2010164899.tif 000048
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数１３】
2010164899.tif 000049
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１４】
2010164899.tif 000050
を、そうでなければ、
【数１５】
2010164899.tif 000051
を論理演算結果として出力する、請求項４に記載の秘密計算システム。
【請求項６】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１６】
2010164899.tif 000052
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数１７】
2010164899.tif 000053
を、そうでなければ、
【数１８】
2010164899.tif 000054
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項７】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１９】
2010164899.tif 000055
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
ｗ1を論理演算結果として出力するステップと、を有する請求項６に記載の秘密計算方法。
【請求項８】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２０】
2010164899.tif 000056
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数２１】
2010164899.tif 000057
を、そうでなければ、
【数２２】
2010164899.tif 000058
を論理演算結果として出力するステップと、を有する請求項６または７に秘密計算方法。
【請求項９】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数２３】
2010164899.tif 000059
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２４】
2010164899.tif 000060
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２５】
2010164899.tif 000061
を、そうでなければ、
【数２６】
2010164899.tif 000062
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項１０】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２７】
2010164899.tif 000063
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２８】
2010164899.tif 000064
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２９】
2010164899.tif 000065
を、そうでなければ、
【数３０】
2010164899.tif 000066
を論理演算結果として出力するステップと、を有する請求項９に秘密計算方法。
【請求項１１】
請求項６から１０のいずれか１項に記載の秘密計算方法をコンピュータに実行させるための秘密計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、入出力を明かすことなく論理演算を行う技術に関する。
【背景技術】
【０００２】
非特許文献１では、任意の論理演算において、ビット毎に秘匿化（暗号化）された入力を復元することなく論理演算を行って、論理演算結果の暗号文を出力する方法が提案されている。このように入出力を秘密にした論理演算は、秘匿回路計算と称されている。
【０００３】
なお、秘匿回路計算の入力としては、例えば、Ｐａｉｌｌｉｅｒ暗号によって秘匿化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文（非特許文献２）が挙げられる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】G. Yamamoto, K. Chida, A. Nasciment, K. Suzuki, and S. Uchiyama, Efficient, non-optimistic secure circuit evaluation based on the ElGamal encryption, WISA 2005, Lecture Notes in Computer Science, pp. 328-343, Springer-Verlag, 2005.
【非特許文献２】B. Schoenmakers and P. Tuyls, Efficient binary conversion for Paillier encrypted values, Advances in Cryptology − EUROCRYPT 2006, Lecture Notes in Computer Science 4004, pp. 522-537, Springer-Verlag, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１に開示された方法では、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられた場合に、データ［ｂi］を復号化することなく、例えば、
【０００６】
【数１】
2010164899.tif 000003
【０００７】
を求めるためには、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要になる。
【０００８】
そこで、本発明の目的は、従来の秘匿回路計算の実行回数を削減することができる秘密計算システム、秘密計算方法、秘密計算プログラムを提供することである。
【課題を解決するための手段】
【０００９】
本発明の秘密計算システムは、
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【００１０】
【数２】
2010164899.tif 000004
【００１１】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【００１２】
【数３】
2010164899.tif 000005
【００１３】
を、そうでなければ、
【００１４】
【数４】
2010164899.tif 000006
【００１５】
を論理演算結果として出力する。
【発明の効果】
【００１６】
秘匿回路計算において、ビットｂi（ｉ＝１，２，・・・，ｎ）のＡＮＤ演算を行う場合、従来では、ｎ−１回のＡＮＤ演算に対する秘匿回路計算の実行を必要としていた。
【００１７】
これに対し、本発明では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済む。いま、
【００１８】
【数５】
2010164899.tif 000007
【００１９】
であるから、本発明は、従来に比べ秘匿回路計算の実行回数を削減することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施例１，２の秘密計算システムの構成を示す図である。
【図２】本発明の実施例１の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【図３】本発明の実施例２の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００２１】
本実施例では、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００２２】
【数６】
2010164899.tif 000008
【００２３】
を求めるＡＮＤ演算を例に挙げて説明する。
【００２４】
先ず、本実施例では、上述の非特許文献２で提案されている技術またはそれに類する技術を利用することを前提とする。
【００２５】
非特許文献２では、Ｐａｉｌｌｉｅｒ暗号によって暗号化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文を生成する方法が提案されている。
【００２６】
このように、数値ｚを秘匿化（暗号化）したデータ［ｚ］を入力とし、ｚを二進数表記したときの各桁ｚi（ｚの下位ｉ桁目のビット）を秘匿化したデータ［ｚi］を出力する装置を秘匿化数値二進変換装置と呼ぶことにする。
【００２７】
また、ビットｂi（ｉ＝１，２，・・・，ｍ）を秘匿化したデータ［ｂi］及びある論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂm）］を出力するような、非特許文献１に開示された方法またはそれに類する方法を実装した装置を秘匿回路計算装置と呼ぶことにする。
【００２８】
本発明では、数値を秘匿化したデータ［ｚ］，［ｚ′］及び秘匿化していない数値ｃについて、［ｚ＋ｚ′］，［ｚ−ｚ′］，［ｃｚ］を計算する機能が必要となるが、非特許文献２の方法では当該機能を満たしている。
【００２９】
以上の準備の下、本実施例の秘密計算システム１０は、図１に示すように、上述の秘匿化数値二進変換装置１２及び秘匿回路計算装置１３を有する他、ビット毎に秘匿化されたデータ［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力する秘密計算装置１１を有している。
【００３０】
なお、図１においては、説明の簡略化のため、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３をそれぞれ単一の装置としているが、それぞれ複数台の装置で構成しても良い。
【００３１】
秘密計算装置１１は、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークで接続されていて、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークを介してデータの送受信が可能であるものとする。
【００３２】
なお、秘密計算装置１１において、［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力することは、秘匿回路計算装置１３の機能そのものであるが、本実施例では、秘密計算装置１１の機能を用いることにより、単純に秘匿回路計算装置１３の機能のみを用いるよりも高速に論理演算を可能とすることが目的である。
【００３３】
次に、本実施例の秘密計算システム１０の動作について図２を用いて説明する。
【００３４】
秘密計算装置１１は、ステップＡ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００３５】
【数７】
2010164899.tif 000009
【００３６】
を出力するために、先ず、ステップＡ２において、［ｂi］及びｎから
【００３７】
【数８】
2010164899.tif 000010
【００３８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００３９】
その応答として、秘匿化数値二進変換装置１２は、ステップＡ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００４０】
ここで、ｗjは、
【００４１】
【数９】
2010164899.tif 000011
【００４２】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。すると、
【００４３】
【数１０】
2010164899.tif 000012
【００４４】
であり、
【００４５】
【数１１】
2010164899.tif 000013
【００４６】
が成り立つことから、
【００４７】
【数１２】
2010164899.tif 000014
【００４８】
となり、秘密計算装置１１は、［ｗj］を秘匿回路計算装置１３に送信する。
【００４９】
その応答として、秘匿回路計算装置１３は、ステップＡ４において、
【００５０】
【数１３】
2010164899.tif 000015
【００５１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【００５２】
以上、ＡＮＤ演算を例に説明したが、ＸＯＲ演算やＯＲ演算であっても同様に処理可能である。
【００５３】
例えば、ＸＯＲ演算であれば、
【００５４】
【数１４】
2010164899.tif 000016
【００５５】
とすれば良く、秘匿回路計算装置１３は不要である。
【００５６】
また、ＯＲ演算であれば、
【００５７】
【数１５】
2010164899.tif 000017
【００５８】
の代わりに、
【００５９】
【数１６】
2010164899.tif 000018
【００６０】
とし、
【００６１】
【数１７】
2010164899.tif 000019
【００６２】
と置き換えて考えれば良い。
【００６３】
本実施例の期待する効果は、秘匿回路計算装置１３の負荷軽減である。
【００６４】
従来のように、単純に秘匿回路計算装置１３の機能のみを用いて実行する場合は、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要となる。
【００６５】
これに対して、本実施例では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済むため、従来の秘匿回路計算の実行回数を削減することができ、秘匿回路計算装置１３の負荷軽減を図ることができる。
【００６６】
いま、
【００６７】
【数１８】
2010164899.tif 000020
【００６８】
であるから、ｎが大きくなるにつれて秘匿回路計算装置１３の負荷軽減の効果がより大きくなる。
【実施例２】
【００６９】
本実施例の秘密計算システム１０は、実施例１と比べて、構成自体は同様であるが、秘匿化数値二進変換装置１２を繰り返し利用することで、秘匿回路計算装置１３の負荷を更に軽減する点が異なる。
【００７０】
次に、本実施例の秘密計算システム１０の動作について図３を用いて説明する。ここでは、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００７１】
【数１９】
2010164899.tif 000021
【００７２】
を求めるＯＲ演算を例に挙げて説明する。
【００７３】
秘密計算装置１１は、ステップＢ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００７４】
【数２０】
2010164899.tif 000022
【００７５】
を出力するために、先ず、ステップＢ２において、［ｂi］及びｎから
【００７６】
【数２１】
2010164899.tif 000023
【００７７】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００７８】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００７９】
ここで、ｗjは、
【００８０】
【数２２】
2010164899.tif 000024
【００８１】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。このとき、
【００８２】
【数２３】
2010164899.tif 000025
【００８３】
であるから、
【００８４】
【数２４】
2010164899.tif 000026
【００８５】
が成り立つ。
【００８６】
これを踏まえ、秘密計算装置１１は、ステップＢ４において、［ｗj］及びｔから
【００８７】
【数２５】
2010164899.tif 000027
【００８８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００８９】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ５において、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）を求め、［ｅk］を秘密計算装置１１に送信する。
【００９０】
ここで、ｅkは、
【００９１】
【数２６】
2010164899.tif 000028
【００９２】
を二進数表記したときの下位ｋ桁目のビットを表し、ｐはｔのビット長を表すものとする。このとき、
【００９３】
【数２７】
2010164899.tif 000029
【００９４】
となり、
【００９５】
【数２８】
2010164899.tif 000030
【００９６】
が成り立つことから、
【００９７】
【数２９】
2010164899.tif 000031
【００９８】
となり、秘密計算装置１１は、［ｅk］を秘匿回路計算装置１３に送信する。
【００９９】
その応答として、秘匿回路計算装置１３は、ステップＢ６において、
【０１００】
【数３０】
2010164899.tif 000032
【０１０１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【０１０２】
本実施例では、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）が全て０であるか否かを判断するために、
【０１０３】
【数３１】
2010164899.tif 000033
【０１０４】
回の秘匿回路計算を実行するだけで済むため、実施例１よりも更に秘匿回路計算装置１３の負荷軽減が見込める。
【０１０５】
以上、ＯＲ演算を例に説明したが、ＡＮＤ演算やＸＯＲ演算であっても同様に処理可能である。
【０１０６】
例えば、ＡＮＤ演算であれば、
【０１０７】
【数３２】
2010164899.tif 000034
【０１０８】
の代わりに、
【０１０９】
【数３３】
2010164899.tif 000035
【０１１０】
とし、
【０１１１】
【数３４】
2010164899.tif 000036
【０１１２】
と置き換えて考えれば良い。
【０１１３】
以上、本発明を実施例を参照して説明したが、本発明は上記実施例に限定されものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１１４】
例えば、実施例２では、秘匿化数値二進変換装置１２を二度利用したが、三度以上利用する方法やその効果は明らかである。
【０１１５】
また、実施例１，２では、秘密計算装置１１と秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とを分離して構成したが、秘密計算装置１１の内部に秘匿化数値二進変換装置１２及び秘匿回路計算装置１３の機能を設けた構成としても良い。更に、この場合、その秘密計算装置１１にて行われる秘密計算方法を、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１６】
１０    秘密計算システム
１１    秘密計算装置
１２    秘匿化数値二進変換装置
１３    秘匿回路計算装置
【図１】
2010164899.tif 000067
【図２】
2010164899.tif 000068
【図３】
2010164899.tif 000069