(57)【要約】【課題】関数への入力値を知ることなく、処理時間の削減を可能にする排他的論理和の秘密計算方法をを提供する。【解決手段】楕円曲線の有理点群をＧ,ＰをＧの元、Ｇの位数をＰとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とする。ａの暗号関数ＥをＥ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒｐ,（ｒ＋ａ）Ｑ）と定義する。制御装置はａ,ｂの暗号文（Ａ,Ｂ）,（Ｘ,Ｙ）を入力し、まず、（Ａ,Ｂ）を暗号文変換装置に送る。暗号文変換装置は（Ａ,Ｂ）の暗号文（Ａ′,Ｂ′）を計算し、各復号装置に送り、各復号装置はｘｉＡ′を計算し、制御装置に送る。制御装置はｘＡ′を計算し、（Ａ′,Ｂ′）の復号結果について、暗号文（Ｃ,Ｄ）を計算し、暗号文変換装置に送る。暗号文変換装置は（Ｃ′,Ｄ′）を計算し、制御装置に送る。制御装置は（Ｃ′,Ｄ′）をａ＋ｂ（排他的論理和）の暗号文と認識する。【選択図】図３
2006201468.tif 000002
【特許請求の範囲】
【請求項１】
ある有限体上で定義された楕円曲線の有理点からなる群をＧとし、ＰをＧの元とし、Ｐの位数をｐとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とし、
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅが
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒｐ,（ｒ＋ａ）Ｑ）
と定義され（ｒは１以上ｐ以下の乱数）、
ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））から、ａ,ｂを知ることなく、ａ＊ｂ（＊は排他的論理和を意味するとする。以下、同様）の暗号文を計算する秘密計算方法であって、
ネットワークで結ばれた、一つあるいは複数の暗号文生成装置、制御装置、暗号文変換装置および複数の復号装置を備え、
制御装置は、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））を暗号文生成装置から入力して、まず、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を暗号文変換装置に送信し、
暗号文変換装置は、（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力として、ランダムビットｅおよび１以上ｐ以下の乱数ｔを生成し、暗号文（Ａ′,Ｂ′）を
【数１】
2006201468.tif 000031
により計算して、該暗号文（Ａ′,Ｂ′）を各復号装置ｉ（ｉ＝１,２,…）に送信し、
各復号装置ｉ（ｉ＝１,２,…）は、（Ａ′,Ｂ′）を入力とし、ｘiＡ′（ｘiは乱数）を計算して、それを制御装置に送信し、
制御装置は、ｘＡ′＝ｘ1Ａ′＋ｘ2Ａ′＋…を計算し、ｘＡ′＝Ｂ′であれば（Ａ′,Ｂ′）の復号結果ｃを“０”、それ以外（ｘＡ′＝Ｂ′−Ｑ）であれば“１”として、該復号結果ｃ∈｛０,１｝について、暗号文（Ｃ,Ｄ）を、
【数２】
2006201468.tif 000032
により計算して（ｗは１以上ｐ以下の乱数）、該暗号文（Ｃ,Ｄ）を暗号文変換装置に送信し、
暗号文変換装置は、（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ,Ｄ）を入力として、１以上ｐ以下の乱数ｕを生成し、暗号文（Ｃ′,Ｄ′）を
【数３】
2006201468.tif 000033
により計算して、該暗号文（Ｃ′,Ｄ′）を制御装置に送信し、
制御装置は、（Ｃ′,Ｄ′）をａ＊ｂの暗号文として出力することを特徴とする秘密計算方法。
【請求項２】
ある有限体上で定義された楕円曲線の有理点からなる群をＧとし、ＰをＧの元とし、Ｐの位数をｐとし、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とし、
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅが
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒｐ,（ｒ＋ａ）Ｑ
と定義され（ｒは１以上ｐ以下の乱数）、
ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））から、ａ,ｂを知ることなく、ａ＊ｂの暗号文を計算する秘密計算方法であって、
ネットワークで結ばれた、一つあるいは複数の暗号文生成装置、制御装置、複数の暗号文変換装置、複数の復号装置および検証装置を備え、
制御装置は、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））、Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））を暗号文生成装置から入力して、まず、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を第１の暗号文変換装置に送信し、
第１の暗号文変換装置は、（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力として、ランダムビットｅ1および１以上ｐ以下の乱数ｔ1を生成し、暗号文（Ａ′,Ｂ′）を
【数４】
2006201468.tif 000034
により計算して、該暗号文（Ａ′,Ｂ′）を第２の暗号文変換装置および検証装置に送信し、
検証装置は、第１の暗号文変換装置の処理正当性を検証して、その結果を第２の暗号文変換装置に通知し、
第２の暗号文変換装置は、検証装置から第１の暗号文変換装置の処理正当の通知を受けると、ランダムビットｅ2および１以上ｐ以下の乱数ｔ2を生成し、暗号文（Ａ″,Ｂ″）を、
【数５】
2006201468.tif 000035
により計算して、該暗号文（Ａ″,Ｂ″）を各復号装置ｉ（ｉ＝１,２,…）および検証装置に送信し、
検証装置は、第２の暗号文変換装置の処理正当性を検証して、その結果を各復号装置に通知し、
各復号装置ｉ（ｉ＝１,２,…）は、検証装置から第２の暗号文変換装置の処理正当の通知を受けると、（Ａ″,Ｂ″）を入力とし、ｘiＡ″（ｘiは乱数）を計算して、それを制御装置に送信し、
検証装置は、各復号装置の処理正当性を検証して、その結果を制御装置に通知し、
制御装置は、検証装置から全ての復号装置の処理正当の通知を受けると、ｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″＋…を計算し、ｘＡ″＝Ｂ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”として、該復号結果ｃ∈｛０,１｝について、暗号文（Ｃ,Ｄ）を、
【数６】
2006201468.tif 000036
により計算して、該暗号文（Ｃ,Ｄ）を第１（あるいは第２の暗号文変換装置に送信し、
第１（あるいは第２）の暗号文変換装置は、（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ,Ｄ）を入力として、１以上ｐ以下の乱数ｕ2を生成し、暗号文（Ｃ′,Ｄ′）を
【数７】
2006201468.tif 000037
により計算して（第１の暗号文変換装置であれは添え字は1となる）、該暗号文（Ｃ′,Ｄ′）を第２（あるいは第１）の暗号文変換装置および検証装置に送信し、
検証装置は、第１（あるいは第２）の暗号文変換装置の処理正当性を検証して、その結果を第２（あるいは第１）の暗号文変換装置に通知し、
第２（あるいは第１）の暗号文変換装置は、検証装置から第１（あるいは第２）の暗号文変換装置の処理正当の通知を受けると、（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ′,Ｄ′）を入力として、１以上ｐ以下の乱数ｕ１を生成し、暗号文（Ｃ″,Ｄ″）を
【数８】
2006201468.tif 000038
により計算して（第２の暗号文変換装置であれは添え字は２となる）、該暗号文（Ｃ″,Ｄ″）を制御装置および検証装置に送信し、
検証装置は、第２（あるいは第１）の暗号文変換装置の処理の正当性を検証して、その結果を制御装置に通知し、
制御装置は、検証装置から第２（あるいは第１）の暗号文変換装置の処理正当の通知を受けると、（Ｃ″,Ｄ″）をａ＊ｂの暗号文として認識することを特徴とする秘密計算方法。
【請求項３】
請求項２記載の秘密計算方法において、
検証装置は、第１あるいは第２の暗号文変換装置を証明者、当該検証装置を検証者として、下記プロトコル１を用いて、（Ａ′,Ｂ′）,（Ａ″,Ｂ″）,（Ｃ′,Ｄ′）（Ｃ″,Ｄ″）が［数４］、［数５］、［数７］、［数８］の関係を満たしていることをゼロ知識証明する、
［プロトコル１］
Ｐを底としたＰ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の離散対数が等しい、あるいは、Ｐを底としたＰ１の離散対数とＱを底としたＱ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）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
さらに、検証装置は、第１あるいは第二の暗号文変換装置を証明者、当該検証装置を検証者として、下記プロトコル３を用いて、（Ｃ′,Ｄ′）（Ｃ″,Ｄ″）が［数７］、［数８］の関係を満たしていることをゼロ知識証明する、
［プロトコル３］
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、
または、
２．Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことを、ゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ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の離散対数が等しいことを、ゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ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）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
さらに、検証装置は、第１あるいは第２の暗号文変換装置を証明者、当該検証装置を検証者として、下記プロトコル４を用いて、（Ｃ′，Ｄ′），（Ｃ″，Ｄ″）が［数７］、［数８］の関係をみたしていることをゼロ知識証明する。
［プロトコル４］
１.Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、
あるいは、
２.Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、
ことが既にゼロ知識証明されているとき（該離散対数をｓとする）、
１が真であるときに限り、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しいことを証明し、
逆に２が真であるときに限り、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい（ともに該離散対数をｔとする）、ことが可能なゼロ知識証明技術を用いて証明するプロトコル、
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′））
証明者の秘密情報：（ｅ,ｓ,ｔ）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）ε＝Ｈ（Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′）を計算する。
（ｂ）１以上ｐ以下の乱数ｒ,ｒ′,ｃ1-eを生成する。
（ｃ）ＲP,e＝ｒＰ,ＲQ,e＝ｒＱ,ＲP,1-e＝ｒ′Ｐ−ｃ1-e（εＰ1-e+Ｐ′1-e）,ＲQ,1-e＝ｒ′Ｑ−ｃ1-e（εＱ1-e+Ｑ′1-e）,ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1）−ｃ1-e,ｚe＝ｒ＋ｃe（εｓ+ｔ）,ｚ1-e＝ｒ′を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はε′＝Ｈ（Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′）を計算し、ｃ0＋ｃ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,１９９１.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
０または１からなる入力の数値が暗号化された状態のまま、当該数値の加算および排他的論理和の結果（の暗号文）を求めることができれば、当該数値の論理和（ＯＲ）および論理積（ＡＮＤ）の結果（の暗号文）を求めることができる。すなわち、理論的には、入力の数値が暗号化された状態のまま多くの関数を計算できることになる。しかし、ＳＴ04では、Ｅ（ａ），Ｅ（ｂ）からＥ（ａ＊ｂ）を計算するために、一旦Ｅ（ａ）をある変換規則に基づいてＥ（ａ′）に変換する必要がある。ここでａ′＝２ａ−１となる。
【０００６】
本発明が解決しようとする一番目の課題は、上記変換を行うことなくＥ（ａ＊ｂ）を計算できるようにし、これにより計算量を削減しようとするものである。
【０００７】
そして、本発明が解決しようとする二番目の課題は、並列計算処理を従来よりも効率化することで、全体の処理時間を削減しようとするものである。ＳＴ04では、各装置が順序的に処理を行う箇所があり、これによりある装置が待ち状態になる場合があると考えられる。本発明では、当該待ち状態が少なくするような方法を新たに与えることで、全体の処理時間の削減効果を狙っている。
【０００８】
また、一番目の課題に対する解決方法に付随した話として、ＳＴ04では、各装置が正しく処理を行ったことを証明する技術を用いているが、当該技術はその安全性が計算量的仮定に基づいており、新しい攻撃アルゴリズムが発見されることで、各装置が持つ秘密情報のゼロ知識性や健全性（正しくない処理を行った場合は処理正当性を証明できないような性質）が失われてしまう可能性がある。したがって、各装置が正しく処理を行ったことを証明する別技術を見つけることは、安全性の観点から、とても意義深いといえる。
【０００９】
そこで本発明が解決しようとする三番目の課題は、一番目の課題に対する解決方法に対して、各装置が正しく処理を行ったことを証明するために、ＳＴ04で提案されている技術とは別の技術を提案することである。
【課題を解決するための手段】
【００１０】
Ｇをある有限体上で定義された楕円曲線の有理点からなる群とし、ＰをＧの元とする。Ｐの位数をｐとする。そして、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とする。
【００１１】
このとき、平文ａ∈｛０,１｝を暗号化する暗号関数Ｅを次のように定義する。  
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
ここでｒは１以上ｐ以下の乱数である。
【００１２】
復号処理はｘＡを計算すれば良く、これにより
【００１３】
【数１】
2006201468.tif 000003
が成り立つことから、秘密鍵ｘを用いることで容易にＥ（ａ,ｒ）を復号できる。するとａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ＋ｂの暗号文を求めることは容易である。すなわち、Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）＝（（ｒ＋ｓ）Ｐ,（ｒ＋ａ＋ｓ＋ｂ）Ｑ）が成り立つことから、この操作によりａ＋ｂの暗号文Ｅ（ａ＋ｂ,ｒ＋ｓ）＝Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）が得られる。
【００１４】
次に、Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ＊ｂの暗号文を求める方法の概略を説明する。これが本発明の主要部分となる。ここで、ｂ，ｂ∈｛０，１｝の暗号文Ｅ（ａ，ｒ）（＝（Ａ，Ｂ），Ｅ（ｂ，ｓ）（＝（Ｘ，Ｙ）は制御装置へ事前に与えられているとする。
先ず、暗号文変換装置が制御装置より（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力として以下の処理を行う。
１.ランダムビットｅおよび１以上ｐ以下の乱数ｔを生成する。
２．以下に従って（Ａ′,Ｂ′）を求め、それを複数の復号装置に送信する。
【００１５】
【数２】
2006201468.tif 000004
【００１６】
次に、複数の復号装置が（Ａ′,Ｂ′）入力として分散復号を行い、制御装置に送信することで、制御装置は（Ａ′,Ｂ′）の復号結果ｃを得る（このときｃ＝ａ＊ｅ（排他的論理和）が成り立つ）。
【００１７】
制御装置は、当該復号結果ｃ∈｛０,１｝について以下の処理を行う。
１.１以上ｐ以下の乱数ｗを生成する。
２.以下に従って（Ｃ,Ｄ）を求め、当該暗号文を暗号文変換装置に送信する。
【００１８】
【数３】
2006201468.tif 000005
このとき（Ｃ，Ｄ）の復号結果はａ＊ｂ＊ｅとなる。
【００１９】
暗号文変換装置は（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ,Ｄ）を入力として、以下の処理を行う。
１.１以上ｐ以下の乱数ｕを生成する。
２．以下に従って（Ｃ′,Ｄ′）を求め、それを制御装置に送信する。
【００２０】
【数４】
2006201468.tif 000006
【００２１】
（Ｃ′,Ｄ′）の復号結果ｃ′は、ｃ′＝ａ＊ｂが成り立つことから、上記の操作により制御装置はａ＊ｂの暗号文、すなわち（Ｃ′,Ｄ′）を得ることができる。
【発明の効果】
【００２２】
本発明の秘密計算方法によれば、従来技術のように、Ｅ（ａ＊ｂ）を計算するためにＥ（ａ）をＥ（ａ′）（ａ′＝２ａ−１）に変換する必要はないため、計算時間の削減が期待できる。また、従来技術では、本発明で（Ａ，Ｂ）から（Ａ′，Ｂ′）を計算する処理（これを［処理１］とする）、および（Ｃ，Ｄ）から（Ｃ′，Ｄ′）を計算する処理（これを［処理２］とする）に相当する、同程度の計算量の処理部分（これらをそれぞれ［処理３］、［処理４］とする）が存在するが、それを従来技術では同時期に計算する必要がある。しかし本発明では当該処理が同時期ではないため、例えば装置Ａが［処理１］を終えれば、直ちに当該計算結果を装置Ｂに送信し、装置Ｂはその後直ちに当該計算結果を入力とした処理を行うことができる。また装置Ａは［処理１］を終えれば、別の入力に対して直ちに処理を行うこともできる。一方従来技術では、［処理３］、［処理４］を終えてから当該計算結果を装置Ｂに送信することになるため、装置Ｂの待ち時間が本発明よりも長くなる場合がある。これにより本発明は並列処理の効率化が期待でき、全体の処理時間の削減効果が期待できる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態について図面を用いて詳細に説明する。
【００２４】
［第１の実施の形態］
第１の実施の形態におけるシステム構成は、図１に示すように、同一のネットワーク１００で結ばれた、１０の暗号文生成装置１,…,Ｎ（Ｎは適当な自然数）、制御装置２０、暗号文変換装置３０、および４０の復号装置１,２からなる。ここで復号装置を複数に設定しているのは、復号装置が単一であれば、当該復号装置は入力の数値の暗号文も復号できる権限を持つことになり、明らかに本発明が取り上げている課題を解決できないが、本実施の形態のように復号装置を複数に設定すれば、分散復号技術を用いて、それら復号装置が結託しない限りは入力の数値を知ることが困難とできるためである。なお、本実施の形態では、簡単に復号装置の数は２としたが、一般に２以上いくつでもよい。
【００２５】
はじめに本発明で用いる暗号方式について、図２の処理シーケンス図を参照して説明する。
制御装置２０は、有限体および楕円曲線を生成するためのパラメータを与えることで有限体および楕円曲線をそれぞれ一つずつ決定し（Ｓ１０１）、更に当該有限体上で定義された当該楕円曲線の有理点からなる群Ｇを決定する（Ｓ１０２）。また、Ｇの元を一つ選び、これをＰとする（Ｓ１０３）。次に、Ｐの位数ｐを計算する（Ｓ１０４）。そして、（Ｇ,ｐ,Ｐ）の組を復号装置４０（ｉ）（ｉ＝１,２）に送信する。
【００２６】
復号装置４０（ｉ）は、（Ｇ,ｐ,Ｐ）を入力として、１以上ｐ以下の乱数ｘiを生成後、Ｑi＝ｘiＰを計算し、Ｑiを制御装置２０に送信する（Ｓ１０５〜Ｓ１０８）。ここでは、復号装置４０（１）は乱数ｘ1を生成し（Ｓ１０５）、Ｑ1＝ｘ1Ｐを計算して（Ｓ１０６）、当該Ｑ1を制御装置２０に送信し、また、復号装置４０（２）は乱数ｘ2を生成し（Ｓ１０７）、Ｑ2＝ｘ2Ｐを計算して（Ｓ１０８）、Ｑ２を制御装置２０に送信する。
【００２７】
制御装置２０は、Ｑ＝Ｑ1＋Ｑ2を計算し（Ｓ１０９）、（Ｇ,ｐ,Ｐ,Ｑ）を公開する（Ｓ１１０）。
【００２８】
以上の準備の下、先ず本発明で用いる暗号化処理について説明する。  
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅを
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
と定義する。ここでｒは１以上ｐ以下の乱数である。
【００２９】
次に復号処理について説明する。
いま、ｘ＝ｘ1＋ｘ2とおくと、ｘＡを計算すればＥ（ａ,ｒ）を復号できる。すなわち、
【００３０】
【数５】
2006201468.tif 000007
が成り立つことから、ｘＡ＝Ｂであれば復号結果を“０”とし、ｘＡ＝Ｂ−Ｑであれば“１”とする。なお当該計算に関わる装置が全て正しい処理を行えばｘＡ＝ＢまたはｘＡ＝Ｂ−Ｑの何れかが成り立つことは明らかである。したがって秘密鍵ｘを用いることで容易にＥ（ａ,ｒ）を復号できる。ただし実際の復号手順としては、復号装置ｉ（ｉ＝１,２）がｘiＡを計算、公開し、その後、制御装置２０がｘＡ＝ｘ1Ａ＋ｘ2Ａを求め、復号結果を得ることになる。
【００３１】
次に具体的な秘密計算方法として、基本論理ゲート（ＮＯＴ,ＡＮＤ,ＯＲ,ＮＡＮＤ,ＮＯＲ）に対する秘密計算方法の手順について説明する。ここで基本論理ゲートヘの入力となるａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）は、上記の暗号化処理方法を用いて暗号文生成装置１０（１）,…,（Ｎ）の何れかによって生成されたものであり、当該暗号文は制御装置２０へ事前に与えられていると仮定する。なおここではどの暗号文生成装置１０がＥ（ａ,ｒ）,Ｅ（ｂ,ｓ）を生成したかについては言及しないが、実際、当該二つの暗号文は同一の装置によって生成される必要はなく、一般に用途によって異なると考えられる。
【００３２】
基本論理ゲート（ＮＯＴ、ＡＮＤ,ＯＲ、ＮＡＮＤ,ＮＯＲ）を表す論理関数は、排他的論理和（＊）、加減算、および定数倍を用いてそれぞれ以下とできる。
【００３３】
【数６】
2006201468.tif 000008
【００３４】
先ずＮＯＴの処理について説明する。この処理は単純で、制御装置２０は,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、１−ａの暗号文（Ａ′,Ｂ′）＝（−Ａ,−Ｂ＋Ｑ）を計算し、当該暗号文を取得すれば良い。ここで、
【００３５】
【数７】
2006201468.tif 000009
であるから、（Ａ′,Ｂ′）＝Ｅ（１−ａ，−ｒ）が成り立ち、（Ａ′,Ｂ′）は１−ａの暗号文、すなわちＦNOT（ａ）の暗号文となることが分かる。したがって制御装置は、ａの暗号文Ｅ（ａ,ｒ）から、ａを知ることなくＦNOT（ａ）の暗号文を計算することができ、更には当該暗号文を取得することができる。
【００３６】
次に定数倍について説明する。この処理も単純で、制御装置２０は、定数ｋおよびＥ（ａ，ｒ）（＝（Ａ，Ｂ））を入力とし、ｋａの暗号文（Ａ′，Ｂ′）＝（ｋＡ，ｋＢ）を計算し、当該暗号文を取得すれば良い。ここで、
【００３７】
【数８】
2006201468.tif 000010
であるから、（Ａ′，Ｂ′）＝Ｅ（ｋａ，ｋｒ）が成り立ち、（Ａ′，Ｂ′）はｋａの暗号文となることが分かる。したがって制御装置２０は、定数ｋ、およびａの暗号文Ｅ（ａ，ｒ）から、ａを知ることなくｋａの暗号文を計算することができ、更には当該暗号文を取得することができる。
【００３８】
次に排他的論理和の処理について、図３の処理シーケンス図を参照して説明する。これが本実施の形態の主要部分となる。
各装置は（Ｇ，ｐ，Ｐ，Ｑ）を保持しているとする。また、ａ，ｂ∈｛０，１｝の暗号文Ｅ（ａ，ｒ）（＝Ａ，Ｂ），Ｅ（ｂ，ｓ）（＝Ｘ，Ｙ））は、暗号文生成装置１０（ｉ），（ｊ）から制御装置２０へ事前にあたえられているとする。
先ず、制御装置２０は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を暗号文変換装置３０に送信する。なお、各装置では、あらかじめ（Ｇ,ｐ,Ｐ,Ｑ）を保持しているとする。
【００３９】
暗号文変換装置３０は（Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、以下の処理を行う。
１．ランダムビットｅおよび１以上ｐ以下の乱数ｔを生成する（Ｓ１１１）。
２．以下に従って暗号文（Ａ′,Ｂ′）を計算する（Ｓ１１２）。
【００４０】
【数９】
2006201468.tif 000011
【００４１】
暗号文変換装置３０は、暗号文（Ａ′,Ｂ′）を復号装置４０（１）、復号装置４０（２）に送信する。
【００４２】
復号装置４０（１）は（Ａ′,Ｂ′）を入力とし、ｘ1Ａ′を計算し、それを制御装置２０に送信する（Ｓ１１３）。同様に、復号装置４０（２）は（Ａ′,Ｂ′）を入力とし、ｘ2Ａ′を計算し、それを制御装置２０に送信する（Ｓ１１４）。
【００４３】
制御装置２０はｘＡ′＝ｘ1Ａ′＋ｘ2Ａ′を計算する（Ｓ１１５）。そして、ｘＡ′＝Ｂ′であれば（Ａ′,Ｂ′）の復号結果ｃを“０”、それ以外（ｘＡ′＝Ｂ′−Ｑ）であれば“１”とする（Ｓ１１６〜Ｓ１１８）。その後、当該復号結果ｃ∈｛０,１｝について以下の処理を行う。
１．１以上ｐ以下の乱数ｗを生成する（Ｓ１１９）。
２．以下に従って暗号文（Ｃ,Ｄ）を計算する（Ｓ１２０）。
【００４４】
【数１０】
2006201468.tif 000012
【００４５】
そして、制御装置２０は、（Ｃ,Ｄ）を暗号文変換置装置３０に送信する。
【００４６】
なお、上記の（Ａ′,Ｂ′）から復号結果ｃを求める処理は分散復号とよばれる処理であるが、先の［非特許文献２］によれば、ｋ（＞２）台の復号装置が復号処理に協力した場合に限り復号が可能であり、また、より一般的にｎ台中、任意のｋ台の復号装置が復号処理に協力した場合に限り復号が可能とすることもできる（ここでｎ,ｋは任意数の設定が可能な値）。しかしここでは、その処理手順については［非特許文献２］からも明らかであるため説明を省略する。
【００４７】
ここで当該復号結果ｃについて、ｃ＝ａ＊ｅ（排他的論理和）が成り立つことを確認しておく。ｅ＝０であれば、（Ａ′,Ｂ′）＝（（ｒ＋ｔ）Ｐ,（ｒ＋ａ＋ｔ）Ｑ）であるから、（Ａ′,Ｂ′）＝Ｅ（ａ,ｒ＋ｔ）が成り立つ。すなわちｃ＝ａ＝ａ＊０が成り立つ。一方ｅ＝１であれば、（Ａ′,Ｂ′）＝（（−ｒ＋ｔ）Ｐ,（−ｒ−ａ＋ｔ＋１）Ｑ）＝（（ｔ−ｒ）Ｐ,（（ｔ−ｒ）＋（１−ａ））Ｑ）であるから、（Ａ′,Ｂ′）＝Ｅ（１−ａ,ｔ−ｒ）が成り立つ。すなわちｃ＝１−ａ＝ａ＊１が成り立つ。したがって、ｃ＝ａ＊ｅが成り立つことが分かる。
【００４８】
そして同様の説明により、（Ｃ,Ｄ）はｂ＊ｃの暗号文となることも分かる。すなわち、ｃ＝０であればｂ＊ｃ＝ｂであり、かつ（Ｃ,Ｄ）＝（Ｘ,Ｙ）＋（ｗＰ,ｗＱ）＝Ｅ（ｂ,ｓ＋ｗ）が成り立つ。一方、ｃ＝１であればｂ＊ｃ＝１−ｂであり、かつ（Ｃ,Ｄ）＝（−Ｘ,−Ｙ）＋（ｗＰ,（ｗ+1）Ｑ）＝Ｅ（−ｂ,−ｓ＋ｗ）が成り立つ。したがって、（Ｃ,Ｄ）はｂ＊ｃの暗号文である。
【００４９】
次に暗号文変換装置３０は（Ｃ,Ｄ）を入力として、以下の処理を行う。
１．１以上ｐ以下の乱数ｕを生成する（Ｓ１２１）。
２．以下に従って暗号文（Ｃ′,Ｄ′）を計算する（Ｓ１２２）。
【００５０】
【数１１】
2006201468.tif 000013
暗号文変換装置３０は、当該暗号文（Ｃ′,Ｄ′）を制御装置２０に送信する。
【００５１】
ここで、（Ｃ′,Ｄ′）の復号結果ｃ′は、ｃ′＝ｂ＊ｃ＊ｅ＝ａ＊ｂが成り立つことから、上記の処理により、制御装置２０はａ,ｂを知ることなく、ａ＊ｂの暗号文、すなわち（Ｃ′,Ｄ′）を得ることができる。制御装置２０は、必要に応じ（Ｃ′,Ｄ′）を出力する（Ｓ１２３）。
【００５２】
ここで当該復号結果ｃ′について、ｃ′＝ａ＊ｂが成り立つことを確認しておく。ｅ＝０であれば、（Ｃ′,Ｄ′）＝（Ｃ＋ｕＰ,Ｄ＋ｕＱ）であるから、（Ｃ′,Ｄ′）の復号結果と（Ｃ,Ｄ）の復号結果は明らかに等しい。すなわちｃ′＝ｂ＊ｃ＝ｂ＊（ａ＊ｅ）ｂ＝ａ＊ｂが成り立つ。一方ｅ＝１であれば、（Ｃ′,Ｄ′）＝（−Ｃ＋ｕＰ,−Ｄ＋（ｕ＋1）Ｑ）であるから、ｃ＝０であれば、（Ｃ′,Ｄ′）＝（（−ｓ−ｗ＋ｕ）Ｐ,（−ｓ−ｂ−ｗ＋ｕ＋１）Ｑ）となり、ｃ′＝1−ｂ＝ｂ＊１を得る。これに対して、いまｃ＝０,ｅ＝１であるから、ａ＝１となり、ｃ′＝ｂ＝ａｂが成り立つ。また、ｃ＝１であれば（Ｃ′,Ｄ′）＝（（−ｓ−ｗ＋ｕ）Ｐ,（ｓ＋ｂ−ｗ＋ｕ）Ｑ）となり、ｃ′＝ｂを得る。これに対して、いまｃ＝ｅ＝１であるから、ａ＝０となり、ｃ′＝ａ＊ｂが成り立つ。したがって（Ｃ′,Ｄ′）はａ＊ｂの暗号文となることが分かる。
【００５３】
以上より、制御装置２０は、暗号文変換装置３０および復号装置４０（１）,（２）の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができる。
【００５４】
最後にＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲの処理についてまとめて説明する。これらの処理は排他的論理和の処理を用いれば後は単純で、制御装置２０はＥ（ａ,ｒ）（＝（Ａ,Ｂ））,Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））,（Ｃ′,Ｄ′）を入力とし（ここで（Ｃ′,Ｄ′）はａｂの暗号文）、それぞれ
【００５５】
【数１２】
2006201468.tif 000014
を計算し、当該暗号文を取得すれば良い。ここで今までの説明からＥAND,ＥOR,ＥNAND,ＥNORはそれぞれＦAND（ａ,ｂ）,ＦOR（ａ,ｂ）,ＦNAND（ａ,ｂ）,ＦNOR（ａ,ｂ）の暗号文となることは明らかである。したがって制御装置２０は、暗号文変換装置３０および復号装置４０（１）,（２）の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなく、ＦAND（ａ,ｂ）,ＦOR（ａ,ｂ）,ＦNAND（ａ,ｂ）,ＦNOR（ａ,ｂ）の暗号文を計算することができ、更には当該暗号文を取得することができる。
【００５６】
以上、基本論理ゲートに対する秘密計算方法の手順について説明したが、各装置が、Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ,ｂを求めることが困難であれば、いずれかの装置の結託が無い限りは、基本論理ゲートに対する秘密計算方法を実行した場合においてもａ,ｂは保護できる。
【００５７】
［第２の実施の形態］
第１の実施の形態では、暗号文変換装置または復号装置が不正な処理を行うことで容易に結果を改ざんすることができてしまう。また、制御装置と暗号文変換装置が不正結託すれば、当該装置はａ,ｂを知り得てしまう（例えばｃ＝ａ＊ｅを知る制御装置とｅを知る暗号文変換装置が結託すれば、容易にａが求まることが分かる）。第２の実施の形態は、上記の問題点を解決する方法の一例を提案するものである。
【００５８】
第２の実施の形態におけるシステム構成は、図４に示すように、同一のネットワーク１００で結ばれた、１０の暗号文生成装置（１）,…,（Ｎ）、制御装置２０、３０の暗号文変換装置（１）,（２）、４０の復号装置（１）,（２）、および検証装置５０からなる。このように、第２の実施形態では不正結託による耐性を高めるために暗号文変換装置３０を複数に設定しており、更に暗号文変換装置３０および復号装置４０が不正処理をした場合にそれが検出できるように検証装置５０を必要とする。なお、暗号文変換装置は、その数を増加すればするほど、不正結託による耐性を高めることができるが、ここでは説明の簡単化のために２とする。
【００５９】
第１の実施の形態における基本論理ゲートに対する秘密計算方法では、排他的論理和を計算する処理以外、すなわちａ,ｂの暗号文Ｅ（ａ,ｒ）、Ｅ（ｂ,ｓ）からａ＊ｂの暗号文（Ｃ′,Ｄ′）を求める処理以外は、秘密鍵や乱数などの秘密情報を必要とせず一意に結果が求まる。言い換えれば、排他的論理和を計算する処理以外は任意の装置が同じ処理を再現することが可能であり、これにより特別な検証処理は不要となる。したがって、ここでは、第１の実施の形態で示した、排他的論理和を計算する処理における、暗号文変換装置および復号装置の処理正当性を検証することが可能な秘密計算方法を説明する。
【００６０】
図５（Ａ）〜（Ｄ）に第２の実施の形態における処理シーケンス図を示す。ここでも、各装置は（Ｇ,ｐ,Ｐ,Ｑ）を保持しているとする。また、ａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））,Ｅ（ｂ,ｓ）（＝（Ｘ,Ｙ））は、暗号文生成装置１０（ｉ）,（ｊ）から制御装置２０へ事前に与えられているとする。
【００６１】
先ず、制御装置２０は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を暗号文変換装置３０（１）へ送信する。
【００６２】
暗号文変換装置３０（１）はＥ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、以下の処理を行う。
１．ランダムビットｅ1および１以上ｐ以下の乱数ｔ1を生成する（Ｓ２０１）。
２．以下の［数１３］に従って暗号文（Ａ′,Ｂ′）を求め、当該暗号文を暗号文変換装置３０（２）および検証装置５０に送信する（Ｓ２０２）。
【００６３】
【数１３】
2006201468.tif 000015
３．（Ａ′,Ｂ′）が［数１３］の関係を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２０３〜Ｓ２０５）。
【００６４】
ゼロ知識証明は、文献「Ｒ.Ｃ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,１９９３」（以下、非特許文献４と称す）の方法を組み合わせて行うとする。
【００６５】
（Ａ′,Ｂ′）が［数１３］の関係を満たすことを示すためには、実際には（Ａ′,Ｂ′）＝（Ａ＋ｔ1Ｐ,Ｂ＋ｔ1Ｑ）または（Ａ′,Ｂ′）＝（−Ａ＋ｔ1Ｐ,−Ｂ＋（ｔ1＋１）Ｑ）が成り立つことを示せば良い。ここではその方法、すなわち［非特許文献３］および［非特許文献４］の方法を組み合わせたゼロ知識証明について、以下で与える［プロトコル１］を用いて具体的に説明する。なお［プロトコル１］は、Ｐを底としたＰ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）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００６７】
すると、暗号文変換装置３０（１）は、［数１３］に（Ａ,Ｂ）を入力した結果が（Ａ′,Ｂ′）であることを［プロトコル１］を用いて証明することができる。すなわち［プロトコル１］において、（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ′−Ａ,Ｂ′−Ｂ）,（Ａ′＋Ａ,Ｂ′＋Ｂ−Ｑ））,（ｅ,ｔ）←（ｅ1,ｔ1）と代入すれば良い。
【００６８】
ここでは、上記［プロトコル１］内の証明者、検証者はそれぞれ暗号文変換装置３０（１）、検証装置５０となる。暗号文変換装置３０（１）は処理Ｓ２０３、Ｓ２０４により（z0,ｚ1,ｃ0,ｃ1）を求めて、それを検証装置５０に送信する。検証装置５０はｃ0＋ｃ1＝Ｈ（ｚ0Ｐ−ｃ0Ｐ0‖ｚ0Ｑ−ｃ0Ｑ0‖ｚ1Ｐ−ｃ1Ｐ1‖ｚ1Ｑ−ｃ1Ｑ1）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する（Ｓ２０５）。
【００６９】
ここでは、検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。  
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを暗号文変換装置３０（２）に伝える。これを受けて暗号文変換装置３０（２）は（Ａ′,Ｂ′）を入力とし、以下の処理を行う。
１．ランダムビットｅ2および１以上ｐ以下の乱数ｔ2を生成する（Ｓ２０６）。
２．以下の［数１４］に従って暗号文（Ａ″,Ｂ″）を求め、当該暗号文を復号装置４０（１）,（２）および検証装置５０、さらに暗号文変換装置３０（１）に送信する（Ｓ２０７）。
【００７０】
【数１４】
2006201468.tif 000016
３．（Ａ″,Ｂ″）が［数１４］の関係を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２０８〜Ｓ２１０）。
【００７１】
ここで、当該ゼロ知識証明は、先の［プロトコル１］において、（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′,Ｂ″−Ｂ′）,（Ａ′＋Ａ″,Ｂ′＋Ｂ″−Ｑ））,（ｅ,ｔ）←（ｅ2,ｔ2）と代入すれば良い。
【００７２】
ここでは、検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したとして話を進める。
【００７３】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを復号装置４０（１）,（２）に伝える。これを受けて、復号装置４０（１）は（Ａ″,Ｂ″）を入力とし、ｘ1Ａ″を計算し、それを制御装置２０に送信する（Ｓ２１１）。同様に、復号装置４０（２）は（Ａ″,Ｂ″）を入力とし、ｘ2Ａ″を計算し、それを制御装置２０に送信する（Ｓ２１２）。
【００７４】
その後、復号装置４０（１）,（２）を証明者、検証装置５０を検証者として、当該送信情報ｘ1Ａ″,ｘ2Ａ″が正しい計算結果であることをゼロ知識非対話証明技術を用いて証明する（Ｓ２１３〜Ｓ２２２）。
【００７５】
当該証明方法は、具体的にはＰを底としたｘ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′）が成り立つかどうか検証し、成り立つときのみ当該証明事項を受理する。
【００７７】
ここでは、復号装置４０（１）は処理Ｓ２１３〜Ｓ２１６により（ｓ,ｚ）を求め、これを検証装置５０に送信し、検証装置５０が検証する（Ｓ２１７）。同様に、復号装置４０（２）は処理Ｓ２１８〜Ｓ２２１により（ｓ,ｚ）を求め、これを検証装置５０に送信し、検証装置５０が検証する（Ｓ２２２）。
【００７８】
検証装置５０は復号装置４０（１）,（２）の当該証明事項を受理したとして話を進める。検証装置５０は、送信情報ｘ1Ａ″,ｘ2Ａ″が正しいことを制御装置２０に伝える。
【００７９】
制御装置２０は、ｘ1Ａ″,ｘ2Ａ″が共に正しい計算結果である場合、ｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″を計算し（Ｓ２２３）、ｘＡ″＝Ｂ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”とする（Ｓ２２４〜Ｓ２２６）。その後、当該復号結果ｃ∈｛０,１｝について、［数１５］に従って暗号文（Ｃ,Ｄ）を求め（Ｓ２２７）、（Ｃ,Ｄ）を暗号文変換装置３０（２）と検証装置５０に送信する。
【００８０】
【数１５】
2006201468.tif 000017
【００８１】
ここで当該復号結果ｃについて、ｃ＝ａ＊ｅ1＊ｅ2（排他的論理和）が成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。なお、処理が冗長になるが、第１の実施の形態と同様に、1以上ｐ以下の乱数ｗを生成し、
【００８２】
【数１６】
2006201468.tif 000018
となるように（Ｃ，Ｄ）を計算してもよい。
【００８３】
暗号文変換装置３０（２）は（Ｃ,Ｄ），（Ａ′，Ｂ′），（Ａ″，Ｂ″），ｔ2，ｅ2を入力として、先ず以下の処理を行う。
１．１以上ｐ以下の乱数ｕ２を生成する（Ｓ２２８）。
２．以下の［数１７］に従って暗号文（Ｃ′,Ｄ′）を求め（Ｓ２２９）、当該暗号文を暗号文変換装置３０（１）および検証装置５０に送信する。  
【００８４】
【数１７】
2006201468.tif 000019
３．（Ｃ′,Ｄ′）が［数１７］を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２３０〜Ｓ２３２）。
【００８５】
ここで、上記ゼロ知識証明の具体的な方法を説明する。いま（Ｃ′,Ｄ′）が［数１７］の関係を満たしていることを示すためには、（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）または（Ｃ′,Ｄ′）＝（−Ｃ＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）が成り立つことを示すだけでは不十分であり、
「（Ａ″,Ｂ″）＝（Ａ′＋ｔ2Ｐ,Ｂ′＋ｔ2Ｑ）かつ（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）」
または
「（Ａ″,Ｂ″）＝（−Ａ′＋ｔ2Ｐ,−Ｂ′＋（ｔ2＋１）Ｑ）かつ
（Ｃ′,Ｄ′）＝（−Ｃ＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）」
であることを示さなければならない。これは
［証明１］
「（Ａ″,Ｂ″）＝（Ａ′＋ｔ2Ｐ,Ｂ′＋ｔ2Ｑ）または
（Ａ″,Ｂ″）＝（−Ａ′＋ｔ2Ｐ,−Ｂ′＋（ｔ2＋１）Ｑ）
かつ
［証明２］
「（Ａ″,Ｂ″）＝（Ａ′＋ｔ2Ｐ,Ｂ′＋ｔ2Ｑ）または
（Ｃ′,Ｄ′）＝（−Ｃ′＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）」
かつ
［証明３］
「（Ａ″,Ｂ″）＝（−Ａ′＋ｔ2Ｐ,−Ｂ′＋（ｔ2＋１）Ｑ）または
（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）」
かつ
［証明４］
「（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）または
（Ｃ′,Ｄ′）＝（−Ｃ′＋ｕ2Ｐ,−Ｄ′＋（ｕ2＋１）Ｑ）」
であることを示すのと等しい。
【００８６】
ここで、［証明１］は既に証明済みであるため、残りの［証明２］、［証明３］、［証明４］を証明すれば良い。これは［プロトコル１］を３回実行することで実現可能であり、具体的には、［証明２］、［証明３］、［証明４］を証明するためにそれぞれ
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′,Ｂ″−Ｂ′）,（Ｃ＋Ｃ′,Ｄ＋Ｄ′−Ｑ））,（ｅ,ｔ）←（ｅ2,ｔ2  or  ｕ2）,
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ′−Ｃ,Ｄ′−Ｄ）,（Ａ′＋Ａ″,Ｂ′＋Ｂ″−Ｑ））,（ｅ,ｔ）←（ｅ2,ｔ2  or  ｕ2）,
（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ′−Ｃ,Ｄ′−Ｄ）,（Ｃ＋Ｃ′,Ｄ＋Ｄ′−Ｑ））,（ｅ,ｔ）←（ｅ2,ｔ2）,
と代入すれば良い。
【００８７】
暗号文変換装置３０（２）および検証装置５０は、処理Ｓ２３０〜Ｓ２３２を３回（ｉ＝１,２,３）実行して上記［証明２］、［証明３］、［証明４］を証明する。
【００８８】
ここでは、検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したとして話を進める。すると（Ｃ′,Ｄ′）の復号結果ｃ′について、ｃ′＝ａ＊ｅ1＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【００８９】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを暗号文変換装置３０（１）に伝える。これを受けて暗号文変換装置３０（１）は（Ｃ′,Ｄ′），（Ａ′，Ｂ′），（Ａ″，Ｂ″），ｔ1，ｅ1を入力とし、先ず以下の処理を行う。
１．１以上ｐ以下の乱数ｕ1を生成する（Ｓ２３３）。
２．以下の［数１８］に従って暗号文（Ｃ″,Ｄ″）を求め、当該暗号文を制御装置１１０および検証装置５０に送信する（Ｓ２３４）。
【００９０】
【数１８】
2006201468.tif 000020
３．（Ｃ″,Ｄ″）が［数１８］の関係を満たしていることを検証装置５０にゼロ知識証明する（Ｓ２３５〜Ｓ２３７）。
【００９１】
ここで（Ｃ″,Ｄ″）が［数１８］の関係を満たしていることを示す方法は、前述の暗号文変換装置３０（２）での説明から明らかであるため省略する。
【００９２】
ここでは、検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。すると（Ｃ″,Ｄ″）の復号結果ｃ″について、ｃ″＝ａ＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【００９３】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを制御装置２０に伝える。これを受けて制御装置２０は、暗号文変換装置３０（１）より先に受信した（Ｃ″,Ｄ″）をａ＊ｂの暗号文として認め、必要に応じて出力する（Ｓ２３８）。
【００９４】
以上より、制御装置２０は、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ,ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができる。ここでａ,ｂの秘匿性は、暗号文変換装置３０（１）,（２）の生成したランダムビットｅ1,ｅ2の秘匿性に依存する。すなわち本実施の形態で示したプロトコルからｅ1およびｅ2を知ることが困難であれば、少なくとも暗号文変換装置３０（１）,（２）の不正結託がない限りはａ,ｂを知ることが困難となる。
【００９５】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第２の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,（２）の処理正当性を検出することが可能である。
【００９６】
また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【００９７】
なお、上記説明では、暗号文変換装置３０（２）が（Ｃ′,Ｄ′）を計算し、暗号文変換装置３０（１）が（Ｃ″,Ｄ″）を計算するとしたが、（Ｃ′,Ｄ′）を暗号文変換装置３０（１）が計算し、（Ｃ″,Ｄ″）を暗号文変換装置３０（２）が計算しても結果は同等である。
【００９８】
［第３の実施の形態］
これは、第１の実施の形態における課題について、第２の実施の形態とは別の方法（プロトコル）で解決するものである。
【００９９】
第３の実施の形態におけるシステム構成は、第２の実施の形態と同様となる。すなわち、図４に示すように同一のネットワーク１００で結ばれた、暗号文生成装置１０（１）,…,（Ｎ）、制御装置２０、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０からなる。
【０１００】
ここでは第２の実施の形態同様、排他的論理和を計算する処理における、暗号文変換装置および復号装置の処理正当性を検証することが可能な方法を説明する。
【０１０１】
まず、制御装置は、Ｅ（ａ，ｒ）（＝（Ａ，Ｂ））を暗号分変換装置３０（１）へ送信する。暗号文変換装置３０（１）は、（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、第２の実施の形態同様、以下の処理を行う。
１．ランダムビットｅ1および１以上ｐ以下の乱数ｔ1を生成する。
２．以下の［数１９］に従って暗号文（Ａ′,Ｂ′）を求め、当該暗号文を暗号文変換装置３０（２）および検証装置５０に送信する。
【０１０２】
【数１９】
2006201468.tif 000021
３．（Ａ′,Ｂ′）が［数１９］の関係を満たしていることを検証装置にゼロ知識証明する。  
当該ゼロ知識証明の方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１０３】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。  
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを暗号文変換装置３０（２）に伝える。これを受けて暗号文変換装置３０（２）は（Ａ′,Ｂ′）を入力とし、第２の実施の形態同様、以下の処理を行う。
１．ランダムビットｅ2および１以上ｐ以下の乱数ｔ2を生成する。
２．以下の［数２０］に従って暗号文（Ａ″,Ｂ″）を求め、当該暗号文を復号装置４０（１）,（２）および検証装置５０、さらに暗号文変換装置３０（１）に送信する。
【０１０４】
【数２０】
2006201468.tif 000022
３．（Ａ″,Ｂ″）が［数２０］の関係を満たしていることを検証装置５０にゼロ知識証明する。
【０１０５】
当該ゼロ知識証明の方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１０６】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したとして話を進める。  
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを復号装置４０（１）,（２）に伝える。これを受けて復号装置４０（１））は（Ａ″,Ｂ″）を入力とし、ｘ1Ａ′を計算し、それを制御装置２０に送信する。同様に、復号装置４０（２）は（Ａ″,Ｂ″）を入力とし、ｘ2Ａ″を計算し、それを制御装置２０に送信する。また当該送信情報が正しい計算結果であることをゼロ知識非対話証明技術を用いて検証装置５０に証明する。当該証明方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１０７】
検証装置５０は復号装置４０（１）,（２）の当該証明事項を受理したとして話を進める。  
制御装置５０はｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″を計算し、ｘＡ″＝ｘＢ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”とする。その後、当該復号結果ｃ∈｛０,１｝について、以下の［数２１］に従って暗号文（Ｃ,Ｄ）を求め、（Ｃ,Ｄ）を暗号文変換装置３０（２）に送信する。
【０１０８】
【数２１】
2006201468.tif 000023
ここで、当該復号結果ｃについて、ｃ＝ａ＊ｅ1＊ｅ2（排他的論理和）が成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１０９】
暗号文変換装置３０（２）は（Ｃ,Ｄ）（Ａ′，Ｂ′），（Ａ″，Ｂ″），ｔ2，ｅ2を入力として、先ず第２の実施の形態同様、以下の処理を行う。
１．１以上ｐ以下の乱数ｕ2を生成する。
２．以下の［数２２］に従って暗号文（Ｃ′,Ｄ′）を求め、当該暗号文を暗号文変換装置３０（１）および検証装置５０に送信する。
【０１１０】
【数２２】
2006201468.tif 000024
３．（Ｃ′,Ｄ′）が［数２２］を満たしていることを検証装置５０にゼロ知識証明する。
【０１１１】
第２の実施の形態で説明したように、いま（Ｃ′,Ｄ′）が［数２２］の関係を満たしていることを示すためには、（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ，Ｄ＋ｕ2Ｑ）または（Ｃ′，Ｄ′）＝（−Ｃ＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）が成り立つことを示すだけでは不十分であり、
「（Ａ″,Ｂ″）＝（Ａ′＋ｔ2Ｐ,Ｂ′＋ｔ2Ｑ）かつ
（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）」
または
「（Ａ″,Ｂ″）＝（−Ａ′＋ｔ2Ｐ,−Ｂ′＋（ｔ2＋１）Ｑ）かつ
（Ｃ′,Ｄ′）＝（−Ｃ＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）」
であることを示さなければならない。
【０１１２】
これを示すために、本実施の形態では、第２の実施の形態で示した方法とは異なる方法を用いる。これについて、以下で与える［プロトコル３］を用いて具体的に説明する。なお、［プロトコル３］は、
１．Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、かつ、Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、
または、
２．Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、かつ、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい、
ことをゼロ知識証明技術を用いて証明するプロトコルである。
【０１１３】
［プロトコル３］
入力：（（Ｇ,ｐ,Ｐ,Ｑ）,（Ｐ0,Ｑ0）,（Ｐ1,Ｑ1）,（Ｐ0′,Ｑ0′）,（Ｐ1′,Ｑ1′）
証明者の秘密情報：（ｅ,ｔ,ｔ′）
１．証明者は以下に従って（ｚ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′）,（ｅ,ｔ，ｔ′））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′,Ｂ″−Ｂ′）,（Ａ′＋Ａ″,Ｂ′＋Ｂ″−Ｑ）,（Ｃ′−Ｃ,Ｄ′−Ｄ）,（Ｃ＋Ｃ′,Ｄ＋Ｄ′−Ｑ））,（ｅ2,ｔ2,ｕ2）），（ｅ，ｔ）←（ｅ2，ｕ2）と代入すれば良い。
【０１１５】
検証装置５０（検証者）は暗号文変換装置３０（２）（証明者）の当該証明事項を受理したとして話を進める。すると（Ｃ′,Ｄ′）の復号結果ｃ′について、ｃ′＝ａ＊ｅ1＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１１６】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを暗号文変換装置３０（１）に伝える。これを受けて暗号文変換装置１は、暗号分変換装置３０（２）より先に受信した（Ｃ′,Ｄ′）（Ａ′，Ｂ′）,（Ａ″，Ｂ″），ｔ1，ｅ1を入力とし、まず第２の実施の形態同様、以下の処理を行う。
１．１以上ｐ以下の乱数ｕ1を生成する。
２．以下の［数２３］に従って暗号文（Ｃ″,Ｄ″）を求め、当該暗号文を制御装置２０および検証装置５０に送信する。
【０１１７】
【数２３】
2006201468.tif 000025
３．（Ｃ″,Ｄ″）が［数２３］の関係を満たしていることを検証装置にゼロ知識証明する。  
ここで（Ｃ″,Ｄ″）が［数２３］の関係を満たしていることを示す方法は、前述の暗号文変換装置３０（２）での説明から明らかであるため省略する。
【０１１８】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。すると（Ｃ″,Ｄ″）の復号結果ｃ″について、ｃ″＝ａ＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１１９】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを制御装置２０に伝える。これを受けて制御装置２０は、暗号文変換装置３０（１）より先に受信した（Ｃ″,Ｄ″）をａ＊ｂの暗号文として認める。
【０１２０】
以上より、制御装置２０は、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ．ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができた。ここでａ,ｂの秘匿性は、暗号文変換装置３０（１）,（２）の生成したランダムビットｅ1，ｅ2の秘匿性に依存する。すなわち本実施の形態で示したプロトコルからｅ1およびｅ2を知ることが困難であれば、少なくとも暗号文変換装置３０（１）,（２）の不正結託がない限りはａ,ｂを知ることが困難となる。また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【０１２１】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第３の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,（２）の処理正当性を検出することが可能である。
【０１２２】
［第４の実施の形態］
これは、第１の実施の形態における課題について、第２の実施の形態や第３の実施の形態とは更に別の方法（プロトコル）で解決するものである。
【０１２３】
第４の実施の形態におけるシステム構成は、第２の実施の形態と同様となる。すなわち、図４に示すように同一のネットワーク１００で結ばれた、暗号文生成装置１０（１）,…,（Ｎ）、制御装置２０、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０からなる。
【０１２４】
ここでは第２の実施の形態や第３の実施の形態同様、排他的論理和を計算する処理における、暗号文変換装置および復号装置の処理正当性を検証することが可能な方法を説明する。
【０１２５】
まず、制御装置２０は、Ｅ（ａ，ｒ）１＝（Ａ，Ｂ）を暗号文変換装置３０（１）へ送信する。暗号文変換装置３０（１）は、Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力とし、第２の実施の形態同様、以下の処理を行う。
１．ランダムビットｅ1および１以上ｐ以下の乱数ｔ1を生成する。
２．以下の［数２４］に従って暗号文（Ａ′,Ｂ′）を求め、当該暗号文を暗号文変換装置３０（２）および検証装置５０に送信する。
【０１２６】
【数２４】
2006201468.tif 000026
３．（Ａ′,Ｂ′）が［数２４］の関係を満たしていることを検証装置５０にゼロ知識証明する。  
当該ゼロ知識証明の方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１２７】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。  
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを暗号文変換装置３０（２）に伝える。これを受けて暗号文変換装置３０（２）は（Ａ′,Ｂ′）を入力とし、第２の実施の形態同様、以下の処理を行う。
１．ランダムビットｅ2および１以上ｐ以下の乱数ｔ2を生成する。
２．以下の［数２５］に従って暗号文（Ａ″,Ｂ″）を求め、当該暗号文を復号装置４０（１）,（２）および検証装置５０、さらに暗号文変換装置３０（１）に送信する。
【０１２８】
【数２５】
2006201468.tif 000027
３．（Ａ″,Ｂ″）が［数２５］の関係を満たしていることを検証装置５０にゼロ知識証する。  
当該ゼロ知識証明の方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１２９】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したとして話を進める。  
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを復号装置４０（１）,（２）に伝える。これを受けて復号装置４０（１）は（Ａ″,Ｂ″）を入力とし、ｘ1Ａ′を計算し、それを制御装置２０に送信する。同様に、復号装置４０（２）は（Ａ″,Ｂ″）を入力とし、ｘ2Ａ″を計算し、それを制御装置２０に送信する。また当該送信情報が正しい計算結果であることをゼロ知識非対話証明技術を用いて検証装置５０に証明する。当該証明方法は、第２の実施の形態と同様であるため、説明を省略する。
【０１３０】
検証装置５０は復号装置４０（１）,（２）の当該証明事項を受理したとして話を進める。  
制御装置５０はｘＡ″＝ｘ1Ａ″＋ｘ2Ａ″を計算し、ｘＡ″＝ｘＢ″であれば（Ａ″,Ｂ″）の復号結果ｃを“０”、それ以外（ｘＡ″＝Ｂ″−Ｑ）であれば“１”とする。その後、当該復号結果ｃ∈｛０,１｝について、以下の［数２６］に従って暗号文（Ｃ,Ｄ）を求め、（Ｃ,Ｄ）を暗号文変換装置３０（２）に送信する。
【０１３１】
【数２６】
2006201468.tif 000028
ここで、当該復号結果ｃについて、ｃ＝ａ＊ｅ1＊ｅ2（排他的論理和）が成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１３２】
暗号文変換装置３０（２）はＥ（ｂ,ｓ）（＝（Ｘ,Ｙ））,（Ｃ,Ｄ），（Ａ′，Ｂ′），（Ａ″，Ｂ″），ｔ2，ｅ2を入力として、まず、第２の実施の形態同様、以下の処理を行う。
１．１以上ｐ以下の乱数ｕ2を生成する。
２．以下の［数２７］に従って暗号文（Ｃ′,Ｄ′）を求め、当該暗号文を暗号文変換装置３０（１）および検証装置５０に送信する。
【０１３３】
【数２７】
2006201468.tif 000029
３．（Ｃ′,Ｄ′）が［数２７］を満たしていることを検証装置５０にゼロ知識証明する。
【０１３４】
第２の実施の形態で説明したように、いま（Ｃ′,Ｄ′）が［数２７］の関係を満たしていることを示すためには、（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ，Ｄ＋ｕ2Ｑ）または（Ｃ′，Ｄ′）＝（−Ｃ＋ｕ2Ｐ,−Ｄ＋（ｕ2＋１）Ｑ）が成り立つことを示すだけでは不十分であり、
「（Ａ″,Ｂ″）＝（Ａ′＋ｔ2Ｐ,Ｂ′＋ｔ2Ｑ）かつ
（Ｃ′,Ｄ′）＝（Ｃ＋ｕ2Ｐ,Ｄ＋ｕ2Ｑ）」
または
「（Ａ″,Ｂ″）＝（−Ａ′＋ｔ2Ｐ,−Ｂ′＋（ｔ2＋１）Ｑ）かつ
（Ｃ′,Ｄ′）＝（−Ｃ＋ｕ2Ｐ＋Ｘ,−Ｄ＋（ｕ2＋１）Ｑ）」
であることを示さなければならない。
【０１３５】
これを示すために、本実施の形態では、第２の実施の形態や第３の実施の形態で示した方法とは異なる方法を用いる。これについて、以下で与える［プロトコル４］を用いて具体的に説明する。なお、［プロトコル４］は、
１.Ｐを底としたＰ0の離散対数とＱを底としたＱ0の離散対数が等しい、
あるいは、
２.Ｐを底としたＰ1の離散対数とＱを底としたＱ1の離散対数が等しい、
ことが既にゼロ知識証明されているとき（該離散対数をｓとする）、
１が真であるときに限り、Ｐを底としたＰ0′の離散対数とＱを底としたＱ0′の離散対数が等しい、
逆に２が真であるときに限り、Ｐを底としたＰ1′の離散対数とＱを底としたＱ1′の離散対数が等しい（ともに該離散対数をｔとする）、
ことをゼロ知識証明技術を用いて証明可能なプロトコルである。
［プロトコル４］
入力：（（Ｇ,ｐ,Ｐ,Ｑ），（Ｐ0,Ｑ0），（Ｐ1,Ｑ1），（Ｐ0′,Ｑ0′），（Ｐ1′,Ｑ1′））
証明者の秘密情報：（ｅ,ｓ,ｔ）
１．証明者は以下に従って（ｚ0,ｚ1,ｃ0,ｃ1）を求め、それを検証者に送信する。
（ａ）ε＝Ｈ（Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′‖）を計算する。
（ｂ）１以上ｐ以下の乱数ｒ,ｒ′,ｃ1-eを生成する。
（ｃ）ＲP,e＝ｒＰ,ＲQ,e＝ｒＱ,ＲP,1-e＝ｒ′Ｐ−ｃ1-e（εＰ1-e+Ｐ′1-e）,ＲQ,1-e＝ｒ′Ｑ−ｃ1-e（εＱ1-e+Ｑ′1-e）,ｃe＝Ｈ（ＲP,0‖ＲQ,0‖ＲP,1‖ＲQ,1）−ｃ1-e,ｚe＝ｒ＋ｃe（εｓ+ｔ）,ｚ1-e＝ｒ′を計算する。ここでＨは汎用一方向性ハッシュ関数とし、“‖”はデータの連結を意味する。
２．検証者はε′＝Ｈ（Ｐ0‖Ｑ0‖Ｐ1‖Ｑ1‖Ｐ0′‖Ｑ0′‖Ｐ1′‖Ｑ1′）を計算し、ｃ0＋ｃ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′）,（ｅ,ｓ，ｔ））←（（Ｇ,ｐ,Ｐ,Ｑ）,（Ａ″−Ａ′,Ｂ″−Ｂ′）,（Ａ′＋Ａ″,Ｂ′＋Ｂ″−Ｑ）,（Ｃ′−Ｃ,Ｄ′−Ｄ）,（Ｃ＋Ｃ′,Ｄ＋Ｄ′−Ｑ））,（ｅ2,ｔ2,ｕ2）），（ｅ，ｔ）←（ｅ2，ｕ2）と代入すれば良い。
【０１３７】
検証装置５０（検証者）は暗号文変換装置３０（２）（証明者）の当該証明事項を受理したとして話を進める。すると（Ｃ′,Ｄ′）の復号結果ｃ′について、ｃ′＝ａ＊ｅ1＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１３８】
検証装置５０は暗号文変換装置３０（２）の当該証明事項を受理したことを暗号文変換装置３０（１）に伝える。これを受けて暗号文変換装置３０（１）は、暗号文変換装置３０（２）より先に受信した（Ｃ′,Ｄ′）（Ａ′，Ｂ′）（Ａ″，Ｂ″），ｔ1，ｅ1を入力とし、先ず、第２の実施の形態同様、以下の処理を行う。
１．１以上ｐ以下の乱数ｕ1を生成する。
２．以下の［数２８］に従って暗号文（Ｃ″,Ｄ″）を求め、当該暗号文を制御装置２０および検証装置５０に送信する。
【０１３９】
【数２８】
2006201468.tif 000030
３．（Ｃ″,Ｄ″）が［数２８］の関係を満たしていることを検証装置５０にゼロ知識証明する。  
ここで（Ｃ″,Ｄ″）が［数２８］の関係を満たしていることを示す方法は、前述の暗号文変換装置３０（２）での説明から明らかであるため省略する。
【０１４０】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したとして話を進める。すると（Ｃ″,Ｄ″）の復号結果ｃ″について、ｃ″＝ａ＊ｂが成り立つ。このことは第１の実施の形態から明らかであり、ここではその説明を省略する。
【０１４１】
検証装置５０は暗号文変換装置３０（１）の当該証明事項を受理したことを制御装置２０に伝える。これを受けて制御装置２０は、暗号文変換装置３０（１）より先に受信した（Ｃ″,Ｄ″）をａ＊ｂの暗号文として認める。
【０１４２】
以上より、制御装置２０は、暗号文変換装置３０（１）,（２）、復号装置４０（１）,（２）、および検証装置５０の協力により、ａの暗号文Ｅ（ａ．ｒ）およびｂの暗号文Ｅ（ｂ,ｓ）から、ａ,ｂを知ることなくａ＊ｂの暗号文を計算することができ、更には当該暗号文を取得することができる。ここでａ,ｂの秘匿性は、暗号文変換装置３０（１）,（２）の生成したランダムビットｅ1，ｅ2の秘匿性に依存する。すなわち本実施の形態で示したプロトコルからｅ1およびｅ2を知ることが困難であれば、少なくとも暗号文変換装置３０（１）,（２）の不正結託がない限りはａ,ｂを知ることが困難となる。また、本実施の形態では暗号文変換装置が２台の例を挙げたが、本プロトコルでは暗号文変換装置を３台以上に拡張することも容易である（ただしその方法は明らかであるため省略する）。そして当該拡張により暗号文変換装置の結託に対する耐性が高まる。これは言い換えればａ,ｂの秘匿性を効果的に高めることができる。
【０１４３】
なお、図１に示した第１の実施の形態のシステム構成に検証装置５０を追加すれば、本第４の実施の形態同様に、暗号文変換装置３０や復号装置４０（１）,（２）の処理正当性を検出することが可能である。
【０１４４】
また、第１、第２、第３あるいは第４の実施の形態において、ａi，ｂi∈｛０,１｝（ｉ＝１，２，…，ｎ）の暗号文（Ａi，Ｂi），（Ｘi，Ｙi）を時間をずらして順次入力し、順次、各装置で所定の処理を実行することで、複数組のａi＊ｂiの暗号文をパイプライン形式に計算することが可能である。
【０１４５】
なお、図１、図４などで示したシステムにおける各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２、図３、図５などで示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【０１４６】
【図１】本発明の第１の実施の形態のシステム構成例を示す図。
【図２】第１の実施の形態において公開鍵（Ｇ,ｐ,Ｐ,Ｑ）を生成する処理シーケンス例を示す図。
【図３】第１の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図４】本発明の第２の実施の形態、第３の実施の形態および第４の実施の形態のシステム構成例を示す図。
【図５Ａ】第２の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図５Ｂ】同じく第２の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図５Ｃ】同じく第２の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【図５Ｄ】同じく第２の実施の形態においてａ,ｂの暗号文からａ＊ｂの暗号文を求める処理シーケンス例を示す図。
【符号の説明】
【０１４７】
１０  暗号文生成装置
２０  制御装置
３０  暗号文変換装置
４０  復号装置
５０  検証装置
１００  ネットワーク
【図１】
2006201468.tif 000039
【図２】
2006201468.tif 000040
【図３】
2006201468.tif 000041
【図４】
2006201468.tif 000042
【図５Ａ】
2006201468.tif 000043
【図５Ｂ】
2006201468.tif 000044
【図５Ｃ】
2006201468.tif 000045
【図５Ｄ】
2006201468.tif 000046