(57)【要約】【課題】鍵生成装置１００、暗号化装置２００、復号化装置３００を保持するユーザが複数存在するシステムにおいて（各ユーザは鍵生成装置１００によって作成された異なる鍵情報をもつ）任意数の暗号文を入手することが可能な攻撃者に対して、鍵長を増やすことなく十分な安全性レベルを保持することが可能であり、かつ、暗号化および復号化処理の効率性に優れた公開鍵暗号方法を提供する。【解決手段】本発明では、上記課題を解決するため、幾つかの方法を提供する。そのなかの一つの方法では、暗号文に対して固有のＩＤ情報を作成し、前記ＩＤ情報をハッシュ関数への入力値の一部に加えることにより暗号文を作成し、前記暗号文に前記ＩＤ情報を添付したものを新たな暗号文とする。この方法は既存の公開鍵暗号方法などに適用可能であり、既存方法の効率性を損なうことなく安全性を強化することが可能となる。【選択図】図１
2012027418.tif 000002
【特許請求の範囲】
【請求項１】
セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)および暗号文空間CSPΠ(k)が一意的に定まる公開鍵暗号Π=(K,E,D)を用いる公開鍵暗号装置における公開鍵暗号方法において、
前記公開鍵暗号装置の制御部は、
前記公開鍵暗号装置の入力部により入力されたセキュリティパラメータkに基づいて、前記公開鍵暗号Πを用いて公開鍵pkおよび秘密鍵skを生成するステップと、
H1を{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数とし、H2を{0,1}*×MSPΠ(k)×CSPΠ(k)×{0,1}2nから{0,1}kへのハッシュ関数としたとき、PK=(pk,H1,H2)およびSK=(sk,PK)を、それぞれを新たな公開鍵および秘密鍵として生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈MSPΠ(k)の暗号文uを、
【数５５】
2012027418.tif 000057
として生成するステップと、
【数５６】
2012027418.tif 000058
により、v,wを生成するステップと、
前記メッセージ文mの暗号文C=(u,v,w)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数５７】
2012027418.tif 000059
により、σを計算するステップと、
【数５８】
2012027418.tif 000060
により、mを計算するステップと、
【数５９】
2012027418.tif 000061
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする公開鍵暗号方法。
【請求項２】
前記制御部は、
Gを、素数qを位数とする乗法群とし、gをGから任意に選ばれた元とし、sを剰余群Zqから任意に選ばれた元とし、hを、
【数６０】
2012027418.tif 000062
とし、Hを{0,1}*×GからZqへのハッシュ関数としたとき、前記公開鍵pkおよび前記秘密鍵skをそれぞれ、pk=(G,q,g,h,H)およびsk=sとして生成するステップと、
H1を{0,1}*×G3から{0,1}nへのハッシュ関数とし、H2を{0,1}*×G3×{0,1}2nから{0,1}kへのハッシュ関数として、前記公開鍵PK=(pk,H1,H2)および前記秘密鍵SK=(sk,PK)を生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈Gの暗号文u=(u1,u2)を、
【数６１】
2012027418.tif 000063
として生成するステップと、
【数６２】
2012027418.tif 000064
により、v,wを生成するステップと、
前記メッセージ文mの暗号文C=(u,v,w)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数６３】
2012027418.tif 000065
により、σを計算するステップと、
【数６４】
2012027418.tif 000066
により、mを計算するステップと、
【数６５】
2012027418.tif 000067
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする請求項１に記載の公開鍵暗号方法。
【請求項３】
セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)、暗号文空間CSPΠ(k)、および乱数空間COINΠ(k)が一意的に定まる公開鍵暗号Π=(K,E,D)を用いる公開鍵暗号装置における公開鍵暗号方法において、
前記公開鍵暗号装置の制御部は、
前記公開鍵暗号装置の入力部により入力されたセキュリティパラメータkに基づいて、前記公開鍵暗号Πを用いて公開鍵pkおよび秘密鍵skを生成するステップと、
H1を{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数とし、H2を{0,1}*×MSPΠ(k)×{0,1}n×CSPΠ(k)×{0,1}nからCOINΠ(k)へのハッシュ関数としたとき、PK=(pk,H1,H2)およびSK=(sk,PK)を、それぞれを新たな公開鍵および秘密鍵として生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、R∈COINΠ(k)を任意に選び、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈MSPΠ(k)の暗号文uを、
【数６６】
2012027418.tif 000068
として生成するステップと、
【数６７】
2012027418.tif 000069
により、v,wを生成するステップと、
前記メッセージ文mの暗号文C=(u,v,w)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数６８】
2012027418.tif 000070
により、σを計算するステップと、
【数６９】
2012027418.tif 000071
により、mを計算するステップと、
【数７０】
2012027418.tif 000072
に対して、
【数７１】
2012027418.tif 000073
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする公開鍵暗号方法。
【請求項４】
前記制御部は、
Gを、素数qを位数とする乗法群とし、gをGから任意に選ばれた元とし、sを剰余群Zqから任意に選ばれた元とし、hを、
【数７２】
2012027418.tif 000074
とし、Hを{0,1}*×ZqからZqへのハッシュ関数としたとき、前記公開鍵pkおよび前記秘密鍵skをそれぞれ、pk=(G,q,g,h,H)およびsk=sとして生成するステップと、
H1を{0,1}*×G3から{0,1}nへのハッシュ関数とし、H2を{0,1}*×G×{0,1}n×G2×{0,1}nからZqへのハッシュ関数として、前記公開鍵PK=(pk,H1,H2)および前記秘密鍵SK=(sk,PK)を生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、R∈Zqを任意に選び、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈Gの暗号文u=(u1,u2)を、
【数７３】
2012027418.tif 000075
として生成するステップと、
【数７４】
2012027418.tif 000076
により、v,wを生成するステップと、
前記メッセージ文mの暗号文C=(u,v,w)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数７５】
2012027418.tif 000077
により、σを計算するステップと、
【数７６】
2012027418.tif 000078
により、mを計算するステップと、
【数７７】
2012027418.tif 000079
に対して、
【数７８】
2012027418.tif 000080
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする請求項３に記載の公開鍵暗号方法。
【請求項５】
公開鍵暗号を用いる公開鍵暗号装置における公開鍵暗号方法において、
前記公開鍵暗号装置の制御部は、
暗号文に対して固有のID情報を生成するステップと、
前記ID情報をハッシュ関数への入力の一部として利用することで、前記公開鍵暗号装置の入力部から入力されたメッセージ文に対し、前記暗号文を生成するステップと、
前記ID情報を前記暗号文に添付したものを新たな暗号文とするステップと、を実行する
ことを特徴とする公開鍵暗号方法。
【請求項６】
セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)、暗号文空間CSPΠ(k)、および乱数空間COINΠ(k)が一意的に定まる公開鍵暗号Π=(K,E,D)を用いる公開鍵暗号装置における公開鍵暗号方法において、
前記公開鍵暗号装置の制御部は、
前記公開鍵暗号装置の入力部により入力されたセキュリティパラメータkに基づいて、前記公開鍵暗号Πを用いて公開鍵pkおよび秘密鍵skを生成するステップと、
H1を{0,1}*×{0,1}*×MSPΠ(k)×{0,1}nからCOINΠ(k)へのハッシュ関数とし、H2を{0,1}*×{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数としたとき、PK=(pk,H1,H2)およびSK=(sk,PK)を、それぞれを新たな公開鍵および秘密鍵として生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、暗号文に固有の情報であるIDを生成し、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈MSPΠ(k)の暗号文uを、
【数７９】
2012027418.tif 000081
として生成するステップと、
【数８０】
2012027418.tif 000082
により、vを生成するステップと、
前記メッセージ文mの暗号文C=(ID,u,v)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数８１】
2012027418.tif 000083
により、σを計算するステップと、
【数８２】
2012027418.tif 000084
により、mを計算するステップと、
【数８３】
2012027418.tif 000085
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする公開鍵暗号方法。
【請求項７】
前記制御部は、
Gを、素数qを位数とする乗法群とし、gをGから任意に選ばれた元とし、sを剰余群Zqから任意に選ばれた元とし、hを、
【数８４】
2012027418.tif 000086
としたとき、前記公開鍵pkおよび前記秘密鍵skをそれぞれ、pk=(G,q,g,h)およびsk=sとして生成するステップと、
H1を{0,1}*×{0,1}*×G×{0,1}nからZqへのハッシュ関数とし、H2を{0,1}*×{0,1}*×G3から{0,1}nへのハッシュ関数として、前記公開鍵PK=(pk,H1,H2)および前記秘密鍵SK=(sk,PK)を生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵PKを取得すると、暗号文に固有の情報であるIDを生成し、前記公開鍵暗号Πの公開鍵pkを用いて、任意に選んだσ∈Gの暗号文u=(u1,u2)を、
【数８５】
2012027418.tif 000087
として生成するステップと、
【数８６】
2012027418.tif 000088
により、vを生成するステップと、
前記メッセージ文mの暗号文C=(ID,u,v)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵SKを取得すると、前記暗号文Cが、前記秘密鍵SKに対応する前記公開鍵PKにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、前記公開鍵暗号Πの秘密鍵skを用いて、前記暗号文uを復号化し、
【数８７】
2012027418.tif 000089
により、σを計算するステップと、
【数８８】
2012027418.tif 000090
により、mを計算するステップと、
【数８９】
2012027418.tif 000091
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする請求項６に記載の公開鍵暗号方法。
【請求項８】
セキュリティパラメータkによって定まる公開鍵暗号を用いる公開鍵暗号装置における公開鍵暗号方法において、
前記公開鍵暗号装置の制御部は、
Gを、素数qを位数とする乗法群とし、g1,g2をGから任意に選ばれた元とし、x1,x2,y1,y2を剰余群Zqから任意に選ばれた元とし、h1,h2を、
【数９０】
2012027418.tif 000092
とし、各i∈{1,2}に対して、Fi={Fi,k}k∈Nは関数族であり、Fi,k={fσi}σ∈Gであり、Gはkに応じて決定される集合I(k)の元であり、fσiは{0,1}kへの関数であるとき、前記公開鍵暗号装置の入力部により入力されたセキュリティパラメータkに基づいて、前記公開鍵暗号を用いて公開鍵pk=(G,q,g1,g2,h1,h2,F1,k,F2,k)、および秘密鍵sk=(x1,x2,y1,y2)を生成するステップと、
前記入力部により入力されたメッセージ文m∈{0,1}n、および前記生成された公開鍵pkを取得すると、任意に選んだr∈Zqを用いて、u1,u2を、
【数９１】
2012027418.tif 000093
として生成するステップと、
【数９２】
2012027418.tif 000094
を計算して、σ1,σ2を生成するステップと、
【数９３】
2012027418.tif 000095
を計算して、Kを生成するステップと、
【数９４】
2012027418.tif 000096
を計算して、eを生成するステップと、
【数９５】
2012027418.tif 000097
を計算して、vを生成するステップと、
前記メッセージ文mの暗号文C=(u1,u2,e,v)を生成するステップと、
前記生成された暗号文C、および前記生成された秘密鍵skを取得すると、前記暗号文Cが、前記秘密鍵skに対応する前記公開鍵pkにより決定される暗号文空間に含まれるか否かを判定するステップと、
前記暗号文Cが前記暗号文空間に含まれれば、
【数９６】
2012027418.tif 000098
を計算して、σ1,σ2を生成するステップと、
【数９７】
2012027418.tif 000099
を計算して、Kを生成するステップと、
【数９８】
2012027418.tif 000100
を計算して、mを生成するステップと、
【数９９】
2012027418.tif 000101
が成立するか否かを検査し、成立すれば、前記暗号文Cのメッセージ文として、前記計算されたmを出力するステップと、を実行する
ことを特徴とする公開鍵暗号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵生成、暗号化、復号化の３つのフェーズから構成される公開鍵暗号を実現する技術に関する。
【背景技術】
【０００２】
暗号理論において、公開鍵暗号の秘匿性（暗号文からメッセージ文に関する情報を漏らさないこと）を保証するための安全性概念として、例えば、semantic securityおよびindistinguishability（以下、識別不能性）が知られている（非特許文献１）。これらの概念は、通常、攻撃者に対してターゲットとなる暗号文が一つ与えられた状況（以下、シングルターゲット環境と呼ぶ）において定式化されている。すなわち、与えられた一つの暗号文から、それに対応する平文に関する情報を求めようとする攻撃者を想定して、安全性が議論されている。
【０００３】
しかし、実世界では、同一の公開鍵暗号システム（以下、単に、システムと呼ぶ場合がある）を用いられている状況においても、異なる鍵情報をもつ多くのユーザが存在し、攻撃者の多くは、それらのユーザに対応した多くの暗号文を手に入れることのできる環境にある（以下、マルチターゲット環境と呼ぶ）。例えば、各ユーザはRSA暗号を用いて暗号文を作成するようなシステムにおいて、各ユーザの鍵情報（公開鍵および秘密鍵）はそれぞれ異なり、攻撃者はネットワークなどを介して、何らかの関係をもつかも知れない様々なメッセージ文（例：電子メールとその返信の電子メール）を異なるユーザの公開鍵で暗号化した暗号文を手に入れることができるかもしれない。そして、それらの暗号文のうちのいずれか一つでも破ることができれば攻撃は成功とみなすことができる。
【０００４】
非特許文献２では、このような環境下における識別不能性の検証を行っている。非特許文献２によると、シングルターゲット環境において識別不能性が示されれば、マルチターゲット環境においても識別不能性は示されるが、一般的な結果としてリダクションの効率が非常に悪くなることが示されている。リダクションの効率が悪いことは、マルチターゲット環境における暗号の安全性設定のためのパラメータ（鍵の長さなど）をシングルターゲット環境の場合よりも大きく選ぶ必要性があることを意味し、実用上、暗号の処理効率を大きく損なう場合が多い。非特許文献２では、ElGamal暗号においては、このような鍵長の問題を回避することができることが示されている。しかし、ElGamal暗号は弱い安全性（IND-CPA安全）しか満たさないことが知られており、強い安全性（IND-CCA安全性）を持つ公開鍵暗号方法で、上述の鍵長の問題を回避できるような暗号方式は知られていない。
なお、公開鍵暗号方法に関する従来技術としては、他にも例えば、非特許文献３〜５が知られている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,［online］、［平成２２年７月１２日検索］、インターネット〈ＵＲＬ：http://www.cse.ucsd.edu/ ~mihir/papers/ro.html〉
【非特許文献２】M. Bellare, A. Boldyreva and S. Micali. Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements, ［online］、［平成２２年７月１２日検索］、インターネット〈ＵＲＬ： http://cseweb.ucsd.edu/~mihir/papers/musu.html〉
【非特許文献３】E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes, In Advances in Cryptology--Crypto’99, LNCS1462, pages 13-25, Springer-Verlag,1999
【非特許文献４】R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, ［online］、［平成２２年７月１２日検索］、インターネット〈ＵＲＬ：http://www.shoup.net/papers/〉
【非特許文献５】R. Cramer and V. Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, ［online］、［平成２２年７月１２日検索］、インターネット〈ＵＲＬ： http://www.shoup.net/papers/〉
【発明の概要】
【発明が解決しようとする課題】
【０００６】
このような事情を鑑みて、本発明は、公開鍵暗号において、シングルターゲット環境で決定された安全性レベルを、鍵長を変えることなくマルチターゲット環境において実現することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するための、具体的な公開鍵暗号方法について述べる。
［鍵生成］セキュリティパラメータkを入力として、次のステップを行う。
（１）公開鍵pk=(G,q,g,h,H)および秘密鍵sk=sを作成する。但し、Gは素数qを位数とする乗法群であり、gはランダムに選ばれたGの元、sはランダムに選ばれた剰余群Zq（０以上q-1以下の整数の集合）の元で、hは、
【数１】
2012027418.tif 000003
であり、Hは{0,1}*×GからZqへのハッシュ関数である。なお、{0,1}*は、０または１が任意の長さ分並んだビット列を示している。
（２）PK=(pk,H1,H2)およびSK=(sk,PK)を求め、それぞれを新たな公開鍵および秘密鍵として出力する。但し、H1は{0,1}*×G3から{0,1}nへのハッシュ関数、H2は{0,1}*×G3×{0,1}2nから{0,1}kへのハッシュ関数である。なお、{0,1}nは、０または１がn個並んだビット列を示している。
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを入力として、次のステップを行う。
（１）σ∈Gをランダムに選び、u=(u1,u2)を 、
【数２】
2012027418.tif 000004
により作成する。
（２）vおよびwを、
【数３】
2012027418.tif 000005
により作成する。
（３）メッセージ文mの暗号文として、C=(u,v,w)を出力する。
［復号化］暗号文C=(u,v,w) および秘密鍵SKを入力として、次のステップを行う。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKにより決定される暗号文空間に含まれていることを確認する。もし暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを出力する。
（２）σ∈Gを、
【数４】
2012027418.tif 000006
により計算する。
（３）m∈{0,1}nを、
【数５】
2012027418.tif 000007
により計算する。
（４）検査式
【数６】
2012027418.tif 000008
が成立すれば、暗号文Cのメッセージ文としてmを出力する。検査式が成立しなければ、暗号文Cを不受理とするメッセージを出力する。
詳細は、後記する。
【発明の効果】
【０００８】
本発明によれば、公開鍵暗号において、シングルターゲット環境で決定された安全性レベルを、鍵長を変えることなくマルチターゲット環境において実現することができる。
【図面の簡単な説明】
【０００９】
【図１】本実施形態の公開鍵暗号方法を実行する計算機のソフトウェア構成を示す図である。
【図２】鍵生成装置の機能構成図である。
【図３】暗号化装置の機能構成図である。
【図４】復号化装置の機能構成図である。
【図５】実施例１における暗号化および復号化の概要を示す図である。
【図６】実施例２における暗号化および復号化の概要を示す図である。
【図７】実施例３における暗号化および復号化の概要を示す図である。
【図８】実施例４における暗号化および復号化の概要を示す図である。
【図９】実施例５における暗号化および復号化の概要を示す図である。
【図１０】実施例６における暗号化および復号化の概要を示す図である。
【図１１】実施例７における暗号化および復号化の概要を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明を実施するための形態（以下、「実施形態」という。）について、適宜図面を参照しながら説明する。
【００１１】
図１は、本実施形態の公開鍵暗号方法を実行する計算機のソフトウェア構成を示す図である。本実施形態の計算機（公開鍵暗号装置）は、鍵生成装置１００、暗号化装置２００、および復号化装置３００といったソフトウェア構成を備える。そして、このような計算機は、図示しない入力部、表示部、記憶部、制御部といったハードウェア構成を備えたコンピュータである。
【００１２】
入力部は、ユーザからの入力を受け付ける入力用インタフェースである。入力部は、例えば、マウスやキーボードである。
表示部は、制御部による情報処理の結果を表示する表示用インタフェースである。表示部は、例えば、ディスプレイやプリンタである。
【００１３】
記憶部は、入力部から入力されたデータ、制御部による情報処理の途中結果や最終結果を示すデータ、計算機が備えるソフトウェア構成を実現するプログラムを記憶する。記憶部は、例えば、HDD（Hard Disk Drive）、ROM（Read Only Memory（記憶媒体にもなる））、RAM（Random Access Memory）である。
【００１４】
制御部は、主に、公開鍵暗号に関する所定の情報処理を実現する。制御部は、例えば、CPU（Central Processing Unit）である。制御部は、入力部から入力されたデータなどを用いて、記憶部に記憶されているプログラムを実行する。これにより、鍵生成装置１００、暗号化装置２００、および復号化装置３００といったソフトウェア構成による機能が実現される。そして、鍵生成装置１００、暗号化装置２００、および復号化装置３００のそれぞれが備える詳細なソフトウェア構成（詳細は後記）による機能も実現される。
【００１５】
鍵生成装置１００は、入力１ｋ（kはセキュリティパラメータ）に対して、公開鍵PKと秘密鍵SKを出力する。入力部からセキュリティパラメータkが入力されれば、鍵生成装置１００には１ｋという値で入力される。以下、説明の便宜上、セキュリティパラメータkが入力されるという表現をする場合があるが、このときは、一般的に、鍵生成装置１００に１ｋという値で入力されることを意味する。公開鍵暗号システムを利用する各ユーザは、鍵生成装置１００によって作成された異なる鍵情報をもつ。
【００１６】
暗号化装置２００は、メッセージ文mと公開鍵PKを入力として、暗号文Cを出力する。
復号化装置３００は、秘密鍵SKと暗号文Cを入力として、m’を出力する。このとき、暗号文Cがメッセージ文mの正しい暗号文であれば、m’=mとなる。
【００１７】
図２は、鍵生成装置の機能構成図である。鍵生成装置１００は、入力装置１０１、鍵生成器１０２、メモリ１０３、出力装置１０４、乱数生成器１０５、演算装置１０６を備える。
【００１８】
入力装置１０１は、例えば、セキュリティパラメータの入力を受け付ける。
鍵生成器１０２は、公開鍵暗号の鍵情報、つまり、公開鍵および秘密鍵を生成する。生成される鍵情報は、既存の技術により生成された鍵情報であったり、その鍵情報を用いて本発明によって生成された新たな鍵情報であったりする。
メモリ１０３は、例えば、生成された鍵情報を記憶する。
出力装置１０４は、例えば、生成された鍵情報を暗号化装置２００に出力する。前記出力には、出力結果を計算機の表示部に表示したり、他の計算機に送信したりすることを含む。
乱数生成器１０５は、例えば、所定の集合（例：乗法群や剰余群）の元を任意に選ぶために用いる乱数を生成する。
演算装置１０６は、例えば、鍵生成方法のアルゴリズムに従い、鍵情報を生成するのに必要な演算を行う。
【００１９】
図３は、暗号化装置の機能構成図である。暗号化装置２００は、入力装置２０１、乱数生成器２０２、暗号文生成器２０３、メモリ２０４、演算装置２０５、関数計算器２０６、出力装置２０７、ID生成装置２０８を備える。
【００２０】
入力装置２０１は、例えば、メッセージ文や、鍵生成装置１００から出力される公開鍵の入力を受け付ける。
乱数生成器２０２は、例えば、所定の集合（例：乗法群や剰余群）の元を任意に選ぶために用いる乱数を生成する。
暗号文生成器２０３は、例えば、公開鍵を用いた暗号文を生成する。生成される暗号文は、既存の技術により生成された暗号文であったり、その暗号文を用いて本発明によって生成された新たな暗号文であったりする。
メモリ２０４は、例えば、生成された暗号文を記憶する。
演算装置２０５は、例えば、暗号化方法のアルゴリズムに従い、暗号文を生成するのに必要な演算を行う。
関数計算器２０６は、例えば、ハッシュ関数などの関数を利用した計算を行う。
出力装置２０７は、例えば、生成された暗号文を復号化装置３００に出力する。前記出力には、出力結果を計算機の表示部に表示したり、他の計算機に送信したりすることを含む。
ID生成装置２０８は、例えば、暗号文に対して固有のIDを生成する。
【００２１】
図４は、復号化装置の機能構成図である。復号化装置３００は、入力装置３０１、検査装置Ａ３０２、復号器３０３、メモリ３０４、関数計算器３０５、演算装置３０６、検査装置Ｂ３０７、出力装置３０８を備える。
【００２２】
入力装置３０１は、例えば、鍵生成装置１００から出力される秘密鍵や、暗号化装置２００から出力される暗号文の入力を受け付ける。
検査装置Ａ３０２は、例えば、所定の検査基準に従い、入力された暗号文が正しい暗号文であるか否かを検査（判定）する。
復号器３０３は、例えば、秘密鍵を用いて暗号文を復号する。
メモリ３０４は、例えば、暗号文を復号したときのデータを記憶する。
関数計算器３０５は、例えば、ハッシュ関数などの関数を利用した計算を行う。
演算装置３０６は、例えば、復号化方法のアルゴリズムに従い、暗号文を復号するのに必要な演算を行う。
検査装置Ｂ３０７は、例えば、所定の検査基準に従い、入力された暗号文が正しい暗号文であるか否かを検査する。
出力装置３０８は、例えば、検査装置Ｂ３０７の検査に応じた検査結果を出力する。前記出力には、出力結果を計算機の表示部に表示したり、他の計算機に送信したりすることを含む。
【００２３】
次に、本実施形態の計算機による処理を、実施例１〜７として説明する。なお、この計算機による処理の主体は、計算機の制御部であるが、説明の便宜上、前記したソフトウェア構成の構成要素を、前記処理の主体とする場合がある。ただし、このような場合であっても、基本的には、制御部が実行することで、相応の処理が実現されることを意味する。
【実施例１】
【００２４】
本実施例では、非特許文献１に記載の公開鍵暗号をベースにして、上記課題を解決するための改良を行った方法について述べる。非特許文献１では、公開鍵である落とし戸付き一方向性関数πおよびメッセージ文mに対して、暗号文C=(u,v,w)を、
【数７】
2012027418.tif 000009
によって作成する公開鍵暗号方法が記載されている。但し、σは、ある集合からランダムに選ばれた元であり、HおよびH2は、ハッシュ関数である。
【００２５】
図５は、実施例１における暗号化および復号化の概要を示す図である。セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)および暗号文空間CSPΠ(k)が一意的に定まる公開鍵暗号Π=(K,E,D)が与えられているとき、この公開鍵暗号を用いて新しい公開鍵暗号を作成（生成）する。但し、Kは鍵生成方法の確率的アルゴリズムであり、Eは暗号化方法のアルゴリズムであり、Dは復号化方法の決定性アルゴリズムである。そして、本実施例では、公開鍵暗号Πにおける暗号化方法Eは決定性アルゴリズムにより行われるものとする。すなわち、同じ入力値に対してEは必ず同じ値を出力する。
【００２６】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて公開鍵暗号Πの公開鍵pkおよび秘密鍵skを作成し、メモリ１０３に(pk,sk)として格納する。
（２）メモリ１０３に格納された(pk,sk)から、PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数であり、H2は{0,1}*×MSPΠ(k)×CSPΠ(k)×{0,1}2nから{0,1}kへのハッシュ関数である。なお、{0,1}*は、０または１が任意の長さ分並んだビット列を示している。また、{0,1}nは、０または１がn個並んだビット列を示している。
【００２７】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内の乱数生成器２０２を用いて、σ∈MSPΠ(k)をランダムに選び、暗号文生成器２０３を用いて、公開鍵暗号Πの公開鍵pkによるσの暗号文である
【数８】
2012027418.tif 000010
を作成し、メモリ２０４に格納する（ステップＳ５０１）。
（２）暗号化装置２００内の演算装置２０５および関数計算器２０６およびメモリ２０４内のuを用いて、
【数９】
2012027418.tif 000011
を計算する（ステップＳ５０２、ステップＳ５０３）。
（３）メッセージ文mの暗号文として、C=(u,v,w)を、出力装置２０７を用いて出力する。
【００２８】
［復号化］暗号文C=(u,v,w) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数１０】
2012027418.tif 000012
を計算し、メモリ３０４に格納する（ステップＳ５０４）。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数１１】
2012027418.tif 000013
を計算する（ステップＳ５０５）。
（４）検査装置Ｂ３０７を用いて、
【数１２】
2012027418.tif 000014
が成立することを検査し（ステップＳ５０６）、検査にパスすれば暗号文Cのメッセージ文としてmを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Cを不受理とするメッセージを出力する。
【００２９】
上記の公開鍵暗号において、公開鍵暗号Πが弱い安全性（選択平文攻撃に対する一方向性）を満たせば、上記公開鍵暗号は、H1およびH2がランダムオラクルであるとき、背景技術で述べたマルチターゲット環境上において強い安全性（IND-CCA安全）を満たすことを示すことができる。この安全性証明は、ユーザ数やターゲットとなる暗号文の個数に依存することのない評価式により与えられるため、公開鍵暗号Πが、背景技術で述べた鍵長の問題を回避することができれば、上記公開鍵暗号も同様の鍵長の問題を回避可能であることを示すことができる。換言すれば、本実施例は、鍵長の問題を回避することができるが弱い安全性しか持たない公開鍵暗号を利用して、鍵長の問題を回避することができる強い安全性を持つ公開鍵暗号の構成方法を提供している。
【実施例２】
【００３０】
本実施例では、実施例１において述べた公開鍵暗号の具体的実現方法について述べる。
図６は、実施例２における暗号化および復号化の概要を示す図である。
【００３１】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて、公開鍵暗号Πの公開鍵pk=(G,q,g,h,H)および秘密鍵sk=sを作成し、メモリ１０３に(pk,sk)として格納する。但し、Gは素数qを位数とする乗法群であり、gはランダムに選ばれたGの元、sはランダムに選ばれた剰余群Zq（０以上q-1以下の整数の集合）の元で、hは、
【数１３】
2012027418.tif 000015
であり、Hは{0,1}*×GからZqへのハッシュ関数である。鍵生成器１０２は、上記pk,skを、鍵生成装置１００内のメモリ１０３、乱数生成器１０５、演算装置１０６を用いて作成することができる。
（２）メモリ１０３に格納された(pk,sk)から、PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×G3から{0,1}nへのハッシュ関数で、H2は{0,1}*×G3×{0,1}2nから{0,1}kへのハッシュ関数である。
【００３２】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内の乱数生成器２０２を用いて、σ∈Gをランダムに選び、暗号文生成器２０３を用いて、公開鍵暗号Πの公開鍵pkによるσの暗号文u=(u1,u2)を、
【数１４】
2012027418.tif 000016
により作成し、メモリ２０４に格納する（ステップＳ６０１、ステップＳ６０２）。暗号文生成器２０３は、上記uを、暗号化装置２００内の乱数生成器２０２、メモリ２０４、演算装置２０５を用いて作成することができる。
（２） 演算装置２０５および関数計算器２０６およびメモリ２０４内のuを用いて、
【数１５】
2012027418.tif 000017
を計算する（ステップＳ６０３、ステップＳ６０４）。
（３）メッセージ文mの暗号文として、C=(u,v,w)を、出力装置２０７を用いて出力する。
【００３３】
［復号化］暗号文C=(u,v,w) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数１６】
2012027418.tif 000018
を計算し、メモリ３０４に格納する（ステップＳ６０５）。復号器３０３は、上記σを、復号化装置３００内のメモリ３０４、演算装置３０６を用いて作成することができる。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数１７】
2012027418.tif 000019
を計算する（ステップＳ６０６）。
（４）検査装置Ｂ３０７を用いて、
【数１８】
2012027418.tif 000020
が成立することを検査し（ステップＳ６０７）、検査にパスすれば暗号文Cのメッセージ文としてｍを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Cを不受理とするメッセージを出力する。
【００３４】
本実施例による公開鍵暗号方法は、H,H1,H2がランダムオラクルとして与えられるとき、decisional Diffie-Hellman（DDH）問題の計算量的困難性を暗号学的仮定としてマルチターゲット環境においてIND-CCA安全であることが証明される。DDH問題の詳細については、非特許文献４に記載されている。さらに、この安全性証明は、シングルターゲット環境と同様の評価式（すなわち、ユーザ数やターゲットとなる暗号文の個数に依存しない）から得られる特徴をもつため、本実施例による公開鍵暗号方法は、背景技術で述べたマルチターゲット環境における鍵長の問題を回避することができる。
【実施例３】
【００３５】
本実施例では、非特許文献３に記載の公開鍵暗号をベースにして、上記発明の課題を解決するための改良を行った方法について述べる。非特許文献３では、公開鍵暗号Π=(K,E,D)（但し、暗号化を行うEは確率的アルゴリズム）を利用して、安全性を強化した公開鍵暗号を作成することを目的として、メッセージ文mに対して、暗号文C=(u,v)を、
【数１９】
2012027418.tif 000021
によって作成する公開鍵暗号方法が記載されている。但し、σは、ある集合の元であり、H1,H2は、ハッシュ関数である。
【００３６】
図７は、実施例３における暗号化および復号化の概要を示す図である。セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)および暗号文空間CSPΠ(k)および乱数空間COINΠ(k)（コイントス空間ともいう）が一意的に定まるKEMスキームΠ=(K,E,D)が与えられているとき、このKEMスキームを用いて新しい公開鍵暗号を作成する方法について述べる。ここで、KEMスキームとは、鍵配送用に限定された公開鍵暗号と考えてよい。すなわち、公開鍵暗号のメッセージ文が鍵情報に当たり、常に乱数として選ばれる。詳細は、非特許文献５に記載されている。よって、KEMスキームΠを、「公開鍵暗号Π」と記載し、説明を続ける場合がある。但し、本実施例では、KEMスキームΠにおける暗号化方法Eは確率的アルゴリズムにより行われるものとする。すなわち、Eに対して、同じ値を入力したとしても、乱数空間COINΠ(k)からどのような値が選ばれるかによって、出力値は必ずしも同じ値とは限らない。
【００３７】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は、公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて公開鍵暗号Πの公開鍵pkおよび秘密鍵skを作成し、メモリ１０３に(pk,sk)として格納する。
（２）メモリ１０３に格納された(pk,sk)から、PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数であり、H2は{0,1}*×MSPΠ(k)×{0,1}n×CSPΠ(k)×{0,1}nからCOINΠ(k)へのハッシュ関数である。
【００３８】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内の乱数生成器２０２を用いて、σ∈MSPΠ(k)およびR∈COINΠ(k)をランダムに選び、暗号文生成器２０３を用いて、公開鍵暗号Πの公開鍵pkによるσの暗号文である
【数２０】
2012027418.tif 000022
を作成し、メモリ２０４に格納する（ステップＳ７０１）。
（２）暗号化装置２００内の演算装置２０５および関数計算器２０６およびメモリ２０４内のuを用いて、
【数２１】
2012027418.tif 000023
を計算する（ステップＳ７０２、ステップＳ７０３）。
（３）メッセージ文ｍの暗号文として、C=(u,v,w)を、出力装置２０７を用いて出力する。
【００３９】
［復号化］暗号文C=(u,v,w) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数２２】
2012027418.tif 000024
を計算し、メモリ３０４に格納する（ステップＳ７０４）。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数２３】
2012027418.tif 000025
および
【数２４】
2012027418.tif 000026
を計算する（ステップＳ７０５、ステップＳ７０６）。
（４）復号化装置３００内の検査装置Ｂ３０７を用いて、
【数２５】
2012027418.tif 000027
が成立することを検査し（ステップＳ７０７）、検査にパスすれば暗号文Cのメッセージ文としてmを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Ｃを不受理とするメッセージを出力する。
【００４０】
上記の公開鍵暗号において、H1およびH2がランダムオラクルであり、KEMスキームΠが弱い安全性（選択平文攻撃に対する識別不能性）を満たせば、上記公開鍵暗号は、背景技術で述べたマルチターゲット環境において強い安全性（IND-CCA安全）を満たすことが示される。この安全性証明は、ユーザ数やターゲットとなる暗号文の個数に依存することのない評価式により与えられるため、KEMスキームΠが、背景技術で述べた鍵長の問題を回避することができれば、上記公開鍵暗号も同様の鍵長の問題を回避可能であることを示すことができる。換言すれば、本実施例は、鍵長の問題を回避することができるが弱い安全性しか持たないKEMスキームを利用して、鍵長の問題を回避することができる強い安全性を持つ公開鍵暗号の構成方法を提供している。実施例１との違いは、実施例１では公開鍵暗号Πの暗号化は決定的アルゴリズムにより行われるのに対して、本実施例ではKEMスキームΠの暗号化は確率的アルゴリズムにより行われる点である。
【実施例４】
【００４１】
本実施例では、実施例３で述べた公開鍵暗号の具体的実現方法について述べる。
図８は、実施例４における暗号化および復号化の概要を示す図である。
【００４２】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は、公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて、公開鍵pk=(G,q,g,h,H)および秘密鍵sk=sを作成し、メモリ１０３に(pk,sk)として格納する。但し、Gは素数qを位数とする乗法群であり、gはランダムに選ばれたGの元、ｓはランダムに選ばれた剰余群Zqの元で、hは、
【数２６】
2012027418.tif 000028
であり、Hは{0,1}*×ZqからZqへのハッシュ関数である。鍵生成器１０２は、上記pk,skを、鍵生成装置１００内のメモリ１０３、乱数生成器１０５、演算装置１０６を用いて作成することができる。
（２）メモリ１０３に格納された(pk,sk)から、PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×G3から{0,1}nへのハッシュ関数，H2は{0,1}*×G×{0,1}n×G2×{0,1}nからZqへのハッシュ関数である。
【００４３】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内の乱数生成器２０２を用いて、σ∈GおよびR∈Zqをランダムに選び、暗号文生成器２０３を用いて、u=(u1,u2)を
【数２７】
2012027418.tif 000029
により作成し、メモリ２０４に格納する（ステップＳ８０１、ステップＳ８０２）。暗号文生成器２０３は、上記uを、暗号化装置２００内の乱数生成器２０２、メモリ２０４、演算装置２０５を用いて作成することができる。
（２）暗号化装置２００内の演算装置２０５および関数計算器２０６およびメモリ２０４内のuを用いて、
【数２８】
2012027418.tif 000030
を計算する（ステップＳ８０３、ステップＳ８０４）。
（３）メッセージ文mの暗号文として、C=(u,v,w)を、出力装置２０７を用いて出力する。
【００４４】
［復号化］暗号文C=(u,v,w) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数２９】
2012027418.tif 000031
を計算し、メモリ３０４に格納する（ステップＳ８０５）。復号器３０３は、上記σを、復号化装置３００内のメモリ３０４、演算装置３０６を用いて作成することができる。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数３０】
2012027418.tif 000032
および
【数３１】
2012027418.tif 000033
を計算する（ステップＳ８０６、ステップＳ８０７）。
（４）検査装置Ｂ３０７を用いて、
【数３２】
2012027418.tif 000034
が成立することを検査し（ステップＳ８０８）、検査にパスすれば暗号文Cのメッセージ文としてｍを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Ｃを不受理とするメッセージを出力する。
【００４５】
本実施例による公開鍵暗号方法は、H1,H2がランダムオラクルにより与えられるとき、DDH問題の計算量的困難性を暗号学的仮定として、マルチターゲット環境においてIND-CCA安全であることが証明される。さらに、この安全性証明は、シングルターゲット環境と同様の評価式（すなわち、ユーザ数やターゲットとなる暗号文の個数に依存しない）から得られる特徴をもつため、本実施例による公開鍵暗号方法は、KEMスキームΠを用いたとしても、背景技術で述べたようなマルチターゲット環境における鍵長の問題を回避することができる。
【実施例５】
【００４６】
本実施例では、実施例３で述べた公開鍵暗号方法の変形例について述べる。
図９は、実施例５における暗号化および復号化の概要を示す図である。セキュリティパラメータkに対して、メッセージ空間MSPΠ(k)および暗号文空間CSPΠ(k)および乱数空間COINΠ(k)が一意的に定まるKEMスキームΠ=(K,E,D)が与えられているとき、このKEMスキームΠを用いて新しい公開鍵暗号を作成する方法について述べる。本実施例では、KEMスキームΠにおける暗号化方法Eは確率的アルゴリズムにより行われるものとする。すなわち、Eに対して、同じ値を入力したとしても、乱数空間COINΠ(k)からどのような値が選ばれるかによって、出力値は必ずしも同じ値とは限らない。
【００４７】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて公開鍵暗号Πの公開鍵pkおよび秘密鍵skを作成し、メモリ１０３に(pk,sk)として格納する。
（２）メモリ１０３に格納された(pk,sk)から，PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×{0,1}*×MSPΠ(k)×{0,1}nからCOINΠ(k)へのハッシュ関数であり、H2は{0,1}*×{0,1}*×MSPΠ(k)×CSPΠ(k)から{0,1}nへのハッシュ関数である。
【００４８】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内のID生成装置２０８を用いて暗号文に固有の情報であるIDを作成し、メモリ２０４に格納する。
（２）暗号化装置２００内の乱数生成器２０２を用いて、σ∈MSPΠ(k)をランダムに選び、暗号文生成器２０３を用いて、公開鍵暗号Πの公開鍵pkによるσの暗号文である
【数３３】
2012027418.tif 000035
を作成し、メモリ２０４に格納する（ステップＳ９０１）。
（３）暗号化装置２００内の演算装置２０５および関数計算器２０６およびメモリ２０４内のuを用いて、
【数３４】
2012027418.tif 000036
を計算する（ステップＳ９０２）。
（４）メッセージ文ｍの暗号文として、C=(ID,u,v)を、出力装置２０７を用いて出力する。
【００４９】
［復号化］暗号文C=(ID,u,v) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数３５】
2012027418.tif 000037
を計算し、メモリ３０４に格納する（ステップＳ９０３）。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数３６】
2012027418.tif 000038
を計算する（ステップＳ９０４）。
（４）検査装置Ｂ３０７を用いて、
【数３７】
2012027418.tif 000039
が成立することを検査し（ステップＳ９０５）、検査にパスすれば暗号文Cのメッセージ文としてｍを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Cを不受理とするメッセージを出力する。
【００５０】
上記の公開鍵暗号において、H1およびH2がランダムオラクルであって、ID情報が暗号文に対して固有のものであり、かつ、KEMスキームΠが弱い安全性（選択平文攻撃に対する識別不能性）を満たせば、上記公開鍵暗号は、背景技術で述べたようなマルチターゲット環境において、強い安全性（IND-CCA安全）を満たすことを示すことができる。この安全性証明は、ユーザ数やターゲットとなる暗号文の個数に依存することのない評価式により与えられるため、KEMスキームΠが、鍵長の問題を回避することができれば、上記公開鍵暗号も鍵長の問題を回避することができる。換言すれば、本実施例は、鍵長の問題を回避することができるが弱い安全性しか持たないKEMスキームを利用して、鍵長の問題を回避することができる強い安全性を持つ公開鍵暗号の構成方法を提供している。これは、実施例３で述べた公開鍵暗号方法の別手段を与えるものである。
【実施例６】
【００５１】
本実施例では、実施例５で述べた公開鍵暗号方法の具定的実現方法について述べる。図１０は、実施例６における暗号化および復号化の概要を示す図である。
【００５２】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００は公開鍵および秘密鍵を次の動作に従い作成する。
（１）鍵生成装置１００内の鍵生成器１０２を用いて公開鍵暗号Πの公開鍵pk=(G,q,g,h)および秘密鍵sk=sを作成し、メモリ１０３に格納する。但し、Gは素数qを位数とする乗法群であり、gはランダムに選ばれたGの元、ｓはランダムに選ばれたZqの元で、hは、
【数３８】
2012027418.tif 000040
である。鍵生成器１０２は、上記pk,skを、鍵生成装置１００内のメモリ１０３、乱数生成器１０５、演算装置１０６を用いて作成することができる。
（２）メモリ１０３に格納された(pk,sk)から、PK=(pk,H1,H2)およびSK=(sk,PK)を新たな公開鍵および秘密鍵として、出力装置１０４を用いて出力する。但し、H1は{0,1}*×{0,1}*×G×{0,1}nから剰余群Zqへのハッシュ関数であり、H2は{0,1}*×{0,1}*×G3から{0,1}nへのハッシュ関数である。
【００５３】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵PKを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内のID生成装置２０８を用いて暗号文に固有の情報であるIDを作成し、メモリ２０４に格納する。
（２）暗号化装置２００内の乱数生成器２０２を用いて、σ∈MSPΠ(k)をランダムに選び、暗号文生成器２０３を用いて、公開鍵暗号Πの公開鍵pkによるσの暗号文u=(u1,u2)を
【数３９】
2012027418.tif 000041
により作成し、メモリ２０４に格納する（ステップＳ１００１、ステップＳ１００２）。暗号文生成器２０３は、上記uを、暗号化装置２００内の乱数生成器２０２、メモリ２０４、演算装置２０５を用いて作成することができる。
（３）暗号化装置２００内の 演算装置２０５および関数計算器２０６およびメモリ２０４内のID，uを用いて、
【数４０】
2012027418.tif 000042
を計算する（ステップＳ１００３）。
（４）メッセージ文mの暗号文として、C=(ID,u,v)を、出力装置２０７を用いて出力する。
【００５４】
［復号化］暗号文C=(ID,u,v) および秘密鍵SKを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵SKに対応する公開鍵PKによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の復号器３０３を用いて、
【数４１】
2012027418.tif 000043
を計算し、メモリ３０４に格納する（ステップＳ１００４）。復号器３０３は、上記σを、復号化装置３００内のメモリ３０４、演算装置３０６を用いて作成することができる。
（３）復号化装置３００内の関数計算器３０５および演算装置３０６およびメモリ３０４に格納されたσを用いて、
【数４２】
2012027418.tif 000044
を計算する（ステップＳ１００５）。
（４）検査装置Ｂ３０７を用いて、
【数４３】
2012027418.tif 000045
が成立することを検査し（ステップＳ１００６）、検査にパスすれば暗号文Cのメッセージ文としてmを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Cを不受理とするメッセージを出力する。
【００５５】
本実施例による公開鍵暗号方法は、H1,H2がランダムオラクルとして与えられるとき、DDH問題の計算量的困難性を暗号学的仮定として、マルチターゲット環境においてIND-CCA安全であることが証明される。さらに、この安全性証明は、シングルターゲット環境と同様の評価式（すなわち、ユーザ数やターゲットとなる暗号文の個数に依存しない）から得られる特徴をもつため、本実施例による公開鍵暗号方法は、ID情報を用いても、背景技術で述べたようなマルチターゲット環境における鍵長の問題を回避することができる。
【実施例７】
【００５６】
本実施例では、非特許文献４に記載の公開鍵暗号をベースにして、上記発明の課題を解決するための改良を行った方法について述べる。非特許文献４では、公開鍵pk=(g1,g2,c,d,H)およびメッセージ文mに対して、乱数r∈Zqを選び、暗号文C=(u1,u2,e,v)を
【数４４】
2012027418.tif 000046
により作成する公開鍵暗号が記載されている。但し、c,dは、ある集合の元であり、Hは、ハッシュ関数である。
図１１は、本実施例７における暗号化および復号化の概要を示す図である。
【００５７】
［鍵生成］セキュリティパラメータkを鍵生成装置１００の入力装置１０１に入力する。鍵生成装置１００内の乱数生成器１０５および演算装置１０６を用いて公開鍵暗号Πのpk=(G,q,g1,g2,h1,h2,F1,k,F2,k)およびsk=(x1,x2,y1,y2)を作成し，メモリ１０３に格納する。但し、Gは素数qを位数とする乗法群であり、g1,g2はランダムに選ばれたGの元、x1,x2,y1,y2はランダムに選ばれた剰余群Zqの元で、h1,h2は、
【数４５】
2012027418.tif 000047
である。 各i∈{1,2}に対して、Fi={Fi,k}k∈Nは関数族で、Fi,k={fσi}σ∈Gであり、Gはkに応じて決定される集合I(k)の元であり、fσiは{0,1}kへの関数である。
【００５８】
［暗号化］メッセージ文m∈{0,1}nおよび公開鍵pkを暗号化装置２００内の入力装置２０１に入力する。暗号化装置２００はメッセージ文mの暗号文を次の動作に従い作成する。
（１）暗号化装置２００内の乱数生成器２０２を用いて、r∈Zqをランダムに選び、演算装置２０５を用いて
【数４６】
2012027418.tif 000048
を計算する（ステップＳ１１０１）。
（２）暗号化装置２００内の演算装置２０５を用いて、
【数４７】
2012027418.tif 000049
を計算する（ステップＳ１１０２）。
（３）暗号化装置２００内の関数計算器２０６を用いて、
【数４８】
2012027418.tif 000050
を計算する。
（４）暗号化装置２００内の演算装置２０５を用いて、
【数４９】
2012027418.tif 000051
を計算する（ステップＳ１１０３）。
（５）暗号化装置２００内の関数計算器２０６を用いて、
【数５０】
2012027418.tif 000052
を計算する（ステップＳ１１０４）。 
（６）メッセージ文mの暗号文として、C=(u1,u2,e,v)を、出力装置２０７を用いて出力する。
【００５９】
［復号化］暗号文C=(u1,u2,e,v)および秘密鍵skを復号化装置３００内の入力装置３０１に入力する。復号化装置３００は暗号文Cのメッセージ文を次の動作に従い作成する。
（１）暗号文Cが秘密鍵skに対応する公開鍵pkによって決定される暗号文空間に含まれていることを復号化装置３００内の検査装置Ａ３０２を用いて確認する。暗号文空間に含まれない場合は、暗号文Cを不受理とするメッセージを、出力装置３０８を用いて出力する。
（２）復号化装置３００内の演算装置３０６を用いて、
【数５１】
2012027418.tif 000053
を計算し、メモリ３０４に格納する（ステップＳ１１０５）。
（３）復号化装置３００内の関数計算器３０５およびメモリ３０４に格納されたσ2を用いて、
【数５２】
2012027418.tif 000054
を計算する。
（４）復号化装置３００内の演算装置３０６を用いて、
【数５３】
2012027418.tif 000055
を計算する（ステップＳ１１０６）。
（５）検査装置Ｂ３０７を用いて、
【数５４】
2012027418.tif 000056
が成立することを検査し（ステップＳ１１０７）、検査にパスすれば暗号文Cのメッセージ文としてmを、出力装置３０８を用いて出力する。検査にパスしなければ、暗号文Cを不受理とするメッセージを出力する。
【００６０】
上記の公開鍵暗号において、関数族F1およびF2が擬似ランダム関数に似たある条件を満たすとき、DDH問題の困難性を暗号学的仮定として、マルチターゲット環境上においてIND-CCA安全であることが示される。この安全性証明は、ユーザ数やターゲットとなる暗号文の個数に依存することのない評価式により与えられるため、背景技術で述べたマルチターゲット環境における鍵長の問題を回避することが可能となる。
【００６１】
以上の説明から、種々のアルゴリズムを用いた本実施形態の公開鍵暗号方法によれば、マルチターゲット環境においてもシングルターゲット環境と同一の条件で安全に公開鍵暗号の利用が可能となるため、マルチターゲット環境において暗号化および復号化処理の効率性に優れた公開鍵暗号システムを構築することが可能となる。
【００６２】
前記実施形態は、本発明を実施するために好適のものであるが、その実施形式はこれらに限定されるものでなく、本発明の要旨を変更しない範囲内において種々変形することが可能である。
【００６３】
例えば、本実施形態の公開鍵暗号装置は、１台の計算機で構成してもよいし、互いにネットワークで通信可能に接続された複数台の計算機で構成してもよい。複数台の計算機で構成する場合、各計算機が鍵生成装置１００、暗号化装置２００、および復号化装置３００の少なくとも一つを備えることが好ましい。
【００６４】
また、本実施形態の計算機が備えるハードウェア構成の全部または一部をソフトウェア構成にしてもよいし、計算機が備えるソフトウェア構成の全部または一部をハードウェア構成にしてもよい。
【００６５】
また、本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
【００６６】
その他、ハードウェア、ソフトウェア、各フローチャート等の具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００６７】
１００      鍵生成装置
１０１      入力装置
１０２      鍵生成器
１０３      メモリ
１０４      出力装置
１０５      乱数生成器
１０６      演算装置
２００      暗号化装置
２０１      入力装置
２０２      乱数生成器
２０３      暗号文生成器
２０４      メモリ
２０５      演算装置
２０６      関数計算器
２０７      出力装置
２０８      ＩＤ生成装置
３００      復号化装置
３０１      入力装置
３０２      検査装置Ａ
３０３      復号器
３０４      メモリ
３０５      関数計算器
３０６      演算装置
３０７      検査装置Ｂ
３０８      出力装置
【図１】
2012027418.tif 000102
【図２】
2012027418.tif 000103
【図３】
2012027418.tif 000104
【図４】
2012027418.tif 000105
【図５】
2012027418.tif 000106
【図６】
2012027418.tif 000107
【図７】
2012027418.tif 000108
【図８】
2012027418.tif 000109
【図９】
2012027418.tif 000110
【図１０】
2012027418.tif 000111
【図１１】
2012027418.tif 000112