(57)【特許請求の範囲】
【請求項１】
共通参照情報生成装置とコミット生成装置とコミット受信装置とを含むコミットメントシステムであって、
^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Sは{0,1}к×(Zn^d+1)3の集合であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、Wは0以上nd+2/2以下の整数の集合であり、tはкビットのタグであり、
前記共通参照情報生成装置は、
前記単数群Zn^d+1×から乱数hを、前記集合Kから乱数k~,k,k1,k2をそれぞれ選択し、値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算し、前記剰余環Zn^dから乱数xを、前記集合Vから乱数ν~をそれぞれ選択し、値u~=hν~、値e~=g-xy~ν~をそれぞれ計算し、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する鍵生成部と、
前記秘密鍵skを廃棄する鍵廃棄部と、
前記公開鍵pkを公開する公開部と、
を含み、
前記コミット生成装置は、
前記タグtと前記公開鍵pkを入力とし、前記集合Wから乱数z~,zを、前記集合Sから乱数υ,e,πをそれぞれ選択し、乱数r:=(z~,z)及びサンプル値u:=(υ,e,π)を出力する乱数生成部と、
平文m∈Zn^dと前記公開鍵pkと前記乱数rと前記タグtと前記サンプル値uとを入力とし、値A=y~z~yz(e~e)m、値a~=hz~u~m、値a=hzυm、値τ=H(pk,t,υ,e)、値b=(y1y2τ)zπmをそれぞれ計算し、暗号文c=(A,a~,a,b)を出力する暗号化部と、
前記暗号文cと前記タグtと前記サンプル値uとを前記コミット受信装置へ送信するコミット部と、
前記平文mと前記乱数rとを前記コミット受信装置へ送信する開示部と、
を含み、
前記コミット受信装置は、
前記平文mと前記公開鍵pkと前記乱数rと前記タグtと前記サンプル値uと前記暗号文cとを入力とし、値A’=y~z~yz(e~e)m、値a~’=hz~u~m、値a’=hzυm、値τ=H(pk,t,υ,e)、値b’=(y1y2τ)zπmをそれぞれ計算し、暗号文c’:=(A’,a~’,a’,b’)を生成し、前記暗号文c’と前記暗号文cとが等しいか否かを確認する開封部、
を含むコミットメントシステム。
【請求項２】
^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、
前記単数群Zn^d+1×から乱数hを、前記集合Kから乱数k~,k,k1,k2をそれぞれ選択し、値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算し、前記剰余環Zn^dから乱数xを、前記集合Vから乱数ν~をそれぞれ選択し、値u~=hν~、値e~=g-xy~ν~をそれぞれ計算し、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する鍵生成部と、
前記秘密鍵skを廃棄する鍵廃棄部と、
前記公開鍵pkを公開する公開部と、
を含む共通参照情報生成装置。
【請求項３】
^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Sは{0,1}к×(Zn^d+1)3の集合であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、Wは0以上nd+2/2以下の整数の集合であり、tはкビットのタグであり、
h∈Zn^d+1×であり、k~,k,k1,k2∈Kであり、x∈Zn^dであり、ν~∈Vであり、y~=hk~であり、y=hkであり、y1=hk_1であり、y2=hk_2であり、u~=hν~であり、値e~=g-xy~ν~であり、
前記タグtと公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)を入力とし、前記集合Wから乱数z~,zを、前記集合Sから乱数υ,e,πをそれぞれ選択し、乱数r:=(z~,z)及びサンプル値u:=(υ,e,π)を出力する乱数生成部と、
平文m∈Zn^dと前記公開鍵pkと前記乱数rと前記タグtと前記サンプル値uとを入力とし、値A=y~z~yz(e~e)m、値a~=hz~u~m、値a=hzυm、値τ=H(pk,t,υ,e)、値b=(y1y2τ)zπmをそれぞれ計算し、暗号文c=(A,a~,a,b)を出力する暗号化部と、
前記暗号文cと前記タグtと前記サンプル値uとを前記コミット受信装置へ送信するコミット部と、
前記平文mと前記乱数rとを前記コミット受信装置へ送信する開示部と、
を含むコミット生成装置。
【請求項４】
^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Sは{0,1}к×(Zn^d+1)3の集合であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、Wは0以上nd+2/2以下の整数の集合であり、tはкビットのタグであり、
h∈Zn^d+1×であり、k~,k,k1,k2∈Kであり、x∈Zn^dであり、ν~∈Vであり、y~=hk~であり、y=hkであり、y1=hk_1であり、y2=hk_2であり、u~=hν~であり、e~=g-xy~ν~であり、
z~,z∈Wであり、ν∈Vであり、υ,e,π∈Sであり、A=y~z~yz(e~e)mであり、a~=hz~u~mであり、a=hzυmであり、τ=H(pk,t,υ,e)であり、b=(y1y2τ)zπmであり、
平文m∈Zn^dと公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)と乱数r:=(z~,z)と前記タグtとサンプル値u:=(υ,e,π)と暗号文c=(A,a~,a,b)とを入力とし、値A’=y~z~yz(e~e)m、値a~’=hz~u~m、値a’=hzυm、値τ=H(pk,t,υ,e)、値b’=(y1y2τ)zπmをそれぞれ計算し、暗号文c’:=(A’,a~’,a’,b’)を生成し、前記暗号文c’と前記暗号文cとが等しいか否かを確認する開封部、
を含むコミット受信装置。
【請求項５】
^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Sは{0,1}к×(Zn^d+1)3の集合であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、Wは0以上nd+2/2以下の整数の集合であり、tはкビットのタグであり、
共通参照情報生成装置が、前記単数群Zn^d+1×から乱数hを、前記集合Kから乱数k~,k,k1,k2をそれぞれ選択し、値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算し、前記剰余環Zn^dから乱数xを、前記集合Vから乱数ν~をそれぞれ選択し、値u~=hν~、値e~=g-xy~ν~をそれぞれ計算し、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する鍵生成ステップと、
前記共通参照情報生成装置が、前記秘密鍵skを廃棄する鍵廃棄ステップと、
前記共通参照情報生成装置が、前記公開鍵pkを公開する公開ステップと、
コミット生成装置が、前記タグtと前記公開鍵pkを入力とし、前記集合Wから乱数z~,zを、前記集合Sから乱数υ,e,πをそれぞれ選択し、乱数r:=(z~,z)及びサンプル値u:=(υ,e,π)を出力する乱数生成ステップと、
前記コミット生成装置が、平文m∈Zn^dと前記公開鍵pkと前記乱数rと前記タグtと前記サンプル値uとを入力とし、値A=y~z~yz(e~e)m、値a~=hz~u~m、値a=hzυm、値τ=H(pk,t,υ,e)、値b=(y1y2τ)zπmをそれぞれ計算し、暗号文c=(A,a~,a,b)を出力する暗号化ステップと、
前記コミット生成装置が、前記暗号文cと前記タグtと前記サンプル値uとをコミット受信装置へ送信するコミットステップと、
前記コミット生成装置が、前記平文mと前記乱数rとを前記コミット受信装置へ送信する開示ステップと、
前記コミット受信装置が、前記平文mと前記公開鍵pkと前記乱数rと前記タグtと前記サンプル値uと前記暗号文cとを入力とし、値A’=y~z~yz(e~e)m、値a~’=hz~u~m、値a’=hzυm、値τ=H(pk,t,υ,e)、値b’=(y1y2τ)zπmをそれぞれ計算し、暗号文c’:=(A’,a~’,a’,b’)を生成し、前記暗号文c’と前記暗号文cとが等しいか否かを確認する開封ステップと、
を含むコミットメント方法。
【請求項６】
請求項２に記載の共通参照情報生成装置もしくは請求項３に記載のコミット生成装置もしくは請求項４に記載のコミット受信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は情報セキュリティ技術に関し、特に、複数の暗号プロトコルに組み込まれ同時に動くような環境であっても高い安全性を保つコミットメント技術に関する。
【背景技術】
【０００２】
暗号におけるコミットメントとは、電子的に行う「封じ手」のことである。コミットメント方式は、コミットする側の送信者（committer）と、コミットメントを受ける側の受信者（receiver）の間で行われるプロトコルのことである。送信者は、コミットフェーズで、受信者に情報を預託（コミット）する。この時、受信者は預託された情報の中身を知ることが出来ない（秘匿性）。次に、送信者は開示フェーズで秘匿した情報を受信者に納得いく形で開示するが、コミットフェーズで預託した情報と違う情報を開示して受信者を満足させることは出来ない（拘束性）。コミットメントは、基本的にこのような秘匿性と拘束性を満たさなければいけない。コミットメントのすぐ思いつく応用例は、電子的なジャンケンやコイン投げ（もちろん、将棋や碁に使う封じ手でもよい）であるが、実際に応用できる範囲はそれより遥かに広い。
【０００３】
コミットメントは、最も基本的な暗号プロトコルであるため、上位の暗号プロトコルの中で頻繁に利用される。近年では、暗号プロトコルをより現実の環境に近づけるため、コミットメントはさらに複雑な組み合わせの中で利用される場合が増えてきた。このような複雑な組み合わせの中では、古典的暗号安全性モデルで作られたコミットメントでは、秘匿性と拘束性を同時に満たすことが出来なくなってしまう。汎用結合可能コミットメントとは、そのような複雑な組み合わせでコミットメントが利用された場合にも、秘匿性と拘束性を満たすよう設計されたコミットメントのことである（汎用結合可能性については非特許文献１，２参照）。
【０００４】
汎用結合可能コミットメントが構成出来るためには、送信者と受信者の双方がアクセスできる第三者の作った共通参照情報（common reference string、以下CRSとも呼ぶ）が必要であることが知られている（非特許文献３参照）。技術的な問題により、このCRSは、コミットごとに使い捨てなければいけない場合（すなわち、コミットの回数だけ新しいCRSが必要となる）と、使い捨てずに同じCRSを再利用できる場合に分かれる。当然ながら、CRSをずっと使える「CRS再利用型」コミットメント方式の方が実用性は高い。従来のCRS再利用型汎用結合可能コミットメントには非特許文献１，３，４，５，６に記載された技術があった。
【０００５】
汎用結合可能コミットメントでは、送信者と受信者が、プロトコルの最中もしくは終了後、途中データを廃棄しないと安全性が担保出来ない方式と、廃棄しなくても安全性を担保できる方式が存在する。当然、後者の「情報廃棄不要型」汎用結合可能コミットメントの方が、安全性が高く望ましい。
【０００６】
さらに、計算量、通信量、交信回数なども、汎用結合コミットメントの良し悪しを判断する指標となる。当然、計算量、通信量、交信回数が少ないほど実用性が高い。特に、送信者から受信者に送るだけでコミットメントが完成する方式を「非対話型」汎用結合可能コミットメントという。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】R. Canetti, “Universally composable security: A new paradigm for cryptographic protocols”, 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2001), pp. 136-145, IEEE Computer Society, 2001.
【非特許文献２】Ran Canetti, “Universally composable security: A new paradigm for cryptograpic protocols”, Technical report, Cryptology ePrint Archive, Report 2000/067, 2005. Preliminary version appeared in FOCS’01.
【非特許文献３】R. Canetti and M. Fischlin, “Universally composable commitments”, CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pp. 19-40, 2001.
【非特許文献４】R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai, “Universally composable two-party and multiparty secure computation”, STOC 2002, pp. 494-503, 2002.
【非特許文献５】Ivan Damgard and Jesper Buus Nielsen, “Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor”, CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pp. 581-596, 2002.
【非特許文献６】Ivan Damgard and Jens Groth, “Non-interactive and reusable non-malleable commitment schemes”, STOC 2003, pp. 426-437, 2003.
【非特許文献７】Ryo Nishimaki, Eiichiro Fujisaki, and Keisuke Tanaka, “Efficient non-interactive universally composable string-commitment schemes”, ProvSec 2009, volume 5848 of Lecture Notes in Computer Science, pp. 3-18, 2009.
【非特許文献８】Yehuda Lindell, “Highly-efficient universally-composable commitments based on the DDH assumption”, EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pp. 446-466, 2011.
【非特許文献９】Marc Fischlin, Benoit Libert, and Mark Manulis, “Non-interactive and re-usable universally composable string commitments with adaptive security”, ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pp. 468-485, 2011.
【非特許文献１０】Eiichiro Fujisaki, “A framework for efficient fully-equipped UC commitments”, IACR Cryptology ePrint Archive, 2012:379, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献５，６以外の従来方式は、1ビットの秘密情報をコミットするのにO(к)ビット（кはセキュリティパラメータで、к=2048,160など）の平文空間を持つ選択暗号文攻撃に対して安全な公開鍵暗号が最低二つ必要であった。すなわち、1ビットの秘密情報をコミットするのに、O(к)ビットの情報量が必要であり効率が悪い。
【０００９】
非特許文献５，６の方式では、кビットの秘密情報をコミットするのにO(к)ビットで済むので効率は改善されている。しかし、これらのプロトコルは送信者と受信者間の交信回数を３回必要としている。また、非特許文献５の方式は、CRSのサイズが参加者の数に比例して増える。これは、コミットメント方式をサブプロトコルに使う上位のプロトコルの参加者数が増えると、それに応じてCRSのサイズが伸びることを意味する。一方、非特許文献６の方式は、CRSのサイズは固定だが、途中データを適切な時に廃棄しないと安全性が担保されない可能性がある。いずれにせよ、非特許文献５，６のいずれの方式とも送信者と受信者の間に３交信が必要であるという欠点がある。
【００１０】
近年、非特許文献７，８，９などの効率のよい方式が提案されているが、非特許文献７の方式は非対話型だがCRS再利用型ではない。非特許文献８の方式は通信量が少ないが５交信対話型であり途中データを適切に廃棄できなければいけない。非特許文献９の方式は非対話型だがやはり途中データを廃棄できなければいけない。
【００１１】
このように従来技術では、CRS再利用型で、非対話型で、情報廃棄不要型の効率的な（理想的にはкビットの秘密をコミットするのにO(к)ビットで済む）汎用結合可能コミットメントは存在しなかった。
【００１２】
最近、非特許文献１０の方式が、CRS再利用型で、非対話型で、情報廃棄不要型の効率的な汎用結合可能コミットメントを発明した。しかし、非特許文献１０の方式ではセキュリティパラメータのサイズкに対して、O(к2)のサイズのCRSを必要としていた。
【００１３】
この発明の目的は、CRS再利用型で、非対話型で、情報廃棄不要型の効率的な汎用結合可能コミットメントにおいて、共通参照情報を短くすることである。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、この発明のコミットメントシステムは、共通参照情報生成装置とコミット生成装置とコミット受信装置とを含む。この発明では、^はべき乗を表し、кは正の整数のセキュリティパラメータであり、p,qは素数であり、n=pqであり、g=1+nであり、dは1以上の整数であり、Zn^dはndを法とする剰余環であり、Zn^d+1はnd+1を法とする剰余環であり、Zn^d+1×は剰余環Zn^d+1の単数群であり、Hは{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数であり、Sは{0,1}к×(Zn^d+1)3の集合であり、Kは0以上n2/2以下の整数の集合であり、Vは0以上n/2以下の整数の集合であり、Wは0以上nd+2/2以下の整数の集合であり、tはкビットのタグであるとする。
【００１５】
共通参照情報生成装置は、鍵生成部と鍵廃棄部と公開部とを含む。鍵生成部は、単数群Zn^d+1×から乱数hを、集合Kから乱数k~,k,k1,k2をそれぞれ選択し、値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算し、剰余環Zn^dから乱数xを、集合Vから乱数ν~をそれぞれ選択し、値u~=hν~、値e~=g-xy~ν~をそれぞれ計算し、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する。鍵廃棄部は、秘密鍵skを廃棄する。公開部は、公開鍵pkを公開する。
【００１６】
コミット生成装置は、乱数生成部と暗号化部とコミット部と開示部とを含む。乱数生成部は、タグtと公開鍵pkを入力とし、集合Wから乱数z~,zを、集合Sから乱数υ,e,πをそれぞれ選択し、乱数r:=(z~,z)及びサンプル値u:=(υ,e,π)を出力する。暗号化部は、平文m∈Zn^dと公開鍵pkと乱数rとタグtとサンプル値uとを入力とし、値A=y~z~yz(e~e)m、値a~=hz~u~m、値a=hzυm、値τ=H(pk,t,υ,e)、値b=(y1y2τ)zπmをそれぞれ計算し、暗号文c=(A,a~,a,b)を出力する。コミット部は、暗号文cとタグtとサンプル値uとをコミット受信装置へ送信する。開示部は、平文mと乱数rとをコミット受信装置へ送信する。
【００１７】
コミット受信装置は、開封部を含む。開封部は、平文mと公開鍵pkと乱数rとタグtとサンプル値uと暗号文cとを入力とし、値A’=y~z~yz(e~e)m、値a~’=hz~u~m、値a’=hzυm、値τ=H(pk,t,υ,e)、値b’=(y1y2τ)zπmをそれぞれ計算し、暗号文c’:=(A’,a~’,a’,b’)を生成し、暗号文c’と暗号文cとが等しいか否かを確認する。
【発明の効果】
【００１８】
この発明は、CRS再利用型で、非対話型で、情報廃棄不要型の効率的な汎用結合可能コミットメントにおいて、共通参照情報を短くすることができる。
【図面の簡単な説明】
【００１９】
【図１】コミットメントシステムの機能構成を例示する図。
【図２】共通参照情報生成装置の機能構成を例示する図。
【図３】コミット生成装置の機能構成を例示する図。
【図４】コミット受信装置の機能構成を例示する図。
【図５】共通参照情報生成の処理フローを例示する図。
【図６】コミットおよびデコミットの処理フローを例示する図。
【発明を実施するための形態】
【００２０】
実施形態の説明に先立ち、この明細書で用いる表記方法および用語を定義する。
【００２１】
［表記方法］
・上付き添字はべき乗を表す。例えば、xyはxのy乗である。
・^（キャレット）は上付き添字を表す。例えば、xy^zはyzがxに対する上付き添字であり、xy^zはyzがxに対する下付き添字であることを表す。
・_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
・~（チルダ）は直前の文字にサーカムフレックスが付されることを表す。例えば、x~は数式内における以下の文字を表している。
【００２２】
【数１】
0005943880.tif 000002
【００２３】
・∃は存在記号である。例えば、∃xは「少なくとも1つのxが存在する」ことを表す。
・以下の記号は床関数を表す。すなわちx以下の最大の整数を表す。
【００２４】
【数２】
0005943880.tif 000003
【００２５】
［All-But-Many暗号］
この発明では、All-but-many暗号（以下、ABM暗号と呼ぶ）を利用する。ABM暗号は、(weak) extractable Sigmaプロトコルと、出力値が予測不能な確率的な擬似ランダム関数を組み合わせることで構成することができる。(weak) extractable Sigmaプロトコルについての詳細は、「Eiichiro Fujisaki, “New constructions of efficient simulation-sound commitments using encryption and their applications”, CT-RSA, volume 7178 of Lecture Notes in Computer Science, pp. 136-155, 2012.（参考文献１）」を参照されたい。ABM暗号の構成方法の詳細は非特許文献１０を参照されたい。
【００２６】
以下、ABM暗号の概略を説明する。ABM暗号は、鍵生成アルゴリズム（ABM.gen）、サンプリングアルゴリズム（ABM.spl）、暗号化アルゴリズム（ABM.enc）、復号アルゴリズム（ABM.dec）、コリジョンアルゴリズム（ABM.col）の、５つのアルゴリズムからなる公開鍵暗号方式である。
【００２７】
鍵生成アルゴリズム（ABM.gen）は確率的アルゴリズムである。セキュリティパラメータ1кを入力とし、公開鍵pkと秘密鍵skの鍵ペア(pk,sk)を出力する。公開鍵pkは集合の組(S,L)の記述を含む。ただし、S={0,1}к×U、L={0,1}к×Lu、LuはUの真部分集合、Uはあらかじめ定めた集合である。なお、記述の簡素化のため秘密鍵skは公開鍵pkを含むものとする。
【００２８】
サンプリングアルゴリズム（ABM.spl）は確率的アルゴリズムである。秘密鍵sk、タグt∈{0,1}кを入力とし、サンプル値u(=ABM.splL(sk,t;r))を出力する。ただし、(t,u)∈L（つまりu∈Lu）である。サンプル値uを出力するときに使用する乱数rをサンプルする領域をCOINsplとする。領域COINsplは公開鍵pkによって一意に定まる。
【００２９】
暗号化アルゴリズム（ABM.enc）は確率的アルゴリズムである。公開鍵pk、タグt∈{0,1}кとサンプル値uとの組(t,u)∈S、平文x∈MSPを入力とし、暗号文c(=ABM.enc(t,u)(pk,x;r))を出力する。ただし、rは乱数、MSPは平文空間、COINを乱数空間とする。平文空間MSPは公開鍵pkから一意に定まる。また、乱数空間COINは公開鍵pkと平文x∈MSPとによって一意に定まる。
【００３０】
復号アルゴリズム（ABM.dec）は確定的アルゴリズムである。秘密鍵sk、タグt∈{0,1}кとサンプル値uとの組(t,u)∈S、暗号文cを入力とし、平文x(=ABM.dec(t,u)(sk,c))を出力する。
【００３１】
コリジョンアルゴリズム（ABM.col）は２つの確率的アルゴリズム（ABM.col1、ABM.col2）の組である。第１のコリジョンアルゴリズム（ABM.col1）は、秘密鍵sk、乱数r~∈COINspl、タグt∈{0,1}кを入力とし、暗号文cと値ξの組(c,ξ)(←ABM.col1(sk,r~;t))を出力する。第２のコリジョンアルゴリズム（ABM.col2）は、値ξ、平文x∈MSPを入力とし、u=ABM.spl(sk,t;r~)かつc=ABM.enc(t,u)(pk,x;r)を満たす乱数r∈COINを出力する。
【００３２】
ABM暗号はall-but-many特性およびdual mode特性を有する公開鍵暗号方式である。all-but-many特性は、鍵生成アルゴリズム（ABM.gen）とサンプリングアルゴリズム（ABM.spl）が確率的擬似ランダム関数（probabilistic pseudo random function; PPRF）の性質を有することを言う。確率的擬似ランダム関数（PPRF）はeasy sampling, pseudo randomness, unforgeabilityの各種安全性を満たす関数である。dual mode特性は、復号方式（Decryption mode）と落とし戸方式（Trap-door mode）の両方を有することを言う。復号方式（Decryption mode）では、すべての(t,u)∈S\Lpk, x∈MSPについて、ABM.dec(t,u)(sk,ABM.enc(t,u)(pk,x))=xが成り立つ。落とし戸方式（Trap-door mode）では、すべての(t,u)∈Lpk, v∈COINspl, (c,ξ)←ABM.col1(sk,v,t), x∈MSPについて、c=ABM.enc(t,u)(pk,x;ABM.col2(ξ,x))が成り立つ。各種安全性条件の詳細及び証明は非特許文献１０を参照されたい。
【００３３】
ABM暗号を用いて、CRS再利用型で、非対話型で、情報廃棄不要型の汎用結合可能コミットメントを構成することができる。具体的には、公開鍵pkを共通参照情報とし、暗号文c=ABM.enc(pk,x;r)をコミットメントとする。コミットメントを開示するには、証拠として乱数rを出せばよい。
【００３４】
この発明の汎用結合可能コミットメントでは、ABM暗号の鍵生成アルゴリズム（ABM.gen）と暗号化アルゴリズム（ABM.enc）のみを用いる。サンプリングアルゴリズム（ABM.spl）と復号アルゴリズム（ABM.dec）とコリジョンアルゴリズム（ABM.col）はコミットメントでは用いられることがないが、ABM暗号の安全性証明のために必要となるアルゴリズムである。
【００３５】
［Damgard-Jurik暗号］
Damgard-Jurik暗号（以下、DJ暗号とも呼ぶ）は準同型性をもつ選択平文攻撃に対して識別不可能な暗号方式である。Damgard-Jurik暗号の安全性はDCR(Decision Composite Residuosity)仮定のもと成り立つ。
【００３６】
Damgard-Jurik暗号は、鍵生成アルゴリズム（K）、暗号化アルゴリズム（E）、復号アルゴリズム（D）の、３つのアルゴリズムからなる公開鍵暗号方式である。
【００３７】
鍵生成アルゴリズム（K）は以下の処理を行う。セキュリティパラメータkを入力とし、kビットの素数p,qを選択し、n=pqを計算する。sを1以上の整数、jをnと互いに素な整数として、g=(1+n)jx mod ns+1を計算する。p-1とq-1の最小公倍数λを計算し、d mod n ∈Znかつd=0 mod λを満たす値dを選択する。(n,g)を公開鍵とし、dを秘密鍵とする。
【００３８】
暗号化アルゴリズム（E）は以下の処理を行う。ns+1を法とする剰余環Zn^s+1から乱数rを選択する。平文i∈Zn^sを入力とし、暗号文c=girn^s mod ns+1を計算する。
【００３９】
復号アルゴリズム（D）は以下の処理を行う。cd mod ns+1, gd mod ns+1を計算する。cd=(1+n)jid mod n^s, gd=(1+n)jid mod n^sであることから、jid mod ns, jd mod nsを計算し、平文i=(jid)・(jd)-1 mod ndを計算する。
【００４０】
Damgard-Jurik暗号の各アルゴリズムについての詳細は「I. Damgard and M. Jurik, “A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system”, PKC 2001, volume 1992 of Lecture Notes in Computer Science, pp. 125-140, 2001.（参考文献２）」を参照されたい。DCR仮定についての詳細は「P. Pallier, “Public-Key Cryptosystems based on Composite Degree Residue Classes”, Proceedings of EuroCrypt 99, pp.223-238.（参考文献３）」を参照されたい。
【００４１】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００４２】
この発明の第一実施形態は、任意のABM暗号から構成される汎用結合可能コミットメントである。第二実施形態は、Damgard-Jurik暗号を利用してNon-Mult仮定に基づいて構成した汎用結合可能コミットメントである。Non-Mult仮定についての詳細は非特許文献１０に記載されている。
【００４３】
［第一実施形態］
上述の通り、第一実施形態は、任意のABM暗号から構成される汎用結合可能コミットメントである。上記のABM暗号の性質を有する暗号方式であれば適用することができる。
【００４４】
＜構成＞
図１を参照して、第一実施形態のコミットメントシステム１の構成例を説明する。コミットメントシステム１は共通参照情報生成装置２とコミット生成装置３とコミット受信装置４を含む。共通参照情報生成装置２とコミット生成装置３とコミット受信装置４とはそれぞれネットワーク５に接続される。ネットワーク５は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などで構成することができる。なお、各装置は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、コミット生成装置３の出力する情報を磁気テープやＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からコミット受信装置４へオフラインで入力するように構成してもよい。他の装置間の情報伝播においても同様であるので詳細な説明は省略する。
【００４５】
図２を参照して、コミットメントシステム１に含まれる共通参照情報生成装置２の構成例を説明する。共通参照情報生成装置２は、制御部２０１、メモリ２０２、入力部２１、鍵生成部２２、鍵廃棄部２３、公開部２４を有する。共通参照情報生成装置２は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。共通参照情報生成装置２は制御部２０１の制御のもとで各処理を実行する。共通参照情報生成装置２に入力されたデータや各処理で得られたデータはメモリ２０２に格納され、メモリ２０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００４６】
図３を参照して、コミットメントシステム１に含まれるコミット生成装置３の構成例を説明する。コミット生成装置３は、制御部３０１、メモリ３０２、記憶部３０３、入力部３１、乱数生成部３２、暗号化部３３、コミット部３４、開示部３５、出力部３６を有する。コミット生成装置３は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。コミット生成装置３は制御部３０１の制御のもとで各処理を実行する。コミット生成装置３に入力されたデータや各処理で得られたデータはメモリ３０２に格納され、メモリ３０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。記憶部３０３は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００４７】
図４を参照して、コミットメントシステム１に含まれるコミット受信装置４の構成例を説明する。コミット受信装置４は、制御部４０１、メモリ４０２、記憶部４０３、入力部４１、確認部４２、開封部４３、出力部４４を有する。コミット受信装置４は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。コミット受信装置４は制御部４０１の制御のもとで各処理を実行する。コミット受信装置４に入力されたデータや各処理で得られたデータはメモリ４０２に格納され、メモリ４０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。記憶部４０３は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００４８】
＜共通参照情報生成処理＞
図５を参照して、共通参照情報生成装置２の実行する共通参照情報生成処理の動作例を説明する。
【００４９】
共通参照情報生成装置２の有する入力部２１を介して鍵生成部２２へセキュリティパラメータ1кが入力される（ステップＳ２１）。鍵生成部２２は、セキュリティパラメータ1кを入力とし、任意のABM暗号の鍵生成アルゴリズム（ABM.gen）を(pk,sk)←ABM.gen(1к)として実行し、公開鍵pkと秘密鍵skの鍵ペア(pk,sk)を生成する（ステップＳ２２）。
【００５０】
鍵ペア(pk,sk)は鍵廃棄部２３へ入力される。鍵廃棄部２３は鍵ペア(pk,sk)に含まれる秘密鍵skを廃棄する（ステップＳ２３）。
【００５１】
公開鍵pkは公開部２４へ入力される。公開部２４は公開鍵pkを共通参照情報として公開する（ステップＳ２４）。公開の方法はコミット生成装置３とコミット受信装置４とが公開鍵pkを参照できる方法であればどのような方法であってもよい。共通参照情報生成装置２からコミット生成装置３とコミット受信装置４とへ個別の通信経路により公開鍵pkを送信してもよいし、任意の公開鍵基盤（Public Key Infrastructure; PKI）などを用いて公開鍵pkを公開し、コミット生成装置３とコミット受信装置４とが任意のタイミングで参照するように構成してもよい。コミット生成装置３は共通参照情報として公開された公開鍵pkを記憶部３０３へ記憶する。コミット受信装置４は同様に共通参照情報として公開された公開鍵pkを記憶部４０３へ記憶する。
【００５２】
＜コミット（封じ手）フェーズ＞
図６を参照して、コミット生成装置３とコミット受信装置４との間で実行されるコミット（封じ手）フェーズの動作例を手続きの順に従って詳細に説明する。
【００５３】
コミット生成装置３の有する入力部３１へタグt∈{0,1}кと平文m∈MSPが入力される（ステップＳ３１）。ただし、MSPは公開鍵pkにより一意に定まる平文空間である。
【００５４】
乱数生成部３２は乱数r∈COINとサンプル値u∈Uを生成する（ステップＳ３２）。ただし、COINは公開鍵pkと平文mとにより一意に定まる乱数空間、Uはあらかじめ定めた集合である。乱数生成部３２は逐一ランダムに乱数rとサンプル値uを選択してもよいし、事前に生成されメモリ３０２に格納されている複数個の値から所定の規則に従って乱数rとサンプル値uを選択してもよい。
【００５５】
平文mと乱数rとタグtとサンプル値uとは暗号化部３３へ入力される。暗号化部３３は記憶部３０３から公開鍵pkを取得する。次に、暗号化部３３は、平文mを入力とし、公開鍵pkと乱数rとタグtとサンプル値uを用いて、任意のABM暗号の暗号化アルゴリズム（ABM.enc）をc←ABM.enc(t,u)(pk,m;r)として実行し、暗号文cを生成する（ステップＳ３３）。
【００５６】
平文mと乱数rとタグtとサンプル値uと暗号文cとはコミット部３４へ入力される。コミット部３４は出力部３６を介してタグtとサンプル値uと暗号文cとをコミット受信装置４へ出力する（ステップＳ３４）。コミット受信装置４は受信したタグtとサンプル値uと暗号文cとを記憶部４０３へ記憶する（ステップＳ４０３）。同時に、コミット部３４は平文mと乱数rとを記憶部３０３へ記憶する（ステップＳ３０３）。
【００５７】
＜デコミット（開示）フェーズ＞
図６を参照して、コミット生成装置３とコミット受信装置４との間で実行されるデコミット（開示）フェーズの動作例を手続きの順に従って詳細に説明する。
【００５８】
コミット生成装置３の有する開示部３５は記憶部３０３から平文mと乱数rとを取得し、出力部３６を介してコミット受信装置４へ出力する（ステップＳ３５）。
【００５９】
平文mと乱数rとはコミット受信装置４の有する入力部４１を介して確認部４２へ入力される（ステップＳ４１）。確認部４２は記憶部４０３からタグtとサンプル値uとを読み出し、以下の条件を検証する（ステップＳ４２）。以下の条件のいずれかが満たさないことを確認した場合には処理を中断する。
１．記憶部４０３から取得したタグtがкビットのビット列であること（t∈{0,1}к）。
２．記憶部４０３から取得したサンプル値uが集合Uの元であること（u∈U）。
３．入力された平文mが平文空間MSPの元であること（m∈MSP）。
４．入力された乱数rが乱数空間COINの元であること（r∈COIN）。
【００６０】
確認部４２が上記の条件をすべて満たすことを確認した場合には、記憶部４０３から取得したタグtとサンプル値uおよび入力された平文mと乱数rとが開封部４３へ入力される。開封部４３は、平文mを入力とし、公開鍵pkと乱数rとタグtとサンプル値uを用いて、任意のABM暗号の暗号化アルゴリズム（ABM.enc）をc’←ABM.enc(t,u)(pk,m;r)として実行し、暗号文c’を生成する（ステップＳ４３）。
【００６１】
次に、開封部４３は記憶部４０３から暗号文cを取得し、生成した暗号文c’と取得した暗号文cとが等しいことを確認する。暗号文c’と暗号文cとが等しい場合には開封を承認する。暗号文c’と暗号文cとが等しくない場合には開封を拒絶する。
【００６２】
開封を承認するか開封を拒絶するかを示す開封結果は出力部４４を介して出力される（ステップＳ４４）。
【００６３】
［第二実施形態］
上述の通り、第二実施形態は、Damgard-Jurik暗号を利用してNon-Mult仮定に基づいて構成した汎用結合可能コミットメントである。第二実施形態では、кビットの情報をコミットするための情報量がO(к)ビットで済むため効率的であり、セキュリティパラメータкに対して共通参照情報のサイズがO(к)ビットのため従来よりも短くなっている。
【００６４】
なお、この実施形態ではDamgard-Jurik暗号を用いてコミットメントシステムを構成する例を説明するが、準同型性をもつ選択平文攻撃に対して識別不可能な暗号方式であれば、容易に置換することが可能である。
【００６５】
＜定義＞
この実施形態では以下のように記号を定義する。
・p,qは素数であり、n=pqである。
・dは1以上の正の整数である（d≧1）。
・Π=(K,E,D)は、Damgard-Jurik暗号の各アルゴリズムである。Kは鍵生成アルゴリズムである。Eは暗号化アルゴリズムである。Dは復号アルゴリズムである。Damgard-Jurik暗号の各アルゴリズムの詳細は参考文献２を参照されたい。
・Zn^dはndを法とする剰余環である。
・Zn^d+1はnd+1を法とする剰余環である。
・Zn^d+1×は剰余環Zn^d+1の単数群である。すなわち、剰余環Zn^d+1の中でnd+1と互いに素となる要素の集合である。
・HはH:{0,1}к×(Zn^d+1)2→Zn^dとなるハッシュ関数である。
・SはS={0,1}к×(Zn^d+1)3の集合である。
・LはL={(t,(υ,e,π))|∃(ν~,ν)}の集合である。ここで、t∈{0,1}к、υ=hν、e=gxyν、π=(y1y2σ)ν、ν~,ν∈Vである。ただし、σ=H(t,υ,e)、g=1+n、y=hk、y1=hk_1、y2=hk_2、k,k1,k2∈Kである。
・Kは0以上n2/2以下の整数の集合である。すなわち、次式で表される集合である。
【００６６】
【数３】
0005943880.tif 000004
【００６７】
・Vは0以上n/2以下の整数の集合である。すなわち、次式で表される集合である。
【００６８】
【数４】
0005943880.tif 000005
【００６９】
・Wは0以上nd+2/2以下の整数の集合である。すなわち、次式で表される集合である。
【００７０】
【数５】
0005943880.tif 000006
【００７１】
＜Damgard-Jurik暗号を用いて構成したABM暗号＞
第一実施形態では任意のABM暗号を用いてコミットメントシステムを構成したが、第二実施形態ではDamgard-Jurik暗号を用いて構成したABM暗号を用いる。
【００７２】
第二実施形態の鍵生成アルゴリズム（ABM.gen）はセキュリティパラメータкを入力とし公開鍵pkと秘密鍵skの鍵ペア(pk,sk)を出力する。具体的には以下の処理を実行する。кビット長の素数p,qを選択し、値n=pq、値g=1+nを計算する。単数群Zn^d+1×から乱数hを選択し、上記で定義したハッシュ関数Hを決定する。集合Kから乱数k~,k,k1,k2を選択する。値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算する。剰余環Zn^dから乱数xを、集合Vから乱数ν~をそれぞれ選択する。値u~=hν~、値e~=g-xy~ν~をそれぞれ計算する。そして、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する。
【００７３】
第二実施形態のサンプリングアルゴリズム（ABM.spl）は秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)及びタグt∈{0,1}кを入力とし、サンプル値u:=(υ,e,π)を出力する。具体的には以下の処理を実行する。集合Vから乱数νを選択する。値υ=hν、値e=gxyν、値π=(y1y2σ)νをそれぞれ計算する。ただし、値σ=H(t,υ,e)である。そして、サンプル値u:=(υ,e,π)を出力する。
【００７４】
第二実施形態の暗号化アルゴリズム（ABM.enc）は公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)、タグt∈{0,1}к、サンプル値u:=(υ,e,π)及び平文m∈Zn^dを入力とし、暗号文cを出力する。具体的には以下の処理を実行する。集合Wから乱数z~,zを選択する。値A=y~z~yz(e~e)m、値a~=hz~υ~m、値a=hzυm、値b=(y1y2τ)zπmをそれぞれ計算する。ただし、値τ=H(pk,t,υ,e)である。そして、暗号文c=(A,a~,a,b)を出力する。
【００７５】
第二実施形態の復号アルゴリズム（ABM.dec）は秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)、タグt∈{0,1}к、サンプル値u:=(υ,e,π)及び暗号文c=(A,a~,a,b)を入力とし、平文m∈Zn^dを出力する。具体的には以下の処理を実行する。まず、値τ=H(pk,t,υ,e)を計算し、以下の式(1)が成立するか否かを確認する。
【００７６】
【数６】
0005943880.tif 000007
【００７７】
式(1)が成立する場合には、以下の式(2)により平文mを生成する。
【００７８】
【数７】
0005943880.tif 000008
【００７９】
式(1)が成立しない場合には、以下の式(3)により平文mを生成する。
【００８０】
【数８】
0005943880.tif 000009
【００８１】
第二実施形態の第１のコリジョンアルゴリズム（ABM.col1）は秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)、乱数ν及びタグt∈{0,1}кを入力とし、暗号文cと値ξの組(c,ξ)を出力する。具体的には以下の処理を実行する。集合Wから乱数w~,wを選択する。値A=y~w~yw、値a~=hw~、値a=hw、値b=(y1y2τ)wを計算する。ただし、値τ=H(pk,t,υ,e)である。そして、暗号文c=(A,a~,a,b)及び値ξ:=(sk,w~,w)を出力する。
【００８２】
第二実施形態の第２のコリジョンアルゴリズム（ABM.col2）は値ξ:=(sk,w~,w)及び平文m∈Zn^dを入力とし、値の組(z~,z)を出力する。具体的には以下の処理を実行する。値z~=w~-m・ν∈Zを計算する。値z=w-m・ν∈Zを計算する。そして、(z~,z)を出力する。ここで、A=y~z~yz(e~e)m、a~=hz~u~m、a=hzum、b=(y1y2τ)zπmが常に成り立っている。
【００８３】
＜共通参照情報生成処理＞
第二実施形態の共通参照情報生成処理の動作例を手続きの順に従って詳細に説明する。ただし、第一実施形態と同様のステップは説明を省略する。
【００８４】
共通参照情報生成装置２の有する鍵生成部２２はセキュリティパラメータ1кを入力として、公開鍵pkと秘密鍵skの鍵ペア(pk,sk)を生成する（ステップＳ２２）。具体的には以下の処理を実行する。
【００８５】
まず、кビット長の素数p,qを選択し、値n=pq、値g=1+nを計算する。単数群Zn^d+1×から乱数hを選択する。ハッシュ関数Hを決定する。集合Kから乱数k~,k,k1,k2を選択する。値y~=hk~、値y=hk、値y1=hk_1、値y2=hk_2をそれぞれ計算する。剰余環Zn^dから乱数xを、集合Vから乱数ν~をそれぞれ選択する。値u~=hν~、値e~=g-xy~ν~をそれぞれ計算する。そして、公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)及び秘密鍵sk:=(pk,k~,k,k1,k2,ν~,x)を出力する。
【００８６】
＜コミット（封じ手）フェーズ＞
第二実施形態のコミット（封じ手）フェーズの動作例を手続きの順に従って詳細に説明する。ただし、第一実施形態と同様のステップは説明を省略する。
【００８７】
コミット生成装置３の有する乱数生成部３２は乱数rとサンプル値uとを生成する（ステップＳ３２）。具体的には以下の処理を実行する。
【００８８】
まず、集合Wから乱数z~,zを、集合Sから乱数υ,e,πをそれぞれ選択する。そして、乱数r:=(z~,z)及びサンプル値u:=(υ,e,π)を出力する。
【００８９】
コミット生成装置３の有する暗号化部３３は、平文m∈Zn^dを公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)、乱数r:=(z~,z)、タグt∈{0,1}к及びサンプル値u:=(υ,e,π)を用いて、Damgard-Jurik暗号の暗号化アルゴリズムEにより暗号化して暗号文cを生成する（ステップＳ３３）。具体的には以下の処理を実行する。
【００９０】
まず、値A=y~z~yz(e~e)m、値a~=hz~υ~m、値a=hzυm、値τ=H(pk,t,υ,e)、値b=(y1y2τ)zπmをそれぞれ計算する。そして、暗号文c=(A,a~,a,b)を生成する。
【００９１】
＜デコミット（開示）フェーズ＞
第二実施形態のデコミット（開示）フェーズの動作例を手続きの順に従って詳細に説明する。ただし、第一実施形態と同様のステップは説明を省略する。
【００９２】
コミット受信装置４の有する開封部４３は、平文m∈Zn^dを公開鍵pk:=(n,d,H,g,h,y~,y,y1,y2,u~,e~)、乱数r:=(z~,z)、タグt∈{0,1}к及びサンプル値u:=(υ,e,π)を用いて、Damgard-Jurik暗号の暗号化アルゴリズムEにより暗号化して暗号文c’を生成する（ステップＳ４３）。具体的には以下の処理を実行する。
【００９３】
まず、値A’=y~z~yz(e~e)m、値a~’=hz~υ~m、値a’=hzυm、値τ=H(pk,t,υ,e)、値b’=(y1y2τ)zπmをそれぞれ計算する。そして、暗号文c’:=(A’,a~’,a’,b’)を生成する。
【００９４】
次に、開封部４３は、暗号文cと暗号文c’とが等しいことを確認する。暗号文cの各要素と暗号文c’の各要素がすべて等しい場合には暗号文cと暗号文c’とが等しいとする。すなわち、A=A’、a~=a~’、a=a’、b=b’をすべて満たす場合には暗号文cと暗号文c’とが等しいものとする。いずれかの条件を満たさない場合には暗号文cと暗号文c’とが等しくないものとする。
【００９５】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００９６】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００９７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１００】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１０１】
１  コミットメントシステム
２  共通参照情報生成装置
３  コミット生成装置
４  コミット受信装置
５  ネットワーク
２１  入力部
２２  鍵生成部
２３  鍵廃棄部
２４  公開部
３１  入力部
３２  乱数生成部
３３  暗号化部
３４  コミット部
３５  開示部
３６  出力部
４１  入力部
４２  確認部
４３  開封部
４４  出力部
２０１  制御部
２０２  メモリ
２０３  記憶部
３０１  制御部
３０２  メモリ
３０３  記憶部
４０１  制御部
４０２  メモリ
４０３  記憶部
【図１】
0005943880.tif 000010
【図２】
0005943880.tif 000011
【図３】
0005943880.tif 000012
【図４】
0005943880.tif 000013
【図５】
0005943880.tif 000014
【図６】
0005943880.tif 000015