(57)【特許請求の範囲】
【請求項１】
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有する回路秘匿装置。
【請求項２】
請求項１の回路秘匿装置であって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、λ（Ｂ）∈｛０，１｝が置換ビットであり、
前記入力鍵設定部は、
前記入力値Ｉ（Ａ）に対応する前記入力鍵ＫＡＩ（Ａ）が設定され、前記入力値Ｉ（Ｂ）に対応する入力鍵ＫＢＩ（Ｂ）が設定されている場合に、ｄｉ＝ＫＡ１−ＫＡ０を得、前記入力値Ｉ（Ｂ）に対応するラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）についてＫＢ’λ（Ｂ）＝ＫＢλ（Ｂ）を得、ＫＢ’１（ｘｏｒ）λ（Ｂ）＝ＫＢ’λ（Ｂ）＋（−１）λ（Ｂ）ｄｉを得、前記入力鍵ＫＢ１（ｘｏｒ）λ（Ｂ）を含む値の関数値を共通鍵としてＫＢ’１（ｘｏｒ）λ（Ｂ）を暗号化した暗号文Ｅｉを得る、回路秘匿装置。
【請求項３】
請求項２の回路秘匿装置であって、
前記入力鍵設定部は、
前記入力値Ｉ（Ａ）に対応する前記入力鍵ＫＡＩ（Ａ）が設定されているが、前記入力値Ｉ（Ｂ）に対応する前記入力鍵ＫＢＩ（Ｂ）が設定されていない場合に、ｄｉ＝ＫＡ１−ＫＡ０を得、ＫＢ’１＝ＫＢ’０＋ｄｉを満たす前記入力鍵ＫＢ’１および前記入力鍵ＫＢ’０を得、
前記入力鍵ＫＡＩ（Ａ）および前記入力鍵ＫＢＩ（Ｂ）が設定されていない場合に、ｄｉをランダムに選択し、ＫＡ１＝ＫＡ０＋ｄｉを満たす前記入力鍵ＫＡ１および前記入力鍵ＫＡ０、ならびに、ＫＢ’１＝ＫＢ’０＋ｄｉを満たす前記入力鍵ＫＢ’１および前記入力鍵ＫＢ’０を得る、回路秘匿装置。
【請求項４】
請求項１から３の何れかの回路秘匿装置であって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、λ（Ａ），λ（Ｂ）∈｛０，１｝が置換ビットであり、
前記入力値Ｉ（Ａ）に対応するラベルＬＡＩ（Ａ）が設定されていない場合に、前記ラベルＬＡＩ（Ａ）＝λ（Ａ）（ｘｏｒ）Ｉ（Ａ）を設定し、前記入力値Ｉ（Ｂ）に対応するラベルＬＢＩ（Ｂ）が設定されていない場合に、前記ラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）を設定する入力ラベル設定部を有する回路秘匿装置。
【請求項５】
請求項１から４の何れかの回路秘匿装置であって、
λ（ｉ）が置換ビットであり、前記入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値を共通鍵として、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対して設定したラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））＝ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））（ｘｏｒ）λ（ｉ）を暗号化した暗号文を得る出力ラベル設定部を有する回路秘匿装置。
【請求項６】
請求項１から５の何れかの回路秘匿装置であって、
前記出力値ｇｉ（１，０）と前記出力値ｇｉ（０，１）とが等しい、回路秘匿装置。
【請求項７】
請求項１から６の何れかの回路秘匿装置であって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０を含む値の関数値とＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０＋ｂ０ｄｉを含む値の関数値を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値とｂ１Ψｉとの排他的論理和を前記出力鍵Ｋｉ１とし、γ（０，０）＝ｂ０、γ（０，１）＝γ（１，０）＝１（ｘｏｒ）ｂ０、およびγ（１，１）＝ｂ１を得る、回路秘匿装置。
【請求項８】
請求項１から６の何れかの回路秘匿装置であって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０を含む値の関数値とｂ１Ψｉとの排他的論理和を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉを含む値の関数値をＫｉ１とし、γ（０，０）＝ｂ１、γ（０，１）＝γ（１，０）＝ｂ０、およびγ（１，１）＝１（ｘｏｒ）ｂ０を得る、回路秘匿装置。
【請求項９】
請求項１から６の何れかの回路秘匿装置であって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０を含む値の関数値とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉを含む値の関数値を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値とｂ１Ψｉとの排他的論理和をＫｉ１とし、γ（０，０）＝ｂ０、γ（０，１）＝γ（１，０）＝ｂ１、およびγ（１，１）＝１（ｘｏｒ）ｂ０を得る、回路秘匿装置。
【請求項１０】
請求項７から９の何れかの回路秘匿装置であって、
前記入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値を共通鍵として、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文を得る回路秘匿装置。
【請求項１１】
請求項１から６の何れかの回路秘匿装置であって、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値γ（０，０）の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる値であり、Ｘ０がＸ１からＸ４と異なる値であり、
前記出力鍵設定部は、
点（Ｘ１，Ｙ１）および点（Ｘ２，Ｙ２）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
点（Ｘ３，Ｙ３）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
Ψｉ＝Ｐ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有する回路秘匿装置。
【請求項１２】
請求項１から６の何れかの回路秘匿装置であって、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる定数であり、Ｘ０がＸ１からＸ４と異なる定数であり、
前記出力鍵設定部は、
点（Ｘ２，Ｙ２）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
点（Ｘ１，Ｙ１）および点（Ｘ４，Ｑ（Ｘ４））を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
Ψｉ＝Ｑ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有する回路秘匿装置。
【請求項１３】
請求項１から６の何れかの回路秘匿装置であって、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値γ（０，０）の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる値であり、Ｘ０がＸ１からＸ４と異なる値であり、
前記出力鍵設定部は、
点（Ｘ１，Ｙ１）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
点（Ｘ２，Ｙ２）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
Ψｉ＝Ｐ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有する回路秘匿装置。
【請求項１４】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０を含む値の関数値とＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０＋ｂ０ｄｉを含む値の関数値を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値とｂ１Ψｉとの排他的論理和を前記出力鍵Ｋｉ１とし、γ（０，０）＝ｂ０、γ（０，１）＝γ（１，０）＝１（ｘｏｒ）ｂ０、およびγ（１，１）＝ｂ１を得、
前記回路秘匿装置は、前記入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値を共通鍵として、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文を得、
前記計算装置は、
前記排他的論理和Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値に対応する入力鍵ＫＡ，ＫＢを含む値の関数値を共通鍵として、前記暗号文を復号してγを得る復号部と、
ＫＡ＋ＫＢを含む値の関数値とγΨｉとの排他的論理和を、前記ゲートの出力値に対応する出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項１５】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０を含む値の関数値とｂ１Ψｉとの排他的論理和を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉを含む値の関数値をＫｉ１とし、γ（０，０）＝ｂ１、γ（０，１）＝γ（１，０）＝ｂ０、およびγ（１，１）＝１（ｘｏｒ）ｂ０を得、
前記回路秘匿装置は、前記入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値を共通鍵として、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文を得、
前記計算装置は、
前記排他的論理和Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値に対応する入力鍵ＫＡ，ＫＢを含む値の関数値を共通鍵として、前記暗号文を復号してγを得る復号部と、
ＫＡ＋ＫＢを含む値の関数値とγΨｉとの排他的論理和を、前記ゲートの出力値に対応する出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項１６】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
α（ｘｏｒ）βがαとβとの排他的論理和であり、
前記出力鍵設定部は、
ＫＡ０＋ＫＢ’０を含む値の関数値とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値との排他的論理和Ψｉを得、任意値ｂ０，ｂ１∈｛０，１｝を選択し、ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉを含む値の関数値を前記出力鍵Ｋｉ０とし、ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値とｂ１Ψｉとの排他的論理和をＫｉ１とし、γ（０，０）＝ｂ０、γ（０，１）＝γ（１，０）＝ｂ１、およびγ（１，１）＝１（ｘｏｒ）ｂ０を得、
前記回路秘匿装置は、前記入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値を共通鍵として、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文を得、
前記計算装置は、
前記排他的論理和Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値に対応する入力鍵ＫＡ，ＫＢを含む値の関数値を共通鍵として、前記暗号文を復号してγを得る復号部と、
ＫＡ＋ＫＢを含む値の関数値とγΨｉとの排他的論理和を、前記ゲートの出力値に対応する出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項１７】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値γ（０，０）の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる値であり、Ｘ０がＸ１からＸ４と異なる値であり、
前記出力鍵設定部は、
点（Ｘ１，Ｙ１）および点（Ｘ２，Ｙ２）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
点（Ｘ３，Ｙ３）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
Ψｉ＝Ｐ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有し、
前記計算装置は、
前記Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値（Ｉ（Ａ），Ｉ（Ｂ））に対応する入力鍵ＫＡ＝ＫＡＩ（Ａ），ＫＢ＝ＫＢＩ（Ｂ）および値γ（Ｉ（Ａ），Ｉ（Ｂ））を入力とし、前記値γ（Ｉ（Ａ），Ｉ（Ｂ））の関数値をＸγとし、ＫＡ＋ＫＢを含む値の関数値をＹＫとして、点（Ｘγ，ＹＫ）を得る座標点特定部と、
前記点（Ｘγ，ＹＫ）および前記点（Ｘ４，Ψｉ）を通る一次多項式Ｙ＝Ｒ（Ｘ）に定数Ｘ０を代入した値Ｙ＝Ｒ（Ｘ０）を出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項１８】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる定数であり、Ｘ０がＸ１からＸ４と異なる定数であり、
前記出力鍵設定部は、
点（Ｘ２，Ｙ２）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
点（Ｘ１，Ｙ１）および点（Ｘ４，Ｑ（Ｘ４））を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
Ψｉ＝Ｑ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有し、
前記計算装置は、
前記Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値（Ｉ（Ａ），Ｉ（Ｂ））に対応する入力鍵ＫＡ＝ＫＡＩ（Ａ），ＫＢ＝ＫＢＩ（Ｂ）および値γ（Ｉ（Ａ），Ｉ（Ｂ））を入力とし、前記値γ（Ｉ（Ａ），Ｉ（Ｂ））の関数値をＸγとし、ＫＡ＋ＫＢを含む値の関数値をＹＫとして、点（Ｘγ，ＹＫ）を得る座標点特定部と、
前記点（Ｘγ，ＹＫ）および前記点（Ｘ４，Ψｉ）を通る一次多項式Ｙ＝Ｒ（Ｘ）に定数Ｘ０を代入した値Ｙ＝Ｒ（Ｘ０）を出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項１９】
回路秘匿装置と計算装置とを有する秘密計算システムであって、
論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、前記ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、
前記回路秘匿装置は、
前記入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、前記入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）であり、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する入力鍵設定部と、
前記入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、前記出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する出力鍵設定部と、を有し、
Ｘ１が（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値γ（０，０）の関数値であり、Ｙ１がＫＡ０＋ＫＢ’０を含む値の関数値であり、
Ｘ２が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）および（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２がＫＡ０＋ＫＢ０＋ｄｉを含む値の関数値であり、
Ｘ３が（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値γ（１，１）の関数値であり、Ｙ３がＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値であり、
Ｘ４がＸ１からＸ３と異なる値であり、Ｘ０がＸ１からＸ４と異なる値であり、
前記出力鍵設定部は、
点（Ｘ１，Ｙ１）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得るＰ多項式設定部と、
点（Ｘ２，Ｙ２）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得るＱ多項式設定部と、
Ψｉ＝Ｐ（Ｘ４）とするΨ設定部と、
Ｐ（Ｘ０）を前記出力鍵Ｋｉ０とし、Ｑ（Ｘ０）を前記出力鍵Ｋｉ１とする出力鍵設定部と、を有し、
前記計算装置は、
前記Ψｉを格納する記憶部と、
論理演算を行うゲートの入力値（Ｉ（Ａ），Ｉ（Ｂ））に対応する入力鍵ＫＡ＝ＫＡＩ（Ａ），ＫＢ＝ＫＢＩ（Ｂ）および値γ（Ｉ（Ａ），Ｉ（Ｂ））を入力とし、前記値γ（Ｉ（Ａ），Ｉ（Ｂ））の関数値をＸγとし、ＫＡ＋ＫＢを含む値の関数値をＹＫとして、点（Ｘγ，ＹＫ）を得る座標点特定部と、
前記点（Ｘγ，ＹＫ）および前記点（Ｘ４，Ψｉ）を通る一次多項式Ｙ＝Ｒ（Ｘ）に定数Ｘ０を代入した値Ｙ＝Ｒ（Ｘ０）を出力鍵Ｋｉとして得る出力鍵設定部と、
を有する、秘密計算システム。
【請求項２０】
請求項１４から１９の何れかに記載の秘密計算システムであって、
α（ｘｏｒ）βがαとβとの排他的論理和であり、λ（Ｂ）∈｛０，１｝が置換ビットであり、
前記入力鍵設定部は、
前記入力値Ｉ（Ａ）に対応する前記入力鍵ＫＡＩ（Ａ）が設定され、前記入力値Ｉ（Ｂ）に対応する入力鍵ＫＢＩ（Ｂ）が設定されている場合に、ｄｉ＝ＫＡ１−ＫＡ０を得、前記入力値Ｉ（Ｂ）に対応するラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）についてＫＢ’λ（Ｂ）＝ＫＢλ（Ｂ）を得、ＫＢ’１（ｘｏｒ）λ（Ｂ）＝ＫＢ’λ（Ｂ）＋（−１）λ（Ｂ）ｄｉを得、前記入力鍵ＫＢ１（ｘｏｒ）λ（Ｂ）を含む値の関数値を共通鍵としてＫＢ’１（ｘｏｒ）λ（Ｂ）を暗号化した暗号文Ｅｉを得、
前記計算装置は、
入力鍵ＫＢを含む値の関数値を共通鍵として、前記暗号文Ｅｉを復号して新たな入力鍵ＫＢを得る鍵復号部を有する、秘密計算システム。
【請求項２１】
請求項１から１３の何れかの回路秘匿装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に秘匿回路を用いた計算技術に関する。
【背景技術】
【０００２】
非特許文献１，２には、秘匿回路を用いた計算方式の従来技術が開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams, “Secure Two-Party Computation Is Practical,”ASIACRYPT 2009, 250-267.
【非特許文献２】A.C.Yao, “How to generate and exchange secrets,” Proc. of FOCS’86, pp. 162-167, IEEE Press, 1986.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１，２に記載された方式には秘匿回路のデータ量を削減する余地がある。本発明の目的は秘匿回路のデータ量を削減することである。
【課題を解決するための手段】
【０００５】
ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定し、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定する。ただし、論理演算を行うゲートの入力値がＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝であり、ゲートの出力値がｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝であり、入力値Ｉ（Ａ）に対応する入力鍵がＫＡＩ（Ａ）であり、入力値Ｉ（Ｂ）に対応する入力鍵がＫＢ’Ｉ（Ｂ）である。
【発明の効果】
【０００６】
ＫＡ１とＫＡ０との差分とＫＢ’１とＫＢ’０との差分を同一にすることで秘匿回路のデータ量を削減できる。
【図面の簡単な説明】
【０００７】
【図１】図１は、実施形態の秘匿計算システムの機能構成を例示したブロック図である。
【図２】図２は、実施形態の回路秘匿装置の機能構成を例示したブロック図である。
【図３】図３Ａから図３Ｃは、入力鍵設定部の機能構成を例示したブロック図である。
【図４】図４Ａは、実施形態の符号化装置の機能構成を例示したブロック図である。図４Ｂは、実施形態の復号装置の機能構成を例示したブロック図である。
【図５】図５は、実施形態の計算装置の機能構成を例示したブロック図である。
【図６】図６は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図７】図７は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図８】図８は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図９】図９は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図１０】図１０は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図１１】図１１Ａは、実施形態の符号化処理を説明するためのフローチャートである。図１１Ｂは、実施形態の復号処理を説明するためのフローチャートである。
【図１２】図１２は、実施形態の秘匿回路の計算処理を説明するためのフローチャートである。
【図１３】図１３は、実施形態の秘匿回路の計算処理を説明するためのフローチャートである。
【図１４】図１４Ａおよび図１４Ｂは、秘匿対象の回路を例示した概念図である。
【図１５】図１５は、実施形態の回路秘匿装置の機能構成を例示したブロック図である。
【図１６】図１６は、実施形態の計算装置の機能構成を例示したブロック図である。
【図１７】図１７は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図１８】図１８は、実施形態の回路秘匿処理を説明するためのフローチャートである。
【図１９】図１９は、実施形態の秘匿回路の計算処理を説明するためのフローチャートである。
【図２０】図２０Ａ〜図２０Ｃは、実施形態の秘匿回路を説明するための図である。
【発明を実施するための形態】
【０００８】
［第１実施形態］
図面を用いて第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の秘匿計算システム１は、回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４を有する。回路秘匿装置１１は符号化装置１２、計算装置１３、および復号装置１４に情報の提供が可能なように構成されている。符号化装置１２は計算装置１３に情報の提供が可能なように構成されている。計算装置１３は復号装置１４に情報の提供が可能なように構成されている。例えば、回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４は、ネットワークを通じて情報の送受信を行う。回路秘匿装置１１と符号化装置１２とが異なるパーティによって利用される。計算装置１３および復号装置１４はどのパーティに利用されてもよい。説明の簡略化のため、図１では、回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４を１つずつ図示するが、これらの少なくとも何れかが複数個存在してもよい。
【０００９】
＜回路秘匿装置１１＞
図２に例示するように、回路秘匿装置１１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部１１４、入力ワイヤ設定部１１５、判定部１１６０、置換ビット設定部１１６１、入力ラベル設定部１１６２、判定部１１７１、入力鍵設定部１１７２〜１１７４、設定部１１８１、Ψ設定部１１８２、ＲＢ選択部１１８３、出力鍵設定部１１８４、出力鍵設定部１１８５、γ設定部１１８６、設定部１１９１、ＲＰＢ選択部１１９２、暗号化部１１９３、Ｆ設定部１１９４、ｅ設定部１１９５、およびｄ設定部１１９６を有する。図３Ａに例示するように、入力鍵設定部１１７２は、減算部１１７２ａ、設定部１１７２ｂ〜１１７２ｄ、および暗号化部１１７２ｅを有する。図３Ｂに例示するように、入力鍵設定部１１７３は、減算部１１７３ａ、選択部１１７３ｂ、および設定部１１７３ｃ〜１１７３ｅを有する。図３Ｃに例示するように、入力鍵設定部１１７４は、選択部１１７４ａ、および設定部１１７４ｂ〜１１７４ｅを有する。
【００１０】
＜符号化装置１２＞
図４Ａに例示するように、符号化装置１２は、通信部１２１１、入力部１２１２、記憶部１２２、制御部１２３、分離部１２４，１２５、および符号化部１２６を有する。
【００１１】
＜計算装置１３＞
図５に例示するように、計算装置１３は、通信部１３１１、記憶部１３２、制御部１３３、分離部１３４、入力ワイヤ設定部１３５１、ラベル計算部１３５２、分離部１３５３、判定部１３５４、設定部１３５５、鍵復号部１３５６、設定部１３５７、復号部１３５８、出力鍵生成部１３５９、および出力値生成部１３６を有する。
【００１２】
＜復号装置１４＞
図４Ｂに例示するように、復号装置１４は、通信部１４１１、記憶部１４２、制御部１４３、分離部１４４，１４５、および復号部１４６を有する。
【００１３】
回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４のそれぞれは、例えば、通信装置、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４は、それぞれ制御部１１３，１２３，１３３，１４３の制御のもとで各処理を行う。回路秘匿装置１１、符号化装置１２、計算装置１３、および復号装置１４へ入力された情報やそれらで得られたデータは、逐一、記憶部１１２，１２２，１３２，１４２にそれぞれ格納され、必要に応じて読み出されて使用される。
【００１４】
＜秘匿対象の回路ｆ＝（ｎ，ｍ，ｕ，Ａ，Ｂ，ｇ）の例示＞
秘匿対象の回路ｆは、ｎビットの入力値Ｚ∈｛０，１｝ｎに対してｍビットの出力値Ｗ∈｛０，１｝ｍを出力する写像（関数）である（ｆ：｛０，１｝ｎ→｛０，１｝ｍ）。ただし、ｎは２以上の偶数であり、ｎ＝４であってもよいし、ｎ≧６であってもよい。ｍは１以上の整数であり、ｍ＝１であってもよいし、ｍ≧２であってもよい。例えば、ｍ＜ｎであってもよい。｛０，１｝ｎはｎ個の０または１の要素からなる集合を表す。すなわち、｛０，１｝ｎはｎビット２進数で表される値の集合を表す。
【００１５】
図１４Ａおよび図１４Ｂに例示するように、回路ｆはｕ個のゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）から構成される。ｕは１以上の整数である。例えば、ｕ≧２であってもよいし、ｕ≧３であってもよい。図１４Ｂはｎ＝１０，ｕ＝９，ｍ＝１の例である。ゲートＧ（ｉ）（ただし、ｉ∈｛ｎ＋１，…，ｎ＋ｕ｝）は２入力１出力の論理ゲートである（Ｇ（ｉ）：｛０，１｝×｛０，１｝→｛０，１｝）。ゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）の集合をＧｓｅｔ：＝｛Ｇ（ｎ＋１），…，Ｇ（ｎ＋ｕ）｝と表記する。ｎビットの入力値Ｚ∈｛０，１｝ｎが入力される入力側のゲートＧ（ｎ＋１），…，Ｇ（３ｎ／２）の集合をＧｉｎｐｕｔ：＝｛Ｇ（ｎ＋１），…，Ｇ（３ｎ／２）｝と表記する。ただし、「α：＝β」はαをβとして設定することを意味する。ゲートの例は、ＡＮＤゲート、ＯＲゲート、ＸＯＲゲートなどである。
【００１６】
ゲートＧ（ｉ）への入力変数を入力ワイヤと呼び、出力変数を出力ワイヤと呼ぶ。各ゲートＧ（ｉ）は２個の入力ワイヤと１個の出力ワイヤを持つ。入力ワイヤおよび出力ワイヤを総称してワイヤと呼ぶ。ゲートＧ（ｉ）の入力ワイヤをＷ（Ａ（ｉ））およびＷ（Ｂ（ｉ））と表記し、出力ワイヤをＷ（ｉ）と表記する。ゲートＧ（ｎ＋１），…，Ｇ（ｎ＋ｕ）のワイヤの集合をＷｓｅｔ：＝｛Ｗ（１），…，Ｗ（ｎ＋ｕ）｝と表記する。ただし、Ａ（ｉ）＜Ｂ（ｉ）＜ｉであり、Ａ（ｎ＋１）＝１，Ｂ（ｎ＋１）＝２，…，Ａ（３ｎ／２）＝ｎ−１，Ｂ（３ｎ／２）＝ｎ，…，Ａ（ｎ＋ｕ）＝ｎ＋ｕ−２，Ｂ（ｎ＋ｕ）＝ｎ＋ｕ−１である。集合Ｇｉｎｐｕｔに属するｎ／２個のゲートＧ（ｎ＋１），…，Ｇ（３ｎ／２）の入力ワイヤＷ（Ａ（ｎ＋１））＝Ｗ（１），Ｗ（Ｂ（ｎ＋１））＝Ｗ（２），…，Ｗ（Ａ（３ｎ／２））＝Ｗ（ｎ−１），Ｗ（Ｂ（３ｎ／２））＝Ｗ（ｎ）の集合をＷｉｎｐｕｔ：＝｛Ｗ（１），…，Ｗ（ｎ）｝と表記する。ゲートＧ（ｎ＋ｕ）の出力ワイヤＷ（ｎ＋ｕ−ｍ＋１），…，Ｗ（ｎ＋ｕ）の集合をＷｏｕｔｐｕｔ：＝｛Ｗ（ｎ＋ｕ−ｍ＋１），…，Ｗ（ｎ＋ｕ）｝と表記する。出力ワイヤＷ（ｎ＋ｕ−ｍ＋１），…，Ｗ（ｎ＋ｕ）が演算結果を表す。
【００１７】
集合Ｇｉｎｐｕｔに属するゲートの入力ワイヤＷ（１），…，Ｗ（ｎ）は回路ｆの入力ワイヤであり、ｎビットの入力値Ｚに対応する。ゲートＧ（ν）（ただし、ν∈｛ｎ＋１，…，ｎ＋ｕ−１｝）の出力ワイヤＷ（ν）は、それぞれ、何れかのゲートＧ（ω）∈cＧｓｅｔの入力ワイヤＷ（Ａ（ω））またはＷ（Ｂ（ω））である。ただし、cＧｓｅｔは集合Ｇｓｅｔにおける集合｛Ｇ（ｎ＋１），…，Ｇ（ｎ＋ｕ−１）｝の補集合を表す。すなわち、cＧｓｅｔは、集合Ｇｓｅｔから集合｛Ｇ（ｎ＋１），…，Ｇ（ｎ＋ｕ−１）｝に属する元を除いて得られる集合を表す。ν＜ωである。互いに異なる出力ワイヤが同一の入力ワイヤとなることはなく、単一の出力ワイヤが複数の入力ワイヤとなることもない。ゲートＧ（ｎ＋ｕ−ｍ＋１），…，Ｇ（ｎ＋ｕ）の出力ワイヤＷ（ｎ＋ｕ−ｍ＋１），…，Ｗ（ｎ＋ｕ）は回路ｆの出力ワイヤであり、出力値Ｗの各ビットに対応する。
【００１８】
ゲートＧ（ｉ）（ただし、ｉ∈｛ｎ＋１，…，ｎ＋ｕ｝）の種類および入力ワイヤＷ（Ａ（ｉ）），Ｗ（Ｂ（ｉ））の入力値Ｉ（Ａ（ｉ）），Ｉ（Ｂ（ｉ））∈｛０，１｝に応じ、出力ワイヤＷ（ｉ）の出力値ｇｉ（Ｉ（Ａ（ｉ）），Ｉ（Ｂ（ｉ）））∈｛０，１｝が決まる。すなわち、Ｉ（Ａ（ｉ））およびＩ（Ｂ（ｉ））に対するゲートＧ（ｉ）での論理演算結果がｇｉ（Ｉ（Ａ（ｉ）），Ｉ（Ｂ（ｉ）））である。例えば、ゲートＧ（ｉ）がＡＮＤゲート、ＯＲゲート、ＸＯＲゲートである場合、Ｉ（Ａ（ｉ）），Ｉ（Ｂ（ｉ）），ｇｉ（Ｉ（Ａ（ｉ）），Ｉ（Ｂ（ｉ）））の関係は、それぞれ以下のようになる。
≪ＡＮＤゲート≫
【表１】
0006629461.tif 000002
≪ＯＲゲート≫
【表２】
0006629461.tif 000003
≪ＸＯＲゲート≫
【表３】
0006629461.tif 000004
なお、ゲートＧ（ｉ）は、ＡＮＤゲート、ＯＲゲート、ＸＯＲゲートに限定されない。出力値ｇｉ（１，０）と出力値ｇｉ（０，１）とが等しい、その他の２入力１出力の論理ゲートをゲートＧ（ｉ）としてもよい。図１４Ａおよび図１４Ｂの回路ｆは一例であり、本発明はこれに限定されない。例えば、いずれかのゲートＧ（ｉ’）の一方の入力ワイヤが他のゲートＧ（ｉ”）の出力ワイヤであり、このゲートＧ（ｉ’）の他方の入力ワイヤがいずれかのゲートの出力ワイヤでなく、回路ｆの入力ワイヤであってもよい。
【００１９】
＜回路秘匿装置１１の回路秘匿処理＞
次に、図６から図１０を用い、回路秘匿装置１１による回路ｆ＝（ｎ，ｍ，ｕ，Ａ，Ｂ，ｇ）の秘匿処理を説明する。
回路秘匿装置１１（図２）の入力部１１１２にセキュリティパラメータｋおよび回路ｆ＝（ｎ，ｍ，ｕ，Ａ，Ｂ，ｇ）が入力され、記憶部１１２に格納される。ただし、ｋは正整数である。例えば、ｋは２以上の整数である。例えば、２ｋ＞ｋ＋８を満たす。初期設定部１１４は、秘匿回路Ｆ、符号化情報ｅ、復号情報ｄそれぞれの空領域を、｜Ｆ｜＝ｕ，｜ｅ｜＝ｎ，｜ｄ｜＝ｍとなるように設定する。なお、｜α｜はαの大きさを意味する。また、内部カウンタを初期値（例えば０）に初期化する。内部カウンタはｎｅｘｔｉｎｄｅｘ（）によって１ずつインクリメントされる（ステップＳ１０１）。制御部１１３はｉ：＝ｎ＋１と設定する（ステップＳ１０２）。
【００２０】
入力ワイヤ設定部１１５は、Ａ：＝Ａ（ｉ）およびＢ：＝Ｂ（ｉ）に設定する（ステップＳ１０３）。判定部１１６０は、入力値Ｉ（Ａ）に対応する入力ワイヤＷ（Ａ）のラベルＬＡＩ（Ａ）∈｛０，１｝が未設定であるかを判定する（ステップＳ１０４）。なお、ラベルＬＡＩ（Ａ）は入力値Ｉ（Ａ）∈｛０，１｝をランダム化した値である。入力ワイヤＷ（Ａ）が他のゲートＧ（ι）（ただし、ι∈｛ｎ＋１，…，ｎ＋ｕ｝）の出力ワイヤである場合、ラベルＬＡＩ（Ａ）は設定されており（他のゲートＧ（ι）の出力ワイヤのラベルｇι（Ｉ（Ａ（ι）），Ｉ（Ｂ（ι）））（ｘｏｒ）λ（ι）∈｛０，１｝として設定されている（後述するステップＳ１３９））、そうでない場合、ラベルＬＡＩ（Ａ）は未設定である。図１４Ａおよび図１４Ｂの例では、Ｗ（Ａ）∈Ｗｉｎｐｕｔである場合にラベルＬＡＩ（Ａ）は未設定である。ラベルＬＡＩ（Ａ）が未設定である場合にはステップＳ１０５に進む。一方、ラベルＬＡＩ（Ａ）が未設定でない場合（ラベルＬＡＩ（Ａ）が設定されている場合）にはステップＳ１０７に進む。なお、特に断りがない限り、「αβ」はαのβ乗を表すのではない。
【００２１】
ステップＳ１０５では、置換ビット設定部１１６１が、置換ビットλ（Ａ）∈｛０，１｝をランダムに選択する（ステップＳ１０５）。次に、入力ラベル設定部１１６２が、置換ビットλ（Ａ）を入力とし、すべてのＩ（Ａ）∈｛０，１｝についてラベルＬＡＩ（Ａ）＝λ（Ａ）（ｘｏｒ）Ｉ（Ａ）∈｛０，１｝を設定して記憶部１１２に格納する。すなわち、入力ラベル設定部１１６２は、ＬＡ０＝λ（Ａ）およびＬＡ１＝λ（Ａ）（ｘｏｒ）１を設定して記憶部１１２に格納する。ただし、「α（ｘｏｒ）β」は、αとβとの排他的論理和
【数１】
0006629461.tif 000005
を表す（ステップＳ１０６）。ステップＳ１０６の後、ステップＳ１０７に進む。
【００２２】
ステップＳ１０７では、判定部１１６０が、入力値Ｉ（Ｂ）に対応する入力ワイヤＷ（Ｂ）のラベルＬＢＩ（Ｂ）が未設定であるかを判定する（ステップＳ１０７）。入力ワイヤＷ（Ｂ）が他のゲートＧ（ι）の出力ワイヤである場合、ラベルＬＢＩ（Ｂ）は設定されており（他のゲートＧ（ι）の出力ワイヤのラベルｇι（Ｉ（Ａ（ι）），Ｉ（Ｂ（ι）））（ｘｏｒ）λ（ι）として設定されている）、そうでない場合、ラベルＬＢＩ（Ｂ）は未設定である。図１４Ａおよび図１４Ｂの例では、Ｗ（Ｂ）∈Ｗｉｎｐｕｔである場合にラベルＬＢＩ（Ｂ）は未設定である。ラベルＬＢＩ（Ｂ）が未設定である場合にはステップＳ１０８に進む。一方、ラベルＬＢＩ（Ｂ）が未設定でない場合（ラベルＬＢＩ（Ｂ）が設定されている場合）にはステップＳ１１０に進む。
【００２３】
ステップＳ１０８では、置換ビット設定部１１６１が、置換ビットλ（Ｂ）∈｛０，１｝をランダムに選択する（ステップＳ１０８）。次に、入力ラベル設定部１１６２が、置換ビットλ（Ｂ）を入力とし、すべてのＩ（Ｂ）∈｛０，１｝についてラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）を設定して記憶部１１２に格納する。すなわち、入力ラベル設定部１１６２は、ＬＢ０＝λ（Ｂ）およびＬＢ１＝λ（Ｂ）（ｘｏｒ）１を設定して記憶部１１２に格納する（ステップＳ１０９）。ステップＳ１０９の次にステップＳ１１０に進む。
【００２４】
ステップＳ１１０〜Ｓ１３０では、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１∈Ｆｑが得られるように、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定する。ただし、Ｆｑは位数ｑの有限体を表す。ｑは正整数であり、有限体Ｆｑの標数は３以上である。また、α∈Ｆｑをｋビットで表現したビット列ｂｉｔα∈｛０，１｝ｋと、β∈Ｆｑをｋビットで表現したビット列ｂｉｔβ∈｛０，１｝ｋとの排他的論理和ｂｉｔα（ｘｏｒ）ｂｉｔβを、「α（ｘｏｒ）β」と表記することにする。すなわち、α∈Ｆｑとβ∈Ｆｑとの排他的論理和α（ｘｏｒ）βとは、ｂｉｔα（ｘｏｒ）ｂｉｔβを意味する。ステップＳ１１０では、判定部１１７１が、入力値Ｉ（Ａ）∈｛０，１｝に対応する入力ワイヤＷ（Ａ）の入力鍵ＫＡＩ（Ａ）∈Ｆｑが設定され、かつ、入力値Ｉ（Ｂ）∈｛０，１｝に対応する入力ワイヤＷ（Ｂ）の入力鍵ＫＢＩ（Ｂ）∈Ｆｑが設定されているかを判定する（ステップＳ１１０）。入力ワイヤＷ（Ａ）が他のゲートＧ（ι）の出力ワイヤである場合、入力鍵ＫＡＩ（Ａ）は設定されており（他のゲートＧ（ι）の出力ワイヤの入力鍵Ｋιｇ（Ｉ（Ａ（ι）），Ｉ（Ｂ（ι）））として設定されている（後述するステップＳ１３４，Ｓ１３５））、そうでない場合、入力鍵ＫＡＩ（Ａ）は設定されていない。図１４Ａおよび図１４Ｂの例では、Ｗ（Ａ）∈Ｗｉｎｐｕｔである場合に入力鍵ＫＡＩ（Ａ）は未設定であり、そうでない場合に入力鍵ＫＡＩ（Ａ）は設定されている。同様に、入力ワイヤＷ（Ｂ）が他のゲートＧ（ι）の出力ワイヤである場合、入力鍵ＫＢＩ（Ｂ）は設定されており（他のゲートＧ（ι）の出力ワイヤの入力鍵Ｋιｇ（Ｉ（Ａ（ι）），Ｉ（Ｂ（ι）））として設定されている）、そうでない場合、入力鍵ＫＢＩ（Ｂ）は設定されていない。図１４Ａおよび図１４Ｂの例では、Ｗ（Ｂ）∈Ｗｉｎｐｕｔである場合に入力鍵ＫＢＩ（Ｂ）は未設定であり、そうでない場合に入力鍵ＫＢＩ（Ｂ）は設定されている。入力鍵ＫＡＩ（Ａ）が設定され、かつ、入力鍵ＫＢＩ（Ｂ）が設定されている場合にはステップＳ１１１に進み、そうでない場合にはステップＳ１１６に進む。
【００２５】
ステップＳ１１１では、入力鍵設定部１１７２の減算部１１７２ａ（図３Ａ）が、ＫＡ１，ＫＡ０を入力としてｄｉ＝ＫＡ１−ＫＡ０∈Ｆｑを得て出力する（ステップＳ１１１）。
di:=KA1-KA0
【００２６】
次に、設定部１１７２ｂが、入力値Ｉ（Ｂ）に対応するラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）に対するＫＢλ（Ｂ）を入力とし、ＫＢ’λ（Ｂ）＝ＫＢλ（Ｂ）を得て出力する（ステップＳ１１２）。
KB’λ(B):=KBλ(B)
【００２７】
次に、設定部１１７２ｃが、ＫＢ’λ（Ｂ）およびｄｉを入力とし、ＫＢ’１（ｘｏｒ）λ（Ｂ）＝ＫＢ’λ（Ｂ）＋（−１）λ（Ｂ）ｄｉを得て出力する（ステップＳ１１３）。
KB’1(xor)λ(B):=KB’λ(B)+(-1)λ(B)di
ただし、λ（Ｂ）＝０の場合には（−１）λ（Ｂ）＝１であり、λ（Ｂ）＝１の場合には（−１）λ（Ｂ）＝−１である。すなわち、（−１）λ（Ｂ）は（−１）のλ（Ｂ）乗を表す。
【００２８】
次に、設定部１１７２ｄが、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＥとして出力する（ステップＳ１１４）。
jE:=nextindex()
【００２９】
次に暗号化部１１７２ｅは、ＫＢ１（ｘｏｒ）λ（Ｂ），ｊＥ，ＫＢ’１（ｘｏｒ）λ（Ｂ）を入力とし、入力鍵ＫＢ１（ｘｏｒ）λ（Ｂ）およびインデックスｊＥに対応するハッシュ値Ｈ（ＫＢ１（ｘｏｒ）λ（Ｂ），ｊＥ）∈Ｆｑと入力鍵ＫＢ’１（ｘｏｒ）λ（Ｂ）∈Ｆｑとの排他的論理和を暗号文Ｅｉ∈Ｆｑとして得て出力する。なお、Ｈは入力に対応するＦｑの元を出力するハッシュ関数であり、例えば、Ｈ（α，β）はαとβのビット結合値のハッシュ値である。また、Ｅｉは入力鍵ＫＢ１（ｘｏｒ）λ（Ｂ）を含む値の関数値（Ｈ（ＫＢ１（ｘｏｒ）λ（Ｂ），ｊＥ））を共通鍵としてＫＢ’１（ｘｏｒ）λ（Ｂ）を暗号化した暗号文に相当する（ステップＳ１１５）。
Ei:=H(KB1(xor)λ(B),jE)(xor)KB’1(xor)λ(B)
ステップＳ１１５の後、ステップＳ１３１に進む。
【００３０】
ステップＳ１１６では、判定部１１７１が入力鍵ＫＡＩ（Ａ）∈Ｆｑが設定されているかを判定する。入力鍵ＫＡＩ（Ａ）が設定されている場合（入力鍵ＫＡＩ（Ａ）が設定されているが、入力鍵ＫＢＩ（Ｂ）が設定されていない場合）にはステップＳ１１７に進み、入力鍵ＫＡＩ（Ａ）が設定されていない場合にはステップＳ１２２に進む（ステップＳ１１６）。
【００３１】
ステップＳ１１７では、入力鍵設定部１１７３の減算部１１７３ａ（図３Ｂ）が、ＫＡ１，ＫＡ０を入力としてｄｉ＝ＫＡ１−ＫＡ０∈Ｆｑを得（ステップＳ１１７）、選択部１１７３ｂがＫＢ０∈Ｆｑをランダムに選択し（ステップＳ１１８）、設定部１１７３ｃがＫＢ０，ｄｉを入力としてＫＢ１＝ＫＢ０＋ｄｉを得（ステップＳ１１９）、設定部１１７３ｄが入力されたＫＢ０を入力鍵ＫＢ’０とし（ステップＳ１２０）、設定部１１７３ｅが入力されたＫＢ１を入力鍵ＫＢ’１として出力する（ステップＳ１２１）。
di:=KA1-KA0
KB0∈Fq
KB1:=KB0+di
KB’0:=KB0
KB’1:=KB1
すなわち、入力鍵設定部１１７３は、入力鍵ＫＡＩ（Ａ）が設定されているが、入力鍵ＫＢＩ（Ｂ）が設定されていない場合に、ｄｉ＝ＫＡ１−ＫＡ０を得、ＫＢ’１＝ＫＢ’０＋ｄｉを満たす入力鍵ＫＢ’１および入力鍵ＫＢ’０を得る。ステップＳ１２１の後、ステップＳ１３１に進む。
【００３２】
ステップＳ１２２では、判定部１１７１が、入力鍵ＫＢＩ（Ｂ）∈Ｆｑが設定されているかを判定する（ステップＳ１２２）。入力鍵ＫＢＩ（Ｂ）が設定されている場合（入力鍵ＫＢＩ（Ｂ）が設定されているが、入力鍵ＫＡＩ（Ａ）が設定されていない場合）にはステップＳ１２３に進み、入力鍵ＫＢＩ（Ｂ）が設定されていない場合（入力鍵ＫＡＩ（Ａ）および入力鍵ＫＢＩ（Ｂ）が設定されていない場合）にはステップＳ１２６に進む。
【００３３】
ステップＳ１２３では、入力鍵設定部１１７３の減算部１１７３ａ（図３Ｂ）が、ＫＢ１，ＫＢ０を入力としてｄｉ＝ＫＢ１−ＫＢ０∈Ｆｑを得（ステップＳ１２３）、選択部１１７３ｂがＫＡ０∈Ｆｑをランダムに選択し（ステップＳ１２４）、設定部１１７３ｃがＫＡ０，ｄｉを入力としてＫＡ１＝ＫＡ０＋ｄｉを得（ステップＳ１２５）、設定部１１７３ｄが入力されたＫＢ０を入力鍵ＫＢ’０とし（ステップＳ１２０）、設定部１１７３ｅが入力されたＫＢ１を入力鍵ＫＢ’１として出力する（ステップＳ１２１）。
di:=KB1-KB0
KA0∈Fq
KA1:=KA0+di
KB’0:=KB0
KB’1:=KB1
すなわち、入力鍵設定部１１７３は、入力鍵ＫＢＩ（Ｂ）が設定されているが、入力鍵ＫＡＩ（Ａ）が設定されていない場合に、ｄｉ＝ＫＢ１−ＫＢ０を得、ＫＡ１＝ＫＡ０＋ｄｉを満たす入力鍵ＫＡ１および入力鍵ＫＡ０を得、入力鍵ＫＢＩ（Ｂ）を入力鍵ＫＢ’Ｉ（Ｂ）とする。ステップＳ１２１の後、ステップＳ１３１に進む。
【００３４】
ステップＳ１２６では、入力鍵設定部１１７４の選択部１１７４ａ（図３Ｃ）が、ＫＡ０，ＫＢ０，ｄｉ∈Ｆｑをランダムに選択し（ステップＳ１２６）、設定部１１７４ｂがＫＡ０，ｄｉを入力としてＫＡ１＝ＫＡ０＋ｄｉを得（ステップＳ１２７）、設定部１１７４ｃがＫＢ０，ｄｉを入力としてＫＢ１＝ＫＢ０＋ｄｉを得（ステップＳ１２８）、設定部１１７４ｄが入力されたＫＢ０を入力鍵ＫＢ’０とし（ステップＳ１２９）、設定部１１７４ｅが入力されたＫＢ１を入力鍵ＫＢ’１として出力する（ステップＳ１３０）。
KA0,KB0,di∈Fq
KA1:=KA0+di
KB1:=KB0+di
KB’0:=KB0
KB’1:=KB1
すなわち、入力鍵設定部１１７４は、入力鍵ＫＡＩ（Ａ）および入力鍵ＫＢＩ（Ｂ）が設定されていない場合に、ｄｉをランダムに選択し、ＫＡ１＝ＫＡ０＋ｄｉを満たす入力鍵ＫＡ１および入力鍵ＫＡ０、ならびに、ＫＢ’１＝ＫＢ’０＋ｄｉを満たす入力鍵ＫＢ’１および入力鍵ＫＢ’０を得る。ステップＳ１３０の後、ステップＳ１３１に進む。
【００３５】
ステップＳ１３１〜Ｓ１３６では、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定し、さらにγ（０，０），γ（０，１）＝γ（１，０），γ（１，１）を得る。なお、ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ａ（θ））とするゲートＧ（θ）が存在する場合、出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））はゲートＧ（θ）の入力鍵ＫＡＩ（Ａ（θ））となる。ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ｂ（θ））とするゲートＧ（θ）が存在する場合、出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））はゲートＧ（θ）の入力鍵ＫＢＩ（Ｂ（θ））となる。ステップＳ１３１〜Ｓ１３６の処理はゲートＧ（ｉ）の種別によって異なる。以下、ゲートＧ（ｉ）がＡＮＤゲート、ＯＲゲート、ＸＯＲゲートである場合のステップＳ１３１〜Ｓ１３６の処理を説明する。
【００３６】
≪ゲートＧ（ｉ）がＡＮＤゲートの場合≫
ステップＳ１３１では、設定部１１８１（図２）が、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬとして出力する（ステップＳ１３１）。
jL:=nextindex()
【００３７】
次に、Ψ設定部１１８２は、ＫＡ０，ＫＢ’０，ｄｉ，ｊＬを入力とし、ＫＡ０＋ＫＢ’０およびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）∈Ｆｑと、ＫＡ０＋ＫＢ’０＋ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）∈Ｆｑとの排他的論理和Ψｉ∈Ｆｑを得て出力する。すなわち、Ψ設定部１１８２は、ＫＡ０＋ＫＢ’０を含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ））とＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ））との排他的論理和Ψｉを得る（ステップＳ１３２）。
Ψi:=H(KA0+KB’0,jL)(xor)H(KA0+KB’0+di,jL)
【００３８】
ＲＢ選択部１１８３は任意値ｂ０，ｂ１∈｛０，１｝をランダムに選択して出力する（ステップＳ１３３）。
b0,b1∈{0,1}
【００３９】
出力鍵設定部１１８４は、ＫＡ０，ＫＢ’０，ｂ０，ｄｉ，ｊＬを入力とし、ＫＡ０＋ＫＢ’０＋ｂ０ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋ｂ０ｄｉ，ｊＬ）∈Ｆｑを出力鍵Ｋｉ０として出力する。すなわち、出力鍵設定部１１８４は、ＫＡ０＋ＫＢ’０＋ｂ０ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋ｂ０ｄｉ，ｊＬ））を出力鍵Ｋｉ０とする（ステップＳ１３４）。
Ki0:=H(KA0+KB’0+b0di,jL)
【００４０】
出力鍵設定部１１８５は、ＫＡ０，ＫＢ’０，ｄｉ，ｊＬ，ｂ１，Ψｉを入力とし、ＫＡ０＋ＫＢ’０＋２ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）∈Ｆｑとｂ１Ψｉ∈Ｆｑとの排他的論理和を出力鍵Ｋｉ１として出力する。すなわち、出力鍵設定部１１８５は、ＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ））とｂ１Ψｉとの排他的論理和を出力鍵Ｋｉ１とする（ステップＳ１３５）。
Ki1:= H(KA0+KB’0+2di,jL)(xor)b1Ψi
【００４１】
γ設定部１１８６は、ｂ０，ｂ１を入力とし、γ（０，０）＝ｂ０、γ（０，１）＝γ（１，０）＝１（ｘｏｒ）ｂ０、およびγ（１，１）＝ｂ１を得て出力する（ステップＳ１３６）。
γ(0,0):=b0, γ(0,1):=γ(1,0):=1(xor)b0, γ(1,1):=b1
【００４２】
≪ゲートＧ（ｉ）がＯＲゲートの場合≫
ステップＳ１３１では、設定部１１８１が、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬとして出力する（ステップＳ１３１）。
jL:=nextindex()
【００４３】
次に、Ψ設定部１１８２は、ＫＡ０，ＫＢ’０，ｄｉ，ｊＬを入力とし、ＫＡ０＋ＫＢ’０＋ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）∈Ｆｑと、ＫＡ０＋ＫＢ’０＋２ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）∈Ｆｑとの排他的論理和Ψｉを得て出力する。すなわち、Ψ設定部１１８２は、ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ））とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ））との排他的論理和Ψｉを得る（ステップＳ１３２）。
Ψi:=H(KA0+KB’0+di,jL)(xor)H(KA0+KB’0+2di,jL) 
【００４４】
ＲＢ選択部１１８３は任意値ｂ０，ｂ１∈｛０，１｝をランダムに選択して出力する（ステップＳ１３３）。
b0,b1∈{0,1}
【００４５】
出力鍵設定部１１８４は、ＫＡ０，ＫＢ’０，ｊＬ，ｂ１，Ψｉを入力とし、ＫＡ０＋ＫＢ’０およびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）∈Ｆｑとｂ１Ψｉとの排他的論理和を出力鍵Ｋｉ０として出力する。すなわち、出力鍵設定部１１８４は、ＫＡ０＋ＫＢ’０を含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ））とｂ１Ψｉとの排他的論理和を出力鍵Ｋｉ０とする（ステップＳ１３４）。
Ki0:=H(KA0+KB’0,jL)(xor)b1Ψi
【００４６】
出力鍵設定部１１８５は、ＫＡ０，ＫＢ’０，ｄｉ，ｂ０，ｊＬを入力とし、ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉ，ｊＬ）∈Ｆｑとｂ１Ψｉ∈Ｆｑとの排他的論理和を出力鍵Ｋｉ１として出力する。すなわち、出力鍵設定部１１８５は、ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉ，ｊＬ））を出力鍵Ｋｉ１とする（ステップＳ１３５）。
Ki1:=H(KA0+KB’0+di+b0 di,jL)
【００４７】
γ設定部１１８６は、ｂ０，ｂ１を入力とし、γ（０，０）＝ｂ１、γ（０，１）＝γ（１，０）＝ｂ０、およびγ（１，１）＝１（ｘｏｒ）ｂ０を得て出力する（ステップＳ１３６）。
γ(0,0):=b1, γ(0,1):=γ(1,0):=b0, γ(1,1):=1(xor)b0
【００４８】
≪ゲートＧ（ｉ）がＸＯＲゲートの場合≫
ステップＳ１３１では、設定部１１８１が、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬとして出力する（ステップＳ１３１）。
jL:=nextindex()
【００４９】
次に、Ψ設定部１１８２は、ＫＡ０，ＫＢ’０，ｊＬ，ｄｉを入力とし、ＫＡ０＋ＫＢ’０およびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）∈Ｆｑと、ＫＡ０＋ＫＢ’０＋２ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）∈Ｆｑとの排他的論理和Ψｉを得て出力する。すなわち、Ψ設定部１１８２は、ＫＡ０＋ＫＢ’０を含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ））とＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ））との排他的論理和Ψｉを得る（ステップＳ１３２）。
Ψi:=H(KA0+KB’0, jL)(xor)H(KA0+KB’0+2di, jL)
【００５０】
ＲＢ選択部１１８３は任意値ｂ０，ｂ１∈｛０，１｝をランダムに選択して出力する（ステップＳ１３３）。
b0,b1∈{0,1}
【００５１】
出力鍵設定部１１８４は、ＫＡ０，ＫＢ’０，ｂ０，ｄｉ，ｊＬを入力とし、ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉ，ｊＬ）∈Ｆｑを出力鍵Ｋｉ０として出力する。すなわち、出力鍵設定部１１８４は、ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉ，ｊＬ））を出力鍵Ｋｉ０する（ステップＳ１３４）。
Ki0:=H(KA0+KB’0+2b0 di, jL)
【００５２】
出力鍵設定部１１８５は、ＫＡ０，ＫＢ’０，ｄｉ，ｊＬ，ｂ１，Ψｉを入力とし、ＫＡ０＋ＫＢ’０＋ｄｉおよびインデックスｊＬに対応するハッシュ値Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）∈Ｆｑとｂ１Ψｉ∈Ｆｑとの排他的論理和を出力鍵Ｋｉ１として出力する。すなわち、出力鍵設定部１１８５は、ＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値（Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ））とｂ１Ψｉとの排他的論理和を出力鍵Ｋｉ１とする（ステップＳ１３５）。
Ki1:=H(KA0+KB’0+di, jL)(xor)b1Ψi
【００５３】
γ設定部１１８６は、ｂ０，ｂ１を入力とし、γ（０，０）＝１（ｘｏｒ）ｂ０、γ（０，１）＝γ（１，０）＝ｂ１、およびγ（１，１）＝ｂ０を得て出力する（ステップＳ１３６）。
γ(0,0):=b0, γ(0,1):=γ(1,0):=b1, γ(1,1):=1(xor)b0
【００５４】
ステップＳ１３１〜Ｓ１３６の後、設定部１１９１がｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬ,γとして出力する（ステップＳ１３７）。
jL,γ:=nextindex()
【００５５】
ＲＰＢ選択部１１９２は、ランダムに置換ビットλ（ｉ）∈｛０，１｝を選択して出力する（ステップＳ１３８）。
【００５６】
暗号化部１１９３（出力ラベル設定部）は、すべてのＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝について、ＫＡＩ（Ａ），ＫＢ’Ｉ（Ｂ），ｊＬ,γ，λ（ｉ），γ（Ｉ（Ａ），Ｉ（Ｂ））を入力とし、
【数２】
0006629461.tif 000006
を得て出力する。ただし、ｌｓｂ２（α）はα∈Ｆｑをｋビットで表現したビット列ｂｉｔα∈｛０，１｝ｋの最下位から２ビット目までの２ビットを表す。ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））はゲートＧ（ｉ）に応じて定まる。ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））（ｘｏｒ）λ（ｉ）は出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対して設定したラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝である。ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ａ（θ））とするゲートＧ（θ）が存在する場合、ラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））はゲートＧ（θ）のラベルＬＡＩ（Ａ（θ））となる。ゲートＧ（ｉ）の出力ワイヤＷ（ｉ）を入力ワイヤＷ（Ｂ（θ））とするゲートＧ（θ）が存在する場合、ラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））はゲートＧ（θ）のラベルＬＢＩ（Ｂ（θ））となる。α｜βはαとβとのビット結合である。
【数３】
0006629461.tif 000007
は、入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値
【数４】
0006629461.tif 000008
を共通鍵として、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対して設定したラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））＝ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））（ｘｏｒ）λ（ｉ）、および、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文である（ステップＳ１３９）。
【００５７】
ステップＳ１１５で暗号文Ｅｉが設定されている場合、Ｆ設定部１１９４は、ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ，Ｅｉを入力として、秘匿ゲートＦ［ｉ］：＝（ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ，Ｅｉ）を得て出力する。一方、ステップＳ１１５で暗号文Ｅｉが設定されていない場合、Ｆ設定部１１９４は、ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉを入力として、秘匿ゲートＦ［ｉ］：＝（ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ）を得て出力する（ステップＳ１４０）。
【００５８】
Ｗ（ｊ）（ただし、ｊ∈｛Ａ，Ｂ｝）が回路ｆの入力ワイヤである場合（図１４Ａおよび図１４Ｂの例では、Ｗ（ｊ）∈Ｗｉｎｐｕｔである場合）、ｅ設定部１１９５は、Ｋｊ０，Ｌｊ０，Ｋｊ１，Ｌｊ１を入力として符号化情報ｅ［ｊ］：＝（Ｋｊ０｜Ｌｊ０，Ｋｊ１｜Ｌｊ１）を得て出力する（ステップＳ１４１）。
【００５９】
Ｗ（ｉ）が回路ｆの出力ワイヤである場合（図１４Ａおよび図１４Ｂの例では、Ｗ（ｉ）∈Ｗｏｕｔｐｕｔである場合）、ｄ設定部１１９６は、λ（ｉ）を入力として復号情報ｄ［ｉ−（ｎ＋ｕ）＋ｍ］：＝λ（ｉ）を得て出力する（ステップＳ１４２）。
【００６０】
制御部１１３はｉ＝ｎ＋ｕであるかを判定する（ステップＳ１４３）。ｉ＝ｎ＋ｕでない場合、制御部１１３はｉ＋１を新たなｉに設定（ｉ：＝ｉ＋１）し（ステップＳ１４４）、処理をステップＳ１０３に戻す。一方、ｉ＝ｎ＋ｕの場合、通信部１１１１は、得られたすべての秘匿ゲートＦ［ｉ］からなる秘匿回路Ｆ、得られたすべての符号化情報ｅ［ｊ］からなる符号化情報ｅ、および、得られたすべての復号情報ｄ［ｉ−（ｎ＋ｕ）＋ｍ］からなる復号情報ｄを送信する。なお、図１４Ａに例示した回路ｆの場合、Ｆ＝（Ｆ［ｎ＋１］，…，Ｆ［ｎ＋ｕ］）、ｅ＝（ｅ［１］，…，ｅ［ｎ］）、ｄ＝（λ（ｎ＋ｕ−ｍ＋１），…，λ（ｎ＋ｕ））となる。秘匿回路Ｆはｍと共に計算装置１３に送信され、符号化情報ｅは符号化装置１２に送信される。ただし、ｍが定数の場合、ｍは計算装置１３に送信されない。復号情報ｄは復号装置１４に送信される（ステップＳ１４５）。
【００６１】
＜符号化装置１２の符号化処理＞
図１１Ａを用い、符号化装置１２の符号化処理を説明する。
符号化装置１２（図４Ａ）の通信部１２１１には符号化情報ｅが入力され、入力部１２１２にはｎビットの入力値ｘ＝（ｘ１，…，ｘｎ）∈｛０，１｝ｎが入力される（ステップＳ１５１）。分離部１２４は、入力値ｘを各ビットｘ１，…，ｘｎに分離する（ステップＳ１５２）。制御部１２３はｉ：＝１と設定する（ステップＳ１５３）。分離部１２５は、符号化情報ｅを構成するｅ［ｉ］をｅ［ｉ］＝（ｅ0，ｅ１）に分離する（ステップＳ１５４）。符号化部１２６は、ｘｉ∈｛０，１｝およびｅ［ｉ］＝（ｅ0，ｅ１）を用い、符号
【数５】
0006629461.tif 000009
を得る（ステップＳ１５５）。制御部１２３はｉ＝ｎであるかを判定する（ステップＳ１５６）。ｉ＝ｎでない場合、制御部１２３はｉ＋１を新たなｉに設定（ｉ：＝ｉ＋１）し（ステップＳ１５７）、処理をステップＳ１５４に戻す。一方、ｉ＝ｎの場合、通信部１２１１は符号列η＝（η［１］，…，η［ｎ］）を送信する。符号列ηは計算装置１３に送信される（ステップＳ１５８）。
【００６２】
＜計算装置１３の計算処理＞
図１２および図１３を用い、計算装置１３の計算処理を説明する。
計算装置１３（図５）の通信部１３１１には、秘匿回路Ｆ＝（Ｆ［ｎ＋１］，…，Ｆ［ｎ＋ｕ］）、ｍ、および符号列η＝（η［１］，…，η［ｎ］）が入力される。ただし、ｍが定数の場合にはｍは入力されない。制御部１３３は、ｎｅｘｔｉｎｄｅｘ（）によって１ずつインクリメントされる内部カウンタを初期値（例えば０）に初期化する（ステップＳ１７１）。
【００６３】
制御部１３３はｊ：＝１と設定する（ステップＳ１７２）。分離部１３４は、符号η［ｊ］を入力とし、それをＫｊ｜Ｌｊ：＝η［ｊ］と分離する（ステップＳ１７３）。制御部１３３はｊ＝ｎであるかを判定する（ステップＳ１７４）。ｊ＝ｎでない場合、制御部１３３はｊ＋１を新たなｊに設定（ｊ：＝ｊ＋１）し（ステップＳ１７５）、処理をステップＳ１７３に戻す。一方、ｊ＝ｎの場合、制御部１３３はｉ：＝ｎ＋１と設定し（ステップＳ１７６）、処理をステップＳ１７７に進める。
【００６４】
ステップＳ１７７では、入力ワイヤ設定部１３５１が、Ａ：＝Ａ（ｉ）およびＢ：＝Ｂ（ｉ）に設定する（ステップＳ１７７）。ラベル計算部１３５２は、ＬＡ，ＬＢを入力としてｔ：＝２ＬＡ＋ＬＢ∈｛０，１，２，３｝を得て出力する（ステップＳ１７８）。分離部１３５３は、Ｆ［ｉ］を分離し、（ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ，Ｅｉ）または（ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ）を得て記憶部１３２に格納する（ステップＳ１７９）。
【００６５】
判定部１３５４は、分離部１３５３からの出力を入力とし、Ｆ［ｉ］が暗号文Ｅｉを含むかを判定する（ステップＳ１８０）。ここで、Ｆ［ｉ］が暗号文Ｅｉを含まない場合、ステップＳ１８４に進む。一方、Ｆ［ｉ］が暗号文Ｅｉを含む場合、設定部１３５５は、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＥとして出力する（ステップＳ１８１）。
jE:=nextindex()
【００６６】
判定部１３５４は、ラベルＬＢを入力としてＬＢ＝１であるかを判定する（ステップＳ１８２）。ここで、ＬＢ＝１でない場合にはステップＳ１８４に進む。一方、ＬＢ＝１である場合には、鍵復号部１３５６がＫＢ，ｊＥ，Ｅｉを入力とし、ＥｉとＨ（ＫＢ，ｊＥ）との排他的論理和を新たな入力鍵ＫＢとして得て出力する。すなわち、鍵復号部１３５６は、入力鍵ＫＢを含む値の関数値（Ｈ（ＫＢ，ｊＥ））を共通鍵として、暗号文Ｅｉを復号して新たな入力鍵ＫＢを得る（ステップＳ１８３）。
KB:=Ei(xor)H(KB, jE)
ステップＳ１８３の次にステップＳ１８４に進む。
【００６７】
ステップＳ１８４では、設定部１３５７がｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬとして出力する（ステップＳ１８４）。
jL:=nextindex()
【００６８】
その後、設定部１３５７がｎｅｘｔｉｎｄｅｘ（）によって内部カウンタをさらに１インクリメントし、インクリメント後の内部カウンタの値をｊＬ，γとして出力する（ステップＳ１８５）。
jL,γ:=nextindex()
【００６９】
復号部１３５８は、ＫＡ，ＫＢ、ｊＬ，γ、および、ステップＳ１７９で得られたｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γのうち、ステップＳ１７８で得られたｔ∈｛０，１，２，３｝に対応するｂｔＬ，γを入力とし、ｌｓｂ２（Ｈ（ＫＡ｜ＫＢ），ｊＬ，γ）とｂｔＬ，γとの排他的論理和をＬｉ｜γとして得て出力する。すなわち、復号部１３５８は、ゲートＧ（ｉ）の入力値に対応するＫＡおよびＫＢを含む値の関数値（ｌｓｂ２（Ｈ（ＫＡ｜ＫＢ），ｊＬ，γ））を共通鍵として、暗号文ｂｔＬ，γを復号してＬｉおよびγ＝γ（Ｉ（Ａ），Ｉ（Ｂ））を得て出力する（ステップＳ１８６）。
【数６】
0006629461.tif 000010
【００７０】
出力鍵生成部１３５９は、ＫＡ，ＫＢ，ｊＬ，γ，Ψｉを入力とし、Ｈ（ＫＡ＋ＫＢ，ｊＬ）とγΨｉとの排他的論理和を出力鍵Ｋｉとして得て出力する。すなわち、出力鍵生成部１３５９は、ＫＡ＋ＫＢを含む値の関数値（Ｈ（ＫＡ＋ＫＢ，ｊＬ））とγΨｉとの排他的論理和を、ゲートの出力値に対応する出力鍵Ｋｉとして得る（ステップＳ１８７）。
Ki:=H(KA+KB, jL)(xor)γΨi
【００７１】
制御部１３３はｉ＝ｎ＋ｕであるかを判定する（ステップＳ１８８）。ｉ＝ｎ＋ｕでない場合、制御部１３３はｉ＋１を新たなｉに設定（ｉ：＝ｉ＋１）し（ステップＳ１８９）、処理をステップＳ１７７に戻す。一方、ｉ＝ｎ＋ｕである場合、出力値生成部１３６はステップＳ１８６で得られたラベルＬｉ（ただしｉ∈｛ｎ＋１，…，ｎ＋ｕ｝）およびｍを入力としてラベル列μ＝（Ｌｎ＋ｕ−ｍ＋１，…，Ｌｎ＋ｕ）を得る。ただし、ｍが定数の場合にはｍは入力されない。通信部１３１１は、ラベル列μを復号装置１４に送信する（ステップＳ１９０）。
μ:=(Ln+u-m+1,...,Ln+u)
【００７２】
＜復号装置１４の復号処理＞
次に、図１１Ｂを用い、復号装置１４の復号処理を説明する。
復号装置１４（図４Ｂ）の通信部１４１１には、復号情報ｄ＝（λ（ｎ＋ｕ−ｍ＋１），…，λ（ｎ＋ｕ））およびラベル列μ＝（Ｌｎ＋ｕ−ｍ＋１，…，Ｌｎ＋ｕ）が入力される（ステップＳ１６１）。分離部１４４は、入力されたラベル列μをＬｎ＋ｕ−ｍ＋１，…，Ｌｎ＋ｕに分離して出力する（ステップＳ１６２）。分離部１４５は、入力された復号情報ｄをλ（ｎ＋ｕ−ｍ＋１），…，λ（ｎ＋ｕ）に分離して出力する（ステップＳ１６３）。復号部１４６は、Ｌｎ＋ｕ−ｍ＋１，…，Ｌｎ＋ｕおよびλ（ｎ＋ｕ−ｍ＋１），…，λ（ｎ＋ｕ）を入力として、Ｌｎ＋ｕ−ｍ＋１（ｘｏｒ）λ（ｎ＋ｕ−ｍ＋１），…，Ｌｎ＋ｕ（ｘｏｒ）λ（ｎ＋ｕ）からなる復号値ｆ（ｘ）を得て出力する（ステップＳ１６４）。
f(x):=(Ln+u-m+1(xor)λ(n+u-m+1),...,Ln+u(xor)λ(n+u))
【００７３】
＜本形態の特徴＞
本形態では、回路秘匿処理において、各ゲートＧ（ｉ）について、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定し、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定した（ステップＳ１１０〜Ｓ１３０）。これにより、すべての入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を独立に生成する従来方式に比べて、秘匿回路Ｆのデータ量を削減できる。本形態ではＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たすことを利用してステップＳ１３２で排他的論理和Ψｉを計算し、これを各秘匿ゲートＦ［ｉ］の要素とする。これにより、各秘匿ゲートＦ［ｉ］のデータ量を削減している。例えば、暗号文Ｅｉを含まない各秘匿ゲートＦ［ｉ］＝（ｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γ，Ψｉ）のビット長はｋ＋８ビットであり、これは各秘匿ゲートのデータ量が２ｋビットとなる非特許文献１の約半分のデータ量である（ｋが十分に大きい場合、例えば、ｋ＝１２８やｋ＝２５６等）。通常のセキュリティパラメータｋは２ｋ＞ｋ＋８の関係を満たすため、本形態の方式は秘匿回路のデータ量を削減できる。
【００７４】
なお、ステップＳ１８７ではＫｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）（ｘｏｒ）γΨｉによって出力鍵を計算しているが、これによって正しい出力鍵Ｋｉが得られることは容易に確かめられる。例えば、ゲートＧ（ｉ）がＡＮＤゲートの場合を例にとると、ステップＳ１３２でΨｉ：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）とし、ステップＳ１３４でＫｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｂ０ｄｉ，ｊＬ）とし、ステップＳ１３５でＫｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）（ｘｏｒ）ｂ１Ψｉとし、ステップＳ１３６でγ（０，０）：＝ｂ０，γ（０，１）：＝γ（１，０）：＝１（ｘｏｒ）ｂ０，γ（１，１）：＝ｂ１としている。さらに（ｂ０，ｂ１）＝（０，０）の場合を例にとると、Ｋｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）、Ｋｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）、γ（０，０）：＝０，γ（０，１）：＝γ（１，０）：＝１，γ（１，１）：＝０となる。ここでＩ（Ａ）＝Ｉ（Ｂ）＝０の場合には、γ＝γ（０，０）＝０であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）となる。これは、出力値ｇｉ（０，０）＝０に対応するＫｉ０＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）と一致する。Ｉ（Ａ）＝０，Ｉ（Ｂ）＝１の場合には、γ＝γ（０，１）＝１であり、ステップＳ１８７で得られるＫｉは、Ｋｉ＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）（ｘｏｒ）Ψｉ＝Ｈ（ＫＡ０＋ＫＢ’１，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）となる。これは、出力値ｇｉ（０，１）＝０に対応するＫｉ０＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）と一致する。Ｉ（Ａ）＝１，Ｉ（Ｂ）＝１の場合には、γ＝γ（１，１）＝０であり、ステップＳ１８７で得られるＫｉは、Ｋｉ＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ１＋ＫＢ１，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ０＋２ｄｉ，ｊＬ）となる。これは出力値ｇｉ（１，１）＝１に対応するＫｉ１＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）と一致する。また、ゲートＧ（ｉ）がＯＲゲートの場合を例にとると、ステップＳ１３２でΨｉ：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）とし、ステップＳ１３４でＫｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）ｂ１Ψｉとし、ステップＳ１３５でＫｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ＋ｂ０ｄｉ，ｊＬ）とし、ステップＳ１３６でγ（０，０）：＝ｂ１，γ（０，１）：＝γ（１，０）：＝ｂ０，γ（１，１）：＝１（ｘｏｒ）ｂ０としている。さらに（ｂ０，ｂ１）＝（０，０）の場合を例にとると、Ｋｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）、Ｋｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）、γ（０，０）：＝０，γ（０，１）：＝γ（１，０）：＝０，γ（１，１）：＝１となる。ここでＩ（Ａ）＝Ｉ（Ｂ）＝０の場合には、γ＝γ（０，０）＝０であり、ステップＳ１８７で得られるＫｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）は、出力値ｇｉ（０，０）＝０に対応するＫｉ０���Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）と一致する。Ｉ（Ａ）＝０，Ｉ（Ｂ）＝１の場合には、γ＝γ（０，１）＝０であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’１，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）となる。これは、出力値ｇｉ（０，１）＝１に対応するＫｉ１＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）と一致する。Ｉ（Ａ）＝１，Ｉ（Ｂ）＝１の場合には、γ＝γ（１，１）＝１であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）（ｘｏｒ）Ψｉ＝Ｈ（ＫＡ１＋ＫＢ１，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）となる。これは出力値ｇｉ（１，１）＝１に対応するＫｉ１＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）と一致する。また、ゲートＧ（ｉ）がＸＯＲゲートの場合を例にとると、ステップＳ１３２でΨｉ：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）とし、ステップＳ１３４でＫｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｂ０ｄｉ，ｊＬ）とし、ステップＳ１３５でＫｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）（ｘｏｒ）ｂ１Ψｉとし、ステップＳ１３６でγ（０，０）：＝ｂ０，γ（０，１）：＝γ（１，０）：＝ｂ１，γ（１，１）：＝１（ｘｏｒ）ｂ０としている。さらに（ｂ０，ｂ１）＝（０，０）の場合を例にとると、Ｋｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）、Ｋｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）、γ（０，０）：＝０，γ（０，１）：＝γ（１，０）：＝０，γ（１，１）：＝１となる。
ここでＩ（Ａ）＝Ｉ（Ｂ）＝０の場合には、γ（０，０）：＝０であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）となる。これは、出力値ｇｉ（０，０）＝０に対応するＫｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）と一致する。Ｉ（Ａ）＝０，Ｉ（Ｂ）＝１の場合には、γ＝γ（０，１）＝０であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’１，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）となる。これは、出力値ｇｉ（０，１）＝１に対応するＫｉ１：＝Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ）と一致する。Ｉ（Ａ）＝１，Ｉ（Ｂ）＝１の場合には、γ（１，１）：＝１であり、ステップＳ１８７で得られるＫｉは、Ｋｉ：＝Ｈ（ＫＡ＋ＫＢ，ｊＬ）（ｘｏｒ）Ψｉ＝Ｈ（ＫＡ１＋ＫＢ’１，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）（ｘｏｒ）Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ）＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）となる。これは、出力値ｇｉ（１，１）＝０に対応するＫｉ０：＝Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ）と一致する。このように、ステップＳ１８７によって正しい出力鍵Ｋｉが得られることが分かる。
【００７５】
また、ゲートＧ（ｉ）の入力鍵ＫＡＩ（Ａ）が他のゲートＧ（α）の出力鍵ＫαＩ（α）であり（入力鍵ＫＡＩ（Ａ）が設定され）、入力鍵ＫＢＩ（Ｂ）が他のゲートＧ（β）の出力鍵ＫβＩ（β）である場合（入力鍵ＫＢＩ（Ｂ）が設定されている場合）、ＫαＩ（α）＝ＫＡＩ（Ａ）そのものを入力鍵ＫＡＩ（Ａ）とし、ＫβＩ（β）＝ＫＢＩ（Ｂ）そのものを入力鍵ＫＢ’Ｉ（Ｂ）としたのでは、通常、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たさない。本形態では、このような場合に、ｄｉ＝ＫＡ１−ＫＡ０を得、入力値Ｉ（Ｂ）に対応するラベルＬＢＩ（Ｂ）＝λ（Ｂ）（ｘｏｒ）Ｉ（Ｂ）についてＫＢ’λ（Ｂ）＝ＫＢλ（Ｂ）を得、ＫＢ’１（ｘｏｒ）λ（Ｂ）＝ＫＢ’λ（Ｂ）＋（−１）λ（Ｂ）ｄｉを得、入力鍵ＫＢ１（ｘｏｒ）λ（Ｂ）を含む値の関数値を共通鍵としてＫＢ’１（ｘｏｒ）λ（Ｂ）を暗号化した暗号文Ｅｉを得ることにした（ステップＳ１１０〜Ｓ１１５）。これにより、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす。計算装置１３は、他のゲートＧ（β）の出力鍵ＫβＩ（β）である入力鍵ＫＢを含む値の関数値を共通鍵として、暗号文Ｅｉを復号することで、新たな入力鍵ＫＢ＝ＫＢ’１（ｘｏｒ）λ（Ｂ）を得ることができる（ステップＳ１８３）。
【００７６】
［第２実施形態］
図面を用いて第２実施形態を説明する。以下では第１実施形態との相違点を中心に説明する。第１実施形態と共通する事項については、前述した参照番号を引用して説明を簡略化する。
【００７７】
＜構成＞
図１に例示するように、本形態の秘匿計算システム２は、回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４を有する。回路秘匿装置２１は符号化装置１２、計算装置２３、および復号装置１４に情報の提供が可能なように構成されており、符号化装置１２は計算装置２３に情報の提供が可能なように構成されており、計算装置２３は復号装置１４に情報の提供が可能なように構成されている。例えば、回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４は、ネットワークを通じて情報の送受信を行う。回路秘匿装置２１と符号化装置１２とが異なるパーティによって利用されるのであれば、計算装置２３および復号装置１４はどのパーティに利用されてもよい。説明の簡略化のため、図１では、回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４を１つずつ図示するが、これらの少なくとも何れかが複数個存在してもよい。
【００７８】
＜回路秘匿装置２１＞
図１５に例示するように、回路秘匿装置２１は、通信部１１１１、入力部１１１２、記憶部１１２、制御部１１３、初期設定部１１４、入力ワイヤ設定部１１５、判定部１１６０、置換ビット設定部１１６１、入力ラベル設定部１１６２、判定部１１７１、入力鍵設定部１１７２〜１１７４、設定部１１８１，２１８１、Ψ設定部２１８２、Ｐ多項式設定部２１８３、出力鍵設定部２１８４、出力鍵設定部２１８５、Ｑ多項式設定部２１８６、座標点特定部２１８７、設定部１１９１、ＲＰＢ選択部１１９２、暗号化部２１９３、Ｆ設定部１１９４、ｅ設定部１１９５、およびｄ設定部１１９６を有する。
【００７９】
＜計算装置２３＞
図１６に例示するように、計算装置２３は、通信部１３１１、記憶部１３２、制御部１３３、分離部１３４、入力ワイヤ設定部１３５１、ラベル計算部１３５２、分離部１３５３、判定部１３５４、設定部１３５５、鍵復号部１３５６、設定部１３５７、復号部２３５８、出力鍵生成部２３５９、出力値生成部１３６、および座標点特定部２３５７を有する。
【００８０】
回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４のそれぞれは、例えば、前述のコンピュータが所定のプログラムを実行することで構成される装置である。回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４は、それぞれ制御部１１３，１２３，１３３，１４３の制御のもとで各処理を行う。回路秘匿装置２１、符号化装置１２、計算装置２３、および復号装置１４へ入力された情報やそれらで得られたデータは、逐一、記憶部１１２，１２２，１３２，１４２にそれぞれ格納され、必要に応じて読み出されて使用される。
【００８１】
＜回路秘匿装置２１の回路秘匿処理＞
図６〜図８、図１７、および図１８を用い、回路秘匿装置２１による回路ｆ＝（ｎ，ｍ，ｕ，Ａ，Ｂ，ｇ）の秘匿処理を説明する。
本形態では、回路秘匿装置１１に代えて回路秘匿装置２１が、第１実施形態で説明したステップＳ１０１〜Ｓ１３０の処理を実行する。その後、回路秘匿装置１１に代えて回路秘匿装置２１が、ステップＳ１３１〜Ｓ１３６に代えて図１７のステップＳ１３１、Ｓ２３１〜Ｓ２３８の処理を実行する。
ステップＳ１３１、Ｓ２３１〜Ｓ２３８では、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））∈｛０，１｝に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定し、さらにγ（０，０），γ（０，１）＝γ（１，０），γ（１，１）を得る。ステップＳ１３１、Ｓ２３１〜Ｓ２３８の処理はゲートＧ（ｉ）の種別によって異なる。以下、ゲートＧ（ｉ）がＡＮＤゲート、ＯＲゲート、ＸＯＲゲートである場合のステップＳ１３１、Ｓ２３１〜Ｓ２３８の処理を説明する。
【００８２】
≪ゲートＧ（ｉ）がＡＮＤゲートの場合≫
ステップＳ１３１では、設定部１１８１（図１５）が、ｎｅｘｔｉｎｄｅｘ（）によって内部カウンタを１インクリメントし、インクリメント後の内部カウンタの値をｊＬとして出力する（ステップＳ１３１）。
jL:=nextindex()
【００８３】
設定部２１８１は、｛１，２，３｝の要素順序をランダムに並び替えるランダム置換関数π：｛１，２，３｝→｛１，２，３｝を設定し（ステップＳ２３１）、このランダム置換関数πをε∈｛１，２，３｝に適用することでπ（ε）∈｛１，２，３｝を得、γ（０，０）：＝π（１）∈｛０，１｝２、γ（０，１）：＝γ（１，０）：＝π（２）∈｛０，１｝２、およびγ（１，１）：＝π（３）∈｛０，１｝２と設定する。γ（０，０）は（Ｉ（Ａ），Ｉ（Ｂ））＝（０，０）に対応する値であり、γ（０，１）は（Ｉ（Ａ），Ｉ（Ｂ））＝（０，１）に対応する値であり、γ（１，０）は（Ｉ（Ａ），Ｉ（Ｂ））＝（１，０）に対応する値であり、γ（１，１）は（Ｉ（Ａ），Ｉ（Ｂ））＝（１，１）に対応する値である。ただし、π（１）≠π（２）であり、π（２）≠π（３）であり、π（１）≠π（３）である（ステップＳ２３２）。
【００８４】
座標点特定部２１８７は、γ（０，０），γ（０，１）＝γ（１，０），γ（１，１），ＫＡ０，ＫＢ’０，ｄｉ，ｊＬを入力とし、点（Ｘ１，Ｙ１）：＝（γ（０，０），Ｈ（ＫＡ０＋ＫＢ’０，ｊＬ））、点（Ｘ２，Ｙ２）：＝（γ（１，０），Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ））＝（γ（０，１），Ｈ（ＫＡ０＋ＫＢ’０＋ｄｉ，ｊＬ））、および、点（Ｘ３，Ｙ３）：＝（γ（１，１），Ｈ（ＫＡ０＋ＫＢ’０＋２ｄｉ，ｊＬ））を得て出力する。Ｘ１は値γ（０，０）の関数値であり、Ｙ１はＫＡ０＋ＫＢ’０を含む値の関数値であり、Ｘ２は値γ（１，０）＝γ（０，１）の関数値であり、Ｙ２はＫＡ０＋ＫＢ’０＋ｄｉを含む値の関数値であり、Ｘ３は値γ（１，１）の関数値であり、Ｙ３はＫＡ０＋ＫＢ’０＋２ｄｉを含む値の関数値である（ステップＳ２３３）。
【００８５】
Ｐ多項式設定部２１８３は、点（Ｘ１，Ｙ１）および点（Ｘ２，Ｙ２）を入力とし、点（Ｘ１，Ｙ１）および点（Ｘ２，Ｙ２）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得て出力する。Ｘはｘ軸の値であり、Ｙはｙ軸の値である。図２０Ａに、π（１）＝１，π（２）＝２，π（３）＝３の場合の（Ｘ１，Ｙ１），（Ｘ２，Ｙ２），Ｙ＝Ｐ（Ｘ）の関係を例示する（ステップＳ２３４）。
【００８６】
Ｑ多項式設定部２１８６は、一次多項式Ｙ＝Ｐ（Ｘ）を入力とし、Ｘ１からＸ３と異なる定数Ｘ４（例えば、Ｘ４＝４）をＹ＝Ｐ（Ｘ）に代入して点（Ｘ４，Ｐ（Ｘ４））を得る。Ｑ多項式設定部２１８６は、さらに点（Ｘ３，Ｙ３）を入力とし、点（Ｘ３，Ｙ３）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得て出力する。図２０Ａに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ４＝４の場合の（Ｘ３，Ｙ３），（Ｘ４，Ｐ（Ｘ４）），Ｙ＝Ｑ（Ｘ）の関係を例示する（ステップＳ２３５）。
【００８７】
Ψ設定部２１８２は、Ｐ（Ｘ４）＝Ｑ（Ｘ４）を入力とし、Ψｉ：＝Ｐ（Ｘ４）と設定して出力する（ステップＳ２３６）。
Ψi:=P(X4)
出力鍵設定部２１８４は、一次多項式Ｙ＝Ｐ（Ｘ）を入力とし、Ｘ１からＸ４と異なる定数Ｘ０（例えば、Ｘ０＝０）をＹ＝Ｐ（Ｘ）に代入して得られるＰ（Ｘ０）を出力鍵Ｋｉ０：＝Ｐ（Ｘ０）として出力する。図２０Ａに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｐ（Ｘ），Ｋｉ０の関係を例示する（ステップＳ２３７）。
Ki0:=P(X0)
出力鍵設定部２１８５は、一次多項式Ｙ＝Ｑ（Ｘ）を入力とし、上述の定数Ｘ０をＹ＝Ｑ（Ｘ）に代入して得られるＱ（Ｘ０）を出力鍵Ｋｉ１：＝Ｑ（Ｘ０）として出力する。図２０Ａに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｑ（Ｘ），Ｋｉ１の関係を例示する（ステップＳ２３８）。
【００８８】
≪ゲートＧ（ｉ）がＯＲゲートの場合≫
ステップＳ１３１，Ｓ２３１〜Ｓ２３３の処理は、ゲートＧ（ｉ）がＡＮＤゲートの場合と同一である。ステップＳ２３３の後、Ｑ多項式設定部２１８６は、点（Ｘ２，Ｙ２）および点（Ｘ３，Ｙ３）を入力とし、点（Ｘ２，Ｙ２）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｑ（Ｘ）を得て出力する。図２０Ｂに、π（１）＝１，π（２）＝２，π（３）＝３の場合の（Ｘ２，Ｙ２），（Ｘ３，Ｙ３），Ｙ＝Ｑ（Ｘ）の関係を例示する（ステップＳ２３４）。
【００８９】
Ｐ多項式設定部２１８３は、一次多項式Ｙ＝Ｑ（Ｘ）を入力とし、Ｘ１からＸ３と異なる定数Ｘ４（例えば、Ｘ４＝４）をＹ＝Ｑ（Ｘ）に代入して点（Ｘ４，Ｑ（Ｘ４））を得る。Ｐ多項式設定部２１８３は、さらに点（Ｘ１，Ｙ１）を入力とし、点（Ｘ１，Ｙ１）および点（Ｘ４，Ｑ（Ｘ４））を通る一次多項式Ｙ＝Ｐ（Ｘ）を得て出力する。図２０Ｂに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ４＝４の場合の（Ｘ１，Ｙ１），（Ｘ４，Ｑ（Ｘ４）），Ｙ＝Ｐ（Ｘ）の関係を例示する（ステップＳ２３５）。
【００９０】
Ψ設定部２１８２は、Ｑ（Ｘ４）＝Ｐ（Ｘ４）を入力とし、Ψｉ：＝Ｑ（Ｘ４）と設定して出力する（ステップＳ２３６）。
Ψi:=Q(X4)
出力鍵設定部２１８４は、一次多項式Ｙ＝Ｐ（Ｘ）を入力とし、Ｘ１からＸ４と異なる定数Ｘ０（例えば、Ｘ０＝０）をＹ＝Ｐ（Ｘ）に代入して得られるＰ（Ｘ０）を出力鍵Ｋｉ０：＝Ｐ（Ｘ０）として出力する。図２０Ｂに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｐ（Ｘ），Ｋｉ０の関係を例示する（ステップＳ２３７）。
Ki0:=P(X0)
出力鍵設定部２１８５は、一次多項式Ｙ＝Ｑ（Ｘ）を入力とし、上述の定数Ｘ０をＹ＝Ｑ（Ｘ）に代入して得られるＱ（Ｘ０）を出力鍵Ｋｉ１：＝Ｑ（Ｘ０）として出力する。図２０Ｂに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｑ（Ｘ），Ｋｉ１の関係を例示する（ステップＳ２３８）。
【００９１】
≪ゲートＧ（ｉ）がＸＯＲゲートの場合≫
ステップＳ１３１，Ｓ２３１〜Ｓ２３３の処理は、ゲートＧ（ｉ）がＡＮＤゲートの場合と同一である。ステップＳ２３３の後、Ｐ多項式設定部２１８３は、点（Ｘ１，Ｙ１）および点（Ｘ３，Ｙ３）を入力とし、点（Ｘ１，Ｙ１）および点（Ｘ３，Ｙ３）を通る一次多項式Ｙ＝Ｐ（Ｘ）を得て出力する。図２０Ｃに、π（１）＝１，π（２）＝２，π（３）＝３の場合の（Ｘ１，Ｙ１），（Ｘ３，Ｙ３），Ｙ＝Ｐ（Ｘ）の関係を例示する（ステップＳ２３４）。
【００９２】
Ｑ多項式設定部２１８６は、一次多項式Ｙ＝Ｐ（Ｘ）を入力とし、Ｘ１からＸ３と異なる定数Ｘ４（例えば、Ｘ４＝４）をＹ＝Ｐ（Ｘ）に代入して点（Ｘ４，Ｐ（Ｘ４））を得る。Ｑ多項式設定部２１８６は、さらに点（Ｘ２，Ｙ２）を入力とし、点（Ｘ２，Ｙ２）および点（Ｘ４，Ｐ（Ｘ４））を通る一次多項式Ｙ＝Ｑ（Ｘ）を得て出力する。図２０Ｃに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ４＝４の場合の（Ｘ２，Ｙ２），（Ｘ４，Ｐ（Ｘ４）），Ｙ＝Ｑ（Ｘ）の関係を例示する（ステップＳ２３５）。
【００９３】
Ψ設定部２１８２は、Ｐ（Ｘ４）＝Ｑ（Ｘ４）を入力とし、Ψｉ：＝Ｐ（Ｘ４）と設定して出力する（ステップＳ２３６）。
Ψi:=P(X4)
出力鍵設定部２１８４は、一次多項式Ｙ＝Ｐ（Ｘ）を入力とし、Ｘ１からＸ４と異なる定数Ｘ０（例えば、Ｘ０＝０）をＹ＝Ｐ（Ｘ）に代入して得られるＰ（Ｘ０）を出力鍵Ｋｉ０：＝Ｐ（Ｘ０）として出力する。図２０Ｃに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｐ（Ｘ），Ｋｉ０の関係を例示する（ステップＳ２３７）。
Ki0:=P(X0)
出力鍵設定部２１８５は、一次多項式Ｙ＝Ｑ（Ｘ）を入力とし、上述の定数Ｘ０をＹ＝Ｑ（Ｘ）に代入して得られるＱ（Ｘ０）を出力鍵Ｋｉ１：＝Ｑ（Ｘ０）として出力する。図２０Ｃに、π（１）＝１，π（２）＝２，π（３）＝３，Ｘ０＝０の場合のＹ＝Ｑ（Ｘ），Ｋｉ１の関係を例示する（ステップＳ２３８）。
【００９４】
ステップＳ１３１、Ｓ２３１〜Ｓ２３８の後、回路秘匿装置１１に代えて回路秘匿装置２１が、第１実施形態で説明したステップＳ１３７およびＳ１３８の処理を行う（図１８）。その後、暗号化部２１９３（出力ラベル設定部）は、すべてのＩ（Ａ），Ｉ（Ｂ）∈｛０，１｝について、ＫＡＩ（Ａ），ＫＢ’Ｉ（Ｂ），ｊＬ,γ，λ（ｉ），γ（Ｉ（Ａ），Ｉ（Ｂ））を入力とし、
【数７】
0006629461.tif 000011
を得て出力する。ただし、ｌｓｂ３（α）はα∈Ｆｑをｋビットで表現したビット列ｂｉｔα∈｛０，１｝ｋの最下位から３ビット目までの３ビットを表す。
【数８】
0006629461.tif 000012
は、入力鍵ＫＡＩ（Ａ）およびＫＢ’Ｉ（Ｂ）を含む値の関数値
【数９】
0006629461.tif 000013
を共通鍵として、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対して設定したラベルＬｉｇ（Ｉ（Ａ），Ｉ（Ｂ））＝ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））（ｘｏｒ）λ（ｉ）、および、γ（Ｉ（Ａ），Ｉ（Ｂ））を暗号化した暗号文である（ステップＳ２３９）。
【００９５】
その後、回路秘匿装置１１に代えて回路秘匿装置２１が、第１実施形態で説明したステップＳ１４０からＳ１４３の処理を行う。ステップＳ１４３でｉ＝ｎ＋ｕでないと判定された場合、制御部１１３はｉ＋１を新たなｉに設定（ｉ：＝ｉ＋１）し（ステップＳ１４４）、処理をステップＳ１０３に戻す。一方、ｉ＝ｎ＋ｕの場合、通信部１１１１は、得られたすべての秘匿ゲートＦ［ｉ］からなる秘匿回路Ｆ、得られたすべての符号化情報ｅ［ｊ］からなる符号化情報ｅ、および、得られたすべての復号情報ｄ［ｉ−（ｎ＋ｕ）＋ｍ］からなる復号情報ｄを送信する。秘匿回路Ｆはｍと共に計算装置１３に送信され、符号化情報ｅは符号化装置１２に送信され、復号情報ｄは復号装置１４に送信される（ステップＳ１４５）。
【００９６】
＜符号化装置１２の符号化処理＞
第１実施形態と同じである。
【００９７】
＜計算装置２３の計算処理＞
図１２および図１９を用い、計算装置２３の計算処理を説明する。
本形態では、計算装置１３に代えて計算装置２３が、第１実施形態で説明したステップＳ１７１〜Ｓ１８５の処理を実行する。次に復号部２３５８が、ＫＡ，ＫＢ、ｊＬ，γ、および、ステップＳ１７９で得られたｂ０Ｌ，γ，ｂ１Ｌ，γ，ｂ２Ｌ，γ，ｂ３Ｌ，γのうち、ステップＳ１７８で得られたｔ∈｛０，１，２，３｝に対応するｂｔＬ，γを入力とし、ｌｓｂ３（Ｈ（ＫＡ｜ＫＢ），ｊＬ，γ）とｂｔＬ，γとの排他的論理和をＬｉ｜γとして得て出力する。すなわち、復号部２３５８は、ゲートＧ（ｉ）の入力値に対応するＫＡおよびＫＢを含む値の関数値（ｌｓｂ３（Ｈ（ＫＡ｜ＫＢ），ｊＬ，γ））を共通鍵として、暗号文ｂｔＬ，γを復号してＬｉおよびγ＝γ（Ｉ（Ａ），Ｉ（Ｂ））を得て出力する（ステップＳ２８６）。
【数１０】
0006629461.tif 000014
【００９８】
座標点特定部２３５７は、入力値（Ｉ（Ａ），Ｉ（Ｂ））に対応する入力鍵ＫＡ＝ＫＡＩ（Ａ），ＫＢ＝ＫＢＩ（Ｂ）∈｛０，１｝、値γ＝γ（Ｉ（Ａ），Ｉ（Ｂ））およびｊＬを入力とし、点（Ｘγ，ＹＫ）＝（γ，Ｈ（ＫＡ＋ＫＢ，ｊＬ））を得て出力する。すなわち、座標点特定部２３５７は、値γ＝γ（Ｉ（Ａ），Ｉ（Ｂ））の関数値をＸγとし、ＫＡ＋ＫＢを含む値の関数値をＹＫとして、点（Ｘγ，ＹＫ）を得て出力する（ステップＳ２８７）。
【００９９】
出力鍵生成部２３５９は、ステップＳ１７９で得られたΨｉ＝Ｐ（Ｘ４）＝Ｑ（Ｘ４）およびステップＳ２８７で得られた点（Ｘγ，ＹＫ）を入力とし、点（Ｘγ，ＹＫ）および点（Ｘ４，Ψｉ）を通る一次多項式Ｙ＝Ｒ（Ｘ）に定数Ｘ０（例えば、Ｘ０＝０）を代入した値Ｙ＝Ｒ（Ｘ０）を出力鍵Ｋｉとして得て出力する。前述のようにＸ４（例えば、Ｘ４＝４）は定数である（ステップＳ２８８）。
【０１００】
制御部１３３はｉ＝ｎ＋ｕであるかを判定する（ステップＳ１８８）。ｉ＝ｎ＋ｕでない場合、制御部１３３はｉ＋１を新たなｉに設定（ｉ：＝ｉ＋１）し（ステップＳ１８９）、処理をステップＳ１７７に戻す。一方、ｉ＝ｎ＋ｕである場合、出力値生成部１３６はステップＳ１８６で得られたラベルＬｉ（ただしｉ∈｛ｎ＋１，…，ｎ＋ｕ｝）およびｍを入力としてラベル列μ＝（Ｌｎ＋ｕ−ｍ＋１，…，Ｌｎ＋ｕ）を得、通信部１３１１は、ラベル列μを復号装置１４に送信する（ステップＳ１９０）。
μ:=(Ln+u-m+1,...,Ln+u)
【０１０１】
＜復号装置１４の符号化処理＞
第１実施形態と同じである。
【０１０２】
＜本形態の特徴＞
本形態でも、回路秘匿処理において、各ゲートＧ（ｉ）について、ＫＡ１−ＫＡ０＝ＫＢ’１−ＫＢ’０＝ｄｉを満たす入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１が得られるように、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１の少なくとも何れかを設定し、入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を用い、出力値ｇｉ（Ｉ（Ａ），Ｉ（Ｂ））に対応する出力鍵Ｋｉｇ（Ｉ（Ａ），Ｉ（Ｂ））を設定した（ステップＳ１１０〜Ｓ１３０）。これにより、すべての入力鍵ＫＡ０，ＫＡ１，ＫＢ’０，ＫＢ’１を独立に生成する従来方式に比べて、秘匿回路Ｆのデータ量を削減できる。
【０１０３】
［その他の変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、回路秘匿装置と符号化装置とが別装置であるならば、回路秘匿装置、符号化装置、計算装置、および復号装置のうち複数の装置が一つの装置として構成されてもよい。また、上記の実施形態では、αを共通鍵としてβを暗号化（例えば、ステップＳ１１５）する方法として、αとβとの排他的論理和を計算する例を示した。しかし、ＡＥＳやカメリア（登録商標）などの共通鍵暗号方式に則り、αを共通鍵としてβを暗号化してもよい。また、「αを含む値の関数値」はαそのものであってもよいし、αの関数値であってもよいし、αと他の情報とを含む値の関数値であってもよい。例えば、ステップＳ１１５のＨ（ＫＢ１（ｘｏｒ）λ（Ｂ），ｊＥ）に代えて、ＫＢ１（ｘｏｒ）λ（Ｂ）そのものが用いられてもよいし、Ｈ（ＫＢ１（ｘｏｒ）λ（Ｂ））が用いられてもよい。また、「関数値」としてハッシュ値以外の単写な関数値（暗号文等）が用いられてもよい。
【０１０４】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１０６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１０８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１０９】
１，２  秘匿計算システム
１１，２１  回路秘匿装置
１２  符号化装置
１３，２３  計算装置
１４  復号装置
【図１】
0006629461.tif 000015
【図２】
0006629461.tif 000016
【図３】
0006629461.tif 000017
【図４】
0006629461.tif 000018
【図５】
0006629461.tif 000019
【図６】
0006629461.tif 000020
【図７】
0006629461.tif 000021
【図８】
0006629461.tif 000022
【図９】
0006629461.tif 000023
【図１０】
0006629461.tif 000024
【図１１】
0006629461.tif 000025
【図１２】
0006629461.tif 000026
【図１３】
0006629461.tif 000027
【図１４】
0006629461.tif 000028
【図１５】
0006629461.tif 000029
【図１６】
0006629461.tif 000030
【図１７】
0006629461.tif 000031
【図１８】
0006629461.tif 000032
【図１９】
0006629461.tif 000033
【図２０】
0006629461.tif 000034