(57)【要約】【課題】準同型暗号処理により平文を暗号化した対象暗号文が正当であることを、簡易に証明する。【解決手段】実施形態の証明装置は、コミットメント生成部と、レスポンス生成部と、を備える。コミットメント生成部は、ランダムに選択された検証値からコミットメント文を生成して、対象暗号文が正当であることを検証する検証装置へと送信する。レスポンス生成部は、取得したチャレンジ値と平文と検証値とを合成したレスポンス値を生成して、検証装置へと送信する。レスポンス生成部は、レスポンス値を用いた第一の演算の結果が、チャレンジ値と対象暗号文とコミットメント文とを第二の演算で処理した結果と同一となる第三の演算により、レスポンス値を生成する。【選択図】図２
2014220661.tif 000002
【特許請求の範囲】
【請求項１】
準同型暗号処理により平文を暗号化した対象暗号文が正当であることを証明する証明装置であって、
ランダムに選択された検証値からコミットメント文を生成して、前記対象暗号文が正当であることを検証する検証装置へと送信するコミットメント生成部と、
取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を生成して、前記検証装置へと送信するレスポンス生成部と、
を備え、
前記レスポンス生成部は、レスポンス値を用いた第一の演算の結果が、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算で処理した結果と同一となる第三の演算により、前記レスポンス値を生成する
証明装置。
【請求項２】
前記コミットメント生成部は、前記検証値を前記準同型暗号処理により暗号化したコミットメント文を生成して、前記検証装置へと送信し、
前記レスポンス生成部は、演算結果を前記準同型暗号処理により暗号化した暗号文が、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを予め定められた準同型演算により合成した暗号文と同一となる演算により、前記レスポンス値を生成する
請求項１に記載の証明装置。
【請求項３】
前記コミットメント文をハッシュ関数に入力して前記チャレンジ値を生成する証明側チャレンジ生成部をさらに備える
請求項１または２に記載の証明装置。
【請求項４】
前記準同型暗号処理は、モディファイドエルガマル暗号処理である
請求項１から３の何れか一項に記載の証明装置。
【請求項５】
前記コミットメント生成部は、２つの検証値ａ、ｂと、前記モディファイドエルガマル暗号処理で用いる公開鍵ＰＫおよび巡回群の生成元ｇとに基づき、下記式（１１）および下記式（１２）で表される２つのコミットメント文Ａ、Ｂを生成し
Ａ＝ｇａ  …（１１）
Ｂ＝ｇｂ・ＰＫａ  …（１２）
前記レスポンス生成部は、前記対象暗号文の生成に用いた乱数ｒおよび平文ｍと、チャレンジ値ｅと、前記モディファイドエルガマル暗号処理で用いる位数ｑとに基づき、下記式（１３）および下記式（１４）で表される２つのレスポンス値Ｚ１、Ｚ２を生成する
Ｚ１＝（ａ＋ｅ・ｒ）  ｍｏｄ  ｑ  …（１３）
Ｚ２＝（ｂ＋ｅ・ｍ）  ｍｏｄ  ｑ  …（１４）
請求項４に記載の証明装置。
【請求項６】
前記証明装置は、同一の前記準同型暗号処理により複数の平文を暗号化した複数の対象暗号文が正当であることを証明するものであって、
ランダムに選択された合成検証値を前記準同型暗号処理により暗号化した合成コミットメント文を生成して、前記検証装置へと送信する合成コミットメント生成部と、
取得した合成チャレンジ値と前記複数の平文と前記合成検証値とを合成した合成レスポンス値を生成して、前記検証装置へと送信する合成レスポンス生成部と、
をさらに備え、
前記合成レスポンス生成部は、演算結果を前記準同型暗号処理により暗号化した暗号文が、前記合成チャレンジ値と前記複数の対象暗号文と前記合成コミットメント文とを予め定められた準同型演算により合成した暗号文と同一となる演算により、前記合成レスポンス値を生成する
請求項１から５の何れか一項に記載の証明装置。
【請求項７】
前記準同型暗号処理が、モディファイドエルガマル暗号処理である場合、
前記コミットメント生成部は、２つの合成検証値ａｔｔｌ、ｂｔｔｌと、前記モディファイドエルガマル暗号処理で用いる公開鍵ＰＫおよび巡回群の生成元ｇとに基づき、下記式（２１）および下記式（２２）で表される２つの合成コミットメント文Ａｔｔｌ、Ｂｔｔｌを生成し、
Ａｔｔｌ＝ｇ＾ａｔｔｌ  …（２１）
Ｂｔｔｌ＝ｇ＾ｂｔｔｌ・ＰＫ＾ａｔｔｌ  …（２２）
前記合成レスポンス生成部は、前記複数の対象暗号文の生成に用いたｋ個（ｋは２以上の整数）の乱数ｒ１，ｒ２，…，ｒｋおよびｋ個の平文ｍ１，ｍ２，…，ｍｋと、合成チャレンジ値ｅｔｔｌと、前記モディファイドエルガマル暗号処理で用いる位数ｑとに基づき、下記式（２３）および下記式（２４）で表される２つの合成レスポンス値Ｚ１，ｔｔｌ、Ｚ２，ｔｔｌを生成する
Ｚ１，ｔｔｌ＝ａｔｔｌ＋ｅｔｔｌ・（（ｒ１＋ｒ２＋…＋ｒｋ）  ｍｏｄ  ｑ））  ｍｏｄ  ｑ    …（２３）
Ｚ２，ｔｔｌ＝ｂｔｔｌ＋ｅｔｔｌ・（（ｍ１＋ｍ２＋…＋ｍｋ）  ｍｏｄ  ｑ））  ｍｏｄ  ｑ    …（２４）
請求項６に記載の証明装置。
【請求項８】
前記証明装置は、
前記複数の対象暗号文のそれぞれに対応する、複数の前記コミットメント生成部と、
前記複数の対象暗号文のそれぞれに対応する、複数の前記レスポンス生成部と、
を備える請求項６または７に記載の証明装置。
【請求項９】
準同型暗号処理により平文を暗号化した対象暗号文を生成する暗号化装置と、
前記暗号化装置により生成した前記対象暗号文が正当であることを証明する、請求項１から８の何れか一項に記載の証明装置と、
を備える出力装置。
【請求項１０】
準同型暗号処理により平文を暗号化した対象暗号文が正当であることを検証する検証装置であって、
前記対象暗号文が正当であることを証明する証明装置から、ランダムに選択された検証値から生成されたコミットメント文、および、取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を取得する取得部と、
前記レスポンス値を第一の演算により演算した結果と、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算により演算した結果とが一致した場合に、前記対象暗号文が正当であると判定する検証部と、
を備え、
前記レスポンス値が予め定められた手順で生成されていた場合に、前記第一の演算の結果と前記第二の演算の結果とは同一となる
検証装置。
【請求項１１】
前記取得部は、前記証明装置から前記検証値を前記準同型暗号処理により暗号化した前記コミットメント文、および、前記レスポンス値を取得し、
前記検証部は、前記レスポンス値を前記準同型暗号処理により暗号化した暗号文と、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを予め定められた準同型演算により合成した暗号文とが一致した場合に、前記対象暗号文が正当であると判定し、
前記検証部は、前記レスポンス値が予め定められた手順で生成されていた場合に、前記レスポンス値を前記準同型暗号処理により暗号化した暗号文と演算結果が同一となる準同型演算により、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを合成する
請求項１０に記載の検証装置。
【請求項１２】
前記コミットメント文をハッシュ関数に入力して前記チャレンジ値を生成する検証側チャレンジ生成部をさらに備える
請求項１０または１１に記載の検証装置。
【請求項１３】
前記準同型暗号処理は、モディファイドエルガマル暗号処理である
請求項１０から１２の何れか一項に記載の検証装置。
【請求項１４】
前記取得部は、２つの検証値ａ、ｂと、前記モディファイドエルガマル暗号処理で用いる公開鍵ＰＫおよび巡回群の生成元ｇとに基づく、下記式（３１）および下記式（３２）で表される２つのコミットメント文Ａ、Ｂを取得し、
Ａ＝ｇａ  …（３１）
Ｂ＝ｇｂ・ＰＫａ  …（３２）
さらに、前記取得部は、前記対象暗号文の生成に用いた乱数ｒおよび平文ｍと、チャレンジ値ｅと、前記モディファイドエルガマル暗号処理で用いる位数ｑとに基づく、下記式（３３）および下記式（３４）で表される２つのレスポンス値Ｚ１、Ｚ２を取得する
Ｚ１＝（ａ＋ｅ・ｒ）  ｍｏｄ  ｑ  …（３３）
Ｚ２＝（ｂ＋ｅ・ｍ）  ｍｏｄ  ｑ  …（３４）
請求項１３に記載の検証装置。
【請求項１５】
前記対象暗号文を下記式（３５）および式（３６）で表されるＣ１およびＣ２とした場合、
Ｃ１＝ｇｒ  …（３５）
Ｃ２＝ｇｍ・ＰＫｒ  …（３６）
前記検証部は、下記式（３７）が真の場合に、前記対象暗号文が正当であると判定する
（ｇ＾Ｚ１＝＝Ａ・Ｃ１ｅ）∧（ｇ＾Ｚ２・ＰＫ＾Ｚ１＝＝Ｂ・Ｃ２ｅ）  …（３７）
請求項１４に記載の検証装置。
【請求項１６】
前記検証装置は、同一の準同型暗号処理により複数の平文を暗号化した複数の対象暗号文が正当であることを検証するものであって、
前記証明装置から、ランダムに選択された合成検証値を前記準同型暗号処理により暗号化した合成コミットメント文、および、取得した合成チャレンジ値と前記複数の平文と前記合成検証値とを合成した合成レスポンス値を取得する合成取得部と、
前記合成レスポンス値を前記準同型暗号処理により暗号化した暗号文と、前記合成チャレンジ値と前記複数の対象暗号文と前記合成コミットメント文とを予め定められた準同型演算により合成した暗号文とが一致した場合に、前記複数の対象暗号文が正当であると判定する合成検証部と、
を備え、
前記合成検証部は、前記合成レスポンス値を前記準同型暗号処理により暗号化した暗号文と演算結果が同一となる準同型演算により、前記合成チャレンジ値と前記複数の対象暗号文と前記合成コミットメント文と合成する
請求項１０から１５の何れか一項に記載の検証装置。
【請求項１７】
前記準同型暗号処理が、モディファイドエルガマル暗号処理である場合、
前記合成取得部は、２つの合成検証値ａｔｔｌ、ｂｔｔｌと、前記モディファイドエルガマル暗号処理で用いる公開鍵ＰＫおよび巡回群の生成元ｇとに基づく、下記式（４１）および下記式（４２）で表される２つの合成コミットメント文Ａｔｔｌ、Ｂｔｔｌを取得し、
Ａｔｔｌ＝ｇ＾ａｔｔｌ  …（４１）
Ｂｔｔｌ＝ｇ＾ｂｔｔｌ・ＰＫ＾ａｔｔｌ  …（４２）
さらに、前記合成取得部は、前記複数の対象暗号文の生成に用いたｋ個（ｋは２以上の整数）の乱数ｒ１，ｒ２，…，ｒｋおよびｋ個の平文ｍ１，ｍ２，…，ｍｋと、合成チャレンジ値ｅｔｔｌと、前記モディファイドエルガマル暗号処理で用いる位数ｑとに基づく、下記式（４３）および下記式（４４）で表される２つの合成レスポンス値Ｚ１，ｔｔｌ、Ｚ２，ｔｔｌを取得する
Ｚ１，ｔｔｌ＝ａｔｔｌ＋ｅｔｔｌ・（（ｒ１＋ｒ２＋…＋ｒｋ）  ｍｏｄ  ｑ））  ｍｏｄ  ｑ    …（４３）
Ｚ２，ｔｔｌ＝ｂｔｔｌ＋ｅｔｔｌ・（（ｍ１＋ｍ２＋…＋ｍｋ）  ｍｏｄ  ｑ））  ｍｏｄ  ｑ    …（４４）
請求項１６に記載の検証装置。
【請求項１８】
対象暗号文を下記式（４５）および式（４６）で表されるＣ１，ｉおよびＣ２，ｉとした場合（ｉは１以上ｋ以下の整数）、
Ｃ１，ｉ＝ｇ＾ｒｉ  …（４５）
Ｃ２，ｉ＝ｇ＾ｍｉ・ＰＫ＾ｒｉ  …（４６）
前記検証部は、下記式（４７）が真の場合に、前記複数の対象暗号文が正当であると判定する
（ｇ＾Ｚ１，ｔｔｌ＝＝Ａｔｔｌ・（Ｃ１，１・Ｃ１，２・…・Ｃ１，ｋ）＾ｅｔｔｌ）∧（ｇ＾Ｚ２，ｔｔｌ・ＰＫ＾Ｚ１，ｔｔｌ＝＝Ｂｔｔｌ・（Ｃ２，１・Ｃ２，２・…・Ｃ２，ｋ）＾ｅｔｔｌ）    …（４７）
請求項１７に記載の検証装置。
【請求項１９】
前記検証装置は、
前記複数の対象暗号文のそれぞれに対応する、複数の前記取得部と、
前記複数の対象暗号文のそれぞれに対応する、複数の前記検証部と、
を備える請求項１６から１８の何れか一項に記載の検証装置。
【請求項２０】
準同型暗号処理により平文を暗号化した対象暗号文を復号する復号装置と、
前記復号装置により復号される前記対象暗号文が正当であることを検証する、請求項１０から１９の何れか一項に記載の検証装置と、
を備え、
前記復号装置は、前記検証装置により前記対象暗号文が正当であると判定されたことを条件として、前記対象暗号文を復号する
入力装置。
【請求項２１】
準同型暗号処理により平文を暗号化した対象暗号文が正当であることを証明する証明方法であって、
ランダムに選択された検証値からコミットメント文を生成して、前記対象暗号文が正当であることを検証する検証装置へと送信するコミットメント生成ステップと、
取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を生成して、前記検証装置へと送信するレスポンス生成ステップと、
を含み、
前記レスポンス生成ステップでは、レスポンス値を用いた第一の演算の結果が、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算で処理した結果と同一となる第三の演算により、前記レスポンス値を生成する
証明方法。
【請求項２２】
準同型暗号処理により平文を暗号化した対象暗号文が正当であることを検証する検証方法であって、
前記対象暗号文が正当であることを証明する証明装置から、ランダムに選択された検証値から生成されたコミットメント文、および、取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を取得する取得ステップと、
前記レスポンス値を第一の演算により演算した結果と、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算により演算した結果とが一致した場合に、前記対象暗号文が正当であると判定する検証ステップと、
を含み、
前記レスポンス値が予め定められた手順で生成されていた場合に、前記第一の演算の結果と前記第二の演算の結果とは同一となる
検証方法。
【請求項２３】
コンピュータを、準同型暗号処理により平文を暗号化した対象暗号文が正当であることを証明する証明装置として機能させるためのプログラムであって、
前記コンピュータを、
ランダムに選択された検証値からコミットメント文を生成して、前記対象暗号文が正当であることを検証する検証装置へと送信するコミットメント生成部と、
取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を生成して、前記検証装置へと送信するレスポンス生成部と、
して機能させ、
前記レスポンス生成部は、レスポンス値を用いた第一の演算の結果が、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算で処理した結果と同一となる第三の演算により、前記レスポンス値を生成する
プログラム。
【請求項２４】
コンピュータを、準同型暗号処理により平文を暗号化した対象暗号文が正当であることを検証する検証装置として機能させるためのプログラムであって、
前記コンピュータを、
前記対象暗号文が正当であることを証明する証明装置から、ランダムに選択された検証値から生成されたコミットメント文、および、取得したチャレンジ値と前記平文と前記検証値とを合成したレスポンス値を取得する取得部と、
前記レスポンス値を第一の演算により演算した結果と、前記チャレンジ値と前記対象暗号文と前記コミットメント文とを第二の演算により演算した結果とが一致した場合に、前記対象暗号文が正当であると判定する検証部と、
して機能させ、
前記レスポンス値が予め定められた手順で生成されていた場合に、前記第一の演算の結果と前記第二の演算の結果とは同一となる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、証明装置、出力装置、検証装置、入力装置、証明方法、検証方法およびプログラムに関する。
【背景技術】
【０００２】
ある問題の解答を知っていることを検証するプロトコルとして、非対話ゼロ知識証明が知られている。この非対話ゼロ知識証明を公開鍵暗号に組み合わせることにより、暗号文の正当性を検証した後に暗号文を復号することができる。これにより、公開鍵暗号の安全性をより高くすることができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】David  Bernhard,  Veronique  Cortier,  Olivier  Pereira,  Ben  Smyth  and  Bogdan  Warinschi,  “Adapting  Helios  for  provable  ballot  privacy”,  16th  European  Symposium  on  Research  in  Computer  Security  2011,  LNCS  6879,  Springer,  pp.335-354
【非特許文献２】Moni  Naor  and  Moti  Yung,  “Public-key  cryptosystems  provably  secure  against  chosen  ciphertext  attacks”,  STOC  1990,  pp.427-437,  ACM  Press,  1990
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非対話ゼロ知識証明を公開鍵暗号と組み合わせると、暗号化および復号の処理に多くの計算コストを必要とするだけでなく、暗号文長も増大するという問題があった。
【課題を解決するための手段】
【０００５】
実施形態の証明装置は、準同型暗号処理により平文を暗号化した対象暗号文が正当であることを証明する。証明装置は、コミットメント生成部と、レスポンス生成部と、を備える。コミットメント生成部は、ランダムに選択された検証値からコミットメント文を生成して、対象暗号文が正当であることを検証する検証装置へと送信する。レスポンス生成部は、取得したチャレンジ値と平文と検証値とを合成したレスポンス値を生成して、検証装置へと送信する。レスポンス生成部は、レスポンス値を用いた第一の演算の結果が、チャレンジ値と対象暗号文とコミットメント文とを第二の演算で処理した結果と同一となる第三の演算により、レスポンス値を生成する。
【図面の簡単な説明】
【０００６】
【図１】第１実施形態に係る暗号処理システムの構成図。
【図２】第１実施形態に係る証明装置および検証装置の構成図。
【図３】第１実施形態に係る暗号処理システムの処理フロー図。
【図４】第２実施形態に係る証明装置および検証装置の構成図。
【図５】第３実施形態に係る暗号処理システムの構成図。
【図６】第３実施形態に係る証明装置の構成図。
【図７】第３実施形態に係る検証装置の構成図。
【図８】第３実施形態に係る暗号化装置および証明装置の処理のフロー図。
【図９】第３実施形態に係る復号装置および検証装置の処理のフロー図。
【図１０】第１〜第３実施形態に係る出力装置および入力装置の構成図。
【発明を実施するための形態】
【０００７】
（第１実施形態）
図１は、第１実施形態に係る暗号処理システムの構成を示す図である。第１実施形態に係る暗号処理システム１０は、出力装置１１と、入力装置１２とを備える。出力装置１１と入力装置１２との間は、ネットワーク等により接続されて情報のやり取りがされる。
【０００８】
出力装置１１は、暗号化装置２０と、証明装置３０とを備える。入力装置１２は、復号装置４０と、検証装置５０とを備える。
【０００９】
暗号化装置２０は、準同型暗号により平文を暗号化した暗号文を生成する。そして、暗号化装置２０は、生成した暗号文を復号装置４０に送信する。復号装置４０は、出力装置１１の暗号化装置２０から暗号文を受信する。そして、復号装置４０は、受信した暗号文を復号して平文を出力する。
【００１０】
本実施形態においては、暗号化装置２０および復号装置４０は、モディファイドエルガマル暗号を用いた処理を行う。モディファイドエルガマル暗号を用いる場合、暗号化装置２０および復号装置４０は、以下の処理を行う。
【００１１】
復号装置４０は、秘密鍵ＳＫを秘匿して保持する。暗号化装置２０は、公開鍵情報を取得する。公開鍵情報には、巡回群Ｇｑ、巡回群Ｇｑの位数ｑ、巡回群Ｇｑの生成元ｇ、および、公開鍵ＰＫが含まれる。
【００１２】
秘密鍵ＳＫおよび公開鍵ＰＫは、下記の式（１１１）および式（１１２）に示される関係を有する。なお、ｘは、巡回群Ｚｑ（例えば、０からｑ−１までの整数）からランダムに選択された値である。
ＳＫ＝ｘ      …（１１１）
ＰＫ＝ｇｘ      …（１１２）
【００１３】
暗号化装置２０は、平文ｍを受け取る。平文ｍは、巡回群Ｚｑから選択された値である。また、暗号化装置２０は、巡回群Ｚｑから乱数ｒをランダムに選択する。
【００１４】
暗号化装置２０は、公開鍵ＰＫ、平文ｍおよび乱数ｒに基づき、下記式（１１３）および式（１１４）の演算をして暗号文Ｃ１，Ｃ２を生成する。
Ｃ１＝ｇｒ    …（１１３）
Ｃ２＝ｇｍ・ＰＫｒ    …（１１４）
【００１５】
暗号化装置２０は、このように生成した暗号文Ｃ１，Ｃ２を復号装置４０に送信する。復号装置４０は、暗号化装置２０から暗号文Ｃ１，Ｃ２を受信する。
【００１６】
復号装置４０は、暗号文Ｃ１，Ｃ２および秘密鍵ＳＫに基づき、下記式（１１５）の演算をして、ｇｍを取得する。
ｇｍ＝Ｃ２／（Ｃ１ＳＫ）    …（１１５）
【００１７】
続いて、復号装置４０は、生成元ｇに対して任意の値を順次に冪乗していき、ｇｍと一致する値を探し出す。そして、復号装置４０は、一致したときに入力した値を、復号結果（平文ｍ）として出力する。
【００１８】
なお、本実施形態においては、モディファイドエルガマル暗号を用いた例を説明するが、暗号化装置２０および復号装置４０は、これに限らず、例えばラビン暗号等の他の準同型暗号を用いた処理を行ってもよい。
【００１９】
一方、証明装置３０および検証装置５０は、暗号化装置２０から復号装置４０へと転送された暗号文が正当であるか、すなわち、正しい平文および乱数を用いて暗号文が生成されたかを証明および検証する。暗号化装置２０から復号装置４０へと転送された検証対象となる暗号文を、対象暗号文という。
【００２０】
本例においては、証明装置３０は、対象暗号文Ｃ１，Ｃ２の生成に用いた平文ｍおよび乱数ｒを暗号化装置２０から受け取る。そして、証明装置３０は、公開鍵情報（Ｚｑ，ｑ，ｇ，ＰＫ）を用いて、シグマプロトコルで検証装置５０とやり取りをして、対象暗号文Ｃ１，Ｃ２が正当であることを検証装置５０に対して証明する。
【００２１】
また、検証装置５０は、対象暗号文Ｃ１，Ｃ２を復号装置４０から受け取る。そして、検証装置５０は、公開鍵情報（Ｚｑ，ｑ，ｇ，ＰＫ）を用いて、シグマプロトコルで証明装置３０とやり取りをして、対象暗号文Ｃ１，Ｃ２が正当であることを検証する。
【００２２】
検証装置５０は、受信した対象暗号文Ｃ１，Ｃ２が正当であると判定した場合、受容（Ａｃｃｅｐｔ）を復号装置４０に与える。また、検証装置５０は、受信した対象暗号文Ｃ１，Ｃ２が正当でないと判定した場合、拒否（Ｒｅｊｅｃｔ）を復号装置４０に与える。そして、復号装置４０は、検証装置５０により対象暗号文Ｃ１，Ｃ２が正当であると判定されたことを条件として、対象暗号文Ｃ１，Ｃ２を復号して、平文ｍを出力する。
【００２３】
図２は、第１実施形態に係る証明装置３０および検証装置５０の構成を示す図である。証明装置３０は、コミットメント生成部６１と、レスポンス生成部６２とを有する。検証装置５０は、チャレンジ生成部６３と、取得部６４と、検証部６５とを有する。
【００２４】
証明装置３０のコミットメント生成部６１は、検証値をランダムに選択する。続いて、コミットメント生成部６１は、ランダムに選択された検証値からコミットメント文を生成する。そして、コミットメント生成部６１は、生成したコミットメント文を検証装置５０の取得部６４へと送信する。また、コミットメント生成部６１は、検証値をレスポンス生成部６２に渡す。
【００２５】
モディファイドエルガマル暗号を用いた例では、コミットメント生成部６１は、巡回群Ｚｑからランダムに２つの検証値ａ，ｂを選択する。そして、コミットメント生成部６１は、ａを乱数とし、ｂを平文とするモディファイドエルガマル暗号の暗号化と同様の処理により、２つのコミットメント文Ａ，Ｂを生成する。なお、具体的な演算式については、詳細を図３で説明する。
【００２６】
検証装置５０のチャレンジ生成部６３は、チャレンジ値をランダムに選択する。そして、チャレンジ生成部６３は、ランダムに選択されたチャレンジ値を証明装置３０のレスポンス生成部６２へと送信する。モディファイドエルガマル暗号を用いた例では、チャレンジ生成部６３は、巡回群Ｚｑからランダムに１つのチャレンジ値ｅを選択する。
【００２７】
証明装置３０のレスポンス生成部６２は、チャレンジ値と平文と検証値とを受け取る。レスポンス生成部６２は、チャレンジ値と平文と検証値とを合成したレスポンス値を生成する。そして、レスポンス生成部６２は、生成したレスポンス値を検証装置５０の取得部６４へと送信する。この場合において、レスポンス生成部６２は、演算結果を準同型暗号処理により暗号化した暗号文が、チャレンジ値と対象暗号文とコミットメント文とを予め定められた準同型演算により合成した暗号文と同一となる演算により、レスポンス値を生成する。
【００２８】
なお、ここで、準同型演算とは、複数の暗号文を演算した場合に、暗号文を復号することなく平文同士を合成できる演算である。すなわち、下記の式（１１６）および式（１１７）のような関係が成り立つ演算である。
Ｅｎｃ（ｘ）×Ｅｎｃ（ｙ）＝Ｅｎｃ（ｘ＋ｙ）    …（１１６）
（Ｅｎｃ（ｘ））ｚ＝Ｅｎｃ（ｚ・ｘ）    …（１１７）
【００２９】
式（１１６）および式（１１７）において、Ｅｎｃ（ｘ）は、平文ｘを暗号化した暗号文を表す。Ｅｎｃ（ｙ）は、平文ｙを暗号化した暗号文を表す。Ｅｎｃ（ｘ＋ｙ）は、平文ｘと平文ｙとを加算した結果を暗号化した暗号文を表す。Ｅｎｃ（ｚ・ｘ）は、平文ｘに平文ｚを乗算した結果を暗号化した暗号文を表す。
【００３０】
そして、式（１１６）および式（１１７）において、“×”は暗号文の乗算を表し、準同型演算の一例である。また、（Ｅｎｃ（ｘ））ｚは、暗号文のＺ乗（すなわち、同一の暗号文のＺ回乗算）を表し、準同型演算の一例である。
【００３１】
なお、準同型演算の具体的な演算内容は、暗号化方式毎により異なる。例えば、モディファイドエルガマル暗号処理では、暗号文同士を乗算することにより平文同士が加算され、暗号文を定数乗することにより、平文に定数が乗算される。
【００３２】
モディファイドエルガマル暗号を用いた例では、レスポンス生成部６２は、チャレンジ値ｅと、平文ｍと、２つの検証値ａ，ｂとを演算により合成して、２つのレスポンス値Ｚ１，Ｚ２を生成する。なお、具体的な演算式については、詳細を図３で説明する。
【００３３】
検証装置５０の取得部６４は、証明装置３０から、コミットメント文およびレスポンス値を取得する。そして、取得部６４は、取得したコミットメント文およびレスポンス値を検証部６５に渡す。モディファイドエルガマル暗号を用いた例では、取得部６４は、２つのコミットメント文Ａ，Ｂ、および、２つのレスポンス値Ｚ１，Ｚ２を受信する。
【００３４】
検証装置５０の検証部６５は、コミットメント文およびレスポンス値を取得部６４から受け取る。また、検証部６５は、復号装置４０から対象暗号文を受信する。そして、検証部６５は、レスポンス値より予め定められた手順で導出される値と、チャレンジ値と対象暗号文とコミットメント文とを予め定められた準同型演算により合成した暗号文とが一致した場合に、対象暗号文が正当であると判定する。この場合において、検証部６５は、レスポンス値を準同型暗号処理により暗号化した暗号文と演算結果が同一となる準同型演算により、チャレンジ値と対象暗号文とコミットメント文とを合成する。
【００３５】
モディファイドエルガマル暗号を用いた例では、検証部６５は、２つのレスポンス値Ｚ１，Ｚ２を、Ｚ１を乱数とし、Ｚ２を平文とするモディファイドエルガマル暗号と同様の処理により暗号化して左辺暗号文を生成する。なお、具体的な演算式については、詳細を図３で説明する。
【００３６】
また、モディファイドエルガマル暗号を用いた例では、検証部６５は、チャレンジ値ｅと対象暗号文Ｃ１，Ｃ２とコミットメント文Ａ，Ｂとを予め定められた準同型演算により合成して右辺暗号文を生成する。この場合において、検証部６５は、演算結果が左辺暗号文と同一となる準同型演算により、右辺暗号文を生成する。なお、具体的な演算式については、詳細を図３で説明する。
【００３７】
そして、モディファイドエルガマル暗号を用いた例では、検証部６５は、左辺暗号文と右辺暗号文とが一致するか否かを判定する。検証部６５は、一致した場合には、対象暗号文Ｃ１，Ｃ２が正当であると判定して、受容（Ａｃｃｅｐｔ）を復号装置４０に供給する。検証部６５は、一致しなかった場合には、対象暗号文Ｃ１，Ｃ２が正当ではないと判定して、拒否（Ｒｅｊｅｃｔ）を復号装置４０に供給する。
【００３８】
図３は、第１実施形態に係る暗号処理システム１０の処理フローを示す図である。図３を参照して、モディファイドエルガマル暗号処理を用いた場合の、第１実施形態に係る暗号処理システム１０の処理フローを説明する。
【００３９】
まず、ステップＳ１１において、暗号化装置２０は、平文ｍを入力する。続いて、ステップＳ１２において、暗号化装置２０は、巡回群Ｚｑからランダムに乱数ｒを選択する。
【００４０】
続いて、ステップＳ１３において、平文ｍを乱数ｒを用いてモディファイドエルガマル暗号処理により暗号化して、対象暗号文Ｃ１，Ｃ２を生成する。すなわち、暗号化装置２０は、下記の式（１２１）および式（１２２）の演算により、対象暗号文Ｃ１，Ｃ２を生成する。
Ｃ１＝ｇｒ    …（１２１）
Ｃ２＝ｇｍ・ＰＫｒ    …（１２２）
【００４１】
続いて、ステップＳ１４において、暗号化装置２０は、対象暗号文Ｃ１，Ｃ２を復号装置４０へと送信する。
【００４２】
続いて、ステップＳ１５において、証明装置３０のコミットメント生成部６１は、巡回群Ｚｑからランダムに２つの検証値ａ，ｂを選択する。
【００４３】
続いて、ステップＳ１６において、コミットメント生成部６１は、検証値ｂを検証値ａを用いてモディファイドエルガマル暗号処理により暗号化して２つのコミットメント文Ａ，Ｂを生成する。すなわち、コミットメント生成部６１は、２つの検証値ａ，ｂ、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（１２３）および式（１２４）の演算により、２つのコミットメント文Ａ，Ｂを生成する。
Ａ＝ｇａ    …（１２３）
Ｂ＝ｇｂ・ＰＫａ    …（１２４）
【００４４】
なお、検証値ａを乱数ｒに置き換え、検証値ｂを平文ｍに置き換えれば、式（１２３）は式（１２１）と同一となり、式（１２４）は式（１２２）と同一となる。すなわち、コミットメント生成部６１は、検証値ａを乱数ｒに対応させ、且つ、検証値ｂを平文ｍに対応させたとした場合に、対象暗号文Ｃ１と同様の演算によりコミットメント文Ａを生成し、対象暗号文Ｃ２と同様の演算によりコミットメント文Ｂを生成する。
【００４５】
続いて、ステップＳ１７において、コミットメント生成部６１は、コミットメント文Ａ，Ｂを検証装置５０の取得部６４に送信する。
【００４６】
続いて、ステップＳ１８において、検証装置５０のチャレンジ生成部６３は、巡回群Ｚｑからランダムにチャレンジ値ｅを選択する。続いて、ステップＳ１９において、チャレンジ生成部６３は、チャレンジ値ｅを証明装置３０のレスポンス生成部６２に送信する。
【００４７】
続いて、ステップＳ２０において、証明装置３０のレスポンス生成部６２は、２つの検証値ａ，ｂ、乱数ｒ、平文ｍ、チャレンジ値ｅ、および、巡回群Ｚｑの位数ｑに基づき、下記の式（１２５）および式（１２６）の演算により、２つのレスポンス値Ｚ１，Ｚ２を生成する。なお、“＋”は加算演算、“・”は乗算演算、“ｍｏｄ”は剰余演算を表す。
Ｚ１＝（ａ＋ｅ・ｒ）  ｍｏｄ  ｑ  …（１２５）
Ｚ２＝（ｂ＋ｅ・ｍ）  ｍｏｄ  ｑ  …（１２６）
【００４８】
続いて、ステップＳ２１において、レスポンス生成部６２は、検証装置５０の取得部６４へ２つのレスポンス値Ｚ１，Ｚ２を送信する。
【００４９】
続いて、ステップＳ２２において、検証装置５０の検証部６５は、レスポンス値Ｚ２をレスポンス値Ｚ１を用いてモディファイドエルガマル暗号処理により暗号化して第１左辺暗号文および第２左辺暗号文を生成する。すなわち、検証部６５は、２つのレスポンス値Ｚ１，Ｚ２、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（１２７）および式（１２８）の演算により、第１左辺暗号文および第２左辺暗号文を生成する。なお、“＾”は、冪乗演算を表す。即ち、“ｘ＾ｙ”は、ｘｙを表す。
第１左辺暗号文＝ｇ＾Ｚ１    …（１２７）
第２左辺暗号文＝ｇ＾Ｚ２・ＰＫ＾Ｚ１    …（１２８）
【００５０】
なお、レスポンス値Ｚ１を乱数ｒに置き換え、レスポンス値Ｚ２を平文ｍに置き換えれば、式（１２７）は式（１２１）と同一となり、式（１２８）は式（１２２）と同一となる。すなわち、検証部６５は、レスポンス値Ｚ１を乱数ｒに対応させ、且つ、レスポンス値Ｚ２を平文ｍに対応させたとした場合に、対象暗号文Ｃ１と同様の演算により第１左辺暗号文（式（１２７））を生成し、対象暗号文Ｃ２と同様の演算により第２左辺暗号文（式（１２８））を生成する。
【００５１】
続いて、ステップＳ２３において、検証部６５は、チャレンジ値ｅと対象暗号文Ｃ１とコミットメント文Ａとを、下記の式（１２９）の準同型演算により合成して第１右辺暗号文を生成する。これとともに、検証部６５は、チャレンジ値ｅと対象暗号文Ｃ２とコミットメント文Ｂとを、下記の式（１３０）の準同型演算により合成して第２右辺暗号文を生成する。
第１右辺暗号文＝Ａ・Ｃ１ｅ    …（１２９）
第２右辺暗号文＝Ｂ・Ｃ２ｅ    …（１３０）
【００５２】
ここで、式（１２７）の第１左辺暗号文は、下記の式（１３１）に示されるように展開される。
第１左辺暗号文＝ｇ＾Ｚ１＝ｇ（ａ＋ｅ・ｒ）    …（１３１）
【００５３】
式（１２９）の第１右辺暗号文は、下記の式（１３２）に示されるように展開される。
第１右辺暗号文＝Ａ・Ｃ１ｅ＝ｇａ・（ｇｒ）ｅ＝ｇ（ａ＋ｅ・ｒ）…（１３２）
【００５４】
従って、式（１２７）の第１左辺暗号文と式（１２９）の第１右辺暗号文とは同一である。
【００５５】
また、式（１２８）の第２左辺暗号文は、下記の式（１３３）に示されるように展開される。
第２左辺暗号文＝ｇ＾Ｚ２・ＰＫ＾Ｚ１＝ｇ（ｂ＋ｅ・ｍ）・ＰＫ（ａ＋ｅ・ｒ）    …（１３３）
【００５６】
式（１３０）の第２右辺暗号文は、下記の式（１３４）に示されるように展開される。
第２右辺暗号文＝Ｂ・Ｃ２ｅ＝ｇｂ・ＰＫａ・（ｇｍ・ＰＫｒ）ｅ＝ｇ（ｂ＋ｅ・ｍ）・ＰＫ（ａ＋ｅ・ｒ）…（１３４）
【００５７】
従って、式（１２８）の第２左辺暗号文と式（１３０）の第２右辺暗号文とは同一である。
【００５８】
すなわち、レスポンス生成部６２は、演算結果をモディファイドエルガマル暗号処理により暗号化した暗号文（第１左辺暗号文および第２左辺暗号文）が、チャレンジ値ｅと対象暗号文Ｃ１，Ｃ２とコミットメント文Ａ，Ｂとを予め定められた準同型演算により合成した暗号文（第１右辺暗号文および第２右辺暗号文）と同一となる演算により、レスポンス値Ｚ１，Ｚ２を生成する。換言すると、検証部６５は、レスポンス値Ｚ１，Ｚ２をモディファイドエルガマル暗号処理により暗号化した暗号文（第１左辺暗号文および第２左辺暗号文）と演算結果が同一となる準同型演算により、チャレンジ値ｅと対象暗号文Ｃ１，Ｃ２とコミットメント文Ａ，Ｂとを合成した合成暗号文（第１右辺暗号文および第２右辺暗号文）を生成する。
【００５９】
続いて、ステップＳ２４において、検証部６５は、下記の式（１３５）を演算する。
Ｘ＝（ｇ＾Ｚ１＝＝Ａ・Ｃ１ｅ）∧（ｇ＾Ｚ２・ＰＫ＾Ｚ１＝＝Ｂ・Ｃ２ｅ）…（１３５）
【００６０】
なお、“＝＝”は、左辺と右辺が一致していれば真（ｔｒｕｅ）、不一致であれば偽（ｆａｌｓｅ）を出力する。また、“∧”は、左辺と右辺の論理積を出力する。すなわち、“ｔｒｕｅ∧ｔｒｕｅ”の場合にはｔｒｕｅを出力するが、それ以外である場合にはｆａｌｓｅを出力する。
【００６１】
続いて、ステップＳ２５において、検証部６５は、Ｘがｔｒｕｅであるか否かを判定する。すなわち、検証部６５は、第１左辺暗号文と第１右辺暗号文とが一致し且つ第２左辺暗号文と第２右辺暗号文とが一致するか、否かを判定する。
【００６２】
検証部６５は、第１左辺暗号文と第１右辺暗号文とが一致し且つ第２左辺暗号文と第２右辺暗号文とが一致する場合には（ステップＳ２５のＹｅｓ）、処理をステップＳ２６に進める。ステップＳ２６において、復号装置４０は、暗号化装置２０から受信した対象暗号文Ｃ１，Ｃ２を復号して、平文ｍを出力する。そして、復号装置４０は、本フローを終了する。
【００６３】
検証部６５は、第１左辺暗号文と第１右辺暗号文とが一致しない、または、第２左辺暗号文と第２右辺暗号文とが一致しない場合には（ステップＳ２５のＮｏ）、復号を実行せずに、本フローを終了する。
【００６４】
以上のように、第１実施形態に係る暗号処理システム１０では、チャレンジ値と対象暗号文とコミットメント文とを準同型演算により合成した暗号文と、レスポンス値を準同型暗号処理により暗号化した暗号文とが一致するように、コミットメント文およびレスポンス値を生成する。これにより、暗号処理システム１０によれば、対象暗号文を復号することなく、簡易に、対象暗号文が正当であるか否かを検証できる。
【００６５】
（第２実施形態）
図４は、第２実施形態に係る証明装置３０および検証装置５０の構成を示す図である。第２実施形態に係る暗号処理システム１０は、第１実施形態に係る暗号処理システム１０と略同一の機能および構成を有する。従って、第２実施形態に係る暗号処理システム１０の説明では、第１実施形態と略同一の機能および構成を有するユニットには同一の符号を付けて、相違点を除き説明を省略する。
【００６６】
第２実施形態に係る証明装置３０は、証明側チャレンジ生成部７１をさらに有する。また、第２実施形態に係る検証装置５０は、チャレンジ生成部６３に代えて、検証側チャレンジ生成部７２を有する。
【００６７】
証明側チャレンジ生成部７１は、コミットメント生成部６１により生成されたコミットメント文Ａ，Ｂを取得する。証明側チャレンジ生成部７１は、取得したコミットメント文Ａ，Ｂを予め定められたハッシュ関数に入力して、チャレンジ値ｅを生成する。証明側チャレンジ生成部７１は、生成したチャレンジ値ｅをレスポンス生成部６２に供給する。
【００６８】
検証側チャレンジ生成部７２は、取得部６４により受信されたコミットメント文Ａ，Ｂを取得する。検証側チャレンジ生成部７２は、取得したコミットメント文Ａ，Ｂを予め定められたハッシュ関数に入力して、チャレンジ値ｅを生成する。ここで、検証側チャレンジ生成部７２は、証明側チャレンジ生成部７１で用いられているハッシュ関数と同一のハッシュ関数によりチャレンジ値ｅを生成する。検証側チャレンジ生成部７２は、生成したチャレンジ値ｅを検証部６５に供給する。
【００６９】
第２実施形態に係る暗号処理システム１０では、証明側チャレンジ生成部７１および検証側チャレンジ生成部７２を有することにより、検証装置５０から証明装置３０へのチャレンジ値ｅの送信を無くすことができる。これにより、暗号処理システム１０では、証明装置３０から検証装置５０への一方向の情報の送信処理で、対象暗号文Ｃ１，Ｃ２が正当であるか否かを検証することができる。
【００７０】
なお、本実施の形態では、チャレンジ値ｅの生成にハッシュ関数を用いたが、生成に用いることのできる関数はハッシュ関数に限定されず、出力値の予測不能性を持ち、値域が巡回群Ｚｑなる関数ならば何でもよい。
【００７１】
（第３実施形態）
図５は、第３実施形態に係る暗号処理システム１０の構成を示す図である。第３実施形態に係る暗号処理システム１０は、第２実施形態に係る暗号処理システム１０と略同一の機能および構成を有する。従って、第３実施形態に係る暗号処理システム１０の説明では、第２実施形態と略同一の機能および構成を有するユニットには同一の符号を付けて、相違点を除き説明を省略する。
【００７２】
第３実施形態に係る暗号化装置２０は、複数の平文のそれぞれを暗号化して、複数の暗号文を生成する。また、第３実施形態に係る復号装置４０は、複数の暗号文のそれぞれを復号して、複数の平文を出力する。
【００７３】
本例においては、暗号化装置２０は、ｋ個（ｋは２以上の整数）の暗号化部８１−１〜８１−ｋを有する。ｋ個の暗号化部８１−１〜８１−ｋは、ｋ個の乱数ｒ〜ｒｋを生成して、ｋ個の平文ｍ１〜ｍｋをモディファイドエルガマル暗号処理により暗号化して、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を生成する。
【００７４】
また、復号装置４０は、ｋ個の復号部８２−１〜８２−ｋと、決定部８３とを有する。ｋ個の復号部８２−１〜８２−ｋは、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を復号して、ｋ個の平文ｍ１〜ｍｋを出力する。決定部８３は、検証装置５０によりｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）の全てが正当であると判定されたことを条件として、ｋ個の復号部８２−１〜８２−ｋにより復号されたｋ個の平文ｍ１〜ｍｋを出力する。
【００７５】
証明装置３０は、ｋ個の平文ｍ１〜ｍｋおよび乱数ｒ１〜ｒｋを暗号化装置２０から受け取る。そして、証明装置３０は、公開鍵情報（Ｚｑ，ｑ，ｇ，ＰＫ）を用いて、シグマプロトコルで検証装置５０とやり取りをして、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれが正当であることを検証装置５０に対して証明する。
【００７６】
また、検証装置５０は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を復号装置４０から受け取る。そして、検証装置５０は、公開鍵情報（Ｚｑ，ｑ，ｇ，ＰＫ）を用いて、シグマプロトコルで証明装置３０とやり取りをして、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれが正当であることを検証する。
【００７７】
検証装置５０は、受信したｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）の全てが正当であると判定した場合、受容（Ａｃｃｅｐｔ）を復号装置４０に与える。また、検証装置５０は、正当でないと判定した場合、拒否（Ｒｅｊｅｃｔ）を復号装置４０に与える。
【００７８】
図６は、第３実施形態に係る証明装置３０の構成を示す図である。第３実施形態に係る証明装置３０は、ｋ個のコミットメント生成部６１−１〜６１−ｋと、合成コミットメント生成部９１と、証明側チャレンジ生成部７１と、ｋ個のレスポンス生成部６２−１〜６２−ｋと、合成レスポンス生成部９２とを有する。
【００７９】
ｋ個のコミットメント生成部６１−１〜６１−ｋのそれぞれは、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれに対応しており、対応する対象暗号文に対して第１実施形態のコミットメント生成部６１と同様の処理を行う。
【００８０】
より詳しくは、コミットメント生成部６１−１は、２つの検証値ａ１，ｂ１および２つのコミットメント文Ａ１，Ｂ１を生成する。コミットメント生成部６１−２は、２つの検証値ａ２，ｂ２および２つのコミットメント文Ａ２，Ｂ２を生成する。コミットメント生成部６１−ｋは、２つの検証値ａｋ，ｂｋおよび２つのコミットメント文Ａｋ，Ｂｋを生成する。
【００８１】
合成コミットメント生成部９１は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を準同型演算により合成した合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）に対応しており、合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）に対して第１実施形態のコミットメント生成部６１と同様の処理を行う。より詳しくは、合成コミットメント生成部９１は、２つの合成検証値ａｔｔｌ，ｂｔｔｌおよび２つの合成コミットメント文Ａｔｔｌ，Ｂｔｔｌを生成する。
【００８２】
証明側チャレンジ生成部７１は、ｋ個のコミットメント生成部６１−１〜６１−ｋから出力されたｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、合成コミットメント生成部９１から出力された１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）を入力する。そして、証明側チャレンジ生成部７１は、（２ｋ＋２）個のコミットメント文をハッシュ関数に入力して、ｋ個のチャレンジ値ｅ１，ｅ２，…，ｅｋおよび１個の合成チャレンジ値ｅｔｔｌを出力する。
【００８３】
ｋ個のレスポンス生成部６２−１〜６２−ｋのそれぞれは、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれに対応しており、対応する対象暗号文に対して第１実施形態のレスポンス生成部６２と同様の処理を行う。
【００８４】
より詳しくは、レスポンス生成部６２−１は、チャレンジ値ｅ１と、平文ｍ１と、乱数ｒ１と、２つの検証値ａ１，ｂ１とを演算により合成して、２つのレスポンス値Ｚ１，１，Ｚ２，１を生成する。レスポンス生成部６２−２は、チャレンジ値ｅ２と、平文ｍ２と、乱数ｒ２と、２つの検証値ａ２，ｂ２とを演算により合成して、２つのレスポンス値Ｚ１，２，Ｚ２，２を生成する。レスポンス生成部６２−ｋは、チャレンジ値ｅｋと、平文ｍｋと、乱数ｒｋと、２つの検証値ａｋ，ｂｋとを演算により合成して、２つのレスポンス値Ｚ１，ｋ，Ｚ２，ｋを生成する。
【００８５】
合成レスポンス生成部９２は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を準同型演算により合成した合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）に対応している。合成レスポンス生成部９２は、ｋ個の平文ｍ１，ｍ２，…，ｍｋを準同型演算に対応する平文演算により合成した合成平文ｍｔｔｌを生成する。モディファイドエルガマル暗号の場合には、合成レスポンス生成部９２は、ｋ個の平文ｍ１，ｍ２，…，ｍｋの全てを加算して合成平文ｍｔｔｌを生成する。
【００８６】
合成レスポンス生成部９２は、ｋ個の乱数ｒ１，ｒ２，…，ｒｋを準同型演算に対応する演算により合成した合成乱数ｒｔｔｌを生成する。例えば、モディファイドエルガマル暗号の場合、合成レスポンス生成部９２は、ｋ個の乱数ｒ１，ｒ２，…，ｒｋの全てを加算して合成乱数ｒｔｔｌを生成する。
【００８７】
そして、合成レスポンス生成部９２は、合成チャレンジ値ｅｔｔｌと、合成平文ｍｔｔｌと、合成乱数ｒｔｔｌと、２つの合成検証値ａｔｔｌ，ｂｔｔｌとに基づき、第１実施形態のレスポンス生成部６２と同様の処理を行う。より詳しくは、合成チャレンジ値ｅｔｔｌと、合成平文ｍｔｔｌと、合成乱数ｒｔｔｌと、２つの合成検証値ａｔｔｌ，ｂｔｔｌとを演算により合成して、２つの合成レスポンス値Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌを生成する。
【００８８】
図７は、第３実施形態に係る検証装置５０の構成を示す図である。検証装置５０は、ｋ個の取得部６４−１〜６４−ｋと、合成取得部９３と、検証側チャレンジ生成部７２と、ｋ個の検証部６５−１〜６５−ｋと、合成検証部９４とを有する。
【００８９】
ｋ個の取得部６４−１〜６４−ｋのそれぞれは、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれに対応しており、対応する対象暗号文に対して第１実施形態の取得部６４と同様の処理を行う。
【００９０】
より詳しくは、取得部６４−１は、２つのコミットメント文Ａ１，Ｂ１、および、２つのレスポンス値Ｚ１，１，Ｚ２，１を受信する。取得部６４−２は、２つのコミットメント文Ａ２，Ｂ２、および、２つのレスポンス値Ｚ１，２，Ｚ２，２を受信する。取得部６４−ｋは、２つのコミットメント文Ａｋ，Ｂｋ、および、２つの合成レスポンス値Ｚ１，ｋ，Ｚ２，ｋを受信する。
【００９１】
合成取得部９３は、２つの合成コミットメント文Ａｔｔｌ，Ｂｔｔｌ、および、２つの合成レスポンス値Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌを受信する。
【００９２】
検証側チャレンジ生成部７２は、ｋ個の取得部６４−１〜６４−ｋにより受信されたｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、合成取得部９３により受信された１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）を入力する。そして、検証側チャレンジ生成部７２は、（２ｋ＋２）個のコミットメント文をハッシュ関数に入力して、ｋ個のチャレンジ値ｅ１，ｅ２，…，ｅｋおよび１個の合成チャレンジ値ｅｔｔｌを出力する。ここで、検証側チャレンジ生成部７２は、証明側チャレンジ生成部７１で用いられているハッシュ関数と同一のハッシュ関数によりチャレンジ値ｅ１，ｅ２，…，ｅｋおよび合成チャレンジ値ｅｔｔｌを生成する。
【００９３】
ｋ個の検証部６５−１〜６５−ｋのそれぞれは、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれに対応しており、対応する対象暗号文に対して第１実施形態の検証部６５と同様の処理を行う。
【００９４】
より詳しくは、検証部６５−１は、２つのコミットメント文Ａ１，Ｂ１、２つのレスポンス値Ｚ１，１，Ｚ２，１、チャレンジ値ｅ１、および、対象暗号文（Ｃ１，１，Ｃ２，１）に基づき、対象暗号文（Ｃ１，１，Ｃ２，１）が正当であるか否かを判定する。検証部６５−１は、対象暗号文（Ｃ１，１，Ｃ２，１）が正当である場合には受容（Ａｃｃｅｐｔ）を復号装置４０に供給し、正当でない場合には、拒否（Ｒｅｊｅｃｔ）を復号装置４０に供給する。
【００９５】
検証部６５−２は、２つのコミットメント文Ａ２，Ｂ２、２つのレスポンス値Ｚ１，２，Ｚ２，２、チャレンジ値ｅ２、および、対象暗号文（Ｃ１，２，Ｃ２，２）に基づき、対象暗号文（Ｃ１，２，Ｃ２，２）が正当であるか否かを判定する。検証部６５−２は、対象暗号文（Ｃ１，２，Ｃ２，２）が正当である場合には、受容（Ａｃｃｅｐｔ）を復号装置４０に供給し、正当でない場合には、拒否（Ｒｅｊｅｃｔ）を復号装置４０に供給する。
【００９６】
検証部６５−ｋは、２つのコミットメント文Ａｋ，Ｂｋ、２つのレスポンス値Ｚ１，ｋ，Ｚ２，ｋ、チャレンジ値ｅｋ、および、対象暗号文（Ｃ１，ｋ，Ｃ２，ｋ）に基づき、対象暗号文（Ｃ１，ｋ，Ｃ２，ｋ）が正当であるか否かを判定する。検証部６５−ｋは、対象暗号文（Ｃ１，ｋ，Ｃ２，ｋ）が正当である場合には、受容（Ａｃｃｅｐｔ）を復号装置４０に供給し、正当でない場合には、拒否（Ｒｅｊｅｃｔ）を復号装置４０に供給する。
【００９７】
合成検証部９４は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）の全てを取得する。そして、合成検証部９４は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を準同型演算により合成した合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）を生成する。例えば、モディファイドエルガマル暗号の場合、合成検証部９４は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を乗算して、合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）を生成する。
【００９８】
そして、合成検証部９４は、２つの合成コミットメント文Ａｔｔｌ，Ｂｔｔｌ、２つの合成レスポンス値Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌ、合成チャレンジ値ｅｔｔｌ、および、合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）に基づき、第１実施形態の検証部６５と同様の処理を行い、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）が正当であるか否かを判定する。合成検証部９４は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）が正当である場合には、受容（Ａｃｃｅｐｔ）を復号装置４０に供給し、正当でない場合には、拒否（Ｒｅｊｅｃｔ）を復号装置４０に供給する。
【００９９】
図８は、第３実施形態に係る暗号化装置２０および証明装置３０の処理フローを示す図である。図８を参照して、モディファイドエルガマル暗号処理を用いた場合の、第３実施形態に係る暗号化装置２０および証明装置３０の処理フローを説明する。
【０１００】
まず、ステップＳ５１〜Ｓ５６において、暗号化装置２０は、ｉ＝１からｋまで、ｉを１ずつインクリメントしながらループ処理を実行する。ループ処理内のステップＳ５２において、暗号化装置２０は、平文ｍｉを入力する。続いて、ステップＳ５３において、暗号化装置２０は、巡回群Ｚｑからランダムに乱数ｒｉを選択する。
【０１０１】
続いて、ステップＳ５４において、暗号化装置２０は、平文ｍｉを乱数ｒｉを用いてモディファイドエルガマル暗号処理により暗号化する。すなわち、暗号化装置２０は、下記の式（２２１）および式（２２２）の演算により、対象暗号文Ｃ１，ｉ，Ｃ２，ｉを生成する。
Ｃ１，ｉ＝ｇ＾ｒｉ    …（２２１）
Ｃ２，ｉ＝ｇ＾ｍｉ・ＰＫ＾ｒｉ    …（２２２）
【０１０２】
続いて、ステップＳ５５において、暗号化装置２０は、対象暗号文Ｃ１，ｉ，Ｃ２，ｉを復号装置４０へと送信する。ステップＳ５１〜Ｓ５６のループ処理をｉ＝ｋまで終了すると、暗号化装置２０は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を復号装置４０へと送信することができる。ステップＳ５１〜Ｓ５６のループ処理をｉ＝ｋまで終了すると、暗号化装置２０は、処理をステップＳ５７に進める。
【０１０３】
続いて、ステップＳ５７〜Ｓ６０において、証明装置３０は、ｉ＝１からｋまで、ｉを１ずつインクリメントしながらループ処理を実行する。ループ処理内のステップＳ５８において、証明装置３０は、巡回群Ｚｑからランダムに２つの検証値ａｉ，ｂｉを選択する。
【０１０４】
続いて、ステップＳ５９において、証明装置３０は、検証値ｂｉを検証値ａｉを用いてモディファイドエルガマル暗号処理により暗号化して２つのコミットメント文Ａｉ，Ｂｉを生成する。すなわち、証明装置３０は、２つの検証値ａｉ，ｂｉ、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（２２３）および式（２２４）の演算により、２つのコミットメント文Ａｉ，Ｂｉを生成する。
Ａｉ＝ｇ＾ａｉ    …（２２３）
Ｂｉ＝ｇ＾ｂｉ・ＰＫ＾ａｉ    …（２２４）
【０１０５】
ステップＳ５７〜Ｓ６０のループ処理をｉ＝ｋまで終了すると、証明装置３０は、ｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）を生成することができる。ステップＳ５７〜Ｓ６０のループ処理をｉ＝ｋまで終了すると、証明装置３０は、処理をステップＳ６１に進める。
【０１０６】
続いて、ステップＳ６１において、証明装置３０は、巡回群Ｚｑからランダムに２つの合成検証値ａｔｔｌ，ｂｔｔｌを選択する。
【０１０７】
続いて、ステップＳ６２において、証明装置３０は、合成検証値ｂｔｔｌを合成検証値ａｔｔｌを用いてモディファイドエルガマル暗号処理により暗号化して２つの合成コミットメント文Ａｔｔｌ，Ｂｔｔｌを生成する。すなわち、証明装置３０は、２つの合成検証値ａｔｔｌ，ｂｔｔｌ、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（２２５）および式（２２６）の演算により、２つの合成コミットメント文Ａｔｔｌ，Ｂｔｔｌを生成する。
Ａｔｔｌ＝ｇ＾ａｔｔｌ    …（２２５）
Ｂｔｔｌ＝ｇ＾ｂｔｔｌ・ＰＫ＾ａｔｔｌ    …（２２６）
【０１０８】
続いて、ステップＳ６３において、証明装置３０は、ｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）をハッシュ関数に入力して、ｋ個のチャレンジ値ｅ１〜ｅｋおよび１個の合成チャレンジ値ｅｔｔｌを出力する。証明装置３０は、一例として、下記の式（２２７）のハッシュ関数により、（２Ｋ＋２）個の値から、（ｋ＋１）個の値を出力する。なお、Ｇｑは、巡回群を表す。
Ｈ：Ｇｑ２Ｋ＋２→ＺｑＫ＋１    …（２２７）
【０１０９】
続いて、ステップＳ６４〜Ｓ６６において、証明装置３０は、ｉ＝１からｋまで、ｉを１ずつインクリメントしながらループ処理を実行する。ループ処理内のステップＳ６５において、証明装置３０は、２つの検証値ａｉ，ｂｉ、乱数ｒｉ、平文ｍｉ、チャレンジ値ｅｉ、および、巡回群Ｚｑの位数ｑに基づき、下記の式（２２８）および式（２２９）の演算により、２つのレスポンス値Ｚ１，ｉ，Ｚ２，ｉを生成する。
Ｚ１，ｉ＝（ａｉ＋ｅｉ・ｒｉ）  ｍｏｄ  ｑ  …（２２８）
Ｚ２，ｉ＝（ｂｉ＋ｅｉ・ｍｉ）  ｍｏｄ  ｑ  …（２２９）
【０１１０】
ステップＳ６４〜Ｓ６６のループ処理をｉ＝ｋまで終了すると、証明装置３０は、ｋ組のレスポンス値（Ｚ１，１，Ｚ２，１）〜（Ｚ２，ｋ，Ｚ２，ｋ）を生成することができる。ステップＳ６４〜Ｓ６６のループ処理をｉ＝ｋまで終了すると、証明装置３０は、処理をステップＳ６７に進める。
【０１１１】
続いて、ステップＳ６７において、証明装置３０は、ｋ個の平文ｍ１，ｍ２，…，ｍｋの全てを、下記の式（２３０）に示されるように巡回群Ｚｑ上で加算して合成平文ｍｔｔｌを生成する。これにより、証明装置３０は、ｋ個の平文ｍ１，ｍ２，…，ｍｋを準同型演算に対応する演算により合成することができる。
ｍｔｔｌ＝（ｍ１＋ｍ２＋…＋ｍｋ）  ｍｏｄ  ｑ    …（２３０）
【０１１２】
これとともに、ステップＳ６７において、証明装置３０は、ｋ個の乱数ｒ１，ｒ２，…，ｒｋの全てを、下記の式（２３１）に示されるように巡回群Ｚｑ上で加算して合成乱数ｒｔｔｌを生成する。これにより、証明装置３０は、ｋ個の乱数ｒ１，ｒ２，…，ｒｋを準同型演算に対応する演算により合成することができる。
ｒｔｔｌ＝（ｒ１＋ｒ２＋…＋ｒｋ）  ｍｏｄ  ｑ    …（２３１）
【０１１３】
続いて、ステップＳ６８において、証明装置３０は、合成チャレンジ値ｅｔｔｌと、合成平文ｍｔｔｌと、合成乱数ｒｔｔｌと、２つの合成検証値ａｔｔｌ，ｂｔｔｌと、巡回群Ｚｑの位数ｑに基づき、下記の式（２３２）および式（２３３）の演算により、２つの合成レスポンス値Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌを生成する。
Ｚ１，ｔｔｌ＝（ａｔｔｌ＋ｅｔｔｌ・ｒｔｔｌ）  ｍｏｄ  ｑ  …（２３２）
Ｚ２，ｔｔｌ＝（ｂｔｔｌ＋ｅｔｔｌ・ｍｔｔｌ）  ｍｏｄ  ｑ  …（２３３）
【０１１４】
続いて、ステップＳ６９において、証明装置３０は、ｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）、ｋ組のレスポンス値（Ｚ１，１，Ｚ２，１）〜（Ｚ１，ｋ，Ｚ２，ｋ）、および、１組の合成コミットメント文（Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌ）を、検証装置５０に送信する。
【０１１５】
図９は、第３実施形態に係る復号装置４０および検証装置５０の処理フローを示す図である。
【０１１６】
まず、ステップＳ８１において、検証装置５０は、証明装置３０から、ｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）、ｋ組のレスポンス値（Ｚ１，１，Ｚ２，１）〜（Ｚ１，ｋ，Ｚ２，ｋ）、および、１組の合成コミットメント文（Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌ）を受信する。
【０１１７】
続いて、ステップＳ８２において、検証装置５０は、受信されたｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）をハッシュ関数に入力して、ｋ個のチャレンジ値ｅ１〜ｅｋおよび１個の合成チャレンジ値ｅｔｔｌを出力する。ここで、検証装置５０は、証明装置３０で用いられたハッシュ関数と同一のハッシュ関数により、ｋ個のチャレンジ値ｅ１〜ｅｋおよび１個の合成チャレンジ値ｅｔｔｌを生成する。
【０１１８】
続いて、ステップＳ８３〜Ｓ８８において、検証装置５０は、ｉ＝１からｋまで、ｉを１ずつインクリメントしながらループ処理を実行する。
【０１１９】
ループ処理内のステップＳ８４において、検証装置５０は、レスポンス値Ｚ２，ｉをレスポンス値Ｚ１，ｉを用いてモディファイドエルガマル暗号処理により暗号化して第１左辺暗号文および第２左辺暗号文を生成する。すなわち、検証装置５０は、２つのレスポンス値Ｚ１，ｉ，Ｚ２，ｉ、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（２３４）および式（２３５）の演算により、第１左辺暗号文および第２左辺暗号文を生成する。
第１左辺暗号文＝ｇ＾Ｚ１，ｉ    …（２３４）
第２左辺暗号文＝ｇ＾Ｚ２，ｉ・ＰＫ＾Ｚ１，ｉ    …（２３５）
【０１２０】
続いて、ステップＳ８５において、検証装置５０は、チャレンジ値ｅｉと対象暗号文Ｃ１，ｉとコミットメント文Ａｉとを、下記の式（２３６）の準同型演算により合成して第１右辺暗号文を生成する。また、検証装置５０は、チャレンジ値ｅｉと対象暗号文Ｃ２，ｉとコミットメント文Ｂ，ｉとを、下記の式（２３７）の準同型演算により合成して第２右辺暗号文を生成する。
第１右辺暗号文＝Ａｉ・Ｃ１，ｉ＾ｅｉ    …（２３６）
第２右辺暗号文＝Ｂｉ・Ｃ２，ｉ＾ｅｉ    …（２３７）
【０１２１】
続いて、ステップＳ８６において、検証装置５０は、下記の式（２３８）を演算する。
Ｘｉ＝（第１左辺暗号文＝＝第１右辺暗号文）∧（第２左辺暗号文＝＝第２右辺暗号文）
＝（ｇ＾Ｚ１，ｉ＝＝Ａｉ・Ｃ１，ｉ＾ｅｉ）∧（ｇ＾Ｚ２，ｉ・ＰＫ＾Ｚ１，ｉ＝＝Ｂｉ・Ｃ２，ｉ＾ｅｉ）    …（２３８）
【０１２２】
続いて、ステップＳ８７において、検証装置５０は、Ｘｉがｔｒｕｅであるか否かを判定する。Ｘｉがｔｒｕｅの場合（ステップＳ８７のＹｅｓ）、検証装置５０は、処理をステップＳ８８に進める。Ｘｉがｆａｌｓｅの場合（ステップＳ８７のＮｏ）、検証装置５０は、ループ処理を抜けて、本フローを終了する。
【０１２３】
ステップＳ８３〜Ｓ８８のループ処理をｉ＝ｋまで終了すると、検証装置５０は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）のそれぞれが正当であると検証することができる。ステップＳ８３〜Ｓ８８のループ処理をｉ＝ｋまで終了すると、検証装置５０は、処理をステップＳ８９に進める。
【０１２４】
続いて、ステップＳ８９において、検証装置５０は、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を下記の式（２３９）および式（２４０）に示されるように巡回群Ｇ上で乗算して、合成対象暗号文（Ｃ１，ｔｔｌ，Ｃ２，ｔｔｌ）を生成する。
Ｃ１，ｔｔｌ＝（Ｃ１，１・Ｃ１，２・…・Ｃ１，ｋ）  ｏｖｅｒ  Ｇｑ    …（２３９）
Ｃ２，ｔｔｌ＝（Ｃ２，１・Ｃ２，２・…・Ｃ２，ｋ）  ｏｖｅｒ  Ｇｑ    …（２４０）
【０１２５】
なお、式（２３９）および式（２４０）において、Ｇは、対象暗号文を元とする巡回群を表す。また、（ｘ・ｙ  ｏｖｅｒ  Ｇｑ）は、巡回群Ｇ上での乗算を表す。
【０１２６】
検証装置５０は、式（２３９）および式（２４０）の演算を実行することにより、ｋ組の対象暗号文（Ｃ１，１，Ｃ２，１）〜（Ｃ１，ｋ，Ｃ２，ｋ）を準同型演算により合成することができる。
【０１２７】
続いて、ステップＳ９０において、検証装置５０は、合成レスポンス値Ｚ２，ｔｔｌを合成レスポンス値Ｚ１，ｔｔｌを用いてモディファイドエルガマル暗号処理により暗号化して第１左辺暗号文および第２左辺暗号文を生成する。すなわち、検証装置５０は、２つの合成レスポンス値Ｚ１，ｔｔｌ，Ｚ２，ｔｔｌ、生成元ｇ、および、公開鍵ＰＫに基づき、下記の式（２４１）および式（２４２）の演算により、第１左辺暗号文および第２左辺暗号文を生成する。
第１左辺暗号文＝ｇ＾Ｚ１，ｔｔｌ    …（２４１）
第２左辺暗号文＝ｇ＾Ｚ２，ｔｔｌ・ＰＫ＾Ｚ１，ｔｔｌ    …（２４２）
【０１２８】
続いて、ステップＳ９１において、検証装置５０は、合成チャレンジ値ｅｔｔｌと合成対象暗号文Ｃ１，ｔｔｌと合成コミットメント文Ａｔｔｌとを、下記の式（２４３）の準同型演算により合成して第１右辺暗号文を生成する。また、検証装置５０は、合成チャレンジ値ｅｔｔｌと合成対象暗号文Ｃ２，ｔｔｌと合成コミットメント文Ｂｔｔｌとを、下記の式（２４４）の準同型演算により合成して第２右辺暗号文を生成する。
第１右辺暗号文＝Ａｔｔｌ・Ｃ１，ｔｔｌ＾ｅｔｔｌ    …（２４３）
第２右辺暗号文＝Ｂｔｔｌ・Ｃ２，ｔｔｌ＾ｅｔｔｌ    …（２４４）
【０１２９】
続いて、ステップＳ９２において、検証装置５０は、下記の式（２４５）を演算する。
Ｘｔｔｌ＝（第１左辺暗号文＝＝第１右辺暗号文）∧（第２左辺暗号文＝＝第２右辺暗号文）
＝（ｇ＾Ｚ１，ｔｔｌ＝＝Ａｔｔｌ・Ｃ１，ｔｔｌ＾ｅｔｔｌ）∧（ｇ＾Ｚ２，ｔｔｌ・ＰＫ＾Ｚ１，ｔｔｌ＝＝Ｂｔｔｌ・Ｃ２，ｔｔｌ＾ｅｔｔｌ）    …（２４５）
【０１３０】
続いて、ステップＳ９３において、検証装置５０は、Ｘｔｔｌがｔｒｕｅであるか否かを判定する。Ｘｔｔｌがｔｒｕｅの場合（ステップＳ９３のＹｅｓ）、検証装置５０は、処理をステップＳ９４に進める。Ｘｔｔｌがｆａｌｓｅの場合（ステップＳ９３のＮｏ）、検証装置５０は、ループ処理を抜けて、本フローを終了する。
【０１３１】
続いて、ステップＳ９４〜Ｓ９６において、復号装置４０は、ｉ＝１からｋまで、ｉを１ずつインクリメントしながらループ処理を実行する。ループ処理内のステップＳ９５において、復号装置４０は、暗号化装置２０から受信した対象暗号文Ｃ１，ｉ，Ｃ２，ｉを復号して、平文ｍｉを出力する。
【０１３２】
ステップＳ９４〜Ｓ９６のループ処理をｉ＝ｋまで終了すると、復号装置４０は、ｋ個の平文ｍ１〜ｍｋを出力することができる。ステップＳ９４〜Ｓ９６のループ処理をｉ＝ｋまで終了すると、復号装置４０は、本フローを終了する。
【０１３３】
以上のように第３実施形態に係る暗号処理システム１０によれば、複数の対象暗号文のそれぞれが正当であるか否かを検証することができる。暗号処理システム１０によれば、複数の対象暗号文のそれぞれを個別に検証するとともに、複数の対象暗号文を合成して検証するので、より確実に検証をすることができる。
【０１３４】
また、第３実施形態において、証明装置３０は、複数のコミットメント生成部６１−１〜６１−ｋおよび複数のレスポンス生成部６２−１〜６２−ｋを備えない構成であってもよい。すなわち、証明装置３０は、合成コミットメント生成部９１と、合成レスポンス生成部９２と、証明側チャレンジ生成部７１とを備える構成であってもよい。
【０１３５】
そして、この場合、検証装置５０は、複数の取得部６４−１〜６４−ｋおよび複数の検証部６５−１〜６５−ｋを備えない構成であってもよい。すなわち、検証装置５０は、合成取得部９３と、合成検証部９４と、検証側チャレンジ生成部７２とを備える構成であってもよい。
【０１３６】
これにより、証明装置３０および検証装置５０は、複数の対象暗号文のそれぞれを個別に検証しないでよいので、構成を非常に簡易にすることができる。
【０１３７】
第３の実施形態では、ｋ個のチャレンジ値ｅ１，ｅ２，…，ｅｋおよび１個の合成チャレンジ値ｅｔｔｌは、相異なる値としているが、全て同一の値であってもよい。すなわち、証明側チャレンジ生成部７１は、ｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、合成コミットメント生成部９１から出力された１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）を受け取ると、１個のチャレンジ値ｅを出力し、それをレスポンス生成部６２−１〜６２−ｋと合成レスポンス生成部９２に出力する。また、検証側チャレンジ生成部７２は、ｋ個の取得部６４−１〜６４−ｋにより受信されたｋ組のコミットメント文（Ａ１，Ｂ１）〜（Ａｋ，Ｂｋ）、および、合成取得部９３により受信された１組の合成コミットメント文（Ａｔｔｌ，Ｂｔｔｌ）を受け取ると、（２ｋ＋２）個のコミットメント文をハッシュ関数に入力して、１個のチャレンジ値ｅを、検証部６５−１から６５−ｋと合成検証部９４に出力する。このように構成することで、証明側チャレンジ生成部７１および検証側チャレンジ生成部７２が生成すべきチャレンジのビット長を削減することができる。
【０１３８】
図１０は、第１〜第３実施形態に係る出力装置１１および入力装置１２のハードウェア構成の一例を示す図である。第１〜第３実施形態に係る出力装置１１および入力装置１２は、ＣＰＵ（Central  Processing  Unit）１０１などの制御装置と、ＲＯＭ（Read  Only  Memory）１０２やＲＡＭ（Random  Access  Memory）１０３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ１０４と、各部を接続するバスを備えている。
【０１３９】
実施形態にかかる出力装置１１および入力装置１２で実行されるプログラムは、ＲＯＭ１０２等に予め組み込まれて提供される。
【０１４０】
実施形態にかかる出力装置１１および入力装置１２で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０１４１】
さらに、実施形態にかかる出力装置１１および入力装置１２で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、実施形態にかかる出力装置１１および入力装置１２で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１４２】
実施形態にかかる出力装置１１で実行されるプログラムは、コンピュータを上述した出力装置１１の各部（コミットメント生成部６１，６１−１〜６１−ｋ、レスポンス生成部６２，６２−１〜６２−ｋ、証明側チャレンジ生成部７１、暗号化部８１−１〜８１−ｋ、合成コミットメント生成部９１、および、合成レスポンス生成部９２）として機能させうる。なお、これらの各部は、一部または全部がハードウェアにより構成されていてもよい。
【０１４３】
また、実施形態にかかる入力装置１２で実行されるプログラムは、コンピュータを上述した入力装置１２の各部（チャレンジ生成部６３、取得部６４，６４−１〜６４−ｋ、検証部６５，６５−１〜６５−ｋ、検証側チャレンジ生成部７２、復号部８２−１〜８２−ｋ、合成取得部９３、合成検証部９４）として機能させうる。なお、これらの各部は、一部または全部がハードウェアにより構成されていてもよい。このコンピュータは、ＣＰＵ１０１がコンピュータ読取可能な記憶媒体からプログラムを主記憶装置上に読み出して実行することができる。
【０１４４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１４５】
１０  暗号処理システム
１１  出力装置
１２  入力装置
２０  暗号化装置
３０  証明装置
４０  復号装置
５０  検証装置
６１  コミットメント生成部
６２  レスポンス生成部
６３  チャレンジ生成部
６４  取得部
６５  検証部
７１  証明側チャレンジ生成部
７２  検証側チャレンジ生成部
８１  暗号化部
８２  復号部
８３  決定部
９１  合成コミットメント生成部
９２  合成レスポンス生成部
９３  合成取得部
９４  合成検証部
１０１  ＣＰＵ
１０２  ＲＯＭ
１０３  ＲＡＭ
１０４  通信Ｉ／Ｆ
【図１】
2014220661.tif 000003
【図２】
2014220661.tif 000004
【図３】
2014220661.tif 000005
【図４】
2014220661.tif 000006
【図５】
2014220661.tif 000007
【図６】
2014220661.tif 000008
【図７】
2014220661.tif 000009
【図８】
2014220661.tif 000010
【図９】
2014220661.tif 000011
【図１０】
2014220661.tif 000012