(57)【要約】      （修正有）【課題】ｎ入力対称関数ゲートの秘匿回路の生成に必要な暗号文の数をｎ個程度に抑えた秘匿回路生成装置を提供する。【解決手段】秘匿回路生成部２１０は、ゲート入力鍵生成部２１１とゲート出力鍵生成部２１２と暗号文計算部２１３と暗号文置換部２１４とを含む。暗号文計算部２１３は、ゲート入力鍵の算術加算を用いてｎ入力対称関数ゲートの出力値ごとに異なる２ｋビットの暗号文をｎ＋１個生成し、暗号文置換部２１４はランダム置換を用いて暗号文の順序をランダムにすることにより秘匿回路を生成する。（ただし、ｎは２以上の整数、ｋはセキュリティパラメータ（鍵長））【選択図】図７
2018013608.tif 000002
【特許請求の範囲】
【請求項１】
第一秘匿計算装置と第二秘匿計算装置を含む秘匿計算システムであって、
ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
（ｘ１，…，ｘｍ）∈｛０，１｝ｍ（１≦ｍ＜ｎ）を前記第二秘匿計算装置に秘密である秘密情報、（ｘｍ＋１，…，ｘｎ）∈｛０，１｝ｎ−ｍを前記第一秘匿計算装置に秘密である秘密情報とし、
前記第一秘匿計算装置は、
ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成部と、
ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成部と、
ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算部と、
【数６】
2018013608.tif 000008
前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとして生成する暗号文置換部と、
を含み、
前記第二秘匿計算装置は、
前記秘密情報（ｘ１，…，ｘｍ）から生成した秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）∈Ｒｍと前記秘密情報（ｘｍ＋１，…，ｘｎ）から生成した秘匿化秘密情報（Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）∈Ｒｎ−ｍから生成した秘匿化入力値Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ，Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）と前記秘匿回路Ｆを用いて、ｉ＝０，１，…，ｎに対して、Ｋ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ、Ｌ∈｛０，１｝ｋ）を以下の式を用いて順次計算し、
【数７】
2018013608.tif 000009
Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）に対して、秘匿化出力値Ｙ＝Ｋｎ＋１，ｇ（ｉ＿０）を生成する秘匿回路評価部と
を含む秘匿計算システム。
【請求項２】
ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成部と、
ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成部と、
ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算部と、
【数８】
2018013608.tif 000010
前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとして生成する暗号文置換部と
を含む第一秘匿計算装置。
【請求項３】
ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
乱数Ｋｊ，０∈Ｒ、Ｋｊ，１：＝Ｋｊ，０＋Δ∈Ｒをゲート入力鍵（ｊ＝１，…，ｎ）、乱数Ｋｎ＋１，０∈Ｒ、Ｋｎ＋１，１：＝Ｋｎ＋１，０＋Δ∈Ｒをゲート出力鍵、
【数９】
2018013608.tif 000011
を暗号文Ｃｉ（ｉ＝０，…，ｎ）、前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとし、
ｘ＝（ｘ１，…，ｘｎ）∈｛０，１｝ｎを前記ｎ入力対称関数ゲートｇの入力値、Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）∈Ｒｎを前記入力値ｘから生成した秘匿化入力値とし、
前記秘匿化入力値Ｘと前記秘匿回路Ｆを用いて、ｉ＝０，１，…，ｎに対して、Ｋ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ、Ｌ∈｛０，１｝ｋ）を以下の式を用いて順次計算し、
【数１０】
2018013608.tif 000012
Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）に対して、秘匿化出力値Ｙ＝Ｋｎ＋１，ｇ（ｉ＿０）を生成する秘匿回路評価部と
を含む第二秘匿計算装置。
【請求項４】
ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋ＋１をハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成部と、
ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成部と、
ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算部と、
【数１１】
2018013608.tif 000013
前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとして生成する暗号文置換部と
を含む第一秘匿計算装置。
【請求項５】
ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋ＋１をハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
乱数Ｋｊ，０∈Ｒ、Ｋｊ，１：＝Ｋｊ，０＋Δ∈Ｒをゲート入力鍵（ｊ＝１，…，ｎ）、乱数Ｋｎ＋１，０∈Ｒ、Ｋｎ＋１，１：＝Ｋｎ＋１，０＋Δ∈Ｒをゲート出力鍵、
【数１２】
2018013608.tif 000014
を暗号文Ｃｉ（ｉ＝０，…，ｎ）、前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとし、
ｘ＝（ｘ１，…，ｘｎ）∈｛０，１｝ｎを前記ｎ入力対称関数ゲートｇの入力値、Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）∈Ｒｎを前記入力値ｘから生成した秘匿化入力値とし、
前記秘匿化入力値Ｘと前記秘匿回路Ｆを用いて、ｉ＝０，１，…，ｎに対して、Ｋ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ＋１、Ｌ∈｛０，１｝ｋ）を以下の式を用いて順次計算し、
【数１３】
2018013608.tif 000015
Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）に対して、秘匿化出力値Ｙ＝Ｋｎ＋１，ｇ（ｉ＿０）||ｇ（ｉ）を生成する秘匿回路評価部と
を含む第二秘匿計算装置。
【請求項６】
第一秘匿計算装置がｎ入力対称関数ゲートｇ：｛０，１｝ｎ→｛０，１｝（ただし、ｎは２以上の整数）の秘匿回路Ｆを生成する秘匿回路生成方法であって、
ｋをセキュリティパラメータ、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
前記第一秘匿計算装置が、ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成ステップと、
前記第一秘匿計算装置が、ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成ステップと、
前記第一秘匿計算装置が、ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算ステップと、
【数１４】
2018013608.tif 000016
前記第一秘匿計算装置が、前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記秘匿回路Ｆとして生成する暗号文置換ステップと
を含む秘匿回路生成方法。
【請求項７】
第二秘匿計算装置がｎ入力対称関数ゲートｇ：｛０，１｝ｎ→｛０，１｝（ただし、ｎは２以上の整数）の秘匿回路Ｆを評価する秘匿回路評価方法であって、
ｋをセキュリティパラメータ、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、
乱数Ｋｊ，０∈Ｒ、Ｋｊ，１：＝Ｋｊ，０＋Δ∈Ｒをゲート入力鍵（ｊ＝１，…，ｎ）、乱数Ｋｎ＋１，０∈Ｒ、Ｋｎ＋１，１：＝Ｋｎ＋１，０＋Δ∈Ｒをゲート出力鍵、
【数１５】
2018013608.tif 000017
を暗号文Ｃｉ（ｉ＝０，…，ｎ）、前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記秘匿回路Ｆとし、
ｘ＝（ｘ１，…，ｘｎ）∈｛０，１｝ｎを前記ｎ入力対称関数ゲートｇの入力値、Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）∈Ｒｎを前記入力値ｘから生成した秘匿化入力値とし、
前記第二秘匿計算装置が、前記秘匿化入力値Ｘと前記秘匿回路Ｆを用いて、ｉ＝０，１，…，ｎに対して、Ｋ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ、Ｌ∈｛０，１｝ｋ）を以下の式を用いて順次計算し、
【数１６】
2018013608.tif 000018
Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）に対して、秘匿化出力値Ｙ＝Ｋｎ＋１，ｇ（ｉ＿０）を生成する秘匿回路評価ステップと
を含む秘匿回路評価方法。
【請求項８】
請求項２もしくは請求項４に記載の第一秘匿計算装置、または請求項３もしくは請求項５に記載の第二秘匿計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関するものであり、特に２者間で秘密情報を秘匿して計算を行う秘匿回路を用いた２パーティ計算方式に関する。
【背景技術】
【０００２】
秘匿回路を用いた２パーティ計算方式の従来技術として、非特許文献１に記載の技術がある。この方式では、任意のｎ入力関数ゲートの秘匿回路を実現することができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams, ”Secure Two-Party Computation Is Practical”, In M. Matsui, editor, ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 250-267, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１に記載の方式を用いると、ｎ入力ＡＮＤゲートを実現するためにも、ｋビット（ただし、ｋはセキュリティパラメータ(鍵長)）の暗号文を２ｎ個（入力値のパターンの数）生成する必要があり、暗号文の数をｎ個程度に抑えつつ、ｎ入力ＡＮＤゲートなどのｎ入力対称関数ゲートを実現する秘匿回路を用いた２パーティ計算方式はなかった。ｎ入力対称関数ゲートとは、入力の１の数ごとに値が決まるｎ入力関数ゲートのことである。
【０００５】
ｎ入力対称関数ゲートを用いると、ｎ入力閾値ゲートを実現することができる。ｎ入力閾値ゲートは、ｎ入力ＡＮＤゲート、ｎ入力ＯＲゲート、ｎ入力多数決ゲートなどを含む非常に重要なゲートのクラスである。
【０００６】
そこで本発明では、暗号文の数をｎ個程度に抑えた対称関数ゲートの秘匿回路を生成する装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様は、ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成部と、ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成部と、ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算部と、
【０００８】
【数１】
2018013608.tif 000003
【０００９】
前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとして生成する暗号文置換部とを含む。
【００１０】
本発明の一態様は、ｋをセキュリティパラメータ、ｇ：｛０，１｝ｎ→｛０，１｝をｎ入力対称関数ゲート（ただし、ｎは２以上の整数）、ｇ（ｉ）（ただし、０≦ｉ≦ｎ）を前記ｎ入力対称関数ゲートｇの入力値ｘ∈｛０，１｝ｎに含まれる１の数がｉであるときの出力値ｇ（ｘ）の値、Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）、Δ∈Ｒを乱数、Ｈ：｛０，１｝＊→｛０，１｝２ｋ＋１をハッシュ関数、π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とし、ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとするゲート入力鍵生成部と、ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとするゲート出力鍵生成部と、ｉ＝０，…，ｎに対して、以下の式を用いて暗号文Ｃｉを計算する暗号文計算部と、
【００１１】
【数２】
2018013608.tif 000004
【００１２】
前記ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）から前記ランダム置換πを用いて置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を前記ｎ入力対称関数ゲートｇの秘匿回路Ｆとして生成する暗号文置換部とを含む。
【発明の効果】
【００１３】
本発明によれば、鍵の算術加算を用いて入力の１の数ごとに異なる２ｋビットの暗号文をｎ＋１個生成することにより、ｎ入力対称関数ゲートの秘匿回路を生成することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】秘匿化出力値Ｙと出力値ｙの対応関係を表す対応表の一例を示す図。
【図２】秘匿計算システム１００の構成を示すブロック図。
【図３】第一秘匿計算装置２００の構成を示すブロック図。
【図４】第二秘匿計算装置３００の構成を示すブロック図。
【図５】第一秘匿計算装置２００の動作を示すフローチャート。
【図６】第二秘匿計算装置３００の動作を示すフローチャート。
【図７】秘匿回路生成部２１０の構成を示すブロック図。
【図８】秘匿回路生成部２１０の動作を示すフローチャート。
【図９】秘密情報秘匿化部２２０の構成を示すブロック図。
【図１０】秘密情報秘匿化部２２０の動作を示すフローチャート。
【図１１】秘密情報秘匿化部３１０の構成を示すブロック図。
【図１２】秘密情報秘匿化部３１０の動作を示すフローチャート。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１６】
＜記法＞
^（キャレット）は上付き添字を表す。例えば、xy^zはyzがxに対する上付き添字であり、xy^zはyzがxに対する下付き添字であることを表す。また、_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００１７】
＜実施形態１＞
ｇ：｛０，１｝ｎ→｛０，１｝を、入力の１の数ごとに値が決まるｎ入力対称関数ゲートとする（ただし、ｎは２以上の整数）。
入力ｘ＝（ｘ１，…，ｘｎ）∈｛０，１｝ｎの１の数をＮ（ｘ）＝＃｛ｊ｜ｘｊ＝1（１≦ｊ≦ｎ）｝と表すことにする。また、ｉ＝Ｎ（ｘ）であるとき、ｇ（ｘ）の値をｇ（ｉ）と表すことにする。
Ｈ：｛０，１｝＊→｛０，１｝２ｋをハッシュ関数とする。
π：｛０，１，…，ｎ｝→｛０，１，…，ｎ｝をランダムに選択したｎ＋１次の置換群の元（以下、ランダム置換という）とする。
Ｒ（⊆｛０，１｝ｋ）を整数ｐを法とする剰余類環Ｚｐまたは有限体Ｆｑ＾ｄ（ただし、ｑは素数、ｄは自然数）とする。
【００１８】
秘匿回路生成アルゴリズム（garbling algorithm）、秘匿化入力値生成アルゴリズム（encoding algorithm）、秘匿回路評価アルゴリズム（evaluation algorithm）によって、それぞれ対称関数ゲートｇの秘匿計算を行う秘匿回路Ｆの生成、対称関数ゲートｇへの入力値ｘを秘匿化した秘匿化入力値Ｘの生成、秘匿化入力値Ｘから秘匿回路Ｆを用いて秘匿化出力値Ｙの計算を行う。
【００１９】
［秘匿回路生成アルゴリズム］
秘匿回路生成アルゴリズムＧａｒｂｌｅ（１ｋ,ｇ）はセキュリティパラメータｋ、ｎ入力対称関数ゲートｇ、秘密の乱数Δ∈Ｒを入力とし、ｎ入力対称関数ゲートｇの秘匿計算を行う秘匿回路Ｆ、ｎ入力対称関数ゲートｇへの入力値ｘを秘匿化するためのエンコーディング情報ｅを出力するものである。
【００２０】
なお、乱数ΔはＲからランダムに選択するのでよい。また、乱数Δが秘密であるとは、このアルゴリズムを実行するもの以外に知られてはいけないとの意味である。
【００２１】
以下、Ｒからランダムに選択する場合、一様ランダム、ランダム、疑似ランダムのいずれの方法で選択してもよい。
（ステップ１：初期化）
ここでは、ｎ入力対称関数ゲートｇを秘匿化した秘匿回路Ｆを暗号文の組として生成するために用いる鍵を生成する。
（ステップ１−１）
ゲート入力鍵Ｋｊ，０∈Ｒ（ｊ＝１，…，ｎ）をランダムに選択する。また、ゲート入力鍵Ｋｊ，１∈Ｒ（ｊ＝１，…，ｎ）をＫｊ，１：＝Ｋｊ，０＋Δとする。
（ステップ１−２）
ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択する。また、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとする。
【００２２】
（ステップ２：対称関数ゲートｇの秘匿化）
ここでは、ステップ１で生成した鍵を用いて、入力の１の数ごとに値が決まる対称関数ゲートの値ｇ（ｉ）を秘匿化した暗号文Ｃｉを生成する。
（ステップ２−１）
暗号文Ｃｉを以下の式（１）で計算する（ｉ＝０，１，…，ｎ）。
【００２３】
【数３】
2018013608.tif 000005
【００２４】
なお、Ｋｎ＋１，ｇ（ｉ）∈Ｒは、ｋビットのビット列として表現されている。
（ステップ２−２）
ｎ＋１個の暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）からランダム置換πを用いて（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を生成する。
【００２５】
ランダムに並び替えた暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を秘匿回路Ｆ、ｎ個のゲート入力鍵ペア（Ｋｊ，０，Ｋｊ，１）の組（（Ｋ１，０，Ｋ１，１），…，（Ｋｎ，０，Ｋｎ，１））をエンコーディング情報ｅとする。すなわち、秘匿回路Ｆ：＝（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））、エンコーディング情報ｅ：＝（（Ｋ１，０，Ｋ１，１），…，（Ｋｎ，０，Ｋｎ，１））とし、秘匿回路Ｆとエンコーディング情報ｅを出力する。
【００２６】
［秘匿化入力値生成アルゴリズム］
秘匿化入力値生成アルゴリズムＥｎｃｏｄｅ（ｅ，ｘ）は、エンコーディング情報ｅ、ｎ入力対称関数ゲートｇへの入力値ｘ∈｛０，１｝ｎを入力として、秘匿化入力値Ｘ∈Ｒｎを出力するものである。
（ステップ１）
入力値ｘ∈｛０，１｝ｎに対して、ｘ＝（ｘ１，…，ｘｎ）とする。このとき、入力値ｘの第ｊ要素ｘｊ（ｊ＝１，…，ｎ）は０または１となる。
（ステップ２）
ｊ＝１，…，ｎとし、エンコーディング情報ｅの第ｊ要素であるゲート入力鍵ペア（Ｋｊ，０，Ｋｊ，１）を用いて、秘匿化入力値Ｘの第ｊ要素ＸｊをＫｊ，ｘ＿ｊとする。つまり、Ｘｊ：＝Ｋｊ，ｘ＿ｊとする。
（ステップ３）
最後に、秘匿化入力値Ｘ：＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）として、秘匿化入力値Ｘ∈Ｒｎを出力する。
【００２７】
［秘匿回路評価アルゴリズム］
秘匿回路評価アルゴリズムＥｖａｌ（Ｆ，Ｘ）は秘匿回路Ｆ、秘匿化入力値Ｘ∈Ｒｎを入力として、秘匿化出力値Ｙ∈Ｒを出力するものである。秘匿化出力値Ｙ＝Ｆ（Ｘ）は、出力値ｙ＝ｇ（ｘ）∈｛０，１｝に対応するものである。
（ステップ１）
秘匿回路Ｆに対して、Ｆ＝（Ｆ０，Ｆ１，…，Ｆｎ）とする。このとき、秘匿回路Ｆの第ｉ要素ＦｉはＦｉ＝Ｃπ（ｉ）となる（ｉ＝０，１，…，ｎ）。
（ステップ２）
ｉ＝０，１，…，ｎに対して、秘匿化入力値Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）を用いて、Ｋ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ、Ｌ∈｛０，１｝ｋ）を以下の式（２）で順次計算する。
【００２８】
【数４】
2018013608.tif 000006
【００２９】
Ｌ＝０ｋとなるとき、すなわち式（２）の右辺で計算されるビット列中右側に０ｋが出現するとき、秘匿化出力値Ｙ：＝Ｋとし、秘匿化出力値Ｙ∈Ｒを出力する。
【００３０】
つまり、Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）が存在し、Ｋ＝Ｋｎ＋１，ｇ（ｉ＿０）となる。
【００３１】
なお、秘匿化出力値Ｙから出力値ｙを求めるためには、秘匿化出力値Ｙと出力値ｙの対応関係を表す対応表を用いる。対応表の例を図１に示す。この例は、Ｙ＝Ｋｎ＋１，０のとき、ｙ＝１、Ｙ＝Ｋｎ＋１，１のとき、ｙ＝０であることを示している。ただし、Δを秘匿するために、Ｋｎ＋１，０、Ｋｎ＋１，１ともランダムに生成する。この対応表を用いてＹの値に応じてｙの値（０か１）が決定される。
【００３２】
＜変形例＞
上記実施形態では、対応表を用いて出力値ｙを求めるようにしたが、式（２）を計算するときに出力値ｙ＝ｇ（ｉ）を算出できるようにしてもよい。以下、その方法について説明する。
ハッシュ関数ＨをＨ：｛０，１｝＊→｛０，１｝２ｋ＋１とする。つまり、値域を２ｋ＋１ビット列となるように変更する。
【００３３】
また、秘匿回路生成アルゴリズムＧａｒｂｌｅ（１ｋ,ｇ）の（ステップ２−１）を以下のように変更する。
（ステップ２−１）
暗号文Ｃｉを以下の式（１’）で計算する（ｉ＝０，１，…，ｎ）。
【００３４】
【数５】
2018013608.tif 000007
【００３５】
このようにすると、秘匿回路評価アルゴリズムＥｖａｌ（Ｆ，Ｘ）の（ステップ２）でＫ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ＋１、Ｌ∈｛０，１｝ｋ）を式（２）で順次計算すると、Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）が存在し、Ｋ＝Ｋｎ＋１，ｇ（ｉ＿０）||ｇ（ｉ）となる。このようにして得られたＫを秘匿化出力値Ｙ∈｛０，１｝ｋ＋１とし、Ｋの最も右のビットｇ（ｉ）を出力値ｙとするとよい。
【００３６】
＜応用例＞
また、（入力を上、出力を下として）複数の対称関数ゲートを多段に組み合わせて、新たな関数ゲート（以下、多段関数ゲートという）を構成することもできる。この場合、各対称関数ゲートに対して、前のゲート出力鍵をゲート入力鍵として、秘匿回路を生成する。また、秘匿回路の評価を実行する処理を最上段から最下段に向けて繰り返し実行していくことで、多段関数ゲートの出力値を計算することができる。その際、最下段の対称関数ゲート以外の出力値は秘匿化したまま扱う。そして、最下段における秘匿化出力値と出力値の対応表のみを用意することにより、もしくは上記変形例を用いることにより、最終的な出力値（多段関数ゲートの出力値）のみを求めることができる。
【００３７】
［秘匿計算システム１００の構成及び動作］
以下、図２〜図６を参照して秘匿計算システム１００について説明する。秘匿計算システム１００は上記３つのアルゴリズム（秘匿回路生成アルゴリズム、秘匿化入力値生成アルゴリズム、秘匿回路評価アルゴリズム）を用いて構成され、動作するものである。
【００３８】
図２は、秘匿計算システム１００の構成を示すブロック図である。図３は、第一秘匿計算装置２００の構成を示すブロック図である。図４は、第二秘匿計算装置３００の構成を示すブロック図である。図５は、第一秘匿計算装置２００の動作を示すフローチャートである。図６は、第二秘匿計算装置３００の動作を示すフローチャートである。
【００３９】
図２に示すように、秘匿計算システム１００は、第一秘匿計算装置２００と、第二秘匿計算装置３００を含む。第一秘匿計算装置２００、第二秘匿計算装置３００の各装置はネットワーク８００（例：インターネット）に接続しており、相互に通信することが可能である。図３に示すように、第一秘匿計算装置２００は、秘匿回路生成部２１０と、秘密情報秘匿化部２２０と、通信部２８０と、秘匿回路生成用情報記録部２９０を含む。図４に示すように、第二秘匿計算装置３００は、秘密情報秘匿化部３１０と、秘匿化入力値生成部３２０と、秘匿回路評価部３３０と、出力値生成部３４０と、通信部３８０と、秘匿回路評価用情報記録部３９０と、対応表記録部３９５を含む。
【００４０】
第一秘匿計算装置２００は、ｎ入力対称関数ゲートｇを秘匿化した秘匿回路Ｆと秘密情報（ｘ１，…，ｘｍ）（１≦ｍ＜ｎ）を秘匿化した秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）を生成する。ｘｊ∈｛０，１｝（１≦ｊ≦ｍ）であり、秘密情報（ｘ１，…，ｘｍ）はｎ入力対称関数ゲートｇの入力値の一部となる。
【００４１】
第二秘匿計算装置３００は、第一秘匿計算装置２００から受信した秘匿回路Ｆと秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）、秘密情報（ｘｍ＋１，…，ｘｎ）を用いて秘匿化出力値Ｙを生成する。ｘｊ∈｛０，１｝（ｍ＋１≦ｊ≦ｎ）であり、秘密情報（ｘｍ＋１，…，ｘｎ）はｎ入力対称関数ゲートｇの入力値の一部となる。
【００４２】
秘密情報（ｘ１，…，ｘｍ）とは、この情報が第二秘匿計算装置３００に対して秘密であるという意味であり、秘密情報（ｘｍ＋１，…，ｘｎ）とは、この情報が第一秘匿計算装置２００に対して秘密であるという意味である。また、秘密情報（ｘ１，…，ｘｍ）と秘密情報（ｘｍ＋１，…，ｘｎ）を結合したビット列ｘ＝（ｘ１，…，ｘｍ，ｘｍ＋１，…，ｘｎ）がｎ入力対称関数ゲートｇの入力値ｘとなる。
【００４３】
秘匿回路生成用情報記録部２９０には、秘匿回路生成部２１０が秘匿回路Ｆの生成に用いるハッシュ関数Ｈとランダム置換πが記録されている。また、秘匿回路評価用情報記録部３９０には、秘匿回路評価部３３０が秘匿化出力値Ｙを計算する、つまり秘匿回路Ｆを用いて秘匿化入力値Ｘを評価するために用いるハッシュ関数Ｈが記録されている。秘匿回路生成用情報記録部２９０に記録されているハッシュ関数Ｈと秘匿回路評価用情報記録部３９０に記録されているハッシュ関数Ｈは、同一のものである。
【００４４】
さらに、対応表記録部３９５には、出力値生成部３４０が秘匿化出力値Ｙから出力値ｙを求めるために用いる対応表Ｔが記録されている。この対応表Ｔは、秘匿回路生成部２１０が秘匿回路Ｆを生成する際に生成するゲート出力鍵ペア（Ｋｎ＋１，０，Ｋｎ＋１，１）を用いて表現されるものであり、出力値生成部３４０の実行前までに第二秘匿計算装置３００に送信されるものである。
【００４５】
第一秘匿計算装置２００には、セキュリティパラメータｋ、ｎ入力対称関数ゲートｇ、第二秘匿計算装置３００に秘密の乱数Δ∈Ｒ、第二秘匿計算装置３００に秘密のビット列である秘密情報（ｘ１，…，ｘｍ）（１≦ｍ＜ｎ）が入力される。
【００４６】
秘匿回路生成部２１０は、セキュリティパラメータｋ、対称関数ゲートｇ、乱数Δから、秘匿回路生成アルゴリズムＧａｒｂｌｅ（１ｋ,ｇ）を用いて、秘匿回路Ｆ、秘密情報（ｘ１，…，ｘｍ）と秘密情報（ｘｍ＋１，…，ｘｎ）を秘匿化するためのエンコーディング情報ｅを生成する（Ｓ２１０）。図７、図８を参照して詳細に説明する。ゲート入力鍵生成部２１１は、ｊ＝１，…，ｎに対して、ゲート入力鍵Ｋｊ，０∈Ｒをランダムに選択し、ゲート入力鍵Ｋｊ，１∈ＲをＫｊ，１：＝Ｋｊ，０＋Δとする（Ｓ２１１）。ゲート出力鍵生成部２１２は、ゲート出力鍵Ｋｎ＋１，０∈Ｒをランダムに選択し、ゲート出力鍵Ｋｎ＋１，１∈ＲをＫｎ＋１，１：＝Ｋｎ＋１，０＋Δとする（Ｓ２１２）。暗号文計算部２１３は、秘匿回路生成用情報記録部２９０に記録しているハッシュ関数Ｈを用いて、秘匿回路Ｆを構成する暗号文Ｃｉ（ｉ＝０，１，…，ｎ）を式（１）に基づいて計算する（Ｓ２１３）。暗号文置換部２１４は、秘匿回路生成用情報記録部２９０に記録しているランダム置換πを用いて、暗号文の組（Ｃ０，Ｃ１，…，Ｃｎ）からランダム置換した暗号文の組（Ｃπ（０），Ｃπ（１），…，Ｃπ（ｎ））を秘匿回路Ｆとして生成する（Ｓ２１４）。エンコーディング情報生成部２１５は、ｎ個のゲート入力鍵ペア（Ｋｊ，０，Ｋｊ，１）から、エンコーディング情報ｅ：＝（（Ｋ１，０，Ｋ１，１），…，（Ｋｎ，０，Ｋｎ，１））を生成する（Ｓ２１５）。
【００４７】
秘密情報秘匿化部２２０は、秘密情報（ｘ１，…，ｘｍ）から、秘匿化入力値生成アルゴリズムＥｎｃｏｄｅ（ｅ，ｘ）を用いて、秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）を生成する（Ｓ２２０）。図９、図１０を参照して詳細に説明する。秘匿化ビット生成部２２１は、秘密情報（ｘ１，…，ｘｍ）の第ｊ要素ｘｊ（ｊ＝１，…，ｍ）から、エンコーディング情報ｅの第ｊ要素であるゲート入力鍵ペア（Ｋｊ，０，Ｋｊ，１）を用いて、ｘｊを秘匿化した秘匿化ビットＫｊ，ｘ＿ｊを生成する（Ｓ２２１）。秘匿化ビット結合部２２２は、秘匿化ビットＫｊ，ｘ＿ｊ（ｊ＝１，…，ｍ）から秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）∈Ｒｍを生成する（Ｓ２２２）。
【００４８】
通信部２８０は、秘匿回路Ｆ、秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）を第二秘匿計算装置３００に送信する（Ｓ２８０）。このとき、対応表Ｔをあわせて送信してもよいし、別途送信してもよい。
【００４９】
第二秘匿計算装置３００には、第一秘匿計算装置２００に秘密のビット列である秘密情報（ｘｍ＋１，…，ｘｎ）が入力される。また、第一秘匿計算装置２００が送信した秘匿回路Ｆ、秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）、対応表Ｔも入力される。
【００５０】
通信部３８０は、秘匿回路Ｆ、秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）を受信する（Ｓ３８０）。
【００５１】
秘密情報秘匿化部３１０は、秘密情報（ｘｍ＋１，…，ｘｎ）から秘匿化秘密情報（Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）を生成する（Ｓ３１０）。図１１、図１２を参照して詳細に説明する。秘匿化ビット生成部３１１は、参考非特許文献１に記載の紛失通信（oblivious transfer）を用いて、秘密情報（ｘｍ＋１，…，ｘｎ）の第ｊ要素ｘｊ（ｍ＋１≦ｊ≦ｎ）から秘匿化ビットＫｊ，ｘ＿ｊを生成する（Ｓ３１１）。
（参考非特許文献１： Mihir Bellare, Silvio Micali,”Non-Interactive Oblivious Transfer and Applications”, Advances in Cryptology - CRYPTO’89 Proceedings, Volume 435 of the series Lecture Notes in Computer Science, pp.547-557, 1990.）
秘匿化ビット結合部３１２は、秘匿化ビットＫｊ，ｘ＿ｊ（ｍ＋１≦ｊ≦ｎ）から秘匿化秘密情報（Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）∈Ｒｎ−ｍを生成する（Ｓ３１２）。
【００５２】
秘匿化入力値生成部３２０は、２つの秘匿化秘密情報（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ）、（Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）を結合して秘匿化入力値Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｍ，ｘ＿ｍ，Ｋｍ＋１，ｘ＿ｍ＋１，…，Ｋｎ，ｘ＿ｎ）を生成する（Ｓ３２０）。
【００５３】
秘匿回路評価部３３０は、秘匿回路Ｆ、秘匿化入力値Ｘから、秘匿回路評価アルゴリズムＥｖａｌ（Ｆ，Ｘ）を用いて、秘匿化出力値Ｙを生成する（Ｓ３３０）具体的には、秘匿回路評価用情報記録部３９０に記録しているハッシュ関数Ｈと秘匿化入力値Ｘ＝（Ｋ１，ｘ＿１，…，Ｋｎ，ｘ＿ｎ）を用いて、秘匿回路Ｆの第ｉ要素Ｆｉ＝Ｃπ（ｉ）（ｉ＝０，１，…，ｎ）についてＫ||Ｌ（ただし、Ｋ∈｛０，１｝ｋ、Ｌ∈｛０，１｝ｋ）を式（２）に基づいて順次計算し、Ｌ＝０ｋとなるｉ０（０≦ｉ０≦ｎ）を検出し、Ｙ＝Ｋｎ＋１，ｇ（ｉ＿０）として秘匿化出力値Ｙを生成する。
【００５４】
出力値生成部３４０は、対応表記録部３９５に記録した対応表Ｔを用いて、秘匿化出力値Ｙから出力値ｙを生成する（Ｓ３４０）。出力値ｙはｙ＝ｇ（ｘ１，…，ｘｍ，ｘｍ＋１，…，ｘｎ）を満たす。
【００５５】
なお、最終的な出力値ｙは、第二秘匿計算装置３００が生成するのでなくてもよい。この場合、第二秘匿計算装置３００は出力値生成部３４０と対応表記録部３９５を含まない構成となり、出力値生成部３４０と対応表記録部３９５は第三の装置が持つように構成すればよい。
【００５６】
また、＜変形例＞の場合、第二秘匿計算装置３００には、対応表記録部３９５は不要であり、第一秘匿計算装置２００と第二秘匿計算装置３００の間での対応表の送受信も不要である。
【００５７】
本実施形態の発明によれば、ｎ＋１個の２ｋビット長暗号文Ｃ０，…，Ｃｎを用いて、ｎ入力対称関数ゲートの秘匿回路を生成することができる。
【００５８】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００５９】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００６０】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【００６１】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００６２】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００６３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６７】
１００  秘匿計算システム
２００  第一秘匿計算装置
２１０  秘匿回路生成部
２１１  ゲート入力鍵生成部
２１２  ゲート出力鍵生成部
２１３  暗号文計算部
２１４  暗号文置換部
２１５  エンコーディング情報生成部
２２０  秘密情報秘匿化部
２２１  秘匿化ビット生成部
２２２  秘匿化ビット結合部
２８０  通信部
２９０  秘匿回路生成用情報記録部
３００  第二秘匿計算装置
３１０  秘密情報秘匿化部
３１１  秘匿化ビット生成部
３１２  秘匿化ビット結合部
３２０  秘匿化入力値生成部
３３０  秘匿回路評価部
３４０  出力値生成部
３８０  通信部
３９０  秘匿回路評価用情報記録部
３９５  対応表記録部
【図１】
2018013608.tif 000019
【図２】
2018013608.tif 000020
【図３】
2018013608.tif 000021
【図４】
2018013608.tif 000022
【図５】
2018013608.tif 000023
【図６】
2018013608.tif 000024
【図７】
2018013608.tif 000025
【図８】
2018013608.tif 000026
【図９】
2018013608.tif 000027
【図１０】
2018013608.tif 000028
【図１１】
2018013608.tif 000029
【図１２】
2018013608.tif 000030