秘密計算システム、秘密計算方法、秘密計算プログラム
【課題】従来の秘匿回路計算の実行回数を削減すること。
【解決手段】本発明は、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムに適用される。本発明の秘密計算システムは、ＡＮＤ演算を行う場合、まず、［ｂi］及びｎを基に、［ｎ−Σｂi］を計算する。次に、当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、［ｗj］が全て０であれば［１］を、そうでなければ［０］を論理演算結果として出力する。
【解決手段】本発明は、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムに適用される。本発明の秘密計算システムは、ＡＮＤ演算を行う場合、まず、［ｂi］及びｎを基に、［ｎ−Σｂi］を計算する。次に、当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、［ｗj］が全て０であれば［１］を、そうでなければ［０］を論理演算結果として出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、入出力を明かすことなく論理演算を行う技術に関する。
【背景技術】
【０００２】
非特許文献１では、任意の論理演算において、ビット毎に秘匿化（暗号化）された入力を復元することなく論理演算を行って、論理演算結果の暗号文を出力する方法が提案されている。このように入出力を秘密にした論理演算は、秘匿回路計算と称されている。
【０００３】
なお、秘匿回路計算の入力としては、例えば、Ｐａｉｌｌｉｅｒ暗号によって秘匿化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文（非特許文献２）が挙げられる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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］を復号化することなく、例えば、
【０００６】
【数１】
【０００７】
を求めるためには、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要になる。
【０００８】
そこで、本発明の目的は、従来の秘匿回路計算の実行回数を削減することができる秘密計算システム、秘密計算方法、秘密計算プログラムを提供することである。
【課題を解決するための手段】
【０００９】
本発明の秘密計算システムは、
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【００１０】
【数２】
【００１１】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【００１２】
【数３】
【００１３】
を、そうでなければ、
【００１４】
【数４】
【００１５】
を論理演算結果として出力する。
【発明の効果】
【００１６】
秘匿回路計算において、ビットｂi（ｉ＝１，２，・・・，ｎ）のＡＮＤ演算を行う場合、従来では、ｎ−１回のＡＮＤ演算に対する秘匿回路計算の実行を必要としていた。
【００１７】
これに対し、本発明では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済む。いま、
【００１８】
【数５】
【００１９】
であるから、本発明は、従来に比べ秘匿回路計算の実行回数を削減することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施例１，２の秘密計算システムの構成を示す図である。
【図２】本発明の実施例１の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【図３】本発明の実施例２の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００２１】
本実施例では、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００２２】
【数６】
【００２３】
を求めるＡＮＤ演算を例に挙げて説明する。
【００２４】
先ず、本実施例では、上述の非特許文献２で提案されている技術またはそれに類する技術を利用することを前提とする。
【００２５】
非特許文献２では、Ｐａｉｌｌｉｅｒ暗号によって暗号化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文を生成する方法が提案されている。
【００２６】
このように、数値ｚを秘匿化（暗号化）したデータ［ｚ］を入力とし、ｚを二進数表記したときの各桁ｚi（ｚの下位ｉ桁目のビット）を秘匿化したデータ［ｚi］を出力する装置を秘匿化数値二進変換装置と呼ぶことにする。
【００２７】
また、ビットｂi（ｉ＝１，２，・・・，ｍ）を秘匿化したデータ［ｂi］及びある論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂm）］を出力するような、非特許文献１に開示された方法またはそれに類する方法を実装した装置を秘匿回路計算装置と呼ぶことにする。
【００２８】
本発明では、数値を秘匿化したデータ［ｚ］，［ｚ′］及び秘匿化していない数値ｃについて、［ｚ＋ｚ′］，［ｚ−ｚ′］，［ｃｚ］を計算する機能が必要となるが、非特許文献２の方法では当該機能を満たしている。
【００２９】
以上の準備の下、本実施例の秘密計算システム１０は、図１に示すように、上述の秘匿化数値二進変換装置１２及び秘匿回路計算装置１３を有する他、ビット毎に秘匿化されたデータ［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力する秘密計算装置１１を有している。
【００３０】
なお、図１においては、説明の簡略化のため、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３をそれぞれ単一の装置としているが、それぞれ複数台の装置で構成しても良い。
【００３１】
秘密計算装置１１は、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークで接続されていて、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークを介してデータの送受信が可能であるものとする。
【００３２】
なお、秘密計算装置１１において、［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力することは、秘匿回路計算装置１３の機能そのものであるが、本実施例では、秘密計算装置１１の機能を用いることにより、単純に秘匿回路計算装置１３の機能のみを用いるよりも高速に論理演算を可能とすることが目的である。
【００３３】
次に、本実施例の秘密計算システム１０の動作について図２を用いて説明する。
【００３４】
秘密計算装置１１は、ステップＡ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００３５】
【数７】
【００３６】
を出力するために、先ず、ステップＡ２において、［ｂi］及びｎから
【００３７】
【数８】
【００３８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００３９】
その応答として、秘匿化数値二進変換装置１２は、ステップＡ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００４０】
ここで、ｗjは、
【００４１】
【数９】
【００４２】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。すると、
【００４３】
【数１０】
【００４４】
であり、
【００４５】
【数１１】
【００４６】
が成り立つことから、
【００４７】
【数１２】
【００４８】
となり、秘密計算装置１１は、［ｗj］を秘匿回路計算装置１３に送信する。
【００４９】
その応答として、秘匿回路計算装置１３は、ステップＡ４において、
【００５０】
【数１３】
【００５１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【００５２】
以上、ＡＮＤ演算を例に説明したが、ＸＯＲ演算やＯＲ演算であっても同様に処理可能である。
【００５３】
例えば、ＸＯＲ演算であれば、
【００５４】
【数１４】
【００５５】
とすれば良く、秘匿回路計算装置１３は不要である。
【００５６】
また、ＯＲ演算であれば、
【００５７】
【数１５】
【００５８】
の代わりに、
【００５９】
【数１６】
【００６０】
とし、
【００６１】
【数１７】
【００６２】
と置き換えて考えれば良い。
【００６３】
本実施例の期待する効果は、秘匿回路計算装置１３の負荷軽減である。
【００６４】
従来のように、単純に秘匿回路計算装置１３の機能のみを用いて実行する場合は、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要となる。
【００６５】
これに対して、本実施例では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済むため、従来の秘匿回路計算の実行回数を削減することができ、秘匿回路計算装置１３の負荷軽減を図ることができる。
【００６６】
いま、
【００６７】
【数１８】
【００６８】
であるから、ｎが大きくなるにつれて秘匿回路計算装置１３の負荷軽減の効果がより大きくなる。
【実施例２】
【００６９】
本実施例の秘密計算システム１０は、実施例１と比べて、構成自体は同様であるが、秘匿化数値二進変換装置１２を繰り返し利用することで、秘匿回路計算装置１３の負荷を更に軽減する点が異なる。
【００７０】
次に、本実施例の秘密計算システム１０の動作について図３を用いて説明する。ここでは、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００７１】
【数１９】
【００７２】
を求めるＯＲ演算を例に挙げて説明する。
【００７３】
秘密計算装置１１は、ステップＢ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００７４】
【数２０】
【００７５】
を出力するために、先ず、ステップＢ２において、［ｂi］及びｎから
【００７６】
【数２１】
【００７７】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００７８】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００７９】
ここで、ｗjは、
【００８０】
【数２２】
【００８１】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。このとき、
【００８２】
【数２３】
【００８３】
であるから、
【００８４】
【数２４】
【００８５】
が成り立つ。
【００８６】
これを踏まえ、秘密計算装置１１は、ステップＢ４において、［ｗj］及びｔから
【００８７】
【数２５】
【００８８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００８９】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ５において、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）を求め、［ｅk］を秘密計算装置１１に送信する。
【００９０】
ここで、ｅkは、
【００９１】
【数２６】
【００９２】
を二進数表記したときの下位ｋ桁目のビットを表し、ｐはｔのビット長を表すものとする。このとき、
【００９３】
【数２７】
【００９４】
となり、
【００９５】
【数２８】
【００９６】
が成り立つことから、
【００９７】
【数２９】
【００９８】
となり、秘密計算装置１１は、［ｅk］を秘匿回路計算装置１３に送信する。
【００９９】
その応答として、秘匿回路計算装置１３は、ステップＢ６において、
【０１００】
【数３０】
【０１０１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【０１０２】
本実施例では、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）が全て０であるか否かを判断するために、
【０１０３】
【数３１】
【０１０４】
回の秘匿回路計算を実行するだけで済むため、実施例１よりも更に秘匿回路計算装置１３の負荷軽減が見込める。
【０１０５】
以上、ＯＲ演算を例に説明したが、ＡＮＤ演算やＸＯＲ演算であっても同様に処理可能である。
【０１０６】
例えば、ＡＮＤ演算であれば、
【０１０７】
【数３２】
【０１０８】
の代わりに、
【０１０９】
【数３３】
【０１１０】
とし、
【０１１１】
【数３４】
【０１１２】
と置き換えて考えれば良い。
【０１１３】
以上、本発明を実施例を参照して説明したが、本発明は上記実施例に限定されものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１１４】
例えば、実施例２では、秘匿化数値二進変換装置１２を二度利用したが、三度以上利用する方法やその効果は明らかである。
【０１１５】
また、実施例１，２では、秘密計算装置１１と秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とを分離して構成したが、秘密計算装置１１の内部に秘匿化数値二進変換装置１２及び秘匿回路計算装置１３の機能を設けた構成としても良い。更に、この場合、その秘密計算装置１１にて行われる秘密計算方法を、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１６】
１０ 秘密計算システム
１１ 秘密計算装置
１２ 秘匿化数値二進変換装置
１３ 秘匿回路計算装置
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、入出力を明かすことなく論理演算を行う技術に関する。
【背景技術】
【０００２】
非特許文献１では、任意の論理演算において、ビット毎に秘匿化（暗号化）された入力を復元することなく論理演算を行って、論理演算結果の暗号文を出力する方法が提案されている。このように入出力を秘密にした論理演算は、秘匿回路計算と称されている。
【０００３】
なお、秘匿回路計算の入力としては、例えば、Ｐａｉｌｌｉｅｒ暗号によって秘匿化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文（非特許文献２）が挙げられる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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］を復号化することなく、例えば、
【０００６】
【数１】
【０００７】
を求めるためには、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要になる。
【０００８】
そこで、本発明の目的は、従来の秘匿回路計算の実行回数を削減することができる秘密計算システム、秘密計算方法、秘密計算プログラムを提供することである。
【課題を解決するための手段】
【０００９】
本発明の秘密計算システムは、
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【００１０】
【数２】
【００１１】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【００１２】
【数３】
【００１３】
を、そうでなければ、
【００１４】
【数４】
【００１５】
を論理演算結果として出力する。
【発明の効果】
【００１６】
秘匿回路計算において、ビットｂi（ｉ＝１，２，・・・，ｎ）のＡＮＤ演算を行う場合、従来では、ｎ−１回のＡＮＤ演算に対する秘匿回路計算の実行を必要としていた。
【００１７】
これに対し、本発明では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済む。いま、
【００１８】
【数５】
【００１９】
であるから、本発明は、従来に比べ秘匿回路計算の実行回数を削減することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施例１，２の秘密計算システムの構成を示す図である。
【図２】本発明の実施例１の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【図３】本発明の実施例２の秘密計算システムによる秘密計算方法を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００２１】
本実施例では、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００２２】
【数６】
【００２３】
を求めるＡＮＤ演算を例に挙げて説明する。
【００２４】
先ず、本実施例では、上述の非特許文献２で提案されている技術またはそれに類する技術を利用することを前提とする。
【００２５】
非特許文献２では、Ｐａｉｌｌｉｅｒ暗号によって暗号化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記とした桁ごとに暗号化した暗号文を生成する方法が提案されている。
【００２６】
このように、数値ｚを秘匿化（暗号化）したデータ［ｚ］を入力とし、ｚを二進数表記したときの各桁ｚi（ｚの下位ｉ桁目のビット）を秘匿化したデータ［ｚi］を出力する装置を秘匿化数値二進変換装置と呼ぶことにする。
【００２７】
また、ビットｂi（ｉ＝１，２，・・・，ｍ）を秘匿化したデータ［ｂi］及びある論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂm）］を出力するような、非特許文献１に開示された方法またはそれに類する方法を実装した装置を秘匿回路計算装置と呼ぶことにする。
【００２８】
本発明では、数値を秘匿化したデータ［ｚ］，［ｚ′］及び秘匿化していない数値ｃについて、［ｚ＋ｚ′］，［ｚ−ｚ′］，［ｃｚ］を計算する機能が必要となるが、非特許文献２の方法では当該機能を満たしている。
【００２９】
以上の準備の下、本実施例の秘密計算システム１０は、図１に示すように、上述の秘匿化数値二進変換装置１２及び秘匿回路計算装置１３を有する他、ビット毎に秘匿化されたデータ［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力する秘密計算装置１１を有している。
【００３０】
なお、図１においては、説明の簡略化のため、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３をそれぞれ単一の装置としているが、それぞれ複数台の装置で構成しても良い。
【００３１】
秘密計算装置１１は、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークで接続されていて、秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とネットワークを介してデータの送受信が可能であるものとする。
【００３２】
なお、秘密計算装置１１において、［ｂi］（ｉ＝１，２，・・・，ｎ）及び論理関数ｆを入力として、［ｆ（ｂ1，・・・，ｂn）］を出力することは、秘匿回路計算装置１３の機能そのものであるが、本実施例では、秘密計算装置１１の機能を用いることにより、単純に秘匿回路計算装置１３の機能のみを用いるよりも高速に論理演算を可能とすることが目的である。
【００３３】
次に、本実施例の秘密計算システム１０の動作について図２を用いて説明する。
【００３４】
秘密計算装置１１は、ステップＡ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００３５】
【数７】
【００３６】
を出力するために、先ず、ステップＡ２において、［ｂi］及びｎから
【００３７】
【数８】
【００３８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００３９】
その応答として、秘匿化数値二進変換装置１２は、ステップＡ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００４０】
ここで、ｗjは、
【００４１】
【数９】
【００４２】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。すると、
【００４３】
【数１０】
【００４４】
であり、
【００４５】
【数１１】
【００４６】
が成り立つことから、
【００４７】
【数１２】
【００４８】
となり、秘密計算装置１１は、［ｗj］を秘匿回路計算装置１３に送信する。
【００４９】
その応答として、秘匿回路計算装置１３は、ステップＡ４において、
【００５０】
【数１３】
【００５１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【００５２】
以上、ＡＮＤ演算を例に説明したが、ＸＯＲ演算やＯＲ演算であっても同様に処理可能である。
【００５３】
例えば、ＸＯＲ演算であれば、
【００５４】
【数１４】
【００５５】
とすれば良く、秘匿回路計算装置１３は不要である。
【００５６】
また、ＯＲ演算であれば、
【００５７】
【数１５】
【００５８】
の代わりに、
【００５９】
【数１６】
【００６０】
とし、
【００６１】
【数１７】
【００６２】
と置き換えて考えれば良い。
【００６３】
本実施例の期待する効果は、秘匿回路計算装置１３の負荷軽減である。
【００６４】
従来のように、単純に秘匿回路計算装置１３の機能のみを用いて実行する場合は、ｎ−１回のＡＮＤ演算に対する秘匿回路計算が必要となる。
【００６５】
これに対して、本実施例では、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）が全て０であるか否かを判断するために、ｔ−１回のＯＲ演算及び１回のＮＯＴ演算に対する秘匿回路計算を実行するだけで済むため、従来の秘匿回路計算の実行回数を削減することができ、秘匿回路計算装置１３の負荷軽減を図ることができる。
【００６６】
いま、
【００６７】
【数１８】
【００６８】
であるから、ｎが大きくなるにつれて秘匿回路計算装置１３の負荷軽減の効果がより大きくなる。
【実施例２】
【００６９】
本実施例の秘密計算システム１０は、実施例１と比べて、構成自体は同様であるが、秘匿化数値二進変換装置１２を繰り返し利用することで、秘匿回路計算装置１３の負荷を更に軽減する点が異なる。
【００７０】
次に、本実施例の秘密計算システム１０の動作について図３を用いて説明する。ここでは、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が与えられ、
【００７１】
【数１９】
【００７２】
を求めるＯＲ演算を例に挙げて説明する。
【００７３】
秘密計算装置１１は、ステップＢ１において、ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］が入力されると、
【００７４】
【数２０】
【００７５】
を出力するために、先ず、ステップＢ２において、［ｂi］及びｎから
【００７６】
【数２１】
【００７７】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００７８】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ３において、［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１）を求め、［ｗj］を秘密計算装置１１に送信する。
【００７９】
ここで、ｗjは、
【００８０】
【数２２】
【００８１】
を二進数表記したときの下位ｊ桁目のビットを表し、ｔはｎのビット長を表すものとする。このとき、
【００８２】
【数２３】
【００８３】
であるから、
【００８４】
【数２４】
【００８５】
が成り立つ。
【００８６】
これを踏まえ、秘密計算装置１１は、ステップＢ４において、［ｗj］及びｔから
【００８７】
【数２５】
【００８８】
を計算し、計算結果を秘匿化数値二進変換装置１２に送信する。
【００８９】
その応答として、秘匿化数値二進変換装置１２は、ステップＢ５において、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）を求め、［ｅk］を秘密計算装置１１に送信する。
【００９０】
ここで、ｅkは、
【００９１】
【数２６】
【００９２】
を二進数表記したときの下位ｋ桁目のビットを表し、ｐはｔのビット長を表すものとする。このとき、
【００９３】
【数２７】
【００９４】
となり、
【００９５】
【数２８】
【００９６】
が成り立つことから、
【００９７】
【数２９】
【００９８】
となり、秘密計算装置１１は、［ｅk］を秘匿回路計算装置１３に送信する。
【００９９】
その応答として、秘匿回路計算装置１３は、ステップＢ６において、
【０１００】
【数３０】
【０１０１】
を計算し、計算結果を秘密計算装置１１に送信する。その計算結果は、論理演算結果の暗号文として秘密計算装置１１から出力される。
【０１０２】
本実施例では、［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１）が全て０であるか否かを判断するために、
【０１０３】
【数３１】
【０１０４】
回の秘匿回路計算を実行するだけで済むため、実施例１よりも更に秘匿回路計算装置１３の負荷軽減が見込める。
【０１０５】
以上、ＯＲ演算を例に説明したが、ＡＮＤ演算やＸＯＲ演算であっても同様に処理可能である。
【０１０６】
例えば、ＡＮＤ演算であれば、
【０１０７】
【数３２】
【０１０８】
の代わりに、
【０１０９】
【数３３】
【０１１０】
とし、
【０１１１】
【数３４】
【０１１２】
と置き換えて考えれば良い。
【０１１３】
以上、本発明を実施例を参照して説明したが、本発明は上記実施例に限定されものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１１４】
例えば、実施例２では、秘匿化数値二進変換装置１２を二度利用したが、三度以上利用する方法やその効果は明らかである。
【０１１５】
また、実施例１，２では、秘密計算装置１１と秘匿化数値二進変換装置１２及び秘匿回路計算装置１３とを分離して構成したが、秘密計算装置１１の内部に秘匿化数値二進変換装置１２及び秘匿回路計算装置１３の機能を設けた構成としても良い。更に、この場合、その秘密計算装置１１にて行われる秘密計算方法を、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１６】
１０ 秘密計算システム
１１ 秘密計算装置
１２ 秘匿化数値二進変換装置
１３ 秘匿回路計算装置
【特許請求の範囲】
【請求項１】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数２】
を、そうでなければ、
【数３】
を論理演算結果として出力する、秘密計算システム。
【請求項２】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数４】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
ｗ1を論理演算結果として出力する、請求項１に記載の秘密計算システム。
【請求項３】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数５】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数６】
を、そうでなければ、
【数７】
を論理演算結果として出力する、請求項１または２に秘密計算システム。
【請求項４】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数８】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数９】
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１０】
を、そうでなければ、
【数１１】
を論理演算結果として出力する、秘密計算システム。
【請求項５】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１２】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数１３】
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１４】
を、そうでなければ、
【数１５】
を論理演算結果として出力する、請求項４に記載の秘密計算システム。
【請求項６】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１６】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数１７】
を、そうでなければ、
【数１８】
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項７】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１９】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
ｗ1を論理演算結果として出力するステップと、を有する請求項６に記載の秘密計算方法。
【請求項８】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２０】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数２１】
を、そうでなければ、
【数２２】
を論理演算結果として出力するステップと、を有する請求項６または７に秘密計算方法。
【請求項９】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数２３】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２４】
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２５】
を、そうでなければ、
【数２６】
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項１０】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２７】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２８】
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２９】
を、そうでなければ、
【数３０】
を論理演算結果として出力するステップと、を有する請求項９に秘密計算方法。
【請求項１１】
請求項６から１０のいずれか１項に記載の秘密計算方法をコンピュータに実行させるための秘密計算プログラム。
【請求項１】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数２】
を、そうでなければ、
【数３】
を論理演算結果として出力する、秘密計算システム。
【請求項２】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数４】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
ｗ1を論理演算結果として出力する、請求項１に記載の秘密計算システム。
【請求項３】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数５】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］が全て０であれば、
【数６】
を、そうでなければ、
【数７】
を論理演算結果として出力する、請求項１または２に秘密計算システム。
【請求項４】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算システムであって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数８】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数９】
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１０】
を、そうでなければ、
【数１１】
を論理演算結果として出力する、秘密計算システム。
【請求項５】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１２】
を計算し、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求め、
［ｗj］及びｔを基に、
【数１３】
を計算し、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求め、
［ｅk］が全て０であれば、
【数１４】
を、そうでなければ、
【数１５】
を論理演算結果として出力する、請求項４に記載の秘密計算システム。
【請求項６】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数１６】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数１７】
を、そうでなければ、
【数１８】
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項７】
ＸＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数１９】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
ｗ1を論理演算結果として出力するステップと、を有する請求項６に記載の秘密計算方法。
【請求項８】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２０】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］が全て０であれば、
【数２１】
を、そうでなければ、
【数２２】
を論理演算結果として出力するステップと、を有する請求項６または７に秘密計算方法。
【請求項９】
ビットｂi（ｉ＝１，２，・・・，ｎ）を秘匿化したデータ［ｂi］を入力として、ｂiを復元することなくｂiの論理演算を行い、論理演算結果を出力する秘密計算装置による秘密計算方法であって、
ＡＮＤ演算を行う場合、
［ｂi］及びｎを基に、
【数２３】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２４】
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２５】
を、そうでなければ、
【数２６】
を論理演算結果として出力するステップと、を有する秘密計算方法。
【請求項１０】
ＯＲ演算を行う場合、
［ｂi］及びｎを基に、
【数２７】
を計算するステップと、
当該計算結果を二進数表記した［ｗj］（ｊ＝ｔ，ｔ−１，・・・，１、ｔはｎのビット長）を求めるステップと、
［ｗj］及びｔを基に、
【数２８】
を計算するステップと、
当該計算結果を二進数表記した［ｅk］（ｋ＝ｐ，ｐ−１，・・・，１、ｐはｔのビット長）を求めるステップと、
［ｅk］が全て０であれば、
【数２９】
を、そうでなければ、
【数３０】
を論理演算結果として出力するステップと、を有する請求項９に秘密計算方法。
【請求項１１】
請求項６から１０のいずれか１項に記載の秘密計算方法をコンピュータに実行させるための秘密計算プログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１０−１６４８９９（Ｐ２０１０−１６４８９９Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８９９８（Ｐ２００９−８９９８）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]