(57)【要約】【課題】関数への入力値を知ることなく、処理時間の削減を可能にする排他的論理和の秘密計算方法をを提供する。【解決手段】楕円曲線の有理点群をＧ,ＰをＧの元、Ｇの位数をＰとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とする。ａの暗号関数ＥをＥ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒｐ,（ｒ＋ａ）Ｑ）と定義する。制御装置はａ,ｂの暗号文（Ａ,Ｂ）,（Ｘ,Ｙ）を入力し、（Ａ,Ｂ），（Ｘ,Ｙ）を暗号文変換装置に送る。暗号文変換装置は（Ａ,Ｂ），（Ｘ,Ｙ）の暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を計算し、（Ａ′,Ｂ′）を各復号装置に送り、（Ｘ′,Ｙ′）を制御装置に送る。各復号装置はｘｉＡ′を計算し、制御装置に送る。制御装置はｘＡ′を計算し、（Ａ′,Ｂ′）の復号結果について、（Ｘ′,Ｙ′）を用いて暗号文（Ｃ,Ｄ）を計算し、（Ｃ,Ｄ）をａ＋ｂ（排他的論理和）の暗号文と認識する。【選択図】図３
2006227563.tif 000002
【特許請求の範囲】
【請求項１】
ある有限体上で定義された楕円曲線の有理点からなる群をＧとし、ＰをＧの元とし、Ｐの位数をｐとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とし、
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅが
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
と定義され（ｒは１以上ｐ以下の乱数）、
ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））から、ａ,ｂを知ることなく、ａ＊ｂ（＊は排他的論理和を意味するとする。以下、同様）の暗号文を計算する秘密計算方法であって、
ネットワークで結ばれた、一つあるいは複数の暗号文生成装置、制御装置、暗号文変換装置および複数の復号装置を備え、
制御装置は、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））を暗号文生成装置から入力して、これらＥ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ,ｓ）（＝（Ｘ,Ｙ））を暗号文変換装置に送信し、
暗号文変換装置は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ,ｓ）（＝（Ｘ,Ｙ））を入力として、ランダムビットｅおよび１以上ｐ以下の乱数ｔ，ｕを生成し、暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を
【数１】
2006227563.tif 000017
により計算して、暗号文（Ａ′,Ｂ′）を各復号装置ｉ（ｉ＝１,２,…）に送信し、暗号文（Ｘ′,Ｙ′）を制御装置に送信し、
各復号装置ｉ（ｉ＝１,２,…）は、（Ａ′,Ｂ′）を入力とし、ｘiＡ′（ｘiは乱数）を計算して、それを制御装置に送信し、
制御装置は、ｘＡ′＝ｘ1Ａ′＋ｘ2Ａ′＋…を計算し、ｘＡ′＝Ｂ′であれば（Ａ′,Ｂ′）の復号結果ｃを“０”、それ以外（ｘＡ′＝Ｂ′−Ｑ）であれば“１”として、該復号結果ｃ∈｛０,１｝について、暗号文（Ｃ,Ｄ）を、
【数２】
2006227563.tif 000018
により計算して（ｗは１以上ｐ以下の乱数）、該暗号文（Ｃ,Ｄ）をａ＊ｂの暗号文として出力することを特徴とする秘密計算方法。
【請求項２】
ある有限体上で定義された楕円曲線の有理点からなる群をＧとし、ＰをＧの元とし、Ｐの位数をｐとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とし、
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅが
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ
と定義され（ｒは１以上ｐ以下の乱数）、
ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））から、ａ,ｂを知ることなく、ａ＊ｂの暗号文を計算する秘密計算方法であって、
ネットワークで結ばれた、一つあるいは複数の暗号文生成装置、制御装置、複数の暗号文変換装置、複数の復号装置および検証装置を備え、
制御装置は、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））を暗号文生成装置から入力して、これらＥ（ａ,ｒ）（＝（Ａ,Ｂ））を第１の暗号文変換装置に送信し、
第１の暗号文変換装置は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ,ｓ）（＝（Ｘ,Ｙ））を入力として、ランダムビットｅ1および１以上ｐ以下の乱数ｔ1,ｕ1を生成し、暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を
【数３】
2006227563.tif 000019
により計算して、該暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を第２の暗号文変換装置および検証装置に送信し、且つ、該暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）が［数３］の関係を満たしていることを検証装置に証明し、
検証装置は、第１の暗号文変換装置の処理正当性を検証して、その結果を第２の暗号文変換装置に通知し、
第２の暗号文変換装置は、検証装置から第１の暗号文変換装置の処理正当の通知を受けると、暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を入力として、ランダムビットｅ2および１以上ｐ以下の乱数ｔ2,ｕ2を生成し、暗号文（Ａ″,Ｂ″），（Ｘ″,Ｙ″）を、
【数４】
2006227563.tif 000020
により計算して、（Ａ″,Ｂ″）を各復号装置ｉ（ｉ＝１,２,…）に送信し、（Ｘ″,Ｙ″）を制御装置に送信し、（Ａ″,Ｂ″）および（Ｘ″,Ｙ″）を検証装置に送信し、且つ、該暗号文（Ａ″,Ｂ″），（Ｘ″,Ｙ″）が［数４］の関係を満たしていることを検証装置に証明し、
検証装置は、第２の暗号文変換装置の処理正当性を検証して、その結果を各復号装置に通知し、
各復号装置ｉ（ｉ＝１,２,…）は、検証装置から第２の暗号文変換装置の処理正当の通知を受けると、（Ａ″,Ｂ″）を入力とし、ｘiＡ″（ｘiは乱数）を計算して、それを制御装置に送信し、且つ、ｘ1Ａ″が正しい計算結果であることを検証装置に証明し、
検証装置は、各復号装置の処理正当性を検証して、その結果を制御装置に通知し、
制御装置は、検証装置から全ての復号装置の処理正当の通知を受けると、ｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″＋…を計算し、ｘＡ″＝Ｂ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”として、該復号結果ｃ∈｛０,１｝について、暗号文（Ｃ,Ｄ）を、
【数５】
2006227563.tif 000021
により計算して、該暗号文（Ｃ,Ｄ）をａ＊ｂの暗号文として認識することを特徴とする秘密計算方法。
【請求項３】
請求項２記載の秘密計算方法において、
第１あるいは第２の暗号文変換装置を証明者、検証装置を検証者として、下記プロトコル１を用いて、（Ａ′,Ｂ′），（Ｘ′,Ｙ′）あるいは（Ａ″,Ｂ″），（Ｘ″,Ｙ″）が［数３］あるいは［数４］の関係を満たしていることをゼロ知識証明する、
［プロトコル１］
Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、あるいは、Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しいことを、ゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））
証明者の秘密情報：（ｅ,ｔ）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｃ1-eを生成する。
（ｂ）ＲP,e＝ｒＰ,ＲQ,e＝ｒＱ,ＲP,1-e＝ｒ′Ｐ-ｃ1-eＰ1-e,ＲQ,1-e＝ｒ′Ｑ-ｃ1-eＱ1-e,ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1）−ｃ1-e,ｚe＝ｒ＋ｃeｔ,ｚ1-e＝ｒ′を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ（ｚ0Ｐ−ｃ0Ｐ0‖ｚ0Ｑ−ｃ0Ｑ0‖ｚ1Ｐ−ｃ1Ｐ1‖ｚ1Ｑ−ｃ1Ｑ1）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
ことを特徴とする秘密計算方法。
【請求項４】
請求項２記載の秘密計算方法において、
復号装置を証明者、検証装置を検証者として、下記プロトコル２を用いて、ｘiＡ″が正しい計算結果であることをゼロ知識証明する、
［プロトコル２］
Ｐを底としたｘiＰの離散対数、およびＡ″を底としたｘiＡ″の離散対数が等しい（すなわち、ともにｘiとなる）ことを非対話で証明するプロトコル、
入力：（ｐ,（Ｕ0,Ｖ0）＝（Ｐ,ｘiＰ）,（Ｕ1,Ｖ1）＝（Ａ″,ｘiＡ″））
証明者の秘密情報：ｘi
１．証明者は以下に従ってｓ，ｚを計算し、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒを生成する。
（ｂ）Ｒ0＝ｒＵ0,Ｒ1＝ｒＵ1を計算する。
（ｃ）ｓ＝Ｈ（Ｕ0‖Ｖ0‖Ｕ1‖Ｖ1‖Ｒ0‖Ｒ1）を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
（ｄ）ｚ＝ｒ＋ｓｘiを計算する。
２．検証者はＲ0′＝ｚＵ0＋ｓＶ0，Ｒ1′＝ｚＵ1＋ｓＶ1を計算後、ｓ＝Ｈ（Ｕ0‖Ｖ0‖Ｕ1‖Ｖ1‖Ｒ0′‖Ｒ1′）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
ことを特徴とする秘密計算方法。
【請求項５】
請求項２記載の秘密計算方法において、
第１あるいは第２の暗号文変換装置を証明者、検証装置を検証者として、下記プロトコル３を用いて、（Ａ′,Ｂ′），（Ｘ′,Ｙ′）あるいは（Ａ″,Ｂ″），（Ｘ″,Ｙ″）が［数３］あるいは［数４］の関係を満たしていることをゼロ知識証明する、
［プロトコル３］
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、
または、
２．Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことを、ゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：Ｐe＝ｔＰ，Ｑe＝ｔＱ，Ｐe′＝ｔ′Ｐ，Ｑe′＝ｔ′Ｑとなる（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ0,ｚ1,ｚ0′,ｚ1′,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｒ″,ｒ″′,ｃ1-eを生成する。
（ｂ）Ｒp,e＝ｒＰ,ＲQ,e＝ｒＱ,Ｒp,1-e＝ｒ′Ｐ−ｃ1-eＰ1-e,ＲQ,1-e＝ｒ′Ｑ−ｃ1-eＱ1-e,Ｒ′P,e＝ｒ″Ｐ,Ｒ′Q,e＝ｒ″Ｑ,Ｒ′P,1-e＝ｒ″′Ｐ−ｃ1-eＰ1-e,Ｒ′Q,1-e＝ｒ″′Ｑ−ｃ1-eＱ1-e,
ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1‖Ｒ′P,0‖Ｒ′Q,0‖Ｒ′P,1‖Ｒ′Q,1）−ｃ1-e,
ｚe＝ｒ＋ｃeｔ,ｚ1-e＝ｒ′,ｚ′e＝ｒ″＋ｃeｔ′,ｚ′1-e＝ｒ″′
を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ（ｚ0Ｐ−ｃ0Ｐ0‖ｚ0Ｑ−ｃ0Ｑ0‖ｚ1Ｐ−ｃ1Ｐ1‖ｚ1Ｑ−ｃ1Ｑ1‖ｚ0′Ｐ−ｃ0Ｐ0′‖ｚ0′Ｑ−ｃ0Ｑ0′‖ｚ1′Ｐ−ｃ1Ｐ1′‖ｚ1′Ｑ−ｃ1Ｑ1′）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
ことを特徴とする秘密計算方法。
【請求項６】
請求項２記載の秘密計算方法において、
第１あるいは第２暗号文変換装置を証明者、検証装置を検証者として、下記プロトコル４を用いて、（Ａ′,Ｂ′），（Ｘ′,Ｙ′）あるいは（Ａ″,Ｂ″），（Ｘ″,Ｙ″）が［数３］あるいは［数４］の関係を満たしていることをゼロ知識証明する、
［プロトコル４］
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、
または、
２．Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことをゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：Ｐe＝ｔＰ，Ｑe＝ｔＱ，Ｐe′＝ｔ′Ｐ，Ｑe′＝ｔ′Ｑとなる（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｒ″,ｃ1-eを生成する。
（ｂ）ｄ＝Ｈ0（Ｐ‖Ｑ‖Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′），Ｒp,e＝ｒＰ,ＲQ,e＝ｒＱ,Ｒp,1-e＝ｒ′Ｐ−ｃ1-e（ｄＰ1-e＋Ｐ1-e′），ＲQ,1-e＝ｒ′Ｑ−ｃ1-e（ｄＱ1-e＋Ｑ1-e′），ｃe＝Ｈ1（Ｒp,0‖ＲQ,0‖Ｒp,1‖ＲQ,1）−ｃ1-e，ｚe＝ｒ＋ｃe（ｄｔ＋ｔ′），ｚ1-e＝ｒ′
を計算する。ここでＨ0，Ｈ1はハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ1（ｚ0Ｐ−ｃ0（ｄＰ0＋Ｐ0′）‖ｚ0Ｑ−ｃ0（ｄＱ0＋Ｑ0′）‖ｚ1Ｐ−ｃ1（ｄＰ1＋Ｐ1′）‖ｚ1Ｑ−ｃ1（ｄＱ1＋Ｑ1′））が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
ことを特徴とする秘密計算方法。
【請求項７】
請求項１乃至６いずれか１項に記載の秘密計算方法において、複数組の（Ａi,Ｂi）,（Ｘi,Ｙi）（ｉ＝１,２,…,ｎ）を順次入力して、複数組のａi＊ｂiの暗号文をパイプライン形式に順次計算することを特徴とする秘密計算方法。
【請求項８】
ネットワークで結ばれた、一つあるいは複数の暗号文生成装置、制御装置、複数の暗号文変換装置、複数の復号装置および検証装置を具備し、請求項１乃至７いずれか１項に記載の秘密計算方法を実施することを特徴とする秘密計算システム。
【請求項９】
請求項１乃至７記載の秘密計算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリテイの技術分野に関し、特に暗号技術を応用し、関数への入力値を知ることなく、当該関数の計算および出力結果の取得を可能とする技術に関する。
【背景技術】
【０００２】
従来、関数への入力値を知ることなく、当該関数の計算および出力結果の取得を可能とする手段としては、例えば、非特許文献１で提案されている技術（以降これをＳＴ04と略記する）がある。ＳＴO4を用いれば、ある（複数の）数値に対して、ある暗号アルゴリズムを用いて変換することで当該数値を秘匿し、当該変換された数値を入力として、ある複数の装置が計算に協力することで、入力の（元の）数値を漏らすことなく関数の出力結果を得ることができる。更に出力結果の正当性、すなわち各装置が正しい処理を行ったかどうかを検証することもできる。以降、関数への入力値を知ることなく、当該関数の計算および出力結果の取得が可能な方法を便宜上、秘密計算方法と呼ぶことにする。
【０００３】
ＳＴO4では、非特許文献１の中で明記している暗号アルゴリズムＥに対して、ａ，ｂ（ａ，ｂは０または１のどちらかであるとする）の暗号文Ｅ（ａ），Ｅ（ｂ）が与えられれば、ある複数の装置が計算に協力することで、ａ，ｂを知らなくともａ＋ｂの暗号文Ｅ（ａ＋ｂ）、および暗号文Ｅ（ａ＊ｂ）を求めることができる。便宜上、ここで「＊」は排他的論理和を意味するとする。「＋」は論理和である。また、例えば非特許文献２で提案されている分散復号技術を用いることで、一定数以上の装置が復号計算に協力した暗号文（例えばＥ（ａ＋ｂ）やＥ（ａ＊ｂ））に限り復号できる。
【０００４】
【非特許文献１】Ｂ．Ｓchoenmakers  and  Ｐ．Ｔuyls，“Ｐractical  Ｔwo‐Ｐarty  Ｃomputation  based  on  the  Ｃonditional  Ｇates，”ＡＳＩＡＣＲＹＰＴ  ２００４，Ｄec．２００４．
【非特許文献２】Ｔ.Ｒ.Ｐedersen,“Ａ  threshold  cryptosystem  without  a  trusted  party,”Ａdvances  in  Ｃrytology−ＥＵＲＯＣＲＹＰＴ  ’91,ＬＮＣＳ  ５４７，pp.５２２−５２６,Ｓpringer−Ｖerlag,１９９１.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
０または１からなる入力の数値が暗号化された状態のまま、当該数値の加算および排他的論理和の結果（の暗号文）を求めることができれば、当該数値の論理和（ＯＲ）および論理積（ＡＮＤ）の結果（の暗号文）を求めることができる。すなわち、理論的には、入力の数値が暗号化された状態のまま多くの関数を計算できることになる。この機能を秘密計算と呼ぶことにする。
【０００６】
秘密計算を実現する方式としては、上記のＳＴ０４がある。しかしながら、ＳＴ０４では、暗号文Ｅ（ａ），Ｅ（ｂ）からＥ（ａ＊ｂ）を計算するためには、一旦、Ｅ（ａ）をある変換規則に基づいてＥ（２ａ−１）に変換する必要があった。本発明の一番目の課題は、Ｅ（２ａ−１）への変換を不要とすることで計算時間を削減した秘密計算を実現することである。
【０００７】
また、ＳＴ０４は、処理の正当性をゼロ知識証明技術を用いて証明するために、参加者がある文字列を共有する必要があった。本発明の二番目の課題は、共有の必要性をなくすことで、ゼロ知識証明に要する計算時間、通信時間を削減できる秘密計算を実現することである。
【課題を解決するための手段】
【０００８】
Ｇをある有限体上で定義された楕円曲線の有理点からなる群とし、ＰをＧの元とする。Ｐの位数をｐとする。そして、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とする。
【０００９】
このとき、平文ａ（ａ∈｛０，１｝）を暗号化する暗号関数Ｅを次のように定義する。
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
ここでｒは１以上ｐ以下の乱数である。
【００１０】
復号処理はｘＡを計算すれば良く、これにより
【００１１】
【数１】
2006227563.tif 000003
が成り立つことから、秘密鍵ｘを用いることで容易にＥ（ａ,ｒ）を復号できる。するとａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ＋ｂの暗号文を求めることは容易である。すなわち、Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）＝（（ｒ＋ｓ）Ｐ,（ｒ＋ａ＋ｓ＋ｂ）Ｑ）が成り立つことから、この操作によりａ＋ｂの暗号文Ｅ（ａ＋ｂ,ｒ＋ｓ）＝Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）が得られる。
【００１２】
次に、ａ，ｂ∈｛０,１｝としてＥ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ＊ｂの暗号文を求める方法の概略を説明する。これが本発明の主要部分となる。なお、ａ＊ｂないしｂ＊ａは、ａ＝０のときｂ、ａ＝１のとき１−ｂと定義する。また、ａ，ｂ∈｛０，１｝の暗号文Ｅ（ａ，ｒ）（＝（Ａ，Ｂ），Ｅ（ｂ，ｓ）（＝（Ｘ，Ｙ）は制御装置へ事前に与えられているとする。
先ず、暗号文変換装置が制御装置より（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ）），Ｅ（ｂ，ｓ）（＝（Ｘ，Ｙ））を入力として以下の処理を行う。
１.ランダムビットｅおよび１以上ｐ以下の乱数ｔ，ｕを生成する。
２．以下に従って（Ａ′,Ｂ′），（Ｘ′，Ｙ′）を求め、（Ａ′,Ｂ′）を複数の復号装置に送信し、（Ｘ′，Ｙ′）を制御装置に送信する。
【００１３】
【数２】
2006227563.tif 000004
【００１４】
次に、複数の復号装置が（Ａ′,Ｂ′）を入力として分散復号を行い、その処理結果を制御装置に送信することで、制御装置は（Ａ′,Ｂ′）の復号結果ｃを得る。このときｃ＝ａ＊ｅが成り立つ。一方、（Ｘ′，Ｙ′）は平分ｂ＊ｅに対する暗号文となる。
【００１５】
制御装置は、当該復号結果ｃ∈｛０,１｝について以下の処理を行う。
１.１以上ｐ以下の乱数ｗを生成する。
２.以下に従って（Ｃ,Ｄ）を求める。
【００１６】
【数３】
2006227563.tif 000005
このとき（Ｃ，Ｄ）は平文（ａ＊ｅ）＊（ｂ＊ｅ）＝ａ＊ｂに対する暗号文となる。
上記の操作により制御装置はａ＊ｂの暗号文、すなわち（Ｃ,Ｄ）を得ることができる。
【発明の効果】
【００１７】
本発明の秘密計算によれば、（Ａ，Ｂ），（Ｘ，Ｙ）から（Ａ′,Ｂ′），（Ｘ′，Ｙ′）を計算する処理（これを［処理１］とする）、および（Ｃ，Ｄ）の計算（これを［処理２］とする）において、従来技術ＳＴ０４のように、Ｅ（ａ）をＥ（ａ′）（ａ′＝２ａ−１）とする変換を必要としないため、計算時間の削減が期待できる。また、ＳＴ０４では処理の正当性をゼロ知識証明する際、参加者がコミットメント文字列を共有する必要があったが、本発明においては、後述のようにその必要がない。そのため、ゼロ知識証明を要する計算時間、通信時間ともに削減が期待できる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施の形態について図面を用いて詳細に説明する。
【００１９】
［第１の実施の形態］
第１の実施の形態におけるシステム構成は、図１に示すように、同一のネットワーク１００で結ばれた、１０の暗号文生成装置１,…,Ｎ（Ｎは適当な自然数）、制御装置２０、暗号文変換装置３０、および４０の復号装置１,２からなる。ここで復号装置を複数に設定しているのは、復号装置が単一であれば、当該復号装置は入力の数値の暗号文も復号できる権限を持つことになり、明らかに本発明が取り上げている課題を解決できないが、本実施の形態のように復号装置を複数に設定すれば、分散復号技術を用いて、それら復号装置が結託しない限りは入力の数値を知ることが困難とできるためである。なお、本実施の形態では、簡単に復号装置の数は２としたが、一般に２以上いくつでもよい。
【００２０】
はじめに本発明で用いる暗号方式について、図２の処理シーケンス図を参照して説明する。
制御装置２０は、有限体および楕円曲線を生成するためのパラメータを与えることで有限体および楕円曲線をそれぞれ一つずつ決定し（Ｓ１０１）、更に当該有限体上で定義された当該楕円曲線の有理点からなる群Ｇを決定する（Ｓ１０２）。また、Ｇの元を一つ選び、これをＰとする（Ｓ１０３）。次に、Ｐの位数ｐを計算する（Ｓ１０４）。そして、（Ｇ,ｐ,Ｐ）の組を復号装置４０（ｉ）（ｉ＝１,２）に送信する。
【００２１】
復号装置４０（ｉ）は、（Ｇ,ｐ,Ｐ）を入力として、１以上ｐ以下の乱数ｘiを生成後、Ｑi＝ｘiＰを計算し、Ｑiを制御装置２０に送信する（Ｓ１０５〜Ｓ１０８）。ここでは、復号装置４０（１）は乱数ｘ1を生成し（Ｓ１０５）、Ｑ1＝ｘ1Ｐを計算して（Ｓ１０６）、当該Ｑ1を制御装置２０に送信し、また、復号装置４０（２）は乱数ｘ2を生成し（Ｓ１０７）、Ｑ2＝ｘ2Ｐを計算して（Ｓ１０８）、Ｑ２を制御装置２０に送信する。
【００２２】
制御装置２０は、Ｑ＝Ｑ1＋Ｑ2を計算し（Ｓ１０９）、（Ｇ,ｐ,Ｐ,Ｑ）を公開する（Ｓ１１０）。
【００２３】
以上の準備の下、先ず本発明で用いる暗号化処理について説明する。
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅを
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
と定義する。ここでｒは１以上ｐ以下の乱数である。
【００２４】
次に復号処理について説明する。
いま、ｘ＝ｘ1＋ｘ2とおくと、ｘＡを計算すればＥ（ａ,ｒ）を復号できる。すなわち、
【００２５】
【数４】
2006227563.tif 000006
が成り立つことから、ｘＡ＝Ｂであれば復号結果を“０”とし、ｘＡ＝Ｂ−Ｑであれば“１”とする。なお当該計算に関わる装置が全て正しい処理を行えばｘＡ＝ＢまたはｘＡ＝Ｂ−Ｑの何れかが成り立つことは明らかである。したがって秘密鍵ｘを用いることで容易にＥ（ａ,ｒ）を復号できる。ただし実際の復号手順としては、復号装置ｉ（ｉ＝１,２）がｘiＡを計算、公開し、その後、制御装置２０がｘＡ＝ｘ1Ａ＋ｘ2Ａを求め、復号結果を得ることになる。
【００２６】
次に具体的な秘密計算方法として、基本論理ゲート（ＮＯＴ,ＡＮＤ,ＯＲ,ＮＡＮＤ,ＮＯＲ）に対する秘密計算方法の手順について説明する。ここで基本論理ゲートヘの入力となるａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）は、上記の暗号化処理方法を用いて暗号文生成装置１０（１）,…,（Ｎ）の何れかによって生成されたものであり、当該暗号文は制御装置２０へ事前に与えられていると仮定する。なおここではどの暗号文生成装置１０がＥ（ａ,ｒ）,Ｅ（ｂ,ｓ）を生成したかについては言及しないが、実際、当該二つの暗号文は同一の装置によって生成される必要はなく、一般に用途によって異なると考えられる。
【００２７】
基本論理ゲート（ＮＯＴ、ＡＮＤ,ＯＲ、ＮＡＮＤ,ＮＯＲ）を表す論理関数は、排他的論理和（＊）、加減算、および定数倍を用いてそれぞれ以下とできる。
【００２８】
【数５】
2006227563.tif 000007
【００２９】
先ずＮＯＴの処理について説明する。この処理は単純で、制御装置２０は,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、１−ａの暗号文（Ａ′,Ｂ′）＝（−Ａ,−Ｂ＋Ｑ）を計算し、当該暗号文を取得すれば良い。ここで、
【００３０】
【数６】
2006227563.tif 000008
であるから、（Ａ′,Ｂ′）＝Ｅ（１−ａ，−ｒ）が成り立ち、（Ａ′,Ｂ′）は１−ａの暗号文、すなわちＦNOT（ａ）の暗号文となることが分かる。したがって制御装置２０は、ａの暗号文Ｅ（ａ,ｒ）から、ａを知ることなくＦNOT（ａ）の暗号文を計算することができ、更には当該暗号文を取得することができる。
【００３１】
次に定数倍について説明する。この処理も単純で、制御装置２０は、定数ｋおよびＥ（ａ，ｒ）（＝（Ａ，Ｂ））を入力とし、ｋａの暗号文（Ａ′，Ｂ′）＝（ｋＡ，ｋＢ）を計算し、当該暗号文を取得すれば良い。ここで、
【００３２】
【数７】
2006227563.tif 000009
であるから、（Ａ′，Ｂ′）＝Ｅ（ｋａ，ｋｒ）が成り立ち、（Ａ′，Ｂ′）はｋａの暗号文となることが分かる。したがって制御装置２０は、定数ｋ、およびａの暗号文Ｅ（ａ，ｒ）から、ａを知ることなくｋａの暗号文を計算することができ、更には当該暗号文を取得することができる。
【００３３】
次に排他的論理和の処理について、図３の処理シーケンス図を参照して説明する。これが本実施の形態の主要部分となる。
各装置は（Ｇ，ｐ，Ｐ，Ｑ）を保持しているとする。また、ａ，ｂ∈｛０，１｝の暗号文Ｅ（ａ，ｒ）（＝Ａ，Ｂ），Ｅ（ｂ，ｓ）（＝Ｘ，Ｙ））は、暗号文生成装置１０（ｉ），（ｊ）から制御装置２０へ事前にあたえられているとする。
先ず、制御装置２０は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ，ｓ）（＝（Ｘ，Ｙ））を暗号文変換装置３０に送信する。
【００３４】
暗号文変換装置３０は（Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ，ｓ）（＝（Ｘ，Ｙ））を入力とし、以下の処理を行う。
１．ランダムビットｅおよび１以上ｐ以下の乱数ｔ，ｕを生成する（Ｓ１１１）。
２．以下に従って暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を計算する（Ｓ１１２）。
【００３５】
【数８】
2006227563.tif 000010
【００３６】
暗号文変換装置３０は、暗号文（Ａ′,Ｂ′）を復号装置４０（１）、復号装置４０（２）に送信する。また、暗号文（Ｘ′,Ｙ′），（Ａ′,Ｂ′）を制御装置２０に送信する。なお、暗号文変換装置３０から制御装置２０へは、暗号文（Ｘ′,Ｙ′）のみを送信し、暗号文（Ａ′,Ｂ′）は復号装置４０（１），４０（２）から制御装置２０へ送信することでもよい。
【００３７】
復号装置４０（１）は（Ａ′,Ｂ′）を入力とし、ｘ1Ａ′を計算し、それを制御装置２０に送信する（Ｓ１１３）。同様に、復号装置４０（２）は（Ａ′,Ｂ′）を入力とし、ｘ2Ａ′を計算し、それを制御装置２０に送信する（Ｓ１１４）。
【００３８】
制御装置２０はｘＡ′＝ｘ1Ａ′＋ｘ2Ａ′を計算する（Ｓ１１５）。そして、ｘＡ′＝Ｂ′であれば（Ａ′,Ｂ′）の復号結果ｃを“０”、それ以外（ｘＡ′＝Ｂ′−Ｑ）であれば“１”とする（Ｓ１１６〜Ｓ１１８）。その後、当該復号結果ｃ∈｛０,１｝について以下の処理を行う。
１．１以上ｐ以下の乱数ｗを生成する（Ｓ１１９）。
２．以下に従って暗号文（Ｃ,Ｄ）を計算する（Ｓ１２０）。
【００３９】
【数９】
2006227563.tif 000011
【００４０】
なお、上記の（Ａ′,Ｂ′）から復号結果ｃを求める処理は分散復号とよばれる処理であるが、先の［非特許文献２］によれば、ｋ（＞２）台の復号装置が復号処理に協力した場合に限り復号が可能であり、また、より一般的にｎ台中、任意のｋ台の復号装置が復号処理に協力した場合に限り復号が可能とすることもできる（ここでｎ,ｋは任意数の設定が可能な値）。しかしここでは、その処理手順については［非特許文献２］からも明らかであるため説明を省略する。
【００４１】
ここで当該復号結果ｃについて、ｃ＝ａ＊ｅ（排他的論理和）が成り立つことを確認しておく。ｅ＝０であれば、（Ａ′,Ｂ′）＝（（ｒ＋ｔ）Ｐ,（ｒ＋ａ＋ｔ）Ｑ）であるから、（Ａ′,Ｂ′）＝Ｅ（ａ,ｒ＋ｔ）が成り立つ。すなわちｃ＝ａ＝ａ＊０が成り立つ。一方ｅ＝１であれば、（Ａ′,Ｂ′）＝（（−ｒ＋ｔ）Ｐ,（−ｒ−ａ＋ｔ＋１）Ｑ）＝（（ｔ−ｒ）Ｐ,（（ｔ−ｒ）＋（１−ａ））Ｑ）であるから、（Ａ′,Ｂ′）＝Ｅ（１−ａ,ｔ−ｒ）が成り立つ。すなわちｃ＝１−ａ＝ａ＊１が成り立つ。したがって、ｃ＝ａ＊ｅが成り立つことが分かる。
【００４２】
そして同様の説明により、（Ｘ′,Ｙ′）がｂ′＝ｂ＊ｅの暗号文であることが分かる。したがって、（Ｃ,Ｄ）はｂ＊ｅ＊ｃ＝ａ＊ｂの暗号文である。
上記の処理により、制御装置２０はａ,ｂを知ることなく、ａ＊ｂの暗号文、すなわち（Ｃ,Ｄ）を得ることができる。制御装置２０は、必要に応じ（Ｃ,Ｄ）を出力する（Ｓ１２１）。
【００４３】
以上より、制御装置２０は、暗号文変換装置３０および復号装置４０（１）,（２）の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができる。
【００４４】
最後にＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲの処理についてまとめて説明する。これらの処理は排他的論理和の処理を用いれば後は単純で、制御装置２０はＥ（ａ,ｒ）（＝（Ａ,Ｂ））,Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））,（Ｃ′,Ｄ′）を入力とし（ここで（Ｃ′,Ｄ′）はａｂの暗号文）、それぞれ
【００４５】
【数１０】
2006227563.tif 000012
を計算し、当該暗号文を取得すれば良い。ここで今までの説明からＥAND,ＥOR,ＥNAND,ＥNORはそれぞれＦAND（ａ,ｂ）,ＦOR（ａ,ｂ）,ＦNAND（ａ,ｂ）,ＦNOR（ａ,ｂ）の暗号文となることは明らかである。したがって制御装置２０は、暗号文変換装置３０および復号装置４０（１）,（２）の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなく、ＦAND（ａ,ｂ）,ＦOR（ａ,ｂ）,ＦNAND（ａ,ｂ）,ＦNOR（ａ,ｂ）の暗号文を計算することができ、更には当該暗号文を取得することができる。
【００４６】
以上、基本論理ゲートに対する秘密計算方法の手順について説明したが、各装置が、Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ,ｂを求めることが困難であれば、いずれかの装置の結託が無い限りは、基本論理ゲートに対する秘密計算方法を実行した場合においてもａ,ｂは保護できる。
【００４７】
［第２の実施の形態］
第１の実施の形態では、暗号文変換装置または復号装置が不正な処理を行うことで容易に結果を改ざんすることができてしまう。また、制御装置と暗号文変換装置が不正結託すれば、当該装置はａ,ｂを知り得てしまう（例えばｃ＝ａ＊ｅを知る制御装置とｅを知る暗号文変換装置が結託すれば、容易にａが求まることが分かる）。第２の実施の形態は、上記の問題点を解決する方法の一例を提案するものである。
【００４８】
第２の実施の形態におけるシステム構成は、図４に示すように、同一のネットワーク１００で結ばれた、１０の暗号文生成装置（１）,…,（Ｎ）、制御装置２０、３０の暗号文変換装置（１）,（２）、４０の復号装置（１）,（２）、および検証装置５０からなる。このように、第２の実施形態では不正結託による耐性を高めるために暗号文変換装置３０を複数に設定しており、更に暗号文変換装置３０および復号装置４０が不正処理をした場合にそれが検出できるように検証装置５０を必要とする。なお、暗号文変換装置は、その数を増加すればするほど、不正結託による耐性を高めることができるが、ここでは説明の簡単化のために２とする。
【００４９】
第１の実施の形態における基本論理ゲートに対する秘密計算方法では、排他的論理和を計算する処理以外、すなわちａ,ｂの暗号文Ｅ（ａ,ｒ）、Ｅ（ｂ,ｓ）からａ＊ｂの暗号文（Ｃ′,Ｄ′）を求める処理以外は、秘密鍵や乱数などの秘密情報を必要とせず一意に結果が求まる。言い換えれば、排他的論理和を計算する処理以外は任意の装置が同じ処理を再現することが可能であり、これにより特別な検証処理は不要となる。したがって、ここでは、第１の実施の形態で示した、排他的論理和を計算する処理における、暗号文変換装置および復号装置の処理正当性を検証することが可能な秘密計算方法を説明する。
【００５０】
図５（Ａ）〜（Ｃ）に第２の実施の形態における処理シーケンス図を示す。ここでも、各装置は（Ｇ,ｐ,Ｐ,Ｑ）を保持しているとする。また、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））,Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））は、暗号文生成装置１０（ｉ）,（ｊ）から制御装置２０へ事前に与えられているとする。
【００５１】
先ず、制御装置２０は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ，ｓ）（＝（Ｘ，Ｙ））を暗号文変換装置３０（１）へ送信する。以下ではａ∈｛０，１｝と仮定し、ａ＊ｂ乃至ｂ＊ａは、ａ＝０のときｂ，ａ＝１のとき１−ｂと定義する。
【００５２】
暗号文変換装置３０（１）はＥ（ａ,ｒ）（＝（Ａ,Ｂ））とＥ（ｂ，ｓ）（＝（Ｘ，Ｙ））を入力とし、以下の処理を行う。
１．ランダムビットｅ1および１以上ｐ以下の乱数ｔ1，ｕ1を生成する（Ｓ２０１）。
２．以下の［数１１］に従って暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を求め（Ｓ２０２）、当該暗号文（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を暗号文変換装置３０（２）および検証装置５０に送信する。
【００５３】
【数１１】
2006227563.tif 000013
３．（Ａ′,Ｂ′），（Ｘ′,Ｙ′）が［数１１］の関係を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２０３，Ｓ２０４）。
【００５４】
ゼロ知識証明は、文献「Ｒ.Ｃramer,Ｉ.Ｄamgard  and  Ｂ.Ｓchoenmakers,“Ｐroofs  of  partialknowledge  and  Ｓimplified  design  of  withss  hiding  protocols,”Ａcvances  in  Ｃryptology−ＣＲＹＰＴＯ  ′９４」ＬＮＣＳ  ８３９,pp．１７４−１８７,Ｓpringer−Ｖerlag,１９９４．」（以下、非特許文献３と称す）および文献「Ｄ.Ｌ.Ｃhaum  and  Ｔ.Ｐ.Ｐedersen“Ｗallet  databases  with  observers,”Ａcvances  in  Ｃryptology−ＣＲＹＰＴＯ  ’92,ＬＮＣＳ  ７４０,pp.８０−１０５,Ｓpringer−Ｖerlag,１９９３」（以下、非特許文献４と称す）の方法を組み合わせて行うとする。
【００５５】
（Ａ′,Ｂ′），（Ｘ′,Ｙ′）が［数１１］の関係を満たすことを示すためには、（Ａ，Ｂ）に対する計算と（Ｘ，Ｙ）に対する計算では共通のｅ１が用いられていることから、（Ａ′,Ｂ′）＝（Ａ＋ｔ１Ｐ，Ｂ＋ｔ１Ｑ）または（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）が成り立つことと（Ｘ′,Ｙ′）＝（Ｘ＋ｕ１Ｐ，Ｙ＋ｕ１Ｑ）または（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）が成り立つことを示すだけでは不十分であり、
［命題１］
「(Ａ′,Ｂ′)＝(Ａ＋ｔ１Ｐ,Ｂ＋ｔ１Ｑ)かつ(Ｘ′,Ｙ′)＝(Ｘ＋ｕ１Ｐ,Ｙ＋ｕ１Ｑ)」
または、
「（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）かつ
（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）」
であることを示さなければならない。
【００５６】
［命題１］は次の［命題１′］と同値である。
［命題１′］
「（Ａ′,Ｂ′）＝（Ａ＋ｔ１Ｐ，Ｂ＋ｔ１Ｑ）または
（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）」
かつ
「（Ａ′,Ｂ′）＝（Ａ＋ｔ１Ｐ，Ｂ＋ｔ１Ｑ）または
（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）」
かつ
「（Ｘ′,Ｙ′）＝（Ｘ＋ｕ１Ｐ，Ｙ＋ｕ１Ｑ）または
（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）」
かつ
「（Ｘ′,Ｙ′）＝（Ｘ＋ｕ１Ｐ，Ｙ＋ｕ１Ｑ）または
（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）」
【００５７】
［命題１′］のゼロ知識証明を与えるために、まず、以下で与える［プロトコル１］を定義する。これは［非特許文献３］および［非特許文献４］の方法を組み合わせたゼロ知識証明である。
【００５８】
［プロトコル１］は、Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、あるいは、Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しいことを、ゼロ知識証明技術を用いて証明するプロトコルである。
【００５９】
［プロトコル１］
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））
証明者の秘密情報：（ｅ,ｔ）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｃ1-eを生成する。
（ｂ）ＲP,e＝ｒＰ,ＲQ,e＝ｒＱ,ＲP,1-e＝ｒ′Ｐ−ｃ1-eＰ1-e,ＲQ,1-e＝ｒ′Ｑ−ｃ1-eＱ1-e,ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1）−ｃ1-e,ｚe＝ｒ＋ｃeｔ,ｚ1-e＝ｒ′を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ（ｚ0Ｐ−ｃ0Ｐ0‖ｚ0Ｑ−ｃ0Ｑ0‖ｚ1Ｐ−ｃ1Ｐ1‖ｚ1Ｑ−ｃ1Ｑ1）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００６０】
暗号文変換装置３０（１）は、［命題１′］のゼロ知識証明を、下記の手続きにより上記［プロトコル１］を４回実行して得て、証明を暗号文の出力とともに検証装置５０に送信する。
［証明１］
「（Ａ′,Ｂ′）＝（Ａ＋ｔ１Ｐ，Ｂ＋ｔ１Ｑ）または
（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）」
を［プロトコル１］を用いて証明。すなわち、［プロトコル１］において、
（（Ｇ，ｐ，Ｐ，Ｑ），（Ｐ０，Ｑ０），（Ｐ１，Ｑ１））←（（Ｇ，ｐ，Ｐ，Ｑ），（Ａ′−Ａ，Ｂ′−Ｂ），（Ａ＋Ａ′,Ｂ＋Ｂ′−Ｑ））と代入すればよい。
［証明２］
「（Ａ′,Ｂ′）＝（Ａ＋ｔ１Ｐ，Ｂ＋ｔ１Ｑ）または
（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）」
を［プロトコル１］を用いて証明。すなわち、［プロトコル１］において、
（（Ｇ，ｐ，Ｐ，Ｑ），（Ｐ０，Ｑ０），（Ｐ１，Ｑ１））←（（Ｇ，ｐ，Ｐ，Ｑ），（Ａ′−Ａ，Ｂ′−Ｂ），（Ｘ＋Ｘ′,Ｙ＋Ｙ′−Ｑ））と代入すればよい。
［証明３］
「（Ｘ′,Ｙ′）＝（Ｘ＋ｕ１Ｐ，Ｙ＋ｕ１Ｑ）または
（Ａ′,Ｂ′）＝（−Ａ＋ｔ１Ｐ，−Ｂ＋（ｔ１＋１）Ｑ）」
を［プロトコル１］を用いて証明。すなわち、［プロトコル１］において、
（（Ｇ，ｐ，Ｐ，Ｑ），（Ｐ０，Ｑ０），（Ｐ１，Ｑ１））←（（Ｇ，ｐ，Ｐ，Ｑ），（Ｘ′−Ｘ，Ｙ′−Ｙ），（Ａ＋Ａ′,Ｂ＋Ｂ′−Ｑ））と代入すればよい。
［証明４］
「（Ｘ′,Ｙ′）＝（Ｘ＋ｕ１Ｐ，Ｙ＋ｕ１Ｑ）または
（Ｘ′,Ｙ′）＝（−Ｘ＋ｕ１Ｐ，−Ｙ＋（ｕ１＋１）Ｑ）」
を［プロトコル１］を用いて証明。すなわち、［プロトコル１］において、
（（Ｇ，ｐ，Ｐ，Ｑ），（Ｐ０，Ｑ０），（Ｐ１，Ｑ１））←（（Ｇ，ｐ，Ｐ，Ｑ），（Ｘ′−Ｘ，Ｙ′−Ｙ），（Ｘ＋Ｘ′,Ｙ＋Ｙ′−Ｑ））と代入すればよい。
証明を受信した検証装置は、４回の証明すべてについてそれぞれ検証して、すべてが［プロトコル１］の証明として受理される場合に限って、証明を受理する。
【００６１】
ここでは、検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを暗号文変換装置３０（２）に伝える。これを受けて暗号文変換装置３０（２）は（Ａ′,Ｂ′），（Ｘ′,Ｙ′）を入力とし、以下の処理を行う。
１．ランダムビットｅ2および１以上ｐ以下の乱数ｕ2，ｔ2を生成する（Ｓ２０５）。
２．以下の［数１２］に従って暗号文を求め（Ｓ２０６）、復号装置４０（１）,４０（２）に（Ａ″,Ｂ″）を送信し、検証装置５０には（Ａ″,Ｂ″），（Ｘ″,Ｙ″）送信する。さらに、（Ａ″,Ｂ″），（Ｘ″,Ｙ″）を制御装置２０に送信する。本実施例でも、暗号文変換装置３０（２）から制御装置２０へは、暗号文（Ｘ″,Ｙ″）のみを送信し、暗号文（Ａ″,Ｂ″）は復号装置４０（１），４０（２）から制御装置２０へ送信することでもよい。
【００６２】
【数１２】
2006227563.tif 000014
３．（Ａ″,Ｂ″），（Ｘ″,Ｙ″）が［数１２］の関係を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２０７，Ｓ２０８）。
ここで、当該ゼロ知識証明は、先の［数１１］に対する場合と同様であるので省略する。
【００６３】
ここでは、検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したとして話を進める。
【００６４】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを復号装置４０（１）,４０（２）に伝える。これを受けて、復号装置４０（１）は（Ａ″,Ｂ″）を入力とし、ｘ1Ａ″を計算し、それを制御装置２０に送信する（Ｓ２０９）。同様に、復号装置４０（２）は（Ａ″,Ｂ″）を入力とし、ｘ2Ａ″を計算し、それを制御装置２０に送信する（Ｓ２１０）。
【００６５】
その後、復号装置４０（１）,４０（２）を証明者、検証装置５０を検証者として、当該送信情報ｘ1Ａ″,ｘ2Ａ″が正しい計算結果であることをゼロ知識非対話証明技術を用いて証明する（Ｓ２１１〜Ｓ２１４）。
【００６６】
当該証明方法は、具体的にはＰを底としたｘiＰの離散対数、およびＡ″を底としたｘiＡ″の離散対数が等しい（すなわち、ともにｘiとなる）ことを非対話で証明する方法であり、先のゼロ知識証明の基本的な技術により実現可能である。以下にプロトコル例（プロトコル２とする）を示す。
【００６７】
［プロトコル２］
入力：（ｐ,（Ｕ0,Ｖ0）＝（Ｐ,ｘiＰ），（Ｕ1,Ｖ1）＝（Ａ″,ｘiＡ″））
証明者の秘密情報：ｘi
１．証明者は以下に従って（Ｒ0，Ｒ1，ｓ，ｚ）を計算し、（ｓ，ｚ）を検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒを生成する。
（ｂ）Ｒ0＝ｒＵ0,Ｒ1＝ｒＵ1を計算する。
（ｃ）ｓ＝Ｈ（Ｕ0‖Ｖ0‖Ｕ1‖Ｖ1‖Ｒ0‖Ｒ1）を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
（ｄ）ｚ＝ｒ−ｓｘiを計算する。
２．検証者はＲ0′＝ｚＵ0＋ｓＶ0，Ｒ1′＝ｚＵ1＋ｓＶ1を計算後、ｓ＝Ｈ（Ｕ0‖Ｖ0‖Ｕ1‖Ｖ1‖Ｒ0′‖Ｒ1′）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００６８】
復号装置４０（１）は上記１の（ａ）〜（ｄ）の処理により（ｓ,ｚ）を求め（Ｓ２１１）、これを検証装置５０に送信し、検証装置５０が上記２の処理により検証する（Ｓ２１２）。同様に、復号装置４０（２）も（ｓ，ｚ）を求め（Ｓ２１３）、これを検証装置５０に送信し、検証装置５０が検証する（Ｓ２１４）。
【００６９】
ここでは、検証装置５０は復号装置４０（１）,４０（２）の当該証明事項を受理したとして話を進める。検証装置５０は、送信情報ｘ1Ａ″,ｘ2Ａ″が正しいことを制御装置２０に伝える。
【００７０】
制御装置２０は、ｘ1Ａ″,ｘ2Ａ″が共に正しい計算結果である場合、ｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″を計算し（Ｓ２１５）、ｘＡ″＝Ｂ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”とする（Ｓ２１６〜Ｓ２１８）。その後、当該復号結果ｃ∈｛０,１｝について、［数１３］に従って暗号文（Ｃ,Ｄ）を求める（Ｓ２１９）。
【００７１】
【数１３】
2006227563.tif 000015
【００７２】
ここで当該復号結果ｃについて、ｃ＝ａ＊ｅ1＊ｅ2（排他的論理和）が成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。なお、処理が冗長になるが、第１の実施の形態と同様に、1以上ｐ以下の乱数ｗを生成し、
【００７３】
【数１４】
2006227563.tif 000016
となるように（Ｃ，Ｄ）を計算してもよい。
すると（Ｃ，Ｄ）の復号結果ｃ″＝ａ＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
制御装置２０は、（Ｃ，Ｄ）をａ＊ｂの暗号文として認め、必要に応じて出力する（Ｓ２２０）。
【００７４】
以上より、制御装置２０は、暗号文変換装置３０（１）,３０（２）、復号装置４０（１）,４０（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができる。ここでａ,ｂの秘匿性は、暗号文変換装置３０（１）,３０（２）の生成したランダムビットｅ1,ｅ2の秘匿性に依存する。すなわち本実施の形態で示したプロトコルからｅ1およびｅ2を知ることが困難であれば、少なくとも暗号文変換装置３０（１）,３０（２）の不正結託がない限りはａ,ｂを知ることが困難となる。
【００７５】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第２の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,４０（２）の処理正当性を検出することが可能である。
【００７６】
また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【００７７】
［第３の実施の形態］
これは、第１の実施の形態における課題について、第２の実施の形態とは別の方法（プロトコル）で解決するものである。
【００７８】
第３の実施の形態におけるシステム構成は、第２の実施の形態と同様となる。すなわち、図４に示すように同一のネットワーク１００で結ばれた、暗号文生成装置１０（１）,…,（Ｎ）、制御装置２０、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０からなる。
【００７９】
第３の実施の形態の処理は第２の実施の形態とほぼ同様であるが（図５Ａ〜Ｃ）、第２の実施の形態における［命題１］のゼロ知識証明の方式が異なる。
本実施の形態では、［命題１］をゼロ知識証明するために、次の［プロトコル３］を導入する。
［プロトコル３］は、
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、
または、
２．Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことをゼロ知識証明技術を用いて証明するプロトコルである。
【００８０】
［プロトコル３］
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：Ｐe＝ｔＰ，Ｑe＝ｔＱ，Ｐe′＝ｔ′Ｐ，Ｑe′＝ｔ′Ｑとなる（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ0,ｚ1,ｚ0′,ｚ1′,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｒ″,ｒ″′,ｃ1-eを生成する。
（ｂ）Ｒp,e＝ｒＰ,ＲQ,e＝ｒＱ,Ｒp,1-e＝ｒ′Ｐ−ｃ1-eＰ1-e,ＲQ,1-e＝ｒ′Ｑ−ｃ1-eＱ1-e,Ｒ′P,e＝ｒ″Ｐ,Ｒ′Q,e＝ｒ″Ｑ,Ｒ′P,1-e＝ｒ″′Ｐ−ｃ1-eＰ1-e,Ｒ′Q,1-e＝ｒ″′Ｑ−ｃ1-eＱ′1-e,
ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1‖Ｒ′P,0‖Ｒ′Q,0‖Ｒ′P,1‖Ｒ′Q,1）−ｃ1-e,ｚe＝ｒ＋ｃeｔ,ｚ1-e＝ｒ′,ｚ′e＝ｒ″＋ｃeｔ′,ｚ′1-e＝ｒ″′
を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ（ｚ0Ｐ−ｃ0Ｐ0‖ｚ0Ｑ−ｃ0Ｑ0‖ｚ1Ｐ−ｃ1Ｐ1‖ｚ1Ｑ−ｃ1Ｑ1‖ｚ0′Ｐ−ｃ0Ｐ0′‖ｚ0′Ｑ−ｃ0Ｑ0′‖ｚ1′Ｐ−ｃ1Ｐ1′‖ｚ1′Ｑ−ｃ1Ｑ′1）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００８１】
暗号文変換装置３０（１）は、［数１１］の入出力が［命題１］を満たすことを、［プロトコル３］を用いて検証装置５０に対して証明することができる。すなわち、［プロトコル３］において、
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′），（ｅ，ｔ，ｔ′））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ′−Ａ，Ｂ′−Ｂ）,（Ａ＋Ａ′，Ｂ＋Ｂ′−Ｑ）,（Ｘ′−Ｘ，Ｙ′−Ｙ）,（Ｘ＋Ｘ′，Ｙ＋Ｙ′−Ｑ）,（ｅ1，ｔ1，ｕ1））
と代入すればよい。
【００８２】
検証装置５０（検証者）は、暗号文変換装置３０（１）（証明者）の当該証明事項を検証して、それが［プロトコル３］の証明として受理される場合に限っ該証明を受理する。
同様に、暗号文変換装置３０（２）でも、［数１２］のゼロ知識証明には［プロトコル３］を用いる。すなわち、暗号文変換装置３０（２）は、［プロトコル３］において、
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′），（ｅ，ｔ，ｔ′））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′，Ｂ″−Ｂ′）,（Ａ′＋Ａ″，Ｂ′＋Ｂ″−Ｑ）,（Ｘ″−Ｘ′，Ｙ″−Ｙ′）,（Ｘ′＋Ｘ″，Ｙ′＋Ｙ″−Ｑ）,（ｅ2，ｔ2，ｕ2））
と代入すればよい。
上記以外の処理は［実施の形態２］と同様であるために省略する。
【００８３】
以上より、実施の形態２と同様に、制御装置２０は、暗号文変換装置３０（１）,３０（２）、復号装置４０（１）,４０（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ．ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができた。ここでａ,ｂの秘匿性は、暗号文変換装置３０（１）,３０（２）の生成したランダムビットｅ1，ｅ2の秘匿性に依存する。すなわち本実施の形態で示したプロトコルからｅ1およびｅ2を知ることが困難であれば、少なくとも暗号文変換装置３０（１）,３０（２）の不正結託がない限りはａ,ｂを知ることが困難となる。また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【００８４】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第３の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,４０（２）の処理正当性を検出することが可能である。
【００８５】
［第４の実施の形態］
これは、第３の実施の形態における［プロトコル３］を、同様の機能を持つ、より効率の良いプロトコルで置き換えることによって、秘密計算の処理効率を向上させるものである。
【００８６】
第４の実施の形態におけるシステム構成は、第２の実施の形態や第３の実施の形態と同様となる。すなわち、図４に示すように同一のネットワーク１００で結ばれた、暗号文生成装置１０（１）,…,（Ｎ）、制御装置２０、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０からなる。
【００８７】
第４の実施の形態の処理は第２の実施の形態や第３の実施の形態とほぼ同様であるが（図５Ａ〜Ｃ）、第２の実施の形態における［命題１］のゼロ知識証明の方式が異なる。
本実施の形態では、［命題１］をゼロ知識証明するために、次の［プロトコル４］を導入する。
［プロトコル４］は、
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、
または、
２．Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことをゼロ知識証明技術を用いて証明するプロトコルである。これ自体は［プロトコル３］と同じであるが、処理が次のように異なる。
【００８８】
［プロトコル４］
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：Ｐe＝ｔＰ，Ｑe＝ｔＱ，Ｐe′＝ｔ′Ｐ，Ｑe′＝ｔ′Ｑとなる（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）１以上ｐ以下の乱数ｒ,ｒ′,ｒ″,ｃ1-eを生成する。
（ｂ）ｄ＝Ｈ0（Ｐ‖Ｑ‖Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′），Ｒp,e＝ｒＰ,ＲQ,e＝ｒＱ,Ｒp,1-e＝ｒ′Ｐ−ｃ1-e（ｄＰ1-e＋Ｐ1-e′），ＲQ,1-e＝ｒ′Ｑ−ｃ1-e（ｄＱ1-e＋Ｑ1-e′），ｃe＝Ｈ1（Ｒp,0‖ＲQ,0‖Ｒp,1‖ＲQ,1）−ｃ1-e，ｚe＝ｒ＋ｃe（ｄｔ＋ｔ′），ｚ1-e＝ｒ′
を計算する。ここでＨ0，Ｈ1はハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はｃ0＋ｃ1＝Ｈ1（ｚ0Ｐ−ｃ0（ｄＰ0＋Ｐ0′）‖ｚ0Ｑ−ｃ0（ｄＱ0＋Ｑ0′）‖ｚ1Ｐ−ｃ1（ｄＰ1＋Ｐ1′）‖ｚ1Ｑ−ｃ1（ｄＱ1＋Ｑ1′））が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００８９】
暗号文変換装置３０（１）は、［数１１］の入出力が［命題１］を満たすことを、［プロトコル４を用いて検証装置５０に対して証明することができる。すなわち、［プロトコル４］において、
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′），（ｅ，ｔ，ｔ′））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ′−Ａ，Ｂ′−Ｂ）,（Ａ＋Ａ′，Ｂ＋Ｂ′−Ｑ）,（Ｘ′−Ｘ，Ｙ′−Ｙ）,（Ｘ＋Ｘ′，Ｙ＋Ｙ′−Ｑ）,（ｅ1，ｔ1，ｕ1））
と代入すればよい。
【００９０】
検証装置５０（検証者）は、暗号文変換装置３０（１）（証明者）の当該証明事項を検証して、それが［プロトコル４］の証明として受理される場合に限って該証明を受理する。
同様に、暗号文変換装置３０（２）でも、［数１２］のゼロ知識証明には［プロトコル４］を用いる。すなわち、暗号文変換装置３０（２）は、［プロトコル４］において、
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′），（ｅ，ｔ，ｔ′））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′，Ｂ″−Ｂ′）,（Ａ′＋Ａ″，Ｂ′＋Ｂ″−Ｑ）,（Ｘ″−Ｘ′，Ｙ″−Ｙ′）,（Ｘ′＋Ｘ″，Ｙ′＋Ｙ″−Ｑ）,（ｅ2，ｔ2，ｕ2））
と代入すればよい。
上記以外の処理は［実施の形態２］と同様であるために省略する。
【００９１】
以上より、実施の形態２や実施の形態３と同様に、制御装置２０は、暗号文変換装置３０（１）,３０（２）、復号装置４０（１）,４０（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ．ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文をより効率良く計算することができ、更には当該暗号文を取得することができる。また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【００９２】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第４の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,４０（２）の処理正当性を検出することが可能である。
【００９３】
また、第１、第２、第３あるいは第４の実施の形態において、ａi，ｂi∈｛０,１｝（ｉ＝１，２，…，ｎ）の暗号文（Ａi，Ｂi），（Ｘi，Ｙi）を時間をずらして順次入力し、順次、各装置で所定の処理を実行することで、複数組のａi＊ｂiの暗号文をパイプライン形式に計算することが可能である。
【００９４】
また、第２、第３あるいは第４の実施の形態では、検証装置は、検証結果を次の処理装置に送信するとしたが、検証結果をすべて制御装置に送信し、制御装置が該検証結果に基づいて次の処理装置の動作を制御することでもよい（集中制御）。また、システムの信頼性は若干低下するが、復号装置の処理正当性の検証は省略することでよい。
【００９５】
なお、図１、図４などで示したシステムにおける各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２、図３、図５などで示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００９６】
【図１】本発明の第１の実施の形態のシステム構成例を示す図。
【図２】各実施の形態において公開鍵（Ｇ,ｐ,Ｐ,Ｑ）を生成する処理シーケンス例を示す図。
【図３】第１の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図４】本発明の第２の実施の形態、第３の実施の形態および第４の実施の形態のシステム構成例を示す図。
【図５Ａ】第２の実施の形態、第３の実施の形態および第４の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図５Ｂ】同じく第２の実施の形態、第３の実施の形態および第４の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図５Ｃ】同じく第２の実施の形態、第３の実施の形態および第４の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【符号の説明】
【００９７】
１０  暗号文生成装置
２０  制御装置
３０  暗号文変換装置
４０  復号装置
５０  検証装置
１００  ネットワーク
【図１】
2006227563.tif 000022
【図２】
2006227563.tif 000023
【図３】
2006227563.tif 000024
【図４】
2006227563.tif 000025
【図５Ａ】
2006227563.tif 000026
【図５Ｂ】
2006227563.tif 000027
【図５Ｃ】
2006227563.tif 000028