不正検知方法、秘密計算システム、計算装置、計算プログラム
【課題】乗算の秘密計算での計算装置の不正処理を検知する。
【解決手段】秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。乱数共有手段は、計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる。第１乗算結果分散手段は、計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させる。乗算結果加算手段は、Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍの秘密計算を行う。第２乗算結果分散手段は、Ｅ＝ＤＢ ｍｏｄ Ｍの秘密計算を行う。乗算確認手段は、計算装置Ｐ１にｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍを計算させ、計算装置Ｐ２にｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍを計算させ、計算装置Ｐ１または計算装置Ｐ２にｆ＋ｇ＝０ ｍｏｄ Ｍかを確認させる。
【解決手段】秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。乱数共有手段は、計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる。第１乗算結果分散手段は、計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させる。乗算結果加算手段は、Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍの秘密計算を行う。第２乗算結果分散手段は、Ｅ＝ＤＢ ｍｏｄ Ｍの秘密計算を行う。乗算確認手段は、計算装置Ｐ１にｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍを計算させ、計算装置Ｐ２にｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍを計算させ、計算装置Ｐ１または計算装置Ｐ２にｆ＋ｇ＝０ ｍｏｄ Ｍかを確認させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号技術に関し、暗号化された二つの数値を復元すること無く当該数値の乗算結果の暗号文（断片）を得るときの不正検知方法、不正検知機能を有する秘密計算システム、計算装置、および計算プログラムに関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法（以降、このような計算を秘密計算と呼ぶ）として、例えば非特許文献１に記載された方法がある。この方法は、３つの計算装置に１つ以上の数値を分散させて記録する（以降、分散された情報を断片と呼ぶ）。そして、分散された数値を復元すること無く、加減算，定数和，乗算，定数倍，論理演算(否定，論理積，論理和，排他的論理和)，データ形式変換(整数, 二進数)の結果を３つの計算装置に分散保持させることができる(なお、定数とは既知の数値を意味している)。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司，五十嵐大，高橋克巳，“効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察”，第48回情報処理学会研究報告，CSEC, pp.1-7, 2010，3月.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は乗算の秘密計算においていずれかの計算装置が不正処理を行った場合にそれを検知できない場合がある。本発明は、乗算の秘密計算での計算装置の不正処理を検知できる秘密計算システムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の秘密計算システムは、数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う。Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとする。
【０００６】
秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。データ取得手段は、数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０に断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得させ、計算装置Ｐ１に断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得させ、計算装置Ｐ２に断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得させる。乱数共有手段は、計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる。第１乗算結果分散手段は、計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させて、計算装置Ｐ０に断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得させ、計算装置Ｐ１に断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得させ、計算装置Ｐ２に断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得させる。乗算結果加算手段は、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｄ０，ｄ１）を取得させ、計算装置Ｐ１に断片（ｄ１，ｄ２）を取得させ、計算装置Ｐ２に断片（ｄ２，ｄ０）を取得させる。第２乗算結果分散手段は、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｅ０，ｅ１）を取得させ、計算装置Ｐ１に断片（ｅ１，ｅ２）を取得させ、計算装置Ｐ２に断片（ｅ２，ｅ０）を取得させる。
【０００７】
乗算確認手段は、計算装置Ｐ１に
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる。もしくは、乗算確認手段は、計算装置Ｐ１に
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる。
【発明の効果】
【０００８】
本発明の秘密計算システムによれば、乱数Ｓを用いて２通りの演算を行い乗算の結果が同じになることを確認するので、乗算の秘密計算での計算装置の不正処理を検知できる。
【図面の簡単な説明】
【０００９】
【図１】本発明の秘密計算システムの機能構成例を示す図。
【図２】実施例１の秘密計算システムの不正検知の処理フローを示す図。
【図３】実施例２の秘密計算システムの不正検知の処理フローを示す図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１１】
図１に実施例１の秘密計算システムの機能構成例を示す。図２に実施例１の秘密計算システムの不正検知の処理フローを示す。実施例１の秘密計算システムは、ネットワーク１０００を介して接続された３つの計算装置１００α、１００β、１００γで構成される。計算装置１００α、１００β、１００γは、数値Ｘの断片（分散された情報）を分散して記録し、秘密計算を行う。各計算装置１００ｙ（ただし、ｙはα、β、もしくはγ）は、データ取得部１１０ｙ、乱数共有部１２０ｙ、第１乗算結果分散部１３０ｙ、乗算結果加算部１４０ｙ、第２乗算結果分散部１５０ｙ、乗算確認部１６０ｙ、記録部１９０ｙを備える。記録部１９０ｙは、断片のデータなどを記録する。秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。データ取得手段は、データ取得部１１０α，１１０β，１１０γで構成される。乱数共有手段は、乱数共有部１２０α，１２０β，１２０γで構成される。第１乗算結果分散手段は、第１乗算結果分散部１３０α，１３０β，１３０γで構成される。乗算結果加算手段は、乗算結果加算部１４０α，１４０β，１４０γで構成される。第２乗算結果分散手段は、第２乗算結果分散部１５０α，１５０β，１５０γで構成される。乗算確認手段は、乗算確認部１６０α，１６０β，１６０γで構成される。
【００１２】
計算装置１００α、１００β、１００γは、まず、計算装置Ｐ０として動作するか、計算装置Ｐ１として動作するか、計算装置Ｐ２として動作するかが決められる。そして、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）と示すことにする。このとき、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
ただし、Ｍは２以上の整数
の関係を満たすとする。なお、計算装置Ｐｎ（ただし、ｎは０，１，２のいずれか）として動作する計算装置の各構成部を、データ取得部１１０ｎ、乱数共有部１２０ｎ、第１乗算結果分散部１３０ｎ、乗算結果加算部１４０ｎ、第２乗算結果分散部１５０ｎ、乗算確認部１６０ｎ、記録部１９０ｎと表記する。
【００１３】
計算装置Ｐ０のデータ取得部１１００が、数値Ａ，Ｂ，Ｃの断片として断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、記録部１９００に記録する。計算装置Ｐ１のデータ取得部１１０１が、数値Ａ，Ｂ，Ｃの断片として断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、記録部１９０１に記録する。計算装置Ｐ２のデータ取得部１１０２が、数値Ａ，Ｂ，Ｃの断片として断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得し、記録部１９０２に記録する（Ｓ１１０）。なお、数値Ａ，Ｂは、装置Ｑと装置Ｒがそれぞれ保持して分散した数値とする。ここで、装置Ｑと装置Ｒとは同一の装置でもよい。また装置Ｑ，Ｒは、計算装置Ｐ０，Ｐ１，Ｐ２のいずれかであってもよいし、異なる装置でもよい。数値Ｃは、計算装置Ｐ０，Ｐ１，Ｐ２の間で
Ｃ＝ＡＢ ｍｏｄ Ｍ
の秘密計算を実行して、断片を計算装置Ｐ０，Ｐ１，Ｐ２が取得した数値である。
【００１４】
計算装置Ｐ１の乱数共有部１２０１と計算装置Ｐ２の乱数共有部１２０２は、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有する（Ｓ１２０）。計算装置Ｐ１の第１乗算結果分散部１３０１はＳａ１を分散し、計算装置Ｐ１の第１乗算結果分散部１３０１または計算装置Ｐ２の第１乗算結果分散部１３０２はＳａ２を分散し、計算装置Ｐ２の第１乗算結果分散部１３０２はＳａ０を分散し、計算装置Ｐ０が断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１が断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２が断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する（Ｓ１３０）。乗算結果加算部１４００、１４０１、１４０２は、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１が断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２が断片（ｄ２，ｄ０）を取得する（Ｓ１４０）。
【００１５】
第２乗算結果分散部１５００、１５０１、１５０２は、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１が断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２が断片（ｅ２，ｅ０）を取得する（Ｓ１５０）。なお、数値Ｄ，Ｅは、上述のように、計算装置Ｐ０，Ｐ１，Ｐ２の間で
Ｄ＝ＳＡ ｍｏｄ Ｍ
Ｅ＝ＤＢ ｍｏｄ Ｍ ＝ＳＡＢ ｍｏｄ Ｍ
の秘密計算を実行して、断片を計算装置Ｐ０，Ｐ１，Ｐ２が取得した数値である。このように計算を行うので、数値Ｄ，Ｅは、計算装置Ｐ０，Ｐ１，Ｐ２のどの装置も知らない数値である。
【００１６】
計算装置Ｐ１の乗算確認部１６０１は、
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２の乗算確認部１６０２は、
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１の乗算確認部１６０１または計算装置Ｐ２の乗算確認部１６０２は、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する（Ｓ１６０）。この式が成り立つ場合には計算装置Ｐ０は不正を行っていないと判断し、成り立たない場合は計算装置Ｐ０が不正を行ったと判断する。もしくは、ステップＳ１６０として、計算装置Ｐ１の乗算確認部１６０１は、
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２の乗算確認部１６０２は、
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１の乗算確認部１６０１または計算装置Ｐ２の乗算確認部１６０２は、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する。そして、この式が成り立つ場合には計算装置Ｐ０は不正を行っていないと判断し、成り立たない場合は計算装置Ｐ０が不正を行ったと判断する。なお、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
の確認を計算装置Ｐ１で行う場合は計算装置Ｐ１は計算装置Ｐ２からｇを受信した上で、計算装置Ｐ２で行う場合は計算装置Ｐ２は計算装置Ｐ１からｆを受信した上で確認を行う。
【００１７】
このように実施例1の秘密計算システムでは、計算装置Ｐ０，Ｐ１，Ｐ２は数値Ａ，Ｂの断片（分散されたデータ）からＣ＝ＡＢの断片を得る際、計算装置Ｐ１，Ｐ２は乱数Ｓを共有し、計算装置Ｐ０，Ｐ１，Ｐ２はＣ＝ＡＢ，Ｄ＝ＳＡ，Ｅ＝ＤＢの断片を得る手続きを行い、計算装置Ｐ１，Ｐ２はＳＣ＝Ｅとなっているかどうか検証し、なっていれば計算装置Ｐ０は正しいと判断し、なっていなければ不正と判断する。つまり、実施例１の秘密計算システムによれば、乱数Ｓを用いて２通りの演算を行い、乗算の結果が同じになることを確認するので、乗算の秘密計算において計算装置Ｐ０の不正処理を検知できる。
［不正が検知できる理由］
次に、上述の乗算の不正検知について補足説明する。
【００１８】
ｆ＋ｇ＝ｅ０＋ｅ１＋ｅ２−Ｓ（ｃ０＋ｃ１＋ｃ２） ｍｏｄ Ｍ
＝ＤＢ−ＳＣ ｍｏｄ Ｍ
＝ＳＡＢ−ＳＣ ｍｏｄ Ｍ
が成り立つから、秘密計算システムが正しく動作すれば
ｆ＋ｇ＝０ ｍｏｄ Ｍ
となる。計算装置Ｐ０が不正データを送信した場合、ｅ０，ｅ１，ｅ２，ｃ０，ｃ１，ｃ２が不正データとなり得る。これをｅ’０，ｅ’１，ｅ’２，ｃ’０，ｃ’１，ｃ’２とおくと、計算装置Ｐ０は
ｆ’＝ｅ’１＋ｅ’２−Ｓｃ’１−Ｓｃ’２ ｍｏｄ Ｍ
ｇ’＝ｅ’０−Ｓｃ’０ ｍｏｄ Ｍ
もしくは、
ｆ’＝ｅ’１−Ｓｃ’１ ｍｏｄ Ｍ
ｇ’＝ｅ’２＋ｅ’０−Ｓｃ’２−Ｓｃ’０ ｍｏｄ Ｍ
について
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
となるようにｅ’０，ｅ’１，ｅ’２，ｃ’０，ｃ’１，ｃ’２を選ぶ必要がある。ここで、本来の値と不正値の差分を
ΔＣ＝Ｃ−（ｃ’０＋ｃ’１＋ｃ’２） ｍｏｄ Ｍ
ΔＥ＝ＳＣ−（ｅ’０＋ｅ’１＋ｅ’２） ｍｏｄ Ｍ
とおくと、
ｆ’＋ｇ’＝（ＳＣ−ΔＥ）−Ｓ（Ｃ−ΔＣ） ｍｏｄ Ｍ
となるから、
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ ⇔ ΔＥ＝ＳΔＣ ｍｏｄ Ｍ
成り立ち、任意のＳについて
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
が成り立つためには
ΔＥ＝ΔＣ＝０
でなければならないので、不正が成立しない。なお、不正が成立するためには、
ΔＥ≠０またはΔＣ≠０として
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
が成り立つ、すなわちΔＥ＝ＳΔＣ ｍｏｄ Ｍが成り立つ必要がある。しかし、計算装置Ｐ０がＳを知らない限り、Ｍが大きく、かつＳとＭの最大公約数が小さければこれは困難である。
【実施例２】
【００１９】
実施例２の秘密計算システムの機能構成も図１に示す。図３に実施例２の秘密計算システムの不正検知の処理フローを示す。実施例１の秘密計算システムとは、各計算装置１００ｙ（ただし、ｙはα、β、もしくはγ）が、減算結果分散部１７０ｙ、減算確認部１８０ｙも備えている点が異なる。また、減算結果分散部１７０α、１７０β、１７０γが減算結果分散手段を構成し、減算確認部１８０α、１８０β、１８０γが減算確認手段を構成する。そして、本実施例では、各計算装置１００ｙを、計算装置Ｐ０，計算装置Ｐ１，計算装置Ｐ２のどれとして動作させるかを変更しながら、不正検知の処理を行う。
【００２０】
計算装置１００αの記録部１９０αが記録する断片を（ｘγα，ｘαβ）、計算装置１００βの記録部１９０βが記録する断片を（ｘαβ，ｘβγ）、計算装置１００γの記録部１９０γが記録する断片を（ｘβγ，ｘγα）とする。また、断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とする。
【００２１】
本実施例のデータ取得手段では、計算装置１００αのデータ取得部１１０αが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得し、計算装置１００βのデータ取得部１１０βが断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得し、計算装置１００γのデータ取得部１１０γが断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得する（Ｓ１１０’）。
【００２２】
まず、計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として動作するように設定する（Ｓ１０１）。そして、断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として、実施例１と同じようにステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。このことにより、計算装置Ｐ０として動作した計算装置１００αが不正をしていないこと（または不正をしたこと）を確認できる。
【００２３】
秘密計算システムは、計算装置を所定の組合せだけ設定したかを確認する（Ｓ１０２）。所定の組合せとは、例えば、（１）計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として動作する組合せ、（２）計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として動作する組合せ、（３）計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として動作する組合せとすればよい。このように計算装置Ｐ０として動作する計算装置を変更することにより、不正検知の対象となる計算装置を変更できる。また、すべての計算装置が計算装置Ｐ０として動作するまで組合せを変更すれば、すべての計算装置を不正検知の対象にできる。
【００２４】
所定の組合せ分の処理が終わっていなければ（ステップＳ１０２がＮｏならば）、計算装置の設定を変更する。本実施例では、計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として動作するように設定する（Ｓ１０３）。そして、断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて、計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として、ステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１である。このことにより、計算装置Ｐ０として動作した計算装置１００γが不正をしていないこと（または不正をしたこと）を確認できる。
【００２５】
さらに、本実施例では、計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として動作するように設定する（Ｓ１０３）。そして、断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて、計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として、ステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０である。このことにより、計算装置Ｐ０として動作した計算装置１００βが不正をしていないこと（または不正をしたこと）を確認できる。
【００２６】
次に、秘密計算システムは、計算装置１００α、１００β、１００γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、減算結果分散部１７００、１７０１、１７０２が
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０が断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１が断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２が断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する（Ｓ１７０）。
減算確認部１８００、１８０１、１８０２が、数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する（Ｓ１８０）。
【００２７】
本実施例の場合、上述のように計算装置Ｐ０として動作する計算装置を変更しながら不正検知の処理を行う。したがって、すべての計算装置が計算装置Ｐ０として動作したときに不正を行っていないこと（または不正を行ったこと）を検知できる。また、計算装置Ｐ１またはＰ２として動作するときに不正を行い、
Ｃ’≠ＡＢ ｍｏｄ Ｍ
または
Ｃ”≠ＡＢ ｍｏｄ Ｍ
となった場合、ステップＳ１８０で不正が検知できる。したがって、実施例２の秘密計算システムによれば、実施例１と同じ効果が得られるだけでなく、乗算の秘密計算において各計算装置の不正処理を検知できる。
【００２８】
［秘密計算］
実施例１、実施例２の説明では、秘密計算については、１つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、本発明の秘密計算システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、計算装置１０００，１００１，１００２が分散して記録する数値Ａの断片を（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）、数値Ｂの断片を（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）、数値Ｃの断片を（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）とする。また、Ｍを２以上の整数とする。
【００２９】
整数Ａの秘密分散
（１）０以上Ｍ未満の整数の乱数ａ０，ａ１を生成する。
（２）ａ２＝Ａ−ａ０−ａ１を計算し、断片を（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）とし、計算装置Ｐ０，Ｐ１，Ｐ２に分散して記録する。
【００３０】
整数Ａの復元
（１）計算装置Ｐ０は計算装置Ｐ１にａ０を送信し、計算装置Ｐ２にａ１を送信する。計算装置Ｐ１は計算装置Ｐ２にａ１を送信し、計算装置Ｐ０にａ２を送信する。計算装置Ｐ２は計算装置Ｐ０にａ２を送信し、計算装置Ｐ１にａ０を送信する。
（２）計算装置Ｐ０は計算装置Ｐ１から受信したａ２と計算装置Ｐ２から受信したａ２とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。計算装置Ｐ１は計算装置Ｐ２から受信したａ０と計算装置Ｐ０から受信したａ０とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。計算装置Ｐ２は計算装置Ｐ０から受信したａ１と計算装置Ｐ１から受信したａ１とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。
【００３１】
整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０＋ｂ０ ｍｏｄ Ｍ，ａ１＋ｂ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１＋ｂ１ ｍｏｄ Ｍ，ａ２＋ｂ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２＋ｂ２ ｍｏｄ Ｍ，ａ０＋ｂ０ ｍｏｄ Ｍ）
を計算して記録する。
【００３２】
整数の減算（Ｃ＝Ａ−Ｂ ｍｏｄ Ｍ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０−ｂ０ ｍｏｄ Ｍ，ａ１−ｂ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１−ｂ１ ｍｏｄ Ｍ，ａ２−ｂ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２−ｂ２ ｍｏｄ Ｍ，ａ０−ｂ０ ｍｏｄ Ｍ）
を計算して記録する。
【００３３】
整数の加算（Ｃ＝Ａ＋Ｓ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０＋Ｓ ｍｏｄ Ｍ，ａ１）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２，ａ０＋Ｓ ｍｏｄ Ｍ）
を計算して記録する。計算装置Ｐ１の処理はない。
【００３４】
整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０Ｓ ｍｏｄ Ｍ，ａ１Ｓ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１Ｓ ｍｏｄ Ｍ，ａ２Ｓ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２Ｓ ｍｏｄ Ｍ，ａ０Ｓ ｍｏｄ Ｍ）
を計算して記録する。
【００３５】
整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算
（１）計算装置Ｐ０は、０以上Ｍ未満の整数の乱数ｒ１，ｒ２，ｃ０を生成し、
ｃ１＝（ａ０＋ａ１）（ｂ０＋ｂ１）−ｒ１−ｒ２−ｃ０ ｍｏｄ Ｍ
を計算する。そして、計算装置Ｐ０は、計算装置Ｐ１に（ｒ１，ｃ１）を、計算装置Ｐ２に（ｒ２，ｃ０）を送信する。
（２）計算装置Ｐ１は、
ｙ＝ａ１ｂ２＋ａ２ｂ１＋ｒ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２に送信する。
（３）計算装置Ｐ２は、
ｚ＝ａ２ｂ０＋ａ０ｂ２＋ｒ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ０に送信する。
（４）計算装置Ｐ１と計算装置Ｐ２は、それぞれ
ｃ２＝ｙ＋ｚ＋ａ２ｂ２ ｍｏｄ Ｍ
を計算する。
（５）計算装置Ｐ０は（ｃ０，ｃ１）を記録し、計算装置Ｐ１は（ｃ１，ｃ２）を記録し、計算装置Ｐ２は（ｃ２，ｃ０）を記録する。
【００３６】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（１−ａ０，−ａ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（−ａ１ ｍｏｄ Ｍ，−ａ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（−ａ２ ｍｏｄ Ｍ，１−ａ０）
を計算して記録する。
【００３７】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行う。
【００３８】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、計算装置Ｐ０が断片（ｃ０’，ｃ１’）を、計算装置Ｐ１が断片（ｃ１’，ｃ２’）を、計算装置Ｐ２が断片（ｃ２’，ｃ０’）を記録する。また、計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、計算装置Ｐ０が断片（ｃ０”，ｃ１”）を、計算装置Ｐ１が断片（ｃ１”，ｃ２”）を、計算装置Ｐ２が断片（ｃ２”，ｃ０”）を記録する。
（２）計算装置Ｐ０，Ｐ１，Ｐ２は、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、計算装置Ｐ０が断片（ｃ０’’’，ｃ１’’’）を、計算装置Ｐ１が断片（ｃ１’’’，ｃ２’’’）を、計算装置Ｐ２が断片（ｃ２’’’，ｃ０’’’）を記録する。
（３）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、計算装置Ｐ０が断片（ｃ０，ｃ１）を、計算装置Ｐ１が断片（ｃ１，ｃ２）を、計算装置Ｐ２が断片（ｃ２，ｃ０）を記録する。
【００３９】
ビットの排他的論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、計算装置Ｐ０が断片（ｃ０’，ｃ１’）を、計算装置Ｐ１が断片（ｃ１’，ｃ２’）を、計算装置Ｐ２が断片（ｃ２’，ｃ０’）を記録する。また、計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、計算装置Ｐ０が断片（ｃ０”，ｃ１”）を、計算装置Ｐ１が断片（ｃ１”，ｃ２”）を、計算装置Ｐ２が断片（ｃ２”，ｃ０”）を記録する。
（２）計算装置Ｐ０，Ｐ１，Ｐ２は、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、計算装置Ｐ０が断片（ｃ０’’’，ｃ１’’’）を、計算装置Ｐ１が断片（ｃ１’’’，ｃ２’’’）を、計算装置Ｐ２が断片（ｃ２’’’，ｃ０’’’）を記録する。
（３）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、計算装置Ｐ０が断片（ｃ０，ｃ１）を、計算装置Ｐ１が断片（ｃ１，ｃ２）を、計算装置Ｐ２が断片（ｃ２，ｃ０）を記録する。
【００４０】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００４１】
【数１】
【００４２】
を求めることである。また、計算装置１０００，１００１，１００２が分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）０，ａ（ｎ）１）、（ａ（ｎ）１，ａ（ｎ）２）、（ａ（ｎ）２，ａ（ｎ）０）とする。計算装置１０００は、
【００４３】
【数２】
【００４４】
を計算して記録し、計算装置Ｐ１は
【００４５】
【数３】
【００４６】
を計算して記録し、計算装置Ｐ２は
【００４７】
【数４】
【００４８】
を計算して記録する。
【００４９】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、計算装置１００１が（ａ１＋ａ２ ｍｏｄ Ｍ）（ｎ）を秘密分散し、計算装置１０００，１００１，１００２が（ａ１＋ａ２ ｍｏｄ Ｍ）（ｎ）の断片（ｂ（ｎ）０，ｂ（ｎ）１）、（ｂ（ｎ）１，ｂ（ｎ）２）、（ｂ（ｎ）２，ｂ（ｎ）０）を分散して記録する。ｎ＝０からＮ−１について、計算装置１００２が（ａ０）（ｎ）を秘密分散し、計算装置１０００，１００１，１００２が（ａ０）（ｎ）の断片（（ａ０）（ｎ）０，（ａ０）（ｎ）１）、（（ａ０）（ｎ）１，（ａ０）（ｎ）２）、（（ａ０）（ｎ）２，（ａ０）（ｎ）０）を分散して記録する。
（２）ｃ０＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａ０）（ｎ）−２ｂ（ｎ）（ａ０）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａ０）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａ０）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【００５０】
整数Ａの分散データの検証
計算装置Ｐ０は、計算装置Ｐ１から受信したａ１と自身が記録していたａ１が等しいこと、計算装置Ｐ２から受信したａ０と自身が記録していたａ０が等しいことを検証する。計算装置Ｐ１は、計算装置Ｐ２から受信したａ２と自身が記録していたａ２が等しいこと、計算装置Ｐ０から受信したａ１と自身が記録していたａ１が等しいことを検証する。計算装置Ｐ２は、計算装置Ｐ０から受信したａ０と自身が記録していたａ０が等しいこと、計算装置Ｐ１から受信したａ２と自身が記録していたａ２が等しいことを検証する。すべての検証が成功すればtrueを出力し、いずれかの検証が失敗すればfalseを出力する。
【００５１】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５４】
１００ 計算装置 １１０ データ取得部
１２０ 乱数共有部 １３０ 第１乗算結果分散部
１４０ 乗算結果加算部 １５０ 第２乗算結果分散部
１６０ 乗算確認部 １７０ 減算結果分散部
１８０ 減算確認部 １９０ 記録部
１０００ ネットワーク
【技術分野】
【０００１】
本発明は暗号技術に関し、暗号化された二つの数値を復元すること無く当該数値の乗算結果の暗号文（断片）を得るときの不正検知方法、不正検知機能を有する秘密計算システム、計算装置、および計算プログラムに関する。
【背景技術】
【０００２】
暗号化された数値を復元すること無く特定の演算結果を得る方法（以降、このような計算を秘密計算と呼ぶ）として、例えば非特許文献１に記載された方法がある。この方法は、３つの計算装置に１つ以上の数値を分散させて記録する（以降、分散された情報を断片と呼ぶ）。そして、分散された数値を復元すること無く、加減算，定数和，乗算，定数倍，論理演算(否定，論理積，論理和，排他的論理和)，データ形式変換(整数, 二進数)の結果を３つの計算装置に分散保持させることができる(なお、定数とは既知の数値を意味している)。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司，五十嵐大，高橋克巳，“効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察”，第48回情報処理学会研究報告，CSEC, pp.1-7, 2010，3月.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術は乗算の秘密計算においていずれかの計算装置が不正処理を行った場合にそれを検知できない場合がある。本発明は、乗算の秘密計算での計算装置の不正処理を検知できる秘密計算システムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の秘密計算システムは、数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う。Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとする。
【０００６】
秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。データ取得手段は、数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０に断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得させ、計算装置Ｐ１に断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得させ、計算装置Ｐ２に断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得させる。乱数共有手段は、計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる。第１乗算結果分散手段は、計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させて、計算装置Ｐ０に断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得させ、計算装置Ｐ１に断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得させ、計算装置Ｐ２に断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得させる。乗算結果加算手段は、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｄ０，ｄ１）を取得させ、計算装置Ｐ１に断片（ｄ１，ｄ２）を取得させ、計算装置Ｐ２に断片（ｄ２，ｄ０）を取得させる。第２乗算結果分散手段は、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｅ０，ｅ１）を取得させ、計算装置Ｐ１に断片（ｅ１，ｅ２）を取得させ、計算装置Ｐ２に断片（ｅ２，ｅ０）を取得させる。
【０００７】
乗算確認手段は、計算装置Ｐ１に
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる。もしくは、乗算確認手段は、計算装置Ｐ１に
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる。
【発明の効果】
【０００８】
本発明の秘密計算システムによれば、乱数Ｓを用いて２通りの演算を行い乗算の結果が同じになることを確認するので、乗算の秘密計算での計算装置の不正処理を検知できる。
【図面の簡単な説明】
【０００９】
【図１】本発明の秘密計算システムの機能構成例を示す図。
【図２】実施例１の秘密計算システムの不正検知の処理フローを示す図。
【図３】実施例２の秘密計算システムの不正検知の処理フローを示す図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１１】
図１に実施例１の秘密計算システムの機能構成例を示す。図２に実施例１の秘密計算システムの不正検知の処理フローを示す。実施例１の秘密計算システムは、ネットワーク１０００を介して接続された３つの計算装置１００α、１００β、１００γで構成される。計算装置１００α、１００β、１００γは、数値Ｘの断片（分散された情報）を分散して記録し、秘密計算を行う。各計算装置１００ｙ（ただし、ｙはα、β、もしくはγ）は、データ取得部１１０ｙ、乱数共有部１２０ｙ、第１乗算結果分散部１３０ｙ、乗算結果加算部１４０ｙ、第２乗算結果分散部１５０ｙ、乗算確認部１６０ｙ、記録部１９０ｙを備える。記録部１９０ｙは、断片のデータなどを記録する。秘密計算システムは、データ取得手段、乱数共有手段、第１乗算結果分散手段、乗算結果加算手段、第２乗算結果分散手段、乗算確認手段を備える。データ取得手段は、データ取得部１１０α，１１０β，１１０γで構成される。乱数共有手段は、乱数共有部１２０α，１２０β，１２０γで構成される。第１乗算結果分散手段は、第１乗算結果分散部１３０α，１３０β，１３０γで構成される。乗算結果加算手段は、乗算結果加算部１４０α，１４０β，１４０γで構成される。第２乗算結果分散手段は、第２乗算結果分散部１５０α，１５０β，１５０γで構成される。乗算確認手段は、乗算確認部１６０α，１６０β，１６０γで構成される。
【００１２】
計算装置１００α、１００β、１００γは、まず、計算装置Ｐ０として動作するか、計算装置Ｐ１として動作するか、計算装置Ｐ２として動作するかが決められる。そして、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）と示すことにする。このとき、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
ただし、Ｍは２以上の整数
の関係を満たすとする。なお、計算装置Ｐｎ（ただし、ｎは０，１，２のいずれか）として動作する計算装置の各構成部を、データ取得部１１０ｎ、乱数共有部１２０ｎ、第１乗算結果分散部１３０ｎ、乗算結果加算部１４０ｎ、第２乗算結果分散部１５０ｎ、乗算確認部１６０ｎ、記録部１９０ｎと表記する。
【００１３】
計算装置Ｐ０のデータ取得部１１００が、数値Ａ，Ｂ，Ｃの断片として断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、記録部１９００に記録する。計算装置Ｐ１のデータ取得部１１０１が、数値Ａ，Ｂ，Ｃの断片として断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、記録部１９０１に記録する。計算装置Ｐ２のデータ取得部１１０２が、数値Ａ，Ｂ，Ｃの断片として断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得し、記録部１９０２に記録する（Ｓ１１０）。なお、数値Ａ，Ｂは、装置Ｑと装置Ｒがそれぞれ保持して分散した数値とする。ここで、装置Ｑと装置Ｒとは同一の装置でもよい。また装置Ｑ，Ｒは、計算装置Ｐ０，Ｐ１，Ｐ２のいずれかであってもよいし、異なる装置でもよい。数値Ｃは、計算装置Ｐ０，Ｐ１，Ｐ２の間で
Ｃ＝ＡＢ ｍｏｄ Ｍ
の秘密計算を実行して、断片を計算装置Ｐ０，Ｐ１，Ｐ２が取得した数値である。
【００１４】
計算装置Ｐ１の乱数共有部１２０１と計算装置Ｐ２の乱数共有部１２０２は、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有する（Ｓ１２０）。計算装置Ｐ１の第１乗算結果分散部１３０１はＳａ１を分散し、計算装置Ｐ１の第１乗算結果分散部１３０１または計算装置Ｐ２の第１乗算結果分散部１３０２はＳａ２を分散し、計算装置Ｐ２の第１乗算結果分散部１３０２はＳａ０を分散し、計算装置Ｐ０が断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１が断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２が断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する（Ｓ１３０）。乗算結果加算部１４００、１４０１、１４０２は、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１が断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２が断片（ｄ２，ｄ０）を取得する（Ｓ１４０）。
【００１５】
第２乗算結果分散部１５００、１５０１、１５０２は、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１が断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２が断片（ｅ２，ｅ０）を取得する（Ｓ１５０）。なお、数値Ｄ，Ｅは、上述のように、計算装置Ｐ０，Ｐ１，Ｐ２の間で
Ｄ＝ＳＡ ｍｏｄ Ｍ
Ｅ＝ＤＢ ｍｏｄ Ｍ ＝ＳＡＢ ｍｏｄ Ｍ
の秘密計算を実行して、断片を計算装置Ｐ０，Ｐ１，Ｐ２が取得した数値である。このように計算を行うので、数値Ｄ，Ｅは、計算装置Ｐ０，Ｐ１，Ｐ２のどの装置も知らない数値である。
【００１６】
計算装置Ｐ１の乗算確認部１６０１は、
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２の乗算確認部１６０２は、
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１の乗算確認部１６０１または計算装置Ｐ２の乗算確認部１６０２は、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する（Ｓ１６０）。この式が成り立つ場合には計算装置Ｐ０は不正を行っていないと判断し、成り立たない場合は計算装置Ｐ０が不正を行ったと判断する。もしくは、ステップＳ１６０として、計算装置Ｐ１の乗算確認部１６０１は、
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２の乗算確認部１６０２は、
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１の乗算確認部１６０１または計算装置Ｐ２の乗算確認部１６０２は、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する。そして、この式が成り立つ場合には計算装置Ｐ０は不正を行っていないと判断し、成り立たない場合は計算装置Ｐ０が不正を行ったと判断する。なお、
ｆ＋ｇ＝０ ｍｏｄ Ｍ
の確認を計算装置Ｐ１で行う場合は計算装置Ｐ１は計算装置Ｐ２からｇを受信した上で、計算装置Ｐ２で行う場合は計算装置Ｐ２は計算装置Ｐ１からｆを受信した上で確認を行う。
【００１７】
このように実施例1の秘密計算システムでは、計算装置Ｐ０，Ｐ１，Ｐ２は数値Ａ，Ｂの断片（分散されたデータ）からＣ＝ＡＢの断片を得る際、計算装置Ｐ１，Ｐ２は乱数Ｓを共有し、計算装置Ｐ０，Ｐ１，Ｐ２はＣ＝ＡＢ，Ｄ＝ＳＡ，Ｅ＝ＤＢの断片を得る手続きを行い、計算装置Ｐ１，Ｐ２はＳＣ＝Ｅとなっているかどうか検証し、なっていれば計算装置Ｐ０は正しいと判断し、なっていなければ不正と判断する。つまり、実施例１の秘密計算システムによれば、乱数Ｓを用いて２通りの演算を行い、乗算の結果が同じになることを確認するので、乗算の秘密計算において計算装置Ｐ０の不正処理を検知できる。
［不正が検知できる理由］
次に、上述の乗算の不正検知について補足説明する。
【００１８】
ｆ＋ｇ＝ｅ０＋ｅ１＋ｅ２−Ｓ（ｃ０＋ｃ１＋ｃ２） ｍｏｄ Ｍ
＝ＤＢ−ＳＣ ｍｏｄ Ｍ
＝ＳＡＢ−ＳＣ ｍｏｄ Ｍ
が成り立つから、秘密計算システムが正しく動作すれば
ｆ＋ｇ＝０ ｍｏｄ Ｍ
となる。計算装置Ｐ０が不正データを送信した場合、ｅ０，ｅ１，ｅ２，ｃ０，ｃ１，ｃ２が不正データとなり得る。これをｅ’０，ｅ’１，ｅ’２，ｃ’０，ｃ’１，ｃ’２とおくと、計算装置Ｐ０は
ｆ’＝ｅ’１＋ｅ’２−Ｓｃ’１−Ｓｃ’２ ｍｏｄ Ｍ
ｇ’＝ｅ’０−Ｓｃ’０ ｍｏｄ Ｍ
もしくは、
ｆ’＝ｅ’１−Ｓｃ’１ ｍｏｄ Ｍ
ｇ’＝ｅ’２＋ｅ’０−Ｓｃ’２−Ｓｃ’０ ｍｏｄ Ｍ
について
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
となるようにｅ’０，ｅ’１，ｅ’２，ｃ’０，ｃ’１，ｃ’２を選ぶ必要がある。ここで、本来の値と不正値の差分を
ΔＣ＝Ｃ−（ｃ’０＋ｃ’１＋ｃ’２） ｍｏｄ Ｍ
ΔＥ＝ＳＣ−（ｅ’０＋ｅ’１＋ｅ’２） ｍｏｄ Ｍ
とおくと、
ｆ’＋ｇ’＝（ＳＣ−ΔＥ）−Ｓ（Ｃ−ΔＣ） ｍｏｄ Ｍ
となるから、
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ ⇔ ΔＥ＝ＳΔＣ ｍｏｄ Ｍ
成り立ち、任意のＳについて
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
が成り立つためには
ΔＥ＝ΔＣ＝０
でなければならないので、不正が成立しない。なお、不正が成立するためには、
ΔＥ≠０またはΔＣ≠０として
ｆ’＋ｇ’＝０ ｍｏｄ Ｍ
が成り立つ、すなわちΔＥ＝ＳΔＣ ｍｏｄ Ｍが成り立つ必要がある。しかし、計算装置Ｐ０がＳを知らない限り、Ｍが大きく、かつＳとＭの最大公約数が小さければこれは困難である。
【実施例２】
【００１９】
実施例２の秘密計算システムの機能構成も図１に示す。図３に実施例２の秘密計算システムの不正検知の処理フローを示す。実施例１の秘密計算システムとは、各計算装置１００ｙ（ただし、ｙはα、β、もしくはγ）が、減算結果分散部１７０ｙ、減算確認部１８０ｙも備えている点が異なる。また、減算結果分散部１７０α、１７０β、１７０γが減算結果分散手段を構成し、減算確認部１８０α、１８０β、１８０γが減算確認手段を構成する。そして、本実施例では、各計算装置１００ｙを、計算装置Ｐ０，計算装置Ｐ１，計算装置Ｐ２のどれとして動作させるかを変更しながら、不正検知の処理を行う。
【００２０】
計算装置１００αの記録部１９０αが記録する断片を（ｘγα，ｘαβ）、計算装置１００βの記録部１９０βが記録する断片を（ｘαβ，ｘβγ）、計算装置１００γの記録部１９０γが記録する断片を（ｘβγ，ｘγα）とする。また、断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とする。
【００２１】
本実施例のデータ取得手段では、計算装置１００αのデータ取得部１１０αが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得し、計算装置１００βのデータ取得部１１０βが断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得し、計算装置１００γのデータ取得部１１０γが断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得する（Ｓ１１０’）。
【００２２】
まず、計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として動作するように設定する（Ｓ１０１）。そして、断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として、実施例１と同じようにステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。このことにより、計算装置Ｐ０として動作した計算装置１００αが不正をしていないこと（または不正をしたこと）を確認できる。
【００２３】
秘密計算システムは、計算装置を所定の組合せだけ設定したかを確認する（Ｓ１０２）。所定の組合せとは、例えば、（１）計算装置１００αが計算装置Ｐ０として、計算装置１００βが計算装置Ｐ１として、計算装置１００γが計算装置Ｐ２として動作する組合せ、（２）計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として動作する組合せ、（３）計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として動作する組合せとすればよい。このように計算装置Ｐ０として動作する計算装置を変更することにより、不正検知の対象となる計算装置を変更できる。また、すべての計算装置が計算装置Ｐ０として動作するまで組合せを変更すれば、すべての計算装置を不正検知の対象にできる。
【００２４】
所定の組合せ分の処理が終わっていなければ（ステップＳ１０２がＮｏならば）、計算装置の設定を変更する。本実施例では、計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として動作するように設定する（Ｓ１０３）。そして、断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて、計算装置１００αが計算装置Ｐ１として、計算装置１００βが計算装置Ｐ２として、計算装置１００γが計算装置Ｐ０として、ステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１である。このことにより、計算装置Ｐ０として動作した計算装置１００γが不正をしていないこと（または不正をしたこと）を確認できる。
【００２５】
さらに、本実施例では、計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として動作するように設定する（Ｓ１０３）。そして、断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて、計算装置１００αが計算装置Ｐ２として、計算装置１００βが計算装置Ｐ０として、計算装置１００γが計算装置Ｐ１として、ステップＳ１２０（乱数共有ステップ）、ステップＳ１３０（第１乗算結果分散ステップ）、ステップＳ１４０（乗算結果加算ステップ）、ステップＳ１５０（第２乗算結果分散ステップ）、ステップＳ１６０（乗算確認ステップ）を実行する。ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０である。このことにより、計算装置Ｐ０として動作した計算装置１００βが不正をしていないこと（または不正をしたこと）を確認できる。
【００２６】
次に、秘密計算システムは、計算装置１００α、１００β、１００γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、減算結果分散部１７００、１７０１、１７０２が
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０が断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１が断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２が断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する（Ｓ１７０）。
減算確認部１８００、１８０１、１８０２が、数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する（Ｓ１８０）。
【００２７】
本実施例の場合、上述のように計算装置Ｐ０として動作する計算装置を変更しながら不正検知の処理を行う。したがって、すべての計算装置が計算装置Ｐ０として動作したときに不正を行っていないこと（または不正を行ったこと）を検知できる。また、計算装置Ｐ１またはＰ２として動作するときに不正を行い、
Ｃ’≠ＡＢ ｍｏｄ Ｍ
または
Ｃ”≠ＡＢ ｍｏｄ Ｍ
となった場合、ステップＳ１８０で不正が検知できる。したがって、実施例２の秘密計算システムによれば、実施例１と同じ効果が得られるだけでなく、乗算の秘密計算において各計算装置の不正処理を検知できる。
【００２８】
［秘密計算］
実施例１、実施例２の説明では、秘密計算については、１つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、本発明の秘密計算システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、計算装置１０００，１００１，１００２が分散して記録する数値Ａの断片を（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）、数値Ｂの断片を（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）、数値Ｃの断片を（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）とする。また、Ｍを２以上の整数とする。
【００２９】
整数Ａの秘密分散
（１）０以上Ｍ未満の整数の乱数ａ０，ａ１を生成する。
（２）ａ２＝Ａ−ａ０−ａ１を計算し、断片を（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）とし、計算装置Ｐ０，Ｐ１，Ｐ２に分散して記録する。
【００３０】
整数Ａの復元
（１）計算装置Ｐ０は計算装置Ｐ１にａ０を送信し、計算装置Ｐ２にａ１を送信する。計算装置Ｐ１は計算装置Ｐ２にａ１を送信し、計算装置Ｐ０にａ２を送信する。計算装置Ｐ２は計算装置Ｐ０にａ２を送信し、計算装置Ｐ１にａ０を送信する。
（２）計算装置Ｐ０は計算装置Ｐ１から受信したａ２と計算装置Ｐ２から受信したａ２とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。計算装置Ｐ１は計算装置Ｐ２から受信したａ０と計算装置Ｐ０から受信したａ０とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。計算装置Ｐ２は計算装置Ｐ０から受信したａ１と計算装置Ｐ１から受信したａ１とが一致していれば、
ａ０＋ａ１＋ａ２ ｍｏｄ Ｍ
を計算して数値Ａを復元する。
【００３１】
整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０＋ｂ０ ｍｏｄ Ｍ，ａ１＋ｂ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１＋ｂ１ ｍｏｄ Ｍ，ａ２＋ｂ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２＋ｂ２ ｍｏｄ Ｍ，ａ０＋ｂ０ ｍｏｄ Ｍ）
を計算して記録する。
【００３２】
整数の減算（Ｃ＝Ａ−Ｂ ｍｏｄ Ｍ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０−ｂ０ ｍｏｄ Ｍ，ａ１−ｂ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１−ｂ１ ｍｏｄ Ｍ，ａ２−ｂ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２−ｂ２ ｍｏｄ Ｍ，ａ０−ｂ０ ｍｏｄ Ｍ）
を計算して記録する。
【００３３】
整数の加算（Ｃ＝Ａ＋Ｓ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０＋Ｓ ｍｏｄ Ｍ，ａ１）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２，ａ０＋Ｓ ｍｏｄ Ｍ）
を計算して記録する。計算装置Ｐ１の処理はない。
【００３４】
整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）
計算装置Ｐ０は
（ｃ０，ｃ１）＝（ａ０Ｓ ｍｏｄ Ｍ，ａ１Ｓ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（ａ１Ｓ ｍｏｄ Ｍ，ａ２Ｓ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（ａ２Ｓ ｍｏｄ Ｍ，ａ０Ｓ ｍｏｄ Ｍ）
を計算して記録する。
【００３５】
整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算
（１）計算装置Ｐ０は、０以上Ｍ未満の整数の乱数ｒ１，ｒ２，ｃ０を生成し、
ｃ１＝（ａ０＋ａ１）（ｂ０＋ｂ１）−ｒ１−ｒ２−ｃ０ ｍｏｄ Ｍ
を計算する。そして、計算装置Ｐ０は、計算装置Ｐ１に（ｒ１，ｃ１）を、計算装置Ｐ２に（ｒ２，ｃ０）を送信する。
（２）計算装置Ｐ１は、
ｙ＝ａ１ｂ２＋ａ２ｂ１＋ｒ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２に送信する。
（３）計算装置Ｐ２は、
ｚ＝ａ２ｂ０＋ａ０ｂ２＋ｒ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ０に送信する。
（４）計算装置Ｐ１と計算装置Ｐ２は、それぞれ
ｃ２＝ｙ＋ｚ＋ａ２ｂ２ ｍｏｄ Ｍ
を計算する。
（５）計算装置Ｐ０は（ｃ０，ｃ１）を記録し、計算装置Ｐ１は（ｃ１，ｃ２）を記録し、計算装置Ｐ２は（ｃ２，ｃ０）を記録する。
【００３６】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
計算装置Ｐ０は
（ｃ０，ｃ１）＝（１−ａ０，−ａ１ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ１は
（ｃ１，ｃ２）＝（−ａ１ ｍｏｄ Ｍ，−ａ２ ｍｏｄ Ｍ）
を計算して記録し、計算装置Ｐ２は
（ｃ２，ｃ０）＝（−ａ２ ｍｏｄ Ｍ，１−ａ０）
を計算して記録する。
【００３７】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行う。
【００３８】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、計算装置Ｐ０が断片（ｃ０’，ｃ１’）を、計算装置Ｐ１が断片（ｃ１’，ｃ２’）を、計算装置Ｐ２が断片（ｃ２’，ｃ０’）を記録する。また、計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、計算装置Ｐ０が断片（ｃ０”，ｃ１”）を、計算装置Ｐ１が断片（ｃ１”，ｃ２”）を、計算装置Ｐ２が断片（ｃ２”，ｃ０”）を記録する。
（２）計算装置Ｐ０，Ｐ１，Ｐ２は、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、計算装置Ｐ０が断片（ｃ０’’’，ｃ１’’’）を、計算装置Ｐ１が断片（ｃ１’’’，ｃ２’’’）を、計算装置Ｐ２が断片（ｃ２’’’，ｃ０’’’）を記録する。
（３）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、計算装置Ｐ０が断片（ｃ０，ｃ１）を、計算装置Ｐ１が断片（ｃ１，ｃ２）を、計算装置Ｐ２が断片（ｃ２，ｃ０）を記録する。
【００３９】
ビットの排他的論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、計算装置Ｐ０が断片（ｃ０’，ｃ１’）を、計算装置Ｐ１が断片（ｃ１’，ｃ２’）を、計算装置Ｐ２が断片（ｃ２’，ｃ０’）を記録する。また、計算装置Ｐ０，Ｐ１，Ｐ２は、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、計算装置Ｐ０が断片（ｃ０”，ｃ１”）を、計算装置Ｐ１が断片（ｃ１”，ｃ２”）を、計算装置Ｐ２が断片（ｃ２”，ｃ０”）を記録する。
（２）計算装置Ｐ０，Ｐ１，Ｐ２は、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｍ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、計算装置Ｐ０が断片（ｃ０’’’，ｃ１’’’）を、計算装置Ｐ１が断片（ｃ１’’’，ｃ２’’’）を、計算装置Ｐ２が断片（ｃ２’’’，ｃ０’’’）を記録する。
（３）計算装置Ｐ０，Ｐ１，Ｐ２は、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｍ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、計算装置Ｐ０が断片（ｃ０，ｃ１）を、計算装置Ｐ１が断片（ｃ１，ｃ２）を、計算装置Ｐ２が断片（ｃ２，ｃ０）を記録する。
【００４０】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００４１】
【数１】
【００４２】
を求めることである。また、計算装置１０００，１００１，１００２が分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）０，ａ（ｎ）１）、（ａ（ｎ）１，ａ（ｎ）２）、（ａ（ｎ）２，ａ（ｎ）０）とする。計算装置１０００は、
【００４３】
【数２】
【００４４】
を計算して記録し、計算装置Ｐ１は
【００４５】
【数３】
【００４６】
を計算して記録し、計算装置Ｐ２は
【００４７】
【数４】
【００４８】
を計算して記録する。
【００４９】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、計算装置１００１が（ａ１＋ａ２ ｍｏｄ Ｍ）（ｎ）を秘密分散し、計算装置１０００，１００１，１００２が（ａ１＋ａ２ ｍｏｄ Ｍ）（ｎ）の断片（ｂ（ｎ）０，ｂ（ｎ）１）、（ｂ（ｎ）１，ｂ（ｎ）２）、（ｂ（ｎ）２，ｂ（ｎ）０）を分散して記録する。ｎ＝０からＮ−１について、計算装置１００２が（ａ０）（ｎ）を秘密分散し、計算装置１０００，１００１，１００２が（ａ０）（ｎ）の断片（（ａ０）（ｎ）０，（ａ０）（ｎ）１）、（（ａ０）（ｎ）１，（ａ０）（ｎ）２）、（（ａ０）（ｎ）２，（ａ０）（ｎ）０）を分散して記録する。
（２）ｃ０＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａ０）（ｎ）−２ｂ（ｎ）（ａ０）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａ０）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａ０）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【００５０】
整数Ａの分散データの検証
計算装置Ｐ０は、計算装置Ｐ１から受信したａ１と自身が記録していたａ１が等しいこと、計算装置Ｐ２から受信したａ０と自身が記録していたａ０が等しいことを検証する。計算装置Ｐ１は、計算装置Ｐ２から受信したａ２と自身が記録していたａ２が等しいこと、計算装置Ｐ０から受信したａ１と自身が記録していたａ１が等しいことを検証する。計算装置Ｐ２は、計算装置Ｐ０から受信したａ０と自身が記録していたａ０が等しいこと、計算装置Ｐ１から受信したａ２と自身が記録していたａ２が等しいことを検証する。すべての検証が成功すればtrueを出力し、いずれかの検証が失敗すればfalseを出力する。
【００５１】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５４】
１００ 計算装置 １１０ データ取得部
１２０ 乱数共有部 １３０ 第１乗算結果分散部
１４０ 乗算結果加算部 １５０ 第２乗算結果分散部
１６０ 乗算確認部 １７０ 減算結果分散部
１８０ 減算確認部 １９０ 記録部
１０００ ネットワーク
【特許請求の範囲】
【請求項１】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムを用いてＣ＝ＡＢの秘密計算での不正を検知する不正検知方法であって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０が断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、計算装置Ｐ１が断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、計算装置Ｐ２が断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得するデータ取得ステップと、
計算装置Ｐ１と計算装置Ｐ２が、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有する乱数共有ステップと、
計算装置Ｐ１がＳａ１を分散し、計算装置Ｐ１または計算装置Ｐ２がＳａ２を分散し、計算装置Ｐ２がＳａ０を分散して、計算装置Ｐ０が断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１が断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２が断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する第１乗算結果分散ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１が断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２が断片（ｄ２，ｄ０）を取得する乗算結果加算ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１が断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２が断片（ｅ２，ｅ０）を取得する第２乗算結果分散ステップと、
計算装置Ｐ１が
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２が
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２が
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する、もしくは、
計算装置Ｐ１が
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２が
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２が
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する乗算確認ステップと、
を有する不正検知方法。
【請求項２】
請求項１記載の不正検知方法であって、
計算装置αが記録する断片を（ｘγα，ｘαβ）、計算装置βが記録する断片を（ｘαβ，ｘβγ）、計算装置γが記録する断片を（ｘβγ，ｘγα）とし、
断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とし、
前記データ取得ステップは、計算装置αが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得し、計算装置βが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得し、計算装置γが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得するステップであり、
断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて（ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１）、計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて（ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０）、計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
計算装置α、β、γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０が断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１が断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２が断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する減算結果分散ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認ステップと、
を有することを特徴とする不正検知方法。
【請求項３】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムであって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０に断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得させ、計算装置Ｐ１に断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得させ、計算装置Ｐ２に断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得させるデータ取得手段と、
計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる乱数共有手段と、
計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させて、計算装置Ｐ０に断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得させ、計算装置Ｐ１に断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得させ、計算装置Ｐ２に断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得させる第１乗算結果分散手段と、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｄ０，ｄ１）を取得させ、計算装置Ｐ１に断片（ｄ１，ｄ２）を取得させ、計算装置Ｐ２に断片（ｄ２，ｄ０）を取得させる乗算結果加算手段と、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｅ０，ｅ１）を取得させ、計算装置Ｐ１に断片（ｅ１，ｅ２）を取得させ、計算装置Ｐ２に断片（ｅ２，ｅ０）を取得させる第２乗算結果分散手段と、
計算装置Ｐ１に
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる、もしくは、
計算装置Ｐ１に
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる乗算確認手段と、
を有する秘密計算システム。
【請求項４】
請求項３記載の秘密計算システムであって、
計算装置αが記録する断片を（ｘγα，ｘαβ）、計算装置βが記録する断片を（ｘαβ，ｘβγ）、計算装置γが記録する断片を（ｘβγ，ｘγα）とし、
断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とし、
前記データ取得手段は、計算装置αに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得させ、計算装置βに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得させ、計算装置γに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得させる手段であり、
断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて（ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１）、計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて（ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０）、計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
計算装置α、β、γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０に断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得させ、計算装置Ｐ１に断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得させ、計算装置Ｐ２に断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得させる減算結果分散手段と、
数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認手段と、
を備える秘密計算システム。
【請求項５】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムの計算装置であって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０として動作するときは断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、計算装置Ｐ１として動作するときは断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、計算装置Ｐ２として動作するときは断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得するデータ取得部と、
計算装置Ｐ１として動作するときは、ランダムに選んだ２以上Ｍ以下の整数Ｓを計算装置Ｐ２と共有し、計算装置Ｐ２として動作するときは、ランダムに選んだ２以上Ｍ以下の整数Ｓを計算装置Ｐ１と共有する乱数共有部と、
計算装置Ｐ１として動作するときはＳａ１を分散し、計算装置Ｐ１または計算装置Ｐ２として動作するときはＳａ２を分散し、計算装置Ｐ２として動作するときはＳａ０を分散し、計算装置Ｐ０として動作するときは断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１として動作するときは断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２として動作するときは断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する第１乗算結果分散部と、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０として動作するときは断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１として動作するときは断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２として動作するときは断片（ｄ２，ｄ０）を取得する乗算結果加算部と、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０として動作するときは断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１として動作するときは断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２として動作するときは断片（ｅ２，ｅ０）を取得する第２乗算結果分散部と、
計算装置Ｐ１として動作するときは
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２として動作するときは
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２として動作するときは
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する、もしくは、
計算装置Ｐ１として動作するときは
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２として動作するときは
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２として動作するときは
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する乗算確認手段と、
を備える計算装置。
【請求項６】
請求項５記載の計算装置であって、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０として動作するときは断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１として動作するときは断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２として動作するときは断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する減算結果分散部と、
数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認部
も備える計算装置。
【請求項７】
請求項５または６記載の計算装置としてコンピュータを機能させる計算プログラム。
【請求項１】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムを用いてＣ＝ＡＢの秘密計算での不正を検知する不正検知方法であって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０が断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、計算装置Ｐ１が断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、計算装置Ｐ２が断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得するデータ取得ステップと、
計算装置Ｐ１と計算装置Ｐ２が、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有する乱数共有ステップと、
計算装置Ｐ１がＳａ１を分散し、計算装置Ｐ１または計算装置Ｐ２がＳａ２を分散し、計算装置Ｐ２がＳａ０を分散して、計算装置Ｐ０が断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１が断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２が断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する第１乗算結果分散ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１が断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２が断片（ｄ２，ｄ０）を取得する乗算結果加算ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０が断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１が断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２が断片（ｅ２，ｅ０）を取得する第２乗算結果分散ステップと、
計算装置Ｐ１が
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２が
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２が
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する、もしくは、
計算装置Ｐ１が
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２が
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２が
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する乗算確認ステップと、
を有する不正検知方法。
【請求項２】
請求項１記載の不正検知方法であって、
計算装置αが記録する断片を（ｘγα，ｘαβ）、計算装置βが記録する断片を（ｘαβ，ｘβγ）、計算装置γが記録する断片を（ｘβγ，ｘγα）とし、
断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とし、
前記データ取得ステップは、計算装置αが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得し、計算装置βが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得し、計算装置γが断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得するステップであり、
断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて（ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１）、計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて（ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０）、計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１として、前記乱数共有ステップ、前記第１乗算結果分散ステップ、前記乗算結果加算ステップ、前記第２乗算結果分散ステップ、前記乗算確認ステップを実行し、
計算装置α、β、γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０が断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１が断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２が断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する減算結果分散ステップと、
計算装置Ｐ０，Ｐ１，Ｐ２が、数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認ステップと、
を有することを特徴とする不正検知方法。
【請求項３】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムであって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０に断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得させ、計算装置Ｐ１に断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得させ、計算装置Ｐ２に断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得させるデータ取得手段と、
計算装置Ｐ１と計算装置Ｐ２に、ランダムに選んだ２以上Ｍ以下の整数Ｓを共有させる乱数共有手段と、
計算装置Ｐ１にＳａ１を分散させ、計算装置Ｐ１または計算装置Ｐ２にＳａ２を分散させ、計算装置Ｐ２にＳａ０を分散させて、計算装置Ｐ０に断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得させ、計算装置Ｐ１に断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得させ、計算装置Ｐ２に断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得させる第１乗算結果分散手段と、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｄ０，ｄ１）を取得させ、計算装置Ｐ１に断片（ｄ１，ｄ２）を取得させ、計算装置Ｐ２に断片（ｄ２，ｄ０）を取得させる乗算結果加算手段と、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０に断片（ｅ０，ｅ１）を取得させ、計算装置Ｐ１に断片（ｅ１，ｅ２）を取得させ、計算装置Ｐ２に断片（ｅ２，ｅ０）を取得させる第２乗算結果分散手段と、
計算装置Ｐ１に
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる、もしくは、
計算装置Ｐ１に
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ２に
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算させ、計算装置Ｐ１または計算装置Ｐ２に
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認させる乗算確認手段と、
を有する秘密計算システム。
【請求項４】
請求項３記載の秘密計算システムであって、
計算装置αが記録する断片を（ｘγα，ｘαβ）、計算装置βが記録する断片を（ｘαβ，ｘβγ）、計算装置γが記録する断片を（ｘβγ，ｘγα）とし、
断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）は計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）は計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０としてＣ＝ＡＢの秘密計算を行った結果、断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）は計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１としてＣ＝ＡＢの秘密計算を行った結果とし、
前記データ取得手段は、計算装置αに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’１，ｃ’２），（ｃ”２，ｃ”０）を取得させ、計算装置βに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’２，ｃ”０），（ｃ”０，ｃ”１）を取得させ、計算装置γに断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１），（ｃ’０，ｃ’１），（ｃ”１，ｃ”２）を取得させる手段であり、
断片（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）と断片（ｂ０，ｂ１），（ｂ１，ｂ２），（ｂ２，ｂ０）と断片（ｃ０，ｃ１），（ｃ１，ｃ２），（ｃ２，ｃ０）を用いて、計算装置αが計算装置Ｐ０として、計算装置βが計算装置Ｐ１として、計算装置γが計算装置Ｐ２として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
断片（ａ’０，ａ’１），（ａ’１，ａ’２），（ａ’２，ａ’０）と断片（ｂ’０，ｂ’１），（ｂ’１，ｂ’２），（ｂ’２，ｂ’０）と断片（ｃ’０，ｃ’１），（ｃ’１，ｃ’２），（ｃ’２，ｃ’０）を用いて（ただし、ａ’０＝ａ２，ａ’１＝ａ０，ａ’２＝ａ１，ｂ’０＝ｂ２，ｂ’１＝ｂ０，ｂ’２＝ｂ１）、計算装置αが計算装置Ｐ１として、計算装置βが計算装置Ｐ２として、計算装置γが計算装置Ｐ０として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
断片（ａ”０，ａ”１），（ａ”１，ａ”２），（ａ”２，ａ”０）と断片（ｂ”０，ｂ”１），（ｂ”１，ｂ”２），（ｂ”２，ｂ”０）と断片（ｃ”０，ｃ”１），（ｃ”１，ｃ”２），（ｃ”２，ｃ”０）を用いて（ただし、ａ”０＝ａ１，ａ”１＝ａ２，ａ”２＝ａ０，ｂ”０＝ｂ１，ｂ”１＝ｂ２，ｂ”２＝ｂ０）、計算装置αが計算装置Ｐ２として、計算装置βが計算装置Ｐ０として、計算装置γが計算装置Ｐ１として、前記乱数共有手段、前記第１乗算結果分散手段、前記乗算結果加算手段、前記第２乗算結果分散手段、前記乗算確認手段を実行し、
計算装置α、β、γが計算装置Ｐ０，Ｐ１，Ｐ２のいずれの計算装置として動作するかを決め、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０に断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得させ、計算装置Ｐ１に断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得させ、計算装置Ｐ２に断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得させる減算結果分散手段と、
数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認手段と、
を備える秘密計算システム。
【請求項５】
数値Ｘを３つの計算装置α、β、γで分散して記録し、秘密計算を行う秘密計算システムの計算装置であって、
Ｍを２以上の整数、計算装置Ｐ０として動作する計算装置が記録する断片を（ｘ０，ｘ１）、計算装置Ｐ１として動作する計算装置が記録する断片を（ｘ１，ｘ２）、計算装置Ｐ２として動作する計算装置が記録する断片を（ｘ２，ｘ０）、数値Ｘと断片とは
Ｘ＝ｘ０＋ｘ１＋ｘ２ ｍｏｄ Ｍ
の関係を満たすとし、
数値Ａ，Ｂ，Ｃの断片として、計算装置Ｐ０として動作するときは断片（ａ０，ａ１），（ｂ０，ｂ１），（ｃ０，ｃ１）を取得し、計算装置Ｐ１として動作するときは断片（ａ１，ａ２），（ｂ１，ｂ２），（ｃ１，ｃ２）を取得し、計算装置Ｐ２として動作するときは断片（ａ２，ａ０），（ｂ２，ｂ０），（ｃ２，ｃ０）を取得するデータ取得部と、
計算装置Ｐ１として動作するときは、ランダムに選んだ２以上Ｍ以下の整数Ｓを計算装置Ｐ２と共有し、計算装置Ｐ２として動作するときは、ランダムに選んだ２以上Ｍ以下の整数Ｓを計算装置Ｐ１と共有する乱数共有部と、
計算装置Ｐ１として動作するときはＳａ１を分散し、計算装置Ｐ１または計算装置Ｐ２として動作するときはＳａ２を分散し、計算装置Ｐ２として動作するときはＳａ０を分散し、計算装置Ｐ０として動作するときは断片（（Ｓａ０）０，（Ｓａ０）１），（（Ｓａ１）０，（Ｓａ１）１），（（Ｓａ２）０，（Ｓａ２）１）を取得し、計算装置Ｐ１として動作するときは断片（（Ｓａ０）１，（Ｓａ０）２），（（Ｓａ１）１，（Ｓａ１）２），（（Ｓａ２）１，（Ｓａ２）２）を取得し、計算装置Ｐ２として動作するときは断片（（Ｓａ０）２，（Ｓａ０）０），（（Ｓａ１）２，（Ｓａ１）０），（（Ｓａ２）２，（Ｓａ２）０）を取得する第１乗算結果分散部と、
Ｄ＝Ｓａ０＋Ｓａ１＋Ｓａ２ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０として動作するときは断片（ｄ０，ｄ１）を取得し、計算装置Ｐ１として動作するときは断片（ｄ１，ｄ２）を取得し、計算装置Ｐ２として動作するときは断片（ｄ２，ｄ０）を取得する乗算結果加算部と、
Ｅ＝ＤＢ ｍｏｄ Ｍ
の秘密計算を行い、計算装置Ｐ０として動作するときは断片（ｅ０，ｅ１）を取得し、計算装置Ｐ１として動作するときは断片（ｅ１，ｅ２）を取得し、計算装置Ｐ２として動作するときは断片（ｅ２，ｅ０）を取得する第２乗算結果分散部と、
計算装置Ｐ１として動作するときは
ｆ＝ｅ１＋ｅ２−Ｓｃ１−Ｓｃ２ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２として動作するときは
ｇ＝ｅ０−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２として動作するときは
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する、もしくは、
計算装置Ｐ１として動作するときは
ｆ＝ｅ１−Ｓｃ１ ｍｏｄ Ｍ
を計算し、計算装置Ｐ２として動作するときは
ｇ＝ｅ２＋ｅ０−Ｓｃ２−Ｓｃ０ ｍｏｄ Ｍ
を計算し、計算装置Ｐ１または計算装置Ｐ２として動作するときは
ｆ＋ｇ＝０ ｍｏｄ Ｍ
かを確認する乗算確認手段と、
を備える計算装置。
【請求項６】
請求項５記載の計算装置であって、
Ｕ＝Ｃ−Ｃ’ ｍｏｄ Ｍ
の秘密計算と、
Ｖ＝Ｃ−Ｃ” ｍｏｄ Ｍ
の秘密計算とを行い、計算装置Ｐ０として動作するときは断片（ｕ０，ｕ１），（ｖ０，ｖ１）を取得し、計算装置Ｐ１として動作するときは断片（ｕ１，ｕ２），（ｖ１，ｖ２）を取得し、計算装置Ｐ２として動作するときは断片（ｕ２，ｕ０），（ｖ２，ｖ０）を取得する減算結果分散部と、
数値ＵとＶを復元し、Ｕ＝０かつＶ＝０であることを確認する減算確認部
も備える計算装置。
【請求項７】
請求項５または６記載の計算装置としてコンピュータを機能させる計算プログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１２−７８４４６（Ｐ２０１２−７８４４６Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１０−２２１７２３（Ｐ２０１０−２２１７２３）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]