(57)【特許請求の範囲】
【請求項１】
２入力１出力の論理ゲートであるゲートＧ（ｉ）を含む回路を秘匿化した秘匿回路を生成する秘匿計算装置であって、
ｉが整数であり、α（＋）βがαとβとの排他的論理和
【数２５】
0006599215.tif 000027
であり、λＡ，λＢ，λｉ∈｛０，１｝がランダムな置換ビットであり、
前記ゲートＧ（ｉ）の２個の入力値の定義域の元ａ，ｂ∈｛０，１｝のそれぞれに応じた入力ラベルＬａＡ＝λＡ（＋）ａ，ＬｂＢ＝λＢ（＋）ｂを設定して出力する入力ラベル設定部と、
前記ゲートＧ（ｉ）に対応する整数ｉと、前記入力ラベルＬａＡ，ＬｂＢと、前記元ａ，ｂが前記ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）∈｛０，１｝のそれぞれに応じた前記ゲートＧ（ｉ）の出力鍵
【数２６】
0006599215.tif 000028
と、トラップドア一方向性置換Ｅιのトラップドアｔιとを用い、前記整数ｉと前記入力ラベルＬａＡ，ＬｂＢに対する単射な写像ｘ＝ｇ（ＬａＡ，ＬｂＢ）∈｛０，１，２，３｝とに対する一方向性写像ｃｘと、前記出力鍵
【数２７】
0006599215.tif 000029
と、の排他的論理和
【数２８】
0006599215.tif 000030
のトラップドア一方向性置換Ｅιによる逆像
【数２９】
0006599215.tif 000031
を得て出力する逆像部と、
前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３を用い、前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３と予め定められた関係式とから一義的に定まる４変数連立方程式の解
【数３０】
0006599215.tif 000032
を、前記元ａ＝０，ａ＝１，ｂ＝０，ｂ＝１のそれぞれに対応する入力鍵として得て出力する入力鍵生成部と、
前記入力鍵ＫＡａ，ＫＢｂに対する一方向性写像Ｈ’（ＫＡａ｜ＫＢｂ）を用い、前記元ａ，ｂが前記ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）に応じた出力ラベルＬＧｉ（ａ，ｂ）ｉ＝λｉ（＋）Ｇｉ（ａ，ｂ）∈｛０，１｝を秘匿化した秘匿化出力ラベル
【数３１】
0006599215.tif 000033
を得て出力するラベル秘匿化部と、
を有する秘匿計算装置。
【請求項２】
２入力１出力の論理ゲートであるゲートＧ（ｉ）を含む回路を秘匿化した秘匿回路を生成する秘匿計算装置であって、
ｉが整数であり、α（＋）βがαとβとの排他的論理和
【数３２】
0006599215.tif 000034
であり、λＡ，λＢ，λｉ∈｛０，１｝がランダムな置換ビットであり、
前記ゲートＧ（ｉ）の２個の入力値の定義域の元ａ，ｂ∈｛０，１｝のそれぞれに応じた入力ラベルＬａＡ＝λＡ（＋）ａ，ＬｂＢ＝λＢ（＋）ｂを設定して出力する入力ラベル設定部と、
前記ゲートＧ（ｉ）に対応する整数ｉと、前記ゲートＧ（ｉ）の出力値Ｇｉ（ａ，ｂ）＝０に対応する前記ゲートＧ（ｉ）の出力鍵Ｋ０ｉとを用い、互いに異なる所定値Ｘ１，Ｘ２，Ｘ３、前記整数ｉと前記所定値Ｘ１との関数値Ｙ１、および前記整数ｉと前記所定値Ｘ２との関数値Ｙ２についての複数の点（Ｘ１，Ｙ１）および（Ｘ２，Ｙ２）、ならびに、前記所定値Ｘ３と前記出力鍵Ｋ０ｉとからなる点（Ｘ３，Ｋ０ｉ）によって定まる２次多項式である第１整式Ｐを得て出力する第１補完部と、
前記整数ｉと、前記ゲートＧ（ｉ）の出力値Ｇｉ（ａ，ｂ）＝１に対応する前記ゲートＧ（ｉ）の出力鍵Ｋ１ｉとを用い、前記複数の点（Ｘ１，Ｙ１）および（Ｘ２，Ｙ２）、ならびに、前記所定値Ｘ３と前記出力鍵Ｋ１ｉとからなる点（Ｘ３，Ｋ１ｉ）によって定まる２次多項式である第２整式Ｑを得て出力する第２補完部とを有し、
前記第１整式Ｐと、前記第２整式Ｑと、前記入力ラベルＬａＡ，ＬｂＢと、トラップドア一方向性置換Ｅιのトラップドアｔιとを用い、前記ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）が０となる前記元ａ，ｂに応じた前記入力ラベルＬａＡ，ＬｂＢに対する単射な写像ｘ＝ｇ（ＬａＡ，ＬｂＢ）∈｛０，１，２，３｝を前記第１整式Ｐに代入して得られる値Ｐ（ｇ（ＬａＡ，ＬｂＢ））のトラップドア一方向性置換Ｅιによる逆像
【数３３】
0006599215.tif 000035
および、前記ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）が１となる前記元ａ，ｂに応じた入力ラベルＬａＡ，ＬｂＢに対する単射な写像ｘ＝ｇ（ＬａＡ，ＬｂＢ）∈｛０，１，２，３｝を前記第２整式Ｑに代入して得られる値Ｑ（ｇ（ＬａＡ，ＬｂＢ））の前記トラップドア一方向性置換Ｅιによる逆像
【数３４】
0006599215.tif 000036
を得て出力する逆像部と、
前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３を用い、前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３と予め定められた関係式とから一義的に定まる４変数連立方程式の解
【数３５】
0006599215.tif 000037
を、前記元ａ＝０，ａ＝１，ｂ＝０，ｂ＝１のそれぞれに対応する入力鍵として得て出力する入力鍵生成部と、
前記入力鍵ＫＡａ，ＫＢｂに対する一方向性写像Ｈ’（ＫＡａ｜ＫＢｂ）を用い、前記元ａ，ｂが前記ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）に応じた出力ラベルＬＧｉ（ａ，ｂ）ｉ＝λｉ（＋）Ｇｉ（ａ，ｂ）∈｛０，１｝を秘匿化した秘匿化出力ラベル
【数３６】
0006599215.tif 000038
を得て出力するラベル秘匿化部と、
を有する秘匿計算装置。
【請求項３】
請求項１の秘匿回路を用いて秘密計算を行う秘匿計算装置であって、
α（＋）βがαとβとの排他的論理和
【数３７】
0006599215.tif 000039
であり、λｉ∈｛０，１｝がランダムな置換ビットであり、前記予め定められた関係式は、前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３のそれぞれと前記入力鍵ＫＡ０またはＫＡ１とＫＢ０またはＫＢ１との組との間に成り立つ等式であり、
前記ゲートＧ（ｉ）の入力値ａ＝０またはａ＝１の何れかに対応する前記入力鍵ＫａＡおよび前記入力ラベルＬａＡである入力鍵ＫＡおよび入力ラベルＬＡと、前記ゲートＧ（ｉ）の入力値ｂ＝０またはｂ＝１の何れかに対応する前記入力鍵ＫｂＢおよび前記入力ラベルＬｂＢである入力鍵ＫＢおよび入力ラベルＬＢとを用い、前記整数ｉと前記入力ラベルＬＡ，ＬＢに対する単射な写像ｘ＝ｇ（ＬＡ，ＬＢ）∈｛０，１，２，３｝とに対する一方向性写像ｃｘと、前記入力鍵ＫＡ，ＫＢに対して前記予め定められた関係式を満たす前記逆像Ｐｘの前記トラップドア一方向性置換Ｅιによる像Ｅι（Ｐｘ）との排他的論理和Ｋｉ＝Ｅι（Ｐｘ）（＋）ｃｘを、前記入力値ａ，ｂを前記ゲートＧ（ｉ）に入力して得られる出力値Ｇｉに応じた前記ゲートＧ（ｉ）の出力鍵Ｋｉとして得て出力する出力鍵生成部と、
前記入力鍵ＫＡ，ＫＢと前記秘匿化出力ラベルｂｘとを用い、前記入力鍵ＫＡ，ＫＢに対する一方向性写像Ｈ’（ＫＡ｜ＫＢ）と前記秘匿化出力ラベルｂｘとの排他的論理和Ｌｉ＝Ｈ’（ＫＡ｜ＫＢ）（＋）ｂｘを、前記ゲートＧ（ｉ）の出力値Ｇｉ（ａ，ｂ）に応じた出力ラベルＬｉ＝λｉ（＋）Ｇｉ（ａ，ｂ）として得て出力するラベル復元部と、
を有する秘匿計算装置。
【請求項４】
請求項２の秘匿回路を用いて秘密計算を行う秘匿計算装置であって、
α（＋）βがαとβとの排他的論理和
【数３８】
0006599215.tif 000040
であり、λｉ∈｛０，１｝がランダムな置換ビットであり、前記予め定められた関係式は、前記逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３のそれぞれと前記入力鍵ＫＡ０またはＫＡ１とＫＢ０またはＫＢ１との組との間に成り立つ等式であり、
前記ゲートＧ（ｉ）の入力値ａ＝０またはａ＝１の何れかに対応する前記入力鍵ＫａＡおよび前記入力ラベルＬａＡである入力鍵ＫＡおよび入力ラベルＬＡと、前記ゲートＧ（ｉ）の入力値ｂ＝０またはｂ＝１の何れかに対応する前記入力鍵ＫｂＢおよび前記入力ラベルＬｂＢである入力鍵ＫＢおよび入力ラベルＬＢとを用い、前記入力ラベルＬＡ，ＬＢに対する単射な写像ｘ＝ｇ（ＬＡ，ＬＢ）∈｛０，１，２，３｝を得、前記入力鍵ＫＡ，ＫＢに対して前記予め定められた関係式を満たす前記逆像Ｐｘの前記トラップドア一方向性置換Ｅιによる像Ｅι（Ｐｘ）を得、前記複数の点（Ｘ１，Ｙ１）および（Ｘ２，Ｙ２）、ならびに、点（ｘ，Ｅι（Ｐｘ））によって定まる２次多項式である整式Ｕを得て出力する補完部と、
前記整式Ｕに前記所定値Ｘ３を代入して前記ゲートＧ（ｉ）の出力鍵Ｋｉ＝Ｕ（Ｘ３）を得て出力する代入部と、
前記入力鍵ＫＡ，ＫＢと前記秘匿化出力ラベルｂｘとを用い、前記入力鍵ＫＡ，ＫＢに対する一方向性写像Ｈ’（ＫＡ｜ＫＢ）と前記秘匿化出力ラベルｂｘとの排他的論理和Ｌｉ＝Ｈ’（ＫＡ｜ＫＢ）（＋）ｂｘを、前記ゲートＧ（ｉ）の出力値Ｇｉ（ａ，ｂ）に応じた出力ラベルＬｉ＝λｉ（＋）Ｇｉ（ａ，ｂ）として得て出力するラベル復元部と、
を含む秘匿計算装置。
【請求項５】
請求項１または２の秘匿計算装置であって、
［α］βがαのβに対応するビット位置のビット値を表し、
Ｈ”が任意長ビットの値をｋビットの値に写す一方向性写像であり、
ｋ＞３であり、
前記ラベル秘匿化部が、
【数３９】
0006599215.tif 000041
に代えて
【数４０】
0006599215.tif 000042
を満たす
【数４１】
0006599215.tif 000043
を得て出力する、秘匿計算装置。
【請求項６】
請求項３または４の秘匿計算装置であって、
［α］βがαのβに対応するビット位置のビット値を表し、
Ｈ”が任意長ビットの値をｋビットの値に写す一方向性写像であり、
ｋ＞３であり、
前記ラベル復元部が、Ｌｉ＝Ｈ’（ＫＡ｜ＫＢ）（＋）ｂｘに代えて
【数４２】
0006599215.tif 000044
を前記出力ラベルＬｉ＝λｉ（＋）Ｇｉ（ａ，ｂ）として得て出力する、秘匿計算装置。
【請求項７】
請求項１から６の何れかの秘匿計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に秘匿回路を用いた計算技術に関する。
【背景技術】
【０００２】
非特許文献１には、秘匿回路を用いた２パーティ計算方式の従来技術が開示されている。非特許文献１の秘匿回路では、秘匿化前の回路を構成する各ゲートの入力の真理値に対応する入力鍵および入力ラベルが設定され、さらに各ゲートの入力の真理値の組み合わせに応じた出力の真理値に対応する出力鍵および出力ラベルが設定される。出力鍵および出力ラベルは、入力鍵の組み合わせによって復号可能なように共通鍵暗号によって暗号化されている。ゲートの出力は次のゲートの入力となる。
【０００３】
この秘匿回路を用いた計算では、各ゲートの入力の真理値の組み合わせに対応する入力鍵および入力ラベルを用いて当該ゲートの暗号文を復号し、出力鍵および出力ラベルを得る。出力鍵および出力ラベルは、次のゲートで入力鍵および入力ラベルとして利用され、同様に次のゲートの暗号文を復号して次の出力鍵および出力ラベルを得る。これを繰り返すことで最終段のゲートの出力ラベルを得る。この出力ラベルは演算結果に対応する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams, “Secure Two-Party Computation Is Practical,” ASIACRYPT 2009, 250-267.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来方式では、各ゲートの出力鍵および出力ラベルの暗号文を保存しておかなければならず、秘匿回路のサイズが大きいという問題がある。本発明の課題は、秘匿回路のサイズを削減することである。
【課題を解決するための手段】
【０００６】
各ゲートの定義域の元のそれぞれに応じた入力ラベルに対応する値と、当該元が当該ゲートに入力された際の出力値のそれぞれに応じたゲートの出力鍵と、に応じた像のトラップドア一方向性置換による逆像を得、当該逆像を用いて当該元のそれぞれに応じた入力鍵を得る。さらに当該入力鍵を用い、当該元が当該ゲートに入力された際の出力値に応じた出力ラベルを秘匿化した秘匿化出力ラベルを得る。
【発明の効果】
【０００７】
これにより、各ゲートの出力鍵に対応する暗号文の保存が不要となり、秘匿回路のサイズを削減できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の秘匿計算システムの構成を例示したブロック図である。
【図２】図２は実施形態の秘匿計算装置の構成を例示したブロック図である。
【図３】図３は実施形態の秘匿計算装置の構成を例示したブロック図である。
【図４】図４は第１実施形態の回路秘匿化方法を例示したフロー図である。
【図５】図５は第１実施形態の回路秘匿化方法を例示したフロー図である。
【図６】図６は第１実施形態の入力値の符号化方法を例示したフロー図である。
【図７】図７は第１実施形態の秘匿回路の計算方法を例示したフロー図である。
【図８】図８Ａおよび図８Ｂは秘匿化対象の回路を例示した概念図である。
【図９】図９は実施形態の秘匿計算装置の構成を例示したブロック図である。
【図１０】図１０は実施形態の秘匿計算装置の構成を例示したブロック図である。
【図１１】図１１は第２実施形態の回路秘匿化方法を例示したフロー図である。
【図１２】図１２は第２実施形態の秘匿回路の計算方法を例示したフロー図である。
【図１３】図１３は第２実施形態の秘匿回路を説明するための図である。
【図１４】図１４は第３実施形態の前処理を例示したフロー図である。
【図１５】図１５は第３実施形態の前処理を例示したフロー図である。
【図１６】図１６は第３実施形態の回路秘匿化方法を例示したフロー図である。
【図１７】図１７は第３実施形態の秘匿回路の計算方法を例示したフロー図である。
【図１８】図１８は第４実施形態の前処理を例示したフロー図である。
【図１９】図１９は第４実施形態の秘匿回路の計算方法を例示したフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［概要］
秘匿回路の生成では、各ゲートの定義域の元のそれぞれに応じた入力ラベルに対応する値と、当該元が当該ゲートに入力された際の出力値のそれぞれに応じたゲートの出力鍵と、に応じた像のトラップドア一方向性置換による逆像を得、当該逆像を用いて当該元のそれぞれに応じた入力鍵を得る。さらに当該入力鍵を用い、当該元が当該ゲートに入力された際の出力値に応じた出力ラベルを秘匿化した秘匿化出力ラベルを得る。
【００１０】
通常の一方向性写像の場合、その像から逆像を得ることは困難である。一方、トラップドア一方向性置換の場合、秘密情報であるトラップドアを用いることで、その像から逆像を得ることができる。トラップドア一方向性置換の例は、ＲＳＡ暗号などの公開鍵暗号方式の暗号化関数であり、トラップドアの例は公開鍵暗号方式の秘密鍵である。本形態では、このようなトラップドア一方向性置換を用い、各ゲートの入力値の各真理値に対応する入力ラベルに対応する値と、それに応じた出力値の各真理値に対応する出力鍵とから、その各真理値に応じた入力の真理値に対応する入力鍵を逆向きに設定していき、回路を秘匿化する。これにより、出力鍵の暗号文を保存しておくことなく、入力ラベルに対応する真理値に対応する入力鍵を用いた復号処理によって、当該入力ラベルに対応する真理値に応じた出力値に対応する出力鍵を復元可能な秘匿回路を構成できる。すなわち、この秘匿回路を用いた秘匿計算では、ゲートの入力値に応じた入力ラベルに対応する値と当該ゲートの入力鍵のトラップドア一方向性置換による像とに応じたゲートの出力鍵を得、当該ゲートの出力値に応じた秘匿化出力ラベルおよびゲートの入力鍵を用い、ゲートの出力値に応じた出力ラベルを得ることができる。このように出力鍵の暗号文を保存しておく必要がないため、秘匿回路のサイズを削減できる。
【００１１】
後述の第１実施形態の秘匿回路の生成では、入力ラベルに対応する値と出力鍵との排他的論理和である像のトラップドア一方向性置換による逆像を得、当該逆像を用いて各入力鍵を設定する。これにより、「入力ラベルに対応する値」を出力鍵の暗号文とみなし、入力ラベルに対応する真理値に対応する入力鍵を復号鍵とする復号処理によって、当該入力ラベルに対応する真理値に応じた出力値に対応する出力鍵を復元可能な秘匿回路を構成できる。すなわち、この秘匿回路を用いた秘匿計算では、入力ラベルに対応する値とゲートの入力鍵のトラップドア一方向性置換による像である値との排他的論理和をゲートの出力鍵とする。この「入力ラベルに対応する値」は、入力ラベルから得ることができるため、これを格納しておく必要はない。
【００１２】
後述の第２実施形態の秘匿回路の生成では、（１）各ゲートに応じた複数の点、ならびに、所定値と出力値の何れかである第１値に応じた出力鍵とからなる点によって定まる第１整式を得、（２）当該複数の点、ならびに、所定値と出力値の何れかである第２値に応じた出力鍵とからなる点によって定まる第２整式を得る。ただし、第１値と第２値とは異なる。さらにこの秘匿回路の生成では、（３）ゲートに入力された際の出力値が第１値となる元に応じた入力ラベルに対応する値を第１整式に代入して得られる値である像のトラップドア一方向性置換による逆像、および、ゲートに入力された際の出力値が第２値となる元に応じた入力ラベルに対応する値を第２整式に代入して得られる値である像のトラップドア一方向性置換による逆像を得、当該逆像を用いて各入力鍵を設定する。これにより、入力ラベルに対応する真理値に対応する入力鍵を復号鍵とする復号処理によって、当該入力ラベルに対応する真理値に応じた出力値に対応する出力鍵を復元可能な秘匿回路を構成できる。すなわち、この秘匿回路を用いた秘匿計算では、多項式補完によって、ゲートに応じた複数の点、ならびに、入力ラベルに対応する値およびゲートの入力鍵のトラップドア一方向性置換による像である値からなる点によって定まる整式を得、当該整式に所定値を代入してゲートの出力鍵を得ることができる。「ゲートに応じた複数の点」はゲートに対して定めることができ、「入力ラベルに対応する値」および「入力鍵」はそれぞれ入力ラベルおよび入力鍵から定めることができる。そのため、これらを格納しておく必要はない。
【００１３】
秘匿回路の生成の際の秘匿化出力ラベルの設定は、上述のように設定された入力鍵に基づいて行われる。例えば、入力鍵に対応する値で出力ラベルを秘匿化して秘匿化出力ラベルを得てもよいし、入力鍵に対応するビット列の「ゲートの定義域の元」に応じたビット位置を表す値を秘匿化出力ラベルとしてもよい。秘匿化出力ラベルは格納しておく必要はあるが、ラベルと出力鍵の両方の暗号文を格納していた従来技術よりも秘匿回路のサイズを小さくできる。
【００１４】
［第１実施形態］
次に図面を用いて第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の秘匿計算システム１は、秘匿回路を生成する秘匿計算装置１１、および当該秘匿回路を用いた秘匿計算を行う秘匿計算装置１２を有する。
【００１５】
＜秘匿計算装置１１＞
図２に例示するように、本形態の秘匿計算装置１１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部１１４、入力ワイヤ設定部１１５、置換ビット設定部１１６１、入力ラベル設定部１１６２、写像部１１７１、逆像部１１７２、入力鍵生成部１１７３、入力鍵・ラベルテーブル設定部１１７４、ラベル秘匿化部１１８１、出力ラベルテーブル設定部１１８２、符号化部１１９１、分離部１１９２、および紛失通信処理部１１９３を有する。
【００１６】
＜秘匿計算装置１２＞
図３に例示するように、本形態の秘匿計算装置１２は、通信部１２１１、入力部１２１２、記憶部１２２、制御部１２３、紛失通信処理部１２４、分離部１２５、設定部１２６、入力ワイヤ設定部１２７１、写像部１２７２、出力鍵生成部１２７３、分離部１２７４、およびラベル復元部１２７５、および出力値生成部１２８を有する。
【００１７】
各秘匿計算装置は、例えば、通信装置、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。秘匿計算装置１１，１２は、それぞれ制御部１１３，１２３の制御のもとで各処理を行う。また、各部で得られたデータは、逐一、メモリ（図示せず）に格納され、必要に応じて読み出されて使用される。
【００１８】
＜前処理＞
正整数であるセキュリティパラメータｋに基づき、以下の前処理が行われる。
任意長ビットの値をｋビットの値に写す一方向性写像Ｈ：｛０，１｝＊→｛０，１｝ｋ、および任意長ビットの値を１ビットの値に写す一方向性写像Ｈ’：｛０，１｝＊→｛０，１｝が設定される。一方向性写像の例はハッシュ関数である。例えば、暗号学的なハッシュ関数を一方向性写像とすることができる。Ｈは鍵あり一方向性写像であり、Ｈ’は鍵なし一方向性写像である。共通鍵暗号関数または公開鍵暗号関数を一方向性写像として用いてもよい。一方向性写像は、関数であってもよいし、アルゴリズムであってもよい。
【００１９】
秘匿計算装置１１に入力された秘匿対象の回路ｆが記憶部１１２に格納される。回路ｆはｎビットの入力値Ｚ∈｛０，１｝ｎに対して１ビットの出力値Ｙ∈｛０，１｝を出力する写像（関数）である（ｆ：｛０，１｝ｎ→｛０，１｝）。ただし、ｎは２以上の偶数であり、ｎ＝４であってもよいし、ｎ≧６であってもよい。ｕは１以上の整数であり、ｕ≧３であってもよい。図８Ｂはｎ＝１０，ｕ＝９の例である。
【００２０】
図８Ａおよび図８Ｂに例示するように、回路ｆはｕ個のゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）から構成される。ゲートＧ（ｉ）（ただし、ｉ∈｛ｎ＋１，…，ｎ＋ｕ｝）は２入力１出力の論理ゲートである（Ｇ（ｉ）：｛０，１｝×｛０，１｝→｛０，１｝）。ゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）の集合をＧｓｅｔ：＝｛Ｇ（ｎ＋１），…，Ｇ（ｎ＋ｕ）｝と表記する。入力側のｎ／２個のゲートＧ（ｎ＋１），…，Ｇ（３ｎ／２）の集合をＧｉｎｐｕｔ：＝｛Ｇ（ｎ＋１），…，Ｇ（３ｎ／２）｝と表記する。ただし、「α：＝β」はαをβとすることを意味する。ゲートの例は、ＡＮＤゲート、ＯＲゲート、ＸＯＲゲートなどである。
【００２１】
ゲートＧ（ｉ）への入力変数を入力ワイヤと呼び、出力変数を出力ワイヤと呼ぶ。各ゲートＧ（ｉ）は２個の入力ワイヤと１個の出力ワイヤを持つ。入力ワイヤおよび出力ワイヤを総称してワイヤと呼ぶ。ゲートＧ（ｉ）の入力ワイヤをＷ（Ａ（ｉ））およびＷ（Ｂ（ｉ））と表記し、出力ワイヤをＷ（ｉ）と表記する。ゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）のワイヤの集合をＷｓｅｔ：＝｛Ｗ（１），…，Ｗ（ｎ＋ｕ）｝と表記する。ただし、Ａ（ｉ）＜Ｂ（ｉ）＜ｉであり、Ａ（ｎ＋１）＝１，Ｂ（ｎ＋１）＝２，…，Ａ（３ｎ／２）＝ｎ−１，Ｂ（３ｎ／２）＝ｎ，…，Ａ（ｎ＋ｕ）＝ｎ＋ｕ−２，Ｂ（ｎ＋ｕ）＝ｎ＋ｕ−１である。集合Ｇｉｎｐｕｔに属するｎ／２個のゲートＧ（ｎ＋１），…，Ｇ（３ｎ／２）の入力ワイヤＷ（Ａ（ｎ＋１））＝Ｗ（１），Ｗ（Ｂ（ｎ＋１））＝Ｗ（２），…，Ｗ（Ａ（３ｎ／２））＝Ｗ（ｎ−１），Ｗ（Ｂ（３ｎ／２））＝Ｗ（ｎ）の集合をＷｉｎｐｕｔ：＝｛Ｗ（１），…，Ｗ（ｎ）｝と表記する。ゲートＧ（ｎ＋ｕ）の出力ワイヤＷ（ｎ＋ｕ）をＷｏｕｔｐｕｔ：＝Ｗ（ｎ＋ｕ）と表記する。Ａｓｅｔ：＝｛Ａ（ｎ＋１），…，Ａ（ｎ＋ｕ）｝と表記し、Ｂｓｅｔ：＝｛Ｂ（ｎ＋１），…，Ｂ（ｎ＋ｕ）｝と表記する。また、回路ｆを（ｎ，ｕ，Ａｓｅｔ，Ｂｓｅｔ，Ｇｓｅｔ）と表記する。
【００２２】
集合Ｇｉｎｐｕｔに属するゲートの入力ワイヤＷ（１），…，Ｗ（ｎ）は回路ｆの入力ワイヤであり、ｎビットの入力値Ｚに対応する。ゲートＧ（ν）（ただし、ν∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ν）は、それぞれ、何れかのゲートＧ（ω）∈Ｇｓｅｔ＼｛Ｇ（ｎ＋１），…，Ｇ（ｎ＋ｕ−１）｝の入力ワイヤＷ（Ａ（ω））またはＷ（Ｂ（ω））である。ただし、「α＼β」は集合αにおける集合βの補集合を表す。ν＜ωであり、互いに異なる出力ワイヤが同一の入力ワイヤとなることはなく、単一の出力ワイヤが複数の入力ワイヤとなることもない。ゲートＧ（ｎ＋ｕ）の出力ワイヤＷ（ｎ＋ｕ）は回路ｆの出力ワイヤであり、出力値Ｙに対応する。
【００２３】
ゲートＧ（μ）（ただし、μ∈｛ｎ＋１，…，ｎ＋ｕ｝）の種類および入力ワイヤＷ（Ａ（μ）），Ｗ（Ｂ（μ））の入力値Ｉ（Ａ（μ）），Ｉ（Ｂ（μ））∈｛０，１｝に応じ、出力ワイヤＷ（μ）の出力値Ｇμ（Ｉ（Ａ（μ）），Ｉ（Ｂ（μ）））∈｛０，１｝が決まる。すなわち、Ｉ（Ａ（μ））およびＩ（Ｂ（μ））に対するゲートＧ（μ）での論理演算結果がＧμ（Ｉ（Ａ（μ）），Ｉ（Ｂ（μ）））となる。例えば、ゲートＧ（μ）がＡＮＤゲートである場合、Ｉ（Ａ（μ）），Ｉ（Ｂ（μ）），Ｇμ（Ｉ（Ａ（μ）），Ｉ（Ｂ（μ）））の関係は以下のようになる。
【表１】
0006599215.tif 000002
【００２４】
＜秘匿回路の生成処理＞
図４および図５を用い、本形態の秘匿回路の生成処理を説明する。
まず、秘匿計算装置１１（図２）の初期設定部１１４が、位数ｑの有限体Ｆｑの元をＦｑの元に写すトラップドア一方向性置換Ｅι：Ｆｑ→Ｆｑおよびそのトラップドアｔιを選択する。ただし、ｑは正整数であり、例えば素数である。トラップドアｔιを用いない限り、トラップドア一方向性置換の逆像を得ることは困難である。一方、トラップドアｔιを用いることにより、トラップドア一方向性置換の逆像を多項式時間で求めることができる。トラップドア一方向性置換は、関数であってもよいし、アルゴリズムであってもよい。また初期設定部１１４は、Ｈの鍵Ｒをランダム（例えば、一様ランダム）に選択して出力する（ステップＳ１００）。
【００２５】
さらに、初期設定部１１４は、記憶部１１２に格納された回路ｆを参照し、有限体Ｆｑの２個の元をランダム（例えば、一様ランダム）に選択し、それらを出力鍵Ｋ０ｎ＋ｕ，Ｋ１ｎ＋ｕ∈Ｆｑとして設定して出力する。ただし、出力鍵Ｋ０ｎ＋ｕはＧｎ＋ｕ（Ｉ（Ａ（ｎ＋ｕ）），Ｉ（Ｂ（ｎ＋ｕ）））＝０に対応し、出力鍵Ｋ１ｎ＋ｕはＧｎ＋ｕ（Ｉ（Ａ（ｎ＋ｕ）），Ｉ（Ｂ（ｎ＋ｕ）））＝１に対応する（ステップＳ１０１）。
【００２６】
次に、初期設定部１１４は、置換ビットλｎ＋ｕ、出力ラベルＬ０ｎ＋ｕ：＝λｎ＋ｕ，Ｌ１ｎ＋ｕ：＝λｎ＋ｕ（＋）１を設定する。ただし、α（＋）βはαとβとの排他的論理和
【数１】
0006599215.tif 000003
を表す。出力ラベルＬ０ｎ＋ｕはＧｎ＋ｕ（Ｉ（Ａ（ｎ＋ｕ）），Ｉ（Ｂ（ｎ＋ｕ）））＝０に対応し、出力ラベルＬ１ｎ＋ｕはＧｎ＋ｕ（Ｉ（Ａ（ｎ＋ｕ）），Ｉ（Ｂ（ｎ＋ｕ）））＝１に対応する。λｎ＋ｕ＝０であってもよいし、λｎ＋ｕ＝１であってもよい（ステップＳ１０２）。さらに制御部１１３がｉ：＝ｎ＋ｕに設定する（ステップＳ１０３）。
【００２７】
入力ワイヤ設定部１１５は、Ａ：＝Ａ（ｉ），Ｂ：＝Ｂ（ｉ）に設定する（ステップＳ１０４）。置換ビット設定部１１６１は、入力ワイヤＷ（Ａ），Ｗ（Ｂ）に対し、それぞれ置換ビットλＡ，λＢ∈｛０，１｝をランダムに選択する（ステップＳ１０５）。入力ラベル設定部１１６２は、すべての（ａ，ｂ）∈｛０，１｝２について、以下のように入力ラベルＬａＡ，ＬｂＢ∈｛０，１｝を設定する。ただし、ａ∈｛０，１｝は入力ワイヤＷ（Ａ）の入力値であり、ｂ∈｛０，１｝は入力ワイヤＷ（Ｂ）の入力値である。
ＬａＡ：＝λＡ（＋）ａ
ＬｂＢ：＝λＢ（＋）ｂ
すなわち、入力ラベル設定部１１６２は、ゲートＧ（ｉ）の定義域の元（ａ，ｂ）のそれぞれに応じた入力ラベル（ＬａＡ，ＬｂＢ）を設定して出力する。なお、図８Ａおよび図８Ｂに例示するように、入力ラベルＬａＡは、ゲートＧ（ｉ）の入力ワイヤＷ（Ａ）となる別のゲートＧ（ｉ’）（ただし、ｉ≠ｉ’，ｉ’∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ｉ’）の出力ラベル
【数２】
0006599215.tif 000004
でもある。同様に、入力ラベルＬｂＢは、ゲートＧ（ｉ）の入力ワイヤＷ（Ｂ）となる別のゲートＧ（ｉ”）（ただし、ｉ≠ｉ”，ｉ”∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ｉ”）の出力ラベル
【数３】
0006599215.tif 000005
でもある（ステップＳ１０６）。
【００２８】
写像部１１７１が、鍵Ｒを用い、ｘ＝０，１，２，３およびｉについてｃｘ：＝Ｈ（Ｒ，ｉ｜ｘ）を生成して出力する。ただし、Ｈ（Ｒ，ｉ｜ｘ）は、Ｒに応じたＨに対し、ｉ｜ｘを入力して得られる像である。α｜βはαとβとの連結を表す。ｘは（ＬａＡ，ＬｂＢ）の４通りの組み合わせに対応する（ステップＳ１０７）。
【００２９】
逆像部１１７２が、記憶部１１２に格納された回路ｆを参照し、Ｅι，ｔι，ＬａＡ，ＬｂＢ，Ｋ０ｉ，Ｋ１ｉを用い、すべての（ａ，ｂ）∈｛０，１｝２について、逆像
【数４】
0006599215.tif 000006
を得て出力する。すなわち、逆像部１１７２は、ゲートＧ（ｉ）の定義域の元（ａ，ｂ）のそれぞれに応じた入力ラベル（ＬａＡ，ＬｂＢ）に対応する値
【数５】
0006599215.tif 000007
と、元（ａ，ｂ）がゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）のそれぞれに応じたゲートＧ（ｉ）の出力鍵
【数６】
0006599215.tif 000008
と、に応じた像
【数７】
0006599215.tif 000009
のトラップドア一方向性置換Ｅιによる逆像を得て出力する。本形態の逆像部１１７２は、入力ラベル（ＬａＡ，ＬｂＢ）に対応する値と当該「出力鍵」との排他的論理和である像のトラップドア一方向性置換による逆像を得て出力する（ステップＳ１０８）。
【００３０】
入力鍵生成部１１７３は、ステップＳ１０８で得られた逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３を用い、以下の連立方程式を解いて、ａ，ｂ∈｛０，１｝のそれぞれに応じた入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂ∈Ｆｑを得て出力する。
【数８】
0006599215.tif 000010
この連立方程式はガウスの消去法等の周知の方法を用いて解くことができる。なお、図８Ａおよび図８Ｂに例示するように、入力鍵Ｋ０Ａ，Ｋ１Ａは、それぞれ、ゲートＧ（ｉ）の入力ワイヤＷ（Ａ）となる別のゲートＧ（ｉ’）（ただし、ｉ≠ｉ’，ｉ’∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ｉ’）の出力鍵Ｋ０ｉ’，Ｋ１ｉ’でもある。同様に、入力鍵Ｋ０Ｂ，Ｋ１Ｂは、それぞれ、ゲートＧ（ｉ）の入力ワイヤＷ（Ｂ）となる別のゲートＧ（ｉ”）（ただし、ｉ≠ｉ”，ｉ”∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ｉ”）の出力鍵Ｋ０ｉ”，Ｋ１ｉ”でもある（ステップＳ１０９）。
【００３１】
入力鍵・ラベルテーブル設定部１１７４は、入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂおよび入力ラベルＬ０Ａ，Ｌ１Ａ，Ｌ０Ｂ，Ｌ１Ｂを入力とし、Ａに対してテーブルｅ［Ａ］：＝（Ｋ０Ａ｜Ｌ０Ａ，Ｋ１Ａ｜Ｌ１Ａ）を設定し、Ｂに対してテーブルｅ［Ｂ］：＝（Ｋ０Ｂ｜Ｌ０Ｂ，Ｋ１Ｂ｜Ｌ１Ｂ）を設定して出力する（ステップＳ１１０）。
【００３２】
ラベル秘匿化部１１８１は、記憶部１１２に格納された回路ｆを参照し、入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂおよび出力ラベルＬｉＧｉ（ａ，ｂ）を用い、すべての（ａ，ｂ）∈｛０，１｝２について、以下のように秘匿化出力ラベル
【数９】
0006599215.tif 000011
を設定して出力する。すなわち、ラベル秘匿化部１１８１は、入力鍵ＫａＡ，ＫｂＢに対応する値Ｈ’（ＫａＡ｜ＫｂＢ）で出力ラベルＬｉＧｉ（ａ，ｂ）を秘匿化してこれらの秘匿化出力ラベルｂ０，ｂ１，ｂ２，ｂ３を得る。出力ラベルＬｉＧｉ（ａ，ｂ）は、元（ａ，ｂ）がゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）に対応する。図８Ａおよび図８Ｂに例示するように、ｉ≠ｎ＋ｕの場合、ゲートＧ（ｉ）の出力ラベルＬｉＧｉ（ａ，ｂ）は、このゲートＧ（ｉ）の出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ａ（ω））とする他のゲートＧ（ω）の入力ラベルＬＡ（ω）ａ’であるか（ただし、ａ’∈｛０，１｝）、出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ｂ（ω））とする他のゲートＧ（ω）の入力ラベルＬＢ（ω）ｂ’である（ただし、ｂ’∈｛０，１｝）。なお、上付き添え字の「Ｇｉ（ａ，ｂ）」は「Ｇｉ（ａ，ｂ）」を意味する（ステップＳ１１１）。
【００３３】
出力ラベルテーブル設定部１１８２は、秘匿化出力ラベルｂ０，ｂ１，ｂ２，ｂ３を用い、秘匿化出力ラベルＬ［ｉ］：＝（ｂ０，ｂ１，ｂ２，ｂ３）を得て出力する（ステップＳ１１２）。
【００３４】
制御部１１３は、ｉ＝ｎ＋１であるかを判定する（ステップＳ１１３）。ｉ＝ｎ＋１でなければ、制御部１１３は、ｉ：＝ｉ−１とし（ｉ−１を新たなｉとし）、処理をステップＳ１０４に戻す（ステップＳ１１４）。一方、ｉ＝ｎ＋１であれば、制御部１１３はステップＳ１１５の処理を実行させる。
【００３５】
ステップＳ１１５では、入力鍵・ラベルテーブル設定部１１７４が、Ｌ［ｎ＋１］，...，Ｌ［ｎ＋ｕ］をＬ：＝｛Ｌ［ｎ＋１］，...，Ｌ［ｎ＋ｕ］｝として出力する（ステップＳ１１５）。次に、入力鍵・ラベルテーブル設定部１１７４が、ｅ［Ａ（３ｎ／２＋１）］，ｅ［Ｂ（３ｎ／２＋１）］，...，ｅ［Ａ（ｎ＋ｕ）］，ｅ［Ｂ（ｎ＋ｕ）］をテーブルｅ：＝｛ｅ［Ａ（３ｎ／２＋１）］，ｅ［Ｂ（３ｎ／２＋１）］，...，ｅ［Ａ（ｎ＋ｕ）］，ｅ［Ｂ（ｎ＋ｕ）］｝として出力する（ステップＳ１１６）。通信部１１１１は、Ｒ，Ｌ，ι，ｅ，λｎ＋ｕを入力として、秘匿回路Ｆ：＝（Ｒ，Ｌ，ι）、テーブルｅ、ラベル復号鍵ｄ：＝λｎ＋ｕとして出力する。ただし、ιはＥιを特定するための情報である。秘匿回路Ｆ：＝（Ｒ，Ｌ，ι）、テーブルｅ、ラベル復号鍵ｄ：＝λｎ＋ｕは秘匿計算装置１２に送信され、秘匿計算装置１２（図３）の通信部１２１１で受信され、記憶部１２２に格納される（ステップＳ１１７）。
【００３６】
秘匿計算装置１１（図２）の入力鍵・ラベルテーブル設定部１１７４は、
ｅ［１］：＝ｅ［Ａ（ｎ＋１）］
ｅ［２］：＝ｅ［Ｂ（ｎ＋１）］
・・・
ｅ［ｎ−１］：＝ｅ［Ａ（３ｎ／２）］
ｅ［ｎ］：＝ｅ［Ｂ（３ｎ／２）］
を記憶部１１２に格納する（ステップＳ１１８）。
【００３７】
＜回路ｆの入力値の符号化処理＞
図６を用い、本形態の入力値の符号化処理を説明する。
以下では、回路ｆの入力値Ｚ∈｛０，１｝ｎの各ビットをｘｊ∈｛０，１｝（ただし、ｊ∈｛１，...，ｎ｝）と表記する。秘匿計算装置１１（図２）の入力部１１１２には、集合｛ｘ１，...，ｘｎ｝の真部分集合ｓｕｂ１：＝｛ｘｕ（１），...，ｘｕ（Ｐ）｝⊂｛ｘ１，...，ｘｎ｝が入力される。ただし、Ｐは１以上の整数であり、｛ｕ（１），...，ｕ（Ｐ）｝⊂｛１，...，ｎ｝である（ステップＳ１２１）。制御部１１３はｐ：＝１とする（ステップＳ１２２）。
【００３８】
分離部１１９２は、記憶部１１２に格納されたｅ［ｕ（ｐ）］を抽出し、ｅ［ｕ（ｐ）］＝（ｅ０，ｅ１）：＝（Ｋ０ｕ（ｐ）｜Ｌ０ｕ（ｐ），Ｋ１ｕ（ｐ）｜Ｌ１ｕ（ｐ））に分離（パース）して出力する（ステップＳ１２３）。
【００３９】
符号化部１１９１は、ｘｕ（１）および（ｅ０，ｅ１）を用い、
【数１０】
0006599215.tif 000012
を得て出力する（ステップＳ１２４）。
【００４０】
制御部１１３はｐ＝Ｐであるかを判定する（ステップＳ１２６）。ｐ＝Ｐでなければ、制御部１１３は、ｐ：＝ｐ＋１とし（ｐ＋１を新たなｐとし）、処理をステップＳ１２３に戻す（ステップＳ１２５）。一方ｐ＝Ｐであれば、Ｘ［ｘｕ（１）］，...，Ｘ［ｘｕ（Ｐ）］が通信部１１１１に送られ、通信部１１１１はＸ［ｘｕ（１）］，...，Ｘ［ｘｕ（Ｐ）］を秘匿計算装置１２に送信する（ステップＳ１２７）。
【００４１】
Ｘ［ｘｕ（１）］，...，Ｘ［ｘｕ（Ｐ）］は秘匿計算装置１２（図３）の通信部１２１１で受信され、記憶部１２２に格納される。なお、秘匿計算装置１２はｅ［１］，...，ｅ［ｎ］を保持していないため、Ｘ［ｘｕ（ｐ）］（ただし、ｐ∈｛１，...，Ｐ｝）に対応するｘｊの値を知ることはできない（ステップＳ１２８）。
【００４２】
秘匿計算装置１２（図３）の入力部１２１２には、集合｛ｘ１，...，ｘｎ｝の真部分集合ｓｕｂ２：＝｛ｘｖ（１），...，ｘｖ（Ｑ）｝⊂｛ｘ１，...，ｘｎ｝が入力される。ただし、Ｑは１以上の整数であり、｛ｖ（１），...，ｖ（Ｑ）｝⊂｛１，...，ｎ｝であり、｛１，...，ｎ｝＝｛ｕ（１），...，ｕ（Ｐ）｝∪｛ｖ（１），...，ｖ（Ｑ）｝である。例えば｛ｕ（１），...，ｕ（Ｐ）｝∩｛ｖ（１），...，ｖ（Ｑ）｝は空集合であるが、これが空集合でなくてもよい（ステップＳ１２９）。制御部１１３はｑ：＝１とする（ステップＳ１３０）。
【００４３】
紛失通信処理部１２４は、ｘｖ（ｑ）を用い、通信部１２１１および秘匿計算装置１１（図２）の通信部１１１１を通じ、紛失通信処理部１１９３と紛失通信（ＯＴ：Oblivious transfer）を行い、ｘｖ（ｑ）に対応する
【数１１】
0006599215.tif 000013
を得る。紛失通信処理部１２４は紛失通信処理部１１９３にｘｖ（ｑ）を開示することなく、紛失通信処理部１１９３は
【数１２】
0006599215.tif 000014
を紛失通信処理部１２４に開示することなく、紛失通信処理部１２４がＸ［ｖ（ｑ）］を得る。紛失通信には周知の方法を用いればよい（例えば、非特許文献１参照）。この紛失通信の一例を示す。
（１）紛失通信処理部１２４はｘｖ（ｑ）に対応する公開鍵ｐｋ（ｘｖ（ｑ））および秘密鍵ｓｋ（ｘｖ（ｑ））ならびにランダムなＰＫ（ｘｖ（ｑ）（＋）１）を生成し、紛失通信処理部１１９３に送信する。
（２）紛失通信処理部１１９３は、ｐｋ（０）を用いてｅ０を暗号化した暗号文ＥＮＣ（ｐｋ（０），ｅ０）およびｐｋ（１）を用いてｅ１を暗号化した暗号文ＥＮＣ（ｐｋ（１），ｅ１）を紛失通信処理部１２４に送る。
（３）紛失通信処理部１２４は、秘密鍵ｓｋ（ｘｖ（ｑ））を用いて暗号文ＥＮＣ（ｐｋ（０），ｅ０）およびＥＮＣ（ｐｋ（１），ｅ１）を復号する。これらのうち、ＥＮＣ（ｐｋ（ｖ（ｑ）），ｅｖ（ｑ））のみが正しく復号され、Ｘ［ｖ（ｑ）］：＝ｅｖ（ｑ）が得られる（ステップＳ１３１）。
【００４４】
制御部１２３はｑ＝Ｑであるかを判定する（ステップＳ１３２）。ｑ＝Ｑでなければ、制御部１２３はｑ：＝ｑ＋１とし（ｑ＋１を新たなｑとし）、処理をステップＳ１３１に戻す（ステップＳ１３３）。一方ｑ＝Ｑであれば、制御部１２３はＸ［ｘｖ（１）］，...，Ｘ［ｘｖ（Ｑ）］を記憶部１２２に格納する（ステップＳ１３４）。
【００４５】
＜秘匿回路を用いた秘匿計算＞
図７を用い、本形態の秘匿回路を用いた秘匿計算処理を説明する。
まず、秘匿計算装置１２（図３）の分離部１２５が、記憶部１２２から秘匿回路Ｆ：＝（Ｒ，Ｌ，ι）を読み込み、それをＲ，Ｌ，ιに分離して出力する（ステップＳ１４１）。制御部１２３はｊ：＝１とする（ステップＳ１４２）。
【００４６】
設定部１２６は、記憶部１２２からＸ［ｘｊ］を読み込み、Ｋｊ｜Ｌｊ：＝Ｘ［ｘｊ］となる入力鍵ｊおよび入力ラベルＬｊを得て出力する。入力鍵Ｋｊおよび入力ラベルＬｊはｘｊに対応する。すなわち、ｘｊ＝０の場合にはＫｊ：＝Ｋ０ｊかつＬｊ：＝Ｌ０ｊであり、ｘｊ＝１の場合にはＫｊ＝Ｋ１ｊかつＬｊ：＝Ｌ１ｊである（ステップＳ１４３）。制御部１２３はｊ＝ｎであるかを判定する（ステップＳ１４４）。ｊ＝ｎでなければ、制御部１２３はｊ：＝ｊ＋１とし（ｊ＋１を新たなｊとし）、処理をステップＳ１４３に戻す（ステップＳ１４５）。一方、ｊ＝ｎであれば、制御部１２３はｉ：＝ｎ＋１とする（ステップＳ１４６）。
【００４７】
ステップＳ１４６の処理の後、入力ワイヤ設定部１２７１は、Ａ：＝Ａ（ｉ），Ｂ：＝Ｂ（ｉ）に設定する（ステップＳ１４７）。写像部１２７２は、入力ラベルＬＡ，ＬＢを用い、ｘ：＝２ＬＡ＋ＬＢを得（ステップＳ１４８）、Ｒ，ｉ，ｘを用いてｃｘ：＝Ｈ（Ｒ，ｉ｜ｘ）を得て出力する（ステップＳ１４９）。制御部１２３はｘ＝０であるかを判定する（ステップＳ１５０）。出力鍵生成部１２７３はιを用いてＥiを特定し、ｘ＝０であればＫＡ，ＫＢおよびｃｘからＫｉ：＝Ｅi（ＫＡ＋２ＫＢ）（＋）ｃｘを得て出力し（ステップＳ１５１）、ｘ≠０であればＫＡ，ＫＢおよびｃｘからＫｉ：＝Ｅi（ＫＡ＋ＫＢ）（＋）ｃｘを得て出力する（ステップＳ１５２）。すなわち、出力鍵生成部１２７３は、ゲートＧ（ｉ）の入力値に応じた入力ラベルＬＡ，ＬＢに対応する値ｃｘとゲートＧ（ｉ）の入力鍵ＫＡ，ＫＢのトラップドア一方向性置換Ｅiによる像Ｅi（ＫＡ＋２ＫＢ）またはＥi（ＫＡ＋ＫＢ）とに応じたゲートの出力鍵Ｋｉを得る。言い換えると、本形態の出力鍵生成部１２７３は、入力ラベルＬＡ，ＬＢに対応する値ｃｘとゲートＧ（ｉ）の入力鍵ＫＡ，ＫＢのトラップドア一方向性置換Ｅiによる像である値Ｅi（ＫＡ＋ＫＢ）との排他的論理和をゲートＧ（ｉ）の出力鍵Ｋｉとする。なお、図８Ａおよび図８Ｂに例示するように、ゲートＧ（ν）の出力鍵Ｋν（ただし、ν∈｛ｎ＋１，…，ｎ＋ｕ−１｝）は、ゲートＧ（ν）の出力ワイヤＷ（ν）を入力ワイヤとする他のゲートＧ（ν’）の入力鍵ＫＡ（ν’）またはＫＢ（ν’）である。
【００４８】
ラベル復元部１２７５は、記憶部１２２からＬが含む秘匿化出力ラベルＬ［ｉ］を読み込み、Ｌ［ｉ］：＝（ｂ０，ｂ１，ｂ２，ｂ３）に分離する（ステップＳ１５３）。ラベル復元部１２７５は、入力鍵ＫＡ，ＫＢ、および秘匿化出力ラベルｂｘを用い、以下のように出力ラベルＬｉを得て出力する。
Ｌｉ：＝Ｈ’（ＫＡ｜ＫＢ）（＋）ｂｘ  （２）
すなわち、ラベル復元部１２７５は、ゲートＧ（ｉ）の入力値に応じた秘匿化出力ラベルｂｘおよびゲートＧ（ｉ）の入力鍵ＫＡ，ＫＢを用い、ゲートＧ（ｉ）の出力値に応じた出力ラベルＬｉを得て出力する。なお、図８Ａおよび図８Ｂに例示するように、ゲートＧ（ν）の出力ラベルＬν（ただし、ν∈｛ｎ＋１，…，ｎ＋ｕ−１｝）は、ゲートＧ（ν）の出力ワイヤＷ（ν）を入力ワイヤとする他のゲートＧ（ν’）の入力ラベルＬＡ（ν’）またはＬＢ（ν’）である（ステップＳ１５４）。
【００４９】
制御部１２３はｉ＝ｎ＋ｕであるかを判定する（ステップＳ１５５）。ｉ＝ｎ＋ｕでなければ、制御部１２３はｉ：＝ｉ＋１とし（ｉ＋１を新たなｉとし）、処理をステップＳ１４７に戻す（ステップＳ１５６）。
【００５０】
一方、ｉ＝ｎ＋ｕであれば、出力値生成部１２８は、出力ラベルＬｎ＋ｕおよび記憶部１２２から読み込んだラベル復号鍵ｄ：＝λｎ＋ｕを用い、Ｙ：＝Ｌｎ＋ｕ（＋）λｎ＋ｕを得て出力する（ステップＳ１５７）。
【００５１】
＜第１実施形態の特徴＞
以上のように、本形態では各ゲートの出力鍵に対応する暗号文を保存して必要がないため、秘匿回路のサイズを削減でき、通信量も従来方式のＯ（ｋ・ｕ）からＯ（ｕ）にまで減らすことができる。
【００５２】
［第２実施形態］
次に第２実施形態を説明する。以降、これまでに説明した事項との相違点を中心に説明し、既に説明した事項についてはそれと同じ参照番号を流用して説明を簡略化する。
＜構成＞
図１に例示するように、本形態の秘匿計算システム２は、秘匿回路を生成する秘匿計算装置２１、および当該秘匿回路を用いた秘匿計算を行う秘匿計算装置２２を有する。
【００５３】
＜秘匿計算装置２１＞
図９に例示するように、本形態の秘匿計算装置２１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部１１４、入力ワイヤ設定部１１５、置換ビット設定部１１６１、入力ラベル設定部１１６２、補完部２１７１ａ，２１７１ｂ、逆像部２１７２、入力鍵生成部１１７３、入力鍵・ラベルテーブル設定部１１７４、ラベル秘匿化部１１８１、出力ラベルテーブル設定部１１８２、符号化部１１９１、分離部１１９２、および紛失通信処理部１１９３を有する。
【００５４】
＜秘匿計算装置２２＞
図１０に例示するように、本形態の秘匿計算装置２２は、通信部１２１１、入力部１２１２、記憶部１２２、制御部１２３、紛失通信処理部１２４、分離部１２５、設定部１２６、入力ワイヤ設定部１２７１、写像部２２７２、出力鍵生成部２２７３、補完部２２７４、およびラベル復元部１２７５、および出力値生成部１２８を有する。
【００５５】
＜前処理＞
第１実施形態と同じである。
【００５６】
＜秘匿回路の生成処理＞
図１１を用い、本形態の秘匿回路の生成処理を説明する。
まず、秘匿計算装置２１（図９）が第１実施形態で説明したステップＳ１００からＳ１０６の処理を実行する。次に、補完部２１７１ａが、鍵Ｒおよび出力鍵Ｋ０ｉを用い、（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５）），（−１，Ｋ０ｉ）を多項式補完して、これら３点を通る２次多項式Ｐを得て出力する（図１３）。すなわち、補完部２１７１ａは、ゲートＧ（ｉ）に応じた複数の点（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５））、ならびに、所定値（−１）と、出力値（０，１）の何れかである第１値（０）に応じた出力鍵Ｋ０ｉとからなる点（−１，Ｋ０ｉ）によって定まる第１整式（Ｐ）を得て出力する。ＰはゲートＧ（ｉ）の出力ワイヤの値が０である場合に対応する（ステップＳ２０７１）。
【００５７】
補完部２１７１ｂが、鍵Ｒおよび出力鍵Ｋ１ｉを用い、（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５）），（−１，Ｋ１ｉ）を多項式補完して、これら３点を通る２次多項式Ｑを得て出力する（図１３）。すなわち、補完部２１７１ｂは、ゲートＧ（ｉ）に応じた複数の点（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５））、ならびに、所定値（−１）と、出力値（０，１）の何れかである第２値（１）に応じた出力鍵Ｋ１ｉとからなる点（−１，Ｋ１ｉ）によって定まる第２整式（Ｑ）を得て出力する。ＱはゲートＧ（ｉ）の出力ワイヤの値が１である場合に対応する（ステップＳ２０７２）。
【００５８】
逆像部２１７２が、記憶部１１２に格納された回路ｆを参照し、Ｅι，ｔι，ＬａＡ，ＬｂＢ，Ｐ，Ｑを用い、すべての（ａ，ｂ）∈｛０，１｝２について、
【数１３】
0006599215.tif 000015
を得て出力する。すなわち、逆像部２１７２は、ゲートＧ（ｉ）の定義域の元（ａ，ｂ）のそれぞれに応じた入力ラベルＬａＡ，ＬｂＢに対応する値２ＬａＡ＋ＬｂＢと、元（ａ，ｂ）がゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）のそれぞれに応じた出力鍵Ｋ０ｉまたはＫ１ｉと（上述のようにＰは出力鍵Ｋ０ｉに応じて定まり、Ｑは出力鍵Ｋ１ｉに応じて定まる）、に応じた像
【数１４】
0006599215.tif 000016
のトラップドア一方向性置換Ｅιによる逆像を得て出力する。言い換えると、逆像部２１７２は、ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）が第１値（０）となる元（ａ，ｂ）に応じた入力ラベルＬａＡ，ＬｂＢに対応する値２ＬａＡ＋ＬｂＢを第１整式（Ｐ）に代入して得られる値である像
【数１５】
0006599215.tif 000017
のトラップドア一方向性置換Ｅιによる逆像、および、ゲートＧ（ｉ）に入力された際の出力値Ｇｉ（ａ，ｂ）が第２値（１）となる元（ａ，ｂ）に応じた入力ラベルＬａＡ，ＬｂＢに対応する値２ＬａＡ＋ＬｂＢを第２整式（Ｑ）に代入して得られる値である像
【数１６】
0006599215.tif 000018
のトラップドア一方向性置換による逆像を得る。図１３に、ゲートＧ（ｉ）がＡＮＤゲートであり、λＡ＝λＢ＝０である場合の像Ｐ（０），Ｐ（１），Ｐ（２），Ｑ（３）を例示する（ステップＳ２０８）。
【００５９】
以降の処理は、秘匿計算装置１１，１２が秘匿計算装置２１，２２に置換される以外、第１実施形態で説明したステップＳ１１１〜Ｓ１１８と同じである。
【００６０】
＜回路ｆの入力値の符号化処理＞
第１実施形態と同じである。
【００６１】
＜秘匿回路を用いた秘匿計算＞
図１２を用い、本形態の秘匿回路を用いた秘匿計算処理を説明する。
まず、秘匿計算装置２２（図１０）が第１実施形態で説明したステップＳ１４１〜Ｓ１４８，Ｓ１５０の処理を実行する。ただし、写像部１２７２に代えて写像部２２７２がステップＳ１４８の処理を実行する。その後、補完部２２７４がιを用いてＥiを特定し、ｘ＝０であれば、ｘおよびＫＡ，ＫＢからＶ：＝（ｘ，Ｅi（ＫＡ＋２ＫＢ））を得て出力し（ステップＳ２５１）、ｘ≠０であれば、ｘおよびＫＡ，ＫＢからＶ：＝（ｘ，Ｅi（ＫＡ＋ＫＢ））を得て出力する（ステップＳ２５２）。次に、補完部２２７４は、Ｒ，ｉ，Ｖを用い、（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５）），Ｖを多項式補完して２次多項式Ｕを生成する。すなわち、補完部２２７４は、ゲートＧ（ｉ）に応じた複数の点（４，Ｈ（Ｒ，ｉ｜４）），（５，Ｈ（Ｒ，ｉ｜５））、ならびに、入力ラベルに対応する値ｘ＝２ＬＡ＋ＬＢおよびゲートＧ（ｉ）の入力鍵のトラップドア一方向性置換による像である値Ｅi（ＫＡ＋２ＫＢ）またはＥi（ＫＡ＋２ＫＢ）からなる点Ｖによって定まる整式Ｕを得る。例えば、図１３の例ではｘ＝２ＬＡ＋ＬＢ＝３のときにＵ＝Ｑとなり、ｘ＝０，１，２のときにＵ＝Ｐとなる（ステップＳ２５３）。出力鍵生成部２２７３は、出力鍵Ｋｉ：＝Ｕ（−１）を得て出力する。すなわち、出力鍵生成部２２７３は、整式Ｕに所定値（−１）を代入してゲートＧ（ｉ）の出力鍵Ｋｉを得て出力する。言い換えると、出力鍵生成部２２７３は、ゲートＧ（ｉ）の入力値（ａ，ｂ）に応じた入力ラベルＬＡ，ＬＢに対応する値ｘ＝２ＬＡ＋ＬＢとゲートＧ（ｉ）の入力鍵ＫＡ，ＫＢのトラップドア一方向性置換Ｅiによる像Ｅi（ＫＡ＋２ＫＢ）とに応じたゲートＧ（ｉ）の出力鍵Ｋｉを得て出力する（ステップＳ２５４）。
【００６２】
それ以降の処理は、第１実施形態で説明したステップＳ１５４〜Ｓ１５７と同じである。
【００６３】
＜第２実施形態の特徴＞
以上のように、本形態では各ゲートの出力鍵に対応する暗号文を保存して必要がないため、秘匿回路のサイズを削減でき、通信量も減らすことができる。
【００６４】
［第３実施形態］
第３実施形態は第１実施形態の変形例である。第１実施形態では、秘匿化対象の回路ｆが特定された後に当該回路ｆの各ゲートが秘匿化された。本形態では、秘匿化対象の回路ｆが特定される前に一般的なＡＮＤゲート、ＯＲゲート、ＸＯＲなどのゲートを秘匿化しておき、秘匿化されたゲートを用いて秘匿化対象の回路ｆを秘匿化する。これにより、秘匿化対象の回路ｆを秘匿化する際の演算量を削減できる。
【００６５】
＜構成＞
図１に例示するように、本形態の秘匿計算システム３は、秘匿回路を生成する秘匿計算装置３１、および当該秘匿回路を用いた秘匿計算を行う秘匿計算装置３２を有する。
【００６６】
＜秘匿計算装置３１＞
図２に例示するように、本形態の秘匿計算装置３１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部３１４、入力ワイヤ設定部３１５、置換ビット設定部１１６１、入力ラベル設定部１１６２、写像部３１７１、逆像部３１７２、入力鍵生成部３１７３、入力鍵・ラベルテーブル設定部３１７４、ラベル秘匿化部３１８１、出力ラベルテーブル設定部３１８２、符号化部１１９１、分離部１１９２、紛失通信処理部１１９３、および秘匿回路構成部３１８３を有する。
【００６７】
＜秘匿計算装置３２＞
図３に例示するように、本形態の秘匿計算装置３２は、通信部１２１１、入力部１２１２、記憶部１２２、制御部１２３、紛失通信処理部１２４、分離部１２５、設定部１２６、入力ワイヤ設定部１２７１、写像部３２７２、出力鍵生成部１２７３、復元部３２７３、分離部１２７４、およびラベル復元部１２７５、および出力値生成部１２８を有する。
【００６８】
＜前処理＞
第１実施形態の前処理との相違点は、秘匿対象の回路ｆを記憶部１１２に格納しない点、および、一般的な複数のゲートを秘匿化しておく点である。その他は、第１実施形態と同じである。
【００６９】
図１４および図１５を用い、本形態で行う一般的なゲートの秘匿化処理を説明する。本形態ではＳをｕ以上の正の整数とし、Ｓ個の一般的なゲートをＧ’（１），…，Ｇ’（Ｓ）と表記する。ゲートＧ’（ｓ）（ただし、ｓ∈｛１，…，Ｓ｝）は２入力１出力の論理ゲートである（Ｇ’（ｓ）：｛０，１｝×｛０，１｝→｛０，１｝）。例えば、Ｇ’（１），…，Ｇ’（Ｓ１）をＡＮＤゲートとし、Ｇ’（Ｓ１＋１），…，Ｇ’（Ｓ２）をＯＲゲートとし、Ｇ’（Ｓ２＋１），…，Ｇ’（Ｓ）をＸＯＲゲートとする。ゲートＧ’（ｓ）の入力ワイヤをＷ（Ａ’（ｓ））およびＷ（Ｂ’（ｓ））と表記し、出力ワイヤをＷ（ｓ）と表記する。ゲートＧ’（ｓ）（ただし、ｓ∈｛１，…，Ｓ｝）の種類および入力ワイヤＷ（Ａ’（ｓ）），Ｗ（Ｂ’（ｓ））の入力値Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ））∈｛０，１｝に応じ、出力ワイヤＷ（ｓ）の出力値Ｇ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））∈｛０，１｝が決まる。すなわち、Ｉ（Ａ’（ｓ））およびＩ（Ｂ’（ｓ））に対するゲートＧ’（ｓ）での論理演算結果がＧ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））となる。
【００７０】
まず、秘匿計算装置３１（図２）の初期設定部３１４が、位数ｑの有限体Ｆｑの元をＦｑの元に写すトラップドア一方向性置換Ｅι：Ｆｑ→Ｆｑおよびそのトラップドアｔιを選択する。また初期設定部３１４は、Ｈの鍵Ｒをランダム（例えば、一様ランダム）に選択して出力する（ステップＳ１００）。次に、制御部１１３がｓ：＝Ｓに設定する（ステップＳ３０３）。
【００７１】
入力ワイヤ設定部３１５は、Ａ：＝Ａ’（ｓ），Ｂ：＝Ｂ’（ｓ）に設定する（ステップＳ３０４）。
【００７２】
初期設定部３１４は、有限体Ｆｑの２個の元をランダム（例えば、一様ランダム）に選択し、それらを出力鍵Ｋ０ｓ，Ｋ１ｓ∈Ｆｑとして設定して出力する。ただし、出力鍵Ｋ０ｓはＧ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））＝０に対応し、出力鍵Ｋ１ｓはＧ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））＝１に対応する（ステップＳ３０１）。
【００７３】
さらに初期設定部３１４は、置換ビットλｓ、出力ラベルＬ０ｓ：＝λｓ，Ｌ１ｓ：＝λｓ（＋）１を設定する。出力ラベルＬ０ｓはＧ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））＝０に対応し、出力ラベルＬ１ｓはＧ’ｓ（Ｉ（Ａ’（ｓ）），Ｉ（Ｂ’（ｓ）））＝１に対応する。すなわち、出力ラベルＬ０ｓは出力鍵Ｋ０ｓに対応し、出力鍵Ｋ１ｓは出力ラベルＬ１ｓに対応する。λｓ＝０であってもよいし、λｓ＝１であってもよい（ステップＳ３０５）。
【００７４】
置換ビット設定部１１６１は、入力ワイヤＷ（Ａ），Ｗ（Ｂ）に対し、それぞれ置換ビットλＡ，λＢ∈｛０，１｝をランダムに選択する（ステップＳ１０５）。入力ラベル設定部１１６２は、すべての（ａ，ｂ）∈｛０，１｝２について、以下のように入力ラベルＬａＡ，ＬｂＢ∈｛０，１｝を設定する。ただし、ａ∈｛０，１｝は入力ワイヤＷ（Ａ）の入力値であり、ｂ∈｛０，１｝は入力ワイヤＷ（Ｂ）の入力値である（ステップＳ１０６）。
ＬａＡ：＝λＡ（＋）ａ
ＬｂＢ：＝λＢ（＋）ｂ
【００７５】
写像部３１７１が、鍵Ｒを用い、ｘ＝０，１，２，３およびｓについてｃｘ：＝Ｈ（Ｒ，ｓ｜ｘ）を生成して出力する（ステップＳ３０７）。
【００７６】
逆像部３１７２が、Ｅι，ｔι，ＬａＡ，ＬｂＢ，Ｋ０ｉ，Ｋ１ｉを用い、すべての（ａ，ｂ）∈｛０，１｝２について、逆像
【数１７】
0006599215.tif 000019
を得て出力する（ステップＳ３０８）。
【００７７】
入力鍵生成部３１７３は、ステップＳ３０８で得られた逆像Ｐ０，Ｐ１，Ｐ２，Ｐ３を用い、以下の連立方程式を解いて、ａ，ｂ∈｛０，１｝のそれぞれに応じた入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂ∈Ｆｑを得て出力する（ステップＳ３０９）。
【数１８】
0006599215.tif 000020
【００７８】
ラベル秘匿化部３１８１は、入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂおよび出力ラベルＬｓＧ’s（ａ，ｂ）を用い、すべての（ａ，ｂ）∈｛０，１｝２について、以下のように秘匿化出力ラベル
【数１９】
0006599215.tif 000021
を設定して出力する。出力ラベルＬｓＧ’s（ａ，ｂ）は、元（ａ，ｂ）がゲートＧ’（ｓ）に入力された際の出力値Ｇ’ｓ（ａ，ｂ）に対応する。なお、上付き添え字の「Ｇ’ｓ（ａ，ｂ）」は「Ｇ’ｓ（ａ，ｂ）」を意味する（ステップＳ３１１）。
【００７９】
出力ラベルテーブル設定部３１８２は、秘匿化出力ラベルｂ０，ｂ１，ｂ２，ｂ３を用い、秘匿化出力ラベルＬ［ｓ］：＝（ｂ０，ｂ１，ｂ２，ｂ３）を得て出力する（ステップＳ３１２）。
【００８０】
入力鍵・ラベルテーブル設定部３１７４は、入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂ、入力ラベルＬ０Ａ，Ｌ１Ａ，Ｌ０Ｂ，Ｌ１Ｂ、出力鍵Ｋｓ０，Ｋｓ１、出力ラベルＬ０ｓ，Ｌ１ｓ、および秘匿化出力ラベルＬ［ｓ］を入力とし、ゲートをＧ’（ｓ）に対して、（Ｇ’（ｓ）；Ｋ０Ａ｜Ｌ０Ａ，Ｋ１Ａ｜Ｌ１Ａ，Ｋ０Ｂ｜Ｌ０Ｂ，Ｋ１Ｂ｜Ｌ１Ｂ，Ｋ０ｓ｜Ｌ０ｓ，Ｋ１ｓ｜Ｌ１ｓ，Ｌ［ｓ］）を設定し、記憶部１１３に格納する（ステップＳ３１２１）。
【００８１】
制御部１１３は、ｓ＝１であるかを判定する（ステップＳ３０９２）。ｓ＝１でなければ、制御部１１３は、ｓ：＝ｓ−１とし（ｓ−１を新たなｓとし）、処理をステップＳ３０４に戻す（ステップＳ３０９３）。一方、ｓ＝１であれば処理を終える。
【００８２】
＜秘匿回路の生成処理＞
図１６を用い、本形態の秘匿回路の生成処理を説明する。
秘匿計算装置３１に秘匿対象の回路ｆ：＝（ｎ，ｕ，Ａｓｅｔ，Ｂｓｅｔ，Ｇｓｅｔ）が入力され、記憶部１１２に格納される。その後まず、制御部１１３がｉ：＝ｎ＋ｕに設定する（ステップＳ３０３）。
【００８３】
入力ワイヤ設定部３１５は、Ａ：＝Ａ（ｉ），Ｂ：＝Ｂ（ｉ）に設定する（ステップＳ１０４）。秘匿回路構成部３１８３は、記憶部１１２に格納された秘匿対象の回路ｆを参照し、回路ｆを構成するゲートＧ（ｉ）∈Ｇｓｅｔと同一の論理演算を行う１つのゲートＧ’（ｓ’）（ただし、ｓ’∈｛１，…，Ｓ｝）を選択し（ステップＳ３０７１）、ｉをｓ’に写す写像ｓ’＝ｍａｐ（ｉ）を設定を設定する。ｍａｐはｓ’とｉとを対応付けるテーブルであってもよいし、ｉからｓ’を得る関数であってもよい（ステップＳ３０７２）。また、秘匿回路構成部３１８３は、以下のようにＫ０Ａ，Ｌ０Ａ，Ｋ１Ａ，Ｌ１Ａ，Ｋ０Ｂ，Ｌ０Ｂ，Ｋ１Ｂ，Ｌ１Ｂ，Ｋ０ｉ，Ｌ０ｉ，Ｋ１ｉ，Ｌ０ｉ，Ｌ［ｉ］を設定する（ステップＳ３０７３）。
Ｋ０Ａ：＝Ｋ０Ａ（ｓ’），Ｌ０Ａ：＝Ｌ０Ａ（ｓ’）
Ｋ１Ａ：＝Ｋ１Ａ（ｓ’），Ｌ１Ａ：＝Ｌ１Ａ（ｓ’）
Ｋ０Ｂ：＝Ｋ０Ｂ（ｓ’），Ｌ０Ｂ：＝Ｌ０Ｂ（ｓ’）
Ｋ１Ｂ：＝Ｋ１Ｂ（ｓ’），Ｌ１Ｂ：＝Ｌ１Ｂ（ｓ’）
Ｋ０ｉ：＝Ｋ０ｓ’，Ｌ０ｉ：＝Ｌ０ｓ’
Ｋ１ｉ：＝Ｋ１ｓ’，Ｌ０ｉ：＝Ｌ０ｓ’
Ｌ［ｉ］：＝Ｌ［ｓ’］
【００８４】
入力鍵・ラベルテーブル設定部３１７４は、入力鍵Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂおよび入力ラベルＬ０Ａ，Ｌ１Ａ，Ｌ０Ｂ，Ｌ１Ｂを入力とし、Ａに対してテーブルｅ［Ａ］：＝（Ｋ０Ａ｜Ｌ０Ａ，Ｋ１Ａ｜Ｌ１Ａ）を設定し、Ｂに対してテーブルｅ［Ｂ］：＝（Ｋ０Ｂ｜Ｌ０Ｂ，Ｋ１Ｂ｜Ｌ１Ｂ）を設定して出力する（ステップＳ３１０）。
【００８５】
制御部１１３は、ｉ＝ｎ＋１であるかを判定する（ステップＳ１１３）。ｉ＝ｎ＋１でなければ、制御部１１３は、ｉ：＝ｉ−１とし（ｉ−１を新たなｉとし）、処理をステップＳ１０４に戻す（ステップＳ１１４）。一方、ｉ＝ｎ＋１であれば、制御部１１３はステップＳ３１３の処理を実行させる。
【００８６】
ステップＳ３１３では、秘匿回路構成部３１８３が、記憶部１１２に格納された秘匿対象の回路ｆを参照し、すべてのｃ∈｛０，１｝，ｉ’∈｛ｎ＋１，．．．，ｎ＋ｕ−１｝について、次のような暗号化処理を行う。
（Ａ）ゲートＧ（ｉ’）∈Ｇｓｅｔの出力ワイヤＷ（ｉ’）が他のゲートＧ（ｉ”）∈Ｇｓｅｔ（ただし、ｉ”≠ｉ’かつｉ”∈｛３ｎ／２＋１，．．．，ｎ＋ｕ｝）の入力ワイヤＷ（Ａ（ｉ”））である場合、秘匿回路構成部３１８３は、ゲートＧ（ｉ’）の出力鍵Ｋｃｉ’を共通鍵として用い、共通鍵暗号方式に則って、ゲートＧ（ｉ”）の入力鍵ＫｃＡ（ｉ”）を暗号化し、暗号文ＥＡ（ｉ”，ｃ）：＝Ｅｎｃ（Ｋｃｉ’，ＫｃＡ（ｉ”））を得て出力する。さらにこの場合、秘匿回路構成部３１８３は、ゲートＧ（ｉ’）の出力ラベルＬｃｉ’を共通鍵として用い、共通鍵暗号方式に則って、ゲートＧ（ｉ”）の入力ラベルＬｃＡ（ｉ”）を暗号化し、暗号文ＥＬＡ（ｉ”，ｃ）：＝Ｅｎｃ（Ｌｃｉ’，ＬｃＡ（ｉ”））を得て出力する。
（Ｂ）ゲートＧ（ｉ’）∈Ｇｓｅｔの出力ワイヤＷ（ｉ’）が他のゲートＧ（ｉ”）∈Ｇｓｅｔ（ただし、ｉ”≠ｉ’かつｉ”∈｛ｎ＋１，．．．，ｎ＋ｕ｝）の入力ワイヤＷ（Ｂ（ｉ”））である場合、秘匿回路構成部３１８３は、ゲートＧ（ｉ’）の出力鍵Ｋｃｉ’を共通鍵として用い、共通鍵暗号方式に則って、ゲートＧ（ｉ”）の入力鍵ＫｃＢ（ｉ”）を暗号化し、暗号文ＥＢ（ｉ”，ｃ）：＝Ｅｎｃ（Ｋｃｉ’，ＫｃＡ（ｉ”））を得て出力する。さらにこの場合、秘匿回路構成部３１８３は、ゲートＧ（ｉ’）の出力ラベルＬｃｉ’を共通鍵として用い、共通鍵暗号方式に則って、ゲートＧ（ｉ”）の入力ラベルＬｃＢ（ｉ”）を暗号化し、暗号文ＥＬＢ（ｉ”，ｃ）：＝Ｅｎｃ（Ｌｃｉ’，ＬｃＢ（ｉ”））を得て出力する（ステップＳ３１３）。
【００８７】
その後、第１実施形態で説明したステップＳ１１５およびＳ１１６の処理が行われる。次に、通信部１１１１は、秘匿回路Ｆ：＝（Ｒ，Ｌ，ι）、テーブルｅ、ラベル復号鍵ｄ：＝λｎ＋ｕ、写像ｍａｐ、暗号化テーブル｛（ＥＡ（ｉ”，０）｜Ｌ０ｉ’），（ＥＡ（ｉ”，１）｜Ｌ１ｉ’），（ＥＬＡ（ｉ”，０）｜Ｌ０ｉ’），（ＥＬＡ（ｉ”，１）｜Ｌ１ｉ’）｝ｏｒ｛（ＥＢ（ｉ”，０）｜Ｌ０ｉ’），（ＥＢ（ｉ”，１）｜Ｌ１ｉ’），（ＥＬＢ（ｉ”，０）｜Ｌ０ｉ’），（ＥＬＢ（ｉ”，１）｜Ｌ１ｉ’）｝を出力する。ただし、ιはＥιを特定するための情報である。これらは秘匿計算装置３２に送信され、秘匿計算装置３２（図３）の通信部１２１１で受信され、記憶部１２２に格納される（ステップＳ３１７）。その後、第１実施形態で説明したステップＳ１１８の処理が行われ、処理を終了する。
【００８８】
＜回路ｆの入力値の符号化処理＞
第１実施形態と同じである。
【００８９】
＜秘匿回路を用いた秘匿計算＞
図１７を用い、本形態の秘匿回路を用いた秘匿計算処理を説明する。
まず、秘匿計算装置１２に代えて秘匿計算装置３２（図３）が、第１実施形態で説明したステップＳ１４１からＳ１４８の処理を実行する。次に、写像部３２７２は、Ｒ，ｉ，ｘ，ｍａｐを用いてｃｘ：＝Ｈ（Ｒ，ｍａｐ（ｉ）｜ｘ）を得て出力する（ステップＳ３４９）。次に、秘匿計算装置１２に代えて秘匿計算装置３２が、第１実施形態で説明したステップＳ１５０からＳ１５５の処理を実行する。
【００９０】
ステップＳ１５５でｉ＝ｎ＋ｕでなければ、復元部３２７３が以下のように（ＫＡ（ｉ”），ＬＡ（ｉ”））または（ＫＢ（ｉ”），ＬＢ（ｉ”））を得て出力する。
（Ａ）ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）が他のゲートＧ（ｉ”）の入力ワイヤＷ（Ａ（ｉ”））である場合、復元部３２７３は、Ｋｉ，Ｌｉ，ＥＡ（ｉ”），ＥＬＡ（ｉ”）から
ＫＡ（ｉ”）：＝Ｄｅｃ（Ｋｉ，ＥＡ（ｉ”））
ＬＡ（ｉ”）：＝Ｄｅｃ（Ｌｉ，ＥＬＡ（ｉ”））
を得て出力する。
（Ｂ）ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）が他のゲートＧ（ｉ”）の入力ワイヤＷ（Ｂ（ｉ”））である場合、復元部３２７３は、Ｋｉ，Ｌｉ，ＥＢ（ｉ”），ＥＬＢ（ｉ”）から
ＫＢ（ｉ”）：＝Ｄｅｃ（Ｋｉ，ＥＢ（ｉ”））
ＬＢ（ｉ”）：＝Ｄｅｃ（Ｌｉ，ＥＬＢ（ｉ”））
を得て出力する。
ただし、Ｌｉ＝Ｌ０ｉの場合にＥＡ（ｉ”）＝ＥＡ（ｉ”，０）かつＥＢ（ｉ”）＝ＥＢ（ｉ”，０）であり、Ｌｉ＝Ｌ１ｉの場合にＥＡ（ｉ”）＝ＥＡ（ｉ”，１）かつＥＢ（ｉ”）＝ＥＢ（ｉ”，１）である。Ｄｅｃ（α，β）は、αを共通鍵として用い、ステップＳ３１３と同じ共通鍵暗号方式に則り、暗号文βを復号して得られる値を意味する（ステップＳ３５５１）。その後、ステップＳ１５６の処理の後、ステップＳ１４７に戻る。
【００９１】
一方、ステップＳ１５５でｉ＝ｎ＋ｕであれば、ステップＳ１５７の処理が実行されて処理を終了する。
【００９２】
［第４実施形態］
第４実施形態は第２実施形態の変形例である。本形態では、秘匿化対象の回路ｆが特定される前に一般的なゲートを秘匿化しておき、秘匿化されたゲートを用いて秘匿化対象の回路ｆを秘匿化する。これにより、秘匿化対象の回路ｆを秘匿化する際の演算量を削減できる。
【００９３】
＜構成＞
図１に例示するように、本形態の秘匿計算システム４は、秘匿回路を生成する秘匿計算装置４１、および当該秘匿回路を用いた秘匿計算を行う秘匿計算装置４２を有する。
【００９４】
＜秘匿計算装置４１＞
図９に例示するように、本形態の秘匿計算装置４１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部３１４、入力ワイヤ設定部３１５、置換ビット設定部１１６１、入力ラベル設定部１１６２、補完部４１７１ａ，４１７１ｂ、逆像部４１７２、入力鍵生成部３１７３、入力鍵・ラベルテーブル設定部３１７４、ラベル秘匿化部３１８１、出力ラベルテーブル設定部３１８２、符号化部１１９１、分離部１１９２、紛失通信処理部１１９３、および秘匿回路構成部３１８３を有する。
【００９５】
＜秘匿計算装置４２＞
図１０に例示するように、本形態の秘匿計算装置４２は、通信部１２１１、入力部１２１２、記憶部１２２、制御部１２３、紛失通信処理部１２４、分離部１２５、設定部１２６、入力ワイヤ設定部１２７１、写像部４２７２、出力鍵生成部２２７３、補完部４２７４、復元部３２７３、ラベル復元部１２７５、および出力値生成部１２８を有する。
【００９６】
＜前処理＞
第１実施形態の前処理との相違点は、秘匿対象の回路ｆを記憶部１１２に格納しない点、および、一般的な複数のゲートを秘匿化しておく点である。その他は、第１実施形態と同じである。
【００９７】
図１８を用い、本形態で行う一般的なゲートの秘匿化処理を説明する。まず、秘匿計算装置４１（図９）が、前述したステップＳ１００，Ｓ３０３，Ｓ３０４，Ｓ３０１，Ｓ１０５，Ｓ３０５，Ｓ１０６の処理を実行する。次に補完部４１７１ａが、鍵Ｒおよび出力鍵Ｋ０ｓを用い、（４，Ｈ（Ｒ，ｓ｜４）），（５，Ｈ（Ｒ，ｓ｜５）），（−１，Ｋ０ｓ）を多項式補完して、これら３点を通る２次多項式Ｐを得て出力する（ステップＳ４０７１）。さらに補完部４１７１ｂが、鍵Ｒおよび出力鍵Ｋ１ｓを用い、（４，Ｈ（Ｒ，ｓ｜４）），（５，Ｈ（Ｒ，ｓ｜５）），（−１，Ｋ１ｓ）を多項式補完して、これら３点を通る２次多項式Ｑを得て出力する（ステップＳ４０７２）。また逆像部２１７２が、Ｅι，ｔι，ＬａＡ，ＬｂＢ，Ｐ，Ｑを用い、すべての（ａ，ｂ）∈｛０，１｝２について、
【数２０】
0006599215.tif 000022
を得て出力する（ステップＳ４０８）。
【００９８】
その後、第３実施形態と同様に、ステップＳ１０９，Ｓ３１１，Ｓ３１２１，Ｓ３０９２の処理が実行され、ｓ＝１でなければ、制御部１１３は、ｓ：＝ｓ−１とし（ｓ−１を新たなｓとし）、処理をステップＳ３０４に戻す（ステップＳ３０９３）。一方、ｓ＝１であれば処理を終える。
【００９９】
＜秘匿回路の生成処理＞
第３実施形態と同じである。
【０１００】
＜回路ｆの入力値の符号化処理＞
第１実施形態と同じである。
【０１０１】
＜秘匿回路を用いた秘匿計算＞
図１９を用い、本形態の秘匿回路を用いた秘匿計算処理を説明する。
まず、秘匿計算装置２２に代えて秘匿計算装置４２（図１０）がステップＳ１４１からＳ１４８，Ｓ１５０，Ｓ２５１，Ｓ２５２の処理を実行する。その後、補完部４２７４は、Ｒ，ｉ，Ｖ，ｍａｐを用い、（４，Ｈ（Ｒ，ｍａｐ（ｉ）｜４）），（５，Ｈ（Ｒ，ｍａｐ（ｉ）｜５）），Ｖを多項式補完して２次多項式Ｕを生成する（ステップＳ４５３）。
【０１０２】
その後、ステップＳ２５４，Ｓ１５３からＳ１５５の処理が実行され、ステップＳ１５５でｉ＝ｎ＋ｕでなければステップＳ３５５１，Ｓ１５６の処理の後、ステップＳ１４７に戻る。ステップＳ１５５でｉ＝ｎ＋ｕであれば、ステップＳ１５７の処理が実行されて処理を終了する。
【０１０３】
［変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、ステップＳ１１１の式（１）に代えて、すべての（ａ、ｂ）∈｛０，１｝２について、
【数２１】
0006599215.tif 000023
を満たす秘匿化出力ラベル
【数２２】
0006599215.tif 000024
を設定してもよい。ただし、Ｈ”は任意長ビットの値をｋビット（ｋ＞３）の値に写す一方向性写像Ｈ”：｛０，１｝＊→｛０，１｝ｋである。一方向性写像の例はハッシュ関数である。共通鍵暗号関数または公開鍵暗号関数を一方向性写像として用いてもよい。一方向性写像は、関数であってもよいし、アルゴリズムであってもよい。また［α］βはαのβに対応するビット位置（例えば先頭からβ＋１ビット目）のビット値を表す。すなわち、秘匿化出力ラベルが、入力鍵に対応するビット列の元（ａ，ｂ）に応じたビット位置を表してもよい。この場合、ステップＳ１５４では、式（２）に代えて、以下のように出力ラベルＬｉを得る。
【数２３】
0006599215.tif 000025
【０１０４】
上述の実施形態では、ＬａＡ，ＬｂＢに対応する値として２ＬａＡ＋ＬｂＢを用い、ＬＡ，ＬＢに対応する値として２ＬＡ＋ＬＢを用いた。しかしながら、２ＬａＡ＋ＬｂＢに代えてその他の単射な写像ｇ（ＬａＡ，ＬｂＢ）：｛０，１｝２→｛０，１｝を用い、２ＬＡ＋ＬＢに代えてｇ（ＬＡ，ＬＢ）を用いてもよい。
【０１０５】
また、ステップＳ１１０で例示したＫ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂについての連立方程式に代え、Ｐ０，Ｐ１，Ｐ２，Ｐ３，Ｋ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂを用いたＫ０Ａ，Ｋ１Ａ，Ｋ０Ｂ，Ｋ１Ｂについてのその他の連立方程式を用いてもよい。この場合には、使用する連立方程式の左辺のＰｘと等号が成立する右辺の式に応じ、ステップＳ１５０，Ｓ１５１，Ｓ１５２，Ｓ２５１，Ｓ２５２の各ｘに対応するＫＡ，ＫＢについての式を変更すればよい。例えば、以下の連立方程式が用いられてもよい。
【数２４】
0006599215.tif 000026
この場合、ステップＳ１５０〜Ｓ１５２に代えて、ｘ＝１であればＫＡ，ＫＢおよびｃｘからＫｉ：＝Ｅi（ＫＡ＋ＫＢ）（＋）ｃｘを得て出力し、ｘ≠１であればＫＡ，ＫＢおよびｃｘからＫｉ：＝Ｅi（ＫＡ＋２ＫＢ）（＋）ｃｘを得て出力すればよい。ステップＳ１５０，Ｓ２５１，Ｓ２５２に代えて、ｘ＝１であれば、ｘおよびＫＡ，ＫＢからＶ：＝（ｘ，Ｅi（ＫＡ＋２ＫＢ））を得て出力し、ｘ≠１であれば、ｘおよびＫＡ，ＫＢからＶ：＝（ｘ，Ｅi（ＫＡ＋ＫＢ））を得て出力すればよい。
【０１０６】
回路ｆが複数並列に存在する場合には、回路ごとに独立に上述の形態の処理を行えばよい。また、第２実施形態の多項式が単項式であってもよい。さらに、１個の秘匿計算装置が回路ｆの全ゲートを秘匿化するのではなく、複数の秘密計算装置で回路ｆのゲートを分担して秘匿化してもよい。例えば、ゲートごとに異なる秘密計算装置が上述した秘匿化処理を行ってもよい。
【０１０７】
また、λｎ＋ｕ＝０であってもよい。この場合にはステップＳ１５７に代えてＹ：＝Ｌｎ＋ｕとすればよい。
【０１０８】
その他、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。
【０１０９】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１０】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１１１】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１１３】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１１４】
１１，１２，２１，２２  秘匿計算装置
【図１】
0006599215.tif 000045
【図２】
0006599215.tif 000046
【図３】
0006599215.tif 000047
【図４】
0006599215.tif 000048
【図５】
0006599215.tif 000049
【図６】
0006599215.tif 000050
【図７】
0006599215.tif 000051
【図８】
0006599215.tif 000052
【図９】
0006599215.tif 000053
【図１０】
0006599215.tif 000054
【図１１】
0006599215.tif 000055
【図１２】
0006599215.tif 000056
【図１３】
0006599215.tif 000057
【図１４】
0006599215.tif 000058
【図１５】
0006599215.tif 000059
【図１６】
0006599215.tif 000060
【図１７】
0006599215.tif 000061
【図１８】
0006599215.tif 000062
【図１９】
0006599215.tif 000063