ｓｉｇｎｃｒｙｐｔｉｏｎ方法と装置及び対応するｓｉｇｎｃｒｙｐｔｉｏｎ検証方法と装置
【課題】署名と暗号の両方の機能を提供する暗号メカニズムを提供する。
【解決手段】signcryptionが、送信器により生成される。公開鍵Epkで平文mを暗号化（Ｓ１）して暗号文e、すなわちe=E.Encrypt(m)を求める第１の暗号化アルゴリズムを用い、カプセル化アルゴリズムと公開鍵Kpk、k,c=KD.Encapsulate()とを用いて、鍵kとそのカプセル化cとを生成し（Ｓ２）、Ssk,s=S.sign(e,c)を用いて(e,c)に署名し（Ｓ３）、第２の暗号化アルゴリズムと鍵kとを用いて署名sを暗号化（Ｓ４)する、e_d＝D.Encrypt(s)。mのsigncryptionは(e,c,e_d)により構成される（Ｓ５）。送信者はeの復号に関する知識を証明でき、e_dが、カプセル化の鍵を用いたcとeの連結の正しい署名を暗号化してものであることを証明できる（Ｓ１１）。
【解決手段】signcryptionが、送信器により生成される。公開鍵Epkで平文mを暗号化（Ｓ１）して暗号文e、すなわちe=E.Encrypt(m)を求める第１の暗号化アルゴリズムを用い、カプセル化アルゴリズムと公開鍵Kpk、k,c=KD.Encapsulate()とを用いて、鍵kとそのカプセル化cとを生成し（Ｓ２）、Ssk,s=S.sign(e,c)を用いて(e,c)に署名し（Ｓ３）、第２の暗号化アルゴリズムと鍵kとを用いて署名sを暗号化（Ｓ４)する、e_d＝D.Encrypt(s)。mのsigncryptionは(e,c,e_d)により構成される（Ｓ５）。送信者はeの復号に関する知識を証明でき、e_dが、カプセル化の鍵を用いたcとeの連結の正しい署名を暗号化してものであることを証明できる（Ｓ１１）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概して暗号に関し、特にsigncryptionに関する。
【背景技術】
【０００２】
このセクションは、以下に説明して特許請求する本発明の様々な態様に関連する様々な態様の技術を読者に紹介することを意図するものである。この説明は、本発明の様々な態様の理解を容易にする背景情報を読者に提供する役に立つはずである。従って、言うまでもなく、これらの記載は上記を考慮して読むべきであり、先行技術として認める（admissions of prior art）ものではない。
【０００３】
多くの異なる暗号方式がある。Laila El Aimaniは、非特許文献１において、いくつかの暗号方式を説明しており、特に強固で否定できない署名、すなわちエンティティとの協力なくしては検証をできない署名を説明している。この論文では、筆者は基本的に基本的暗号からかかる署名をどう構成するか研究している。彼女は、従来のパラダイム（例えば、Encrypt_then_SignやCommit_then_Encrypt_and_Sign）では、リーズナブルなセキュリティレベルを満たすために、高価な暗号が必要であることを示している。次に、彼女は、少し調整するだけで、安価な暗号で構成できるようになり、得られる署名の効率（例えば、コスト、帯域幅、検証可能性）にもよいインパクトを与えることを示している。しかし、署名は、署名されるメッセージを暗号化するものではない。
【０００４】
多くの実生活のアプリケーションには伝送データの秘密性と信ぴょう性／インテグリティの両方が必要なので、署名と暗号の機能を両方とも提供する暗号メカニズムであるいわゆるsigncryptionは、ますます広がりを見せている。一例として、投票者のプライバシーを保証するため暗号化が必要であり、同時に投票センターが暗号化された投票が投票者のものであることを確認する必要がある電子選挙がある。
【０００５】
かかるメカニズムを基本的暗号プリミティブから構成するのは、専用の一体的構成と比較して、分析しやすい方式を実現できるので、暗号技術の分野では慣用されている。基本的暗号プリミティブからこれらのメカニズムを実現するのに用いられる、最も良く使われる先行技術のパラダイムは、「encrypt_then_sign」(ＥｔＳ)パラダイムと「sign_then_encrypt」(ＳｔＥ)パラダイムである。
【０００６】
Encrypt_then_sign（ＥｔＳ）
送信者は、公開鍵と秘密鍵のペア（Spk, Ssk）を有し、受信者は異なる公開鍵と秘密鍵のペア（Epk, Esk）を有する。
【０００７】
送信者は、受信者の公開鍵Epkを用いて平文mを暗号化して、暗号文eを得る。次に、送信者の秘密鍵Sskを用いて暗号文eに署名し、署名sを得る。ペア（e, s）が平文mのsigncryptionを構成する。
【０００８】
その時送信者は、暗号文eの基礎となるメッセージに関する知識を提供することもできる。当業者には言うまでもなく、これは、用いる暗号方式が「クラスＥ」であれば、効率的に行える（非特許文献２参照。）この論文は、必要なプロトコルも、Commit_then_Encrypt_and_Signパラダイムによる確認者署名のセキュリティプルーフとともに説明している。確認者署名をセキュアにするため、このパラダイムは高価な暗号を使わなければならないことが示されている。しかし、このパラダイムは微調整により非常に安価な暗号でも使えるようになり、多くの実際的な構成が得られる。この論文は、さらに、この手法の具体的な場合、すなわちEncrypt_then_Signを検討しており、このソリューションを用いた確認者署名の実際的な実現方法を提示している。しかし、この研究のプリミティブでは、署名されるメッセージを暗号化できない。）クラスＥは、準同形暗号方式により構成され、暗号文がメッセージを暗号化することを証明する効率的プロトコルを受け入れる。かかる暗号方式の例としては、ElGamal暗号（非特許文献３参照）、Paillier暗号（非特許文献４参照）、Linear Diffie-Hellman KEM/DEM（非特許文献５参照）がある。
【０００９】
受信者は送信者の公開鍵Spkを用いて、暗号文eの署名sが正しいかチェックする。そして、署名が正しければ、受信者は、受信者の秘密鍵Ｅｓｋを用いて暗号文eを復号して、平文mを得る。
【００１０】
受信者は、いつでも誰にでも、平文mが暗号文eを復号したものである（または復号したものではない）ことを証明できる。これは、秘密鍵を開示せずに行えることが好ましい。ＥｔＳでは、かかる証明は、「confirm/deny protocols」と呼ばれるが、暗号文があるメッセージを暗号化したものであることを証明することとなる。これらの証明は、ある暗号文があるメッセージを暗号化したものであるかチェックすることが困難な場合に、すなわち使われる暗号化方式が基礎となるメッセージに基づき暗号文を区別することを困難にする識別不能性（indistinguishability）特性を満たす場合に、意味がある。一般的に、２つのメッセージとそのうち一方の暗号文とがあるとき、どちらのメッセージがその暗号文に対応するか、分からない。signcryption構成のセキュリティでは、基礎となる暗号の識別不能性が必要なので、上記のプルーフを効率的に実行させる暗号方式を検討しなければならない。ここで再び、クラスＥの暗号方式は、非特許文献２に記載されているように、この目標を達成している。
【００１１】
Sign_then_encrypt（ＳｔＥ）
ＥｔＳのように、送信者は公開鍵と秘密鍵のペア（Spk, Ssk）を有し、受信者は異なる公開鍵と秘密鍵のペア（Epk, Esk）を有する。
【００１２】
ＳｔＥは、従来技術の署名方法と、従来技術の署名暗号化方法とを用いて、簡単に実現できる。
【００１３】
特許文献１はSign_then_Encryptパラダイムを用いてメッセージをsigncryptする他の一ソリューションを説明している。このアイデアは、まず、署名するメッセージの署名をＲＳＡを用いて作成し、次に、再びＲＳＡを用いて、異なる鍵ペアで、作成した署名を暗号化する。その結果が問題のメッセージのsigncryptionとなる。このsigncryptionのde-signcrypt（すなわち復号と検証）は、まずsigncryptionを復号し、出力される署名を符号で検証し、最後にその符号の基礎であるメッセージを回復することにより行う。このソリューションは、検証機能を提供しないように見える。すなわちメッセージが無ければ、作成されたsigncryptionの適格性を効率的に証明できないように見える。確かに、このソリューションの効率的な検証は、検証を容易にする代数的性質を破壊するハッシュ関数とＸＯＲ演算とがあるため、妥当とは思えなさそうである。
【００１４】
ＳｔＥを実施する他の一方法は、デジタル署名方式と暗号方式とからsigncryption方式を構成することである。これは２つのメカニズム、すなわちセッション鍵を生成するメカニズムである鍵カプセル化メカニズム（ＫＥＭ）と、対称鍵暗号化方式であるデータカプセル化メカニズム（ＤＥＭ）との組み合わせである。
【００１５】
ＫＥＭは３つのアルゴリズム（鍵生成、カプセル化、逆カプセル化（decapsulation））により構成される。鍵生成は鍵ペア（pk，sk）を生成する。カプセル化は、pkを用いて、鍵ｋとそのカプセル化cを生成する。逆カプセル化（decapsulation）は、秘密鍵skを用いて、鍵のカプセル化から鍵を読み出す。一例は、ＥｌＧａｍａｌ暗号方式を基礎としたＫＥＭである。
【００１６】
ＤＥＭーデータカプセル化メカニズム−は、データを暗号化するが、通常は対称鍵暗号アルゴリズムを用いる。
【００１７】
ＳｔＥは図１に示されている。乱数ｒ、ＫＥＭのカプセル化アルゴリズム、及び公開鍵pkを用いて、セッション鍵ｋとそのカプセル化cとを求める。送信者は、その秘密鍵Sskを用いて、平文mとカプセル化cとを連結したものに署名して、署名s（図示せず）を得る。ＤＥＭ暗号化アルゴリズムとセッション鍵ｋとを用いて、（m，s）を暗号化し、eを求める。ペア（c,
e）は平文mのsigncryptionを構成する。（c, e）を「unsigncrypt」するには、ＫＥＭの逆カプセル化アルゴリズムと秘密鍵とを用いて、セッション鍵kのカプセル化cからセッション鍵kを回復する。次に、ＤＥＭの復号アルゴリズムとセッション鍵kとを用いて、eを復号して（m，s）を求める。最後に、送信者の公開鍵を用いて、署名sの正しさを検証する。
【００１８】
送信者は、さらに、求めたsigncryptionの正しさを証明する必要がある。ＳｔＥでは、この証明により、eの復号文が分かり、この復号文はsigncryptされたメッセージと、cと連結されたこのメッセージの署名と連結である。
【００１９】
この証明は、理論的観点から妥当である（非特許文献６参照）。しかし、証明すべきデータはビット列であり代数的要素ではないので、効率的にどう証明するかは分からない。
【００２０】
ＫＥＭ／ＤＥＭ暗号化方式の一例はＥｌＧａｍａｌ暗号である：
１.ElGamal.Setup。元ｇから生成された、情報的に書かれた群Ｇを考える。群Ｇは有限群であり、位数はｄであるとする。
【００２１】
２.ElGamal.Keygen。鍵生成アルゴリズムは、入力がセキュリティパラメータであり、出力がZdの整数xである。群の元はy=gxである。鍵のペアは（sk=x, pk=y）である。
【００２２】
３.ElGamal.Encrypt(m)。［第１ステップ：ＫＥＭカプセル化アルゴリズム］：Zdのランダムなrを用いて、鍵k=yrとそのカプセル化c=grとを生成する。［第２ステップ：ＤＥＭ暗号化アルゴリズム］：mを暗号化しe=m・k。［最終的出力］：（c, e）がmの暗号を構成する。
【００２３】
４.ElGamal.Decrypt(c, e)。［第１ステップ：ＫＥＭ逆カプセル化アルゴリズム］：ｘを用いて、k=cx=(gr)x=(gx)r=yrとして、cから鍵kを回復する。［第２ステップ：ＤＥＭ復号アルゴリズム］：m=c・k-１としてmを回復する。
【００２４】
最後に、構成の正しさを効率的に証明するため、（ＫＥＭ／ＤＥＭパラダイムから得られる）用いる暗号化方式が前述の「クラスＥ」になることが必要である。すなわち、暗号化が同形であり、ある暗号文があるメッセージの暗号文であることを証明する効率的な証明ができることが必要である。ＥｌＧａｍａｌ暗号はこれを満たす。
【００２５】
一般的に、signcryptionが検証可能であるためには次の特性が必要である。
【００２６】
１.不可鍛性（unforgeability）：（必ずしも敵対者によりコントロールされていなくても）メッセージの送信者のふりをすることが計算的に実現不可能である。
【００２７】
２.区別性（indistinguishability）：メッセージに関してそのsigncryptionから何らかの情報を推測することが計算的に実現不可能である。
【００２８】
３.検証可能性（verifiability）：signcryptionの正しさを効率的に証明できる可能性。
【００２９】
電子選挙の例をもう一度考えるが、投票センターは投票者から「signcrypt」された投票の正しさの証明を必要とする。また、投票を復号するtrustされたパーティ（受信者）は、例えば、後で問題にならないように、送信者が問題の投票をしたのだということを証明しなければならないだろう。そのため、受信者の秘密鍵を開示せずにかかる証明を提供する効率的な手段により、受信者を支援することが望ましい。
【００３０】
これらの特性を考慮して、ＥｔＳとＳｔＥは次を実行する：
ＥｔＳはverifiabilityに関してよい比較ができるが、それは単に送信者が暗号文の復号に関する知識を証明する必要があるからである。また、受信者はメッセージが暗号文の復号である、または復号でないことを証明しなければならない。かかる証明は、同形暗号と呼ばれる特殊な暗号クラスを考えた場合、容易に実行できる。しかし、indistinguishabilityを実現するためには、ＥｔＳは基礎となる署名方式が最高のセキュリティnotionを満たすことを、すなわち、敵対者が署名を取得したかも知れないメッセージに対し、新しい署名を取得するのが困難であることを非公式的に示す、選択されたメッセージ攻撃の下での強いunforgeabilityを要求する。かかる必要性は、署名方式が上記の要件を満たさない場合、署名されたメッセージに新しいsigncryptionを生成する可能性により正当化される。かかる可能性は、よく使われるほとんどの攻撃モデルにおいて、indistinguishability adversaryにメッセージを読み出すスキを与える。
【００３１】
ＳｔＥは、基礎となる署名方式に高いsecurity notionsは必要としない。この場合、敵対者はデジタル署名を有していないことが明確だからである。ＳｔＥに好意的な他の議論は、ＳｔＥが送信者に完全な匿名性を提供することである。メッセージｍのsigncryptionは暗号文である。一方、ＥｔＳでは、送信者がsigncryption（e，s）に係わったか、単に（送信者の公開鍵を用いて）暗号文eのデジタル署名の正しさをチェックすることにより、誰でもチェックできる。しかし、verifiabilityはハードルとなる。上記手法は（用いた署名方式の）署名アルゴリズムを、用いたカプセル化と連結してsigncryptするメッセージに適用する。さらに、得られる署名を問題のメッセージと連結したものの暗号化をする。暗号化された署名とメッセージに関する知識の証明をするため、できたsigncryptionの正しさを証明するには、署名の同形性と暗号方式の同形性とを利用する必要がある。結果として、用いる暗号化と署名の方式は、ビットストリングではなく、代数的構造が既知の集合の要素に作用する必要がある。
まとめると、ＥｔＳにより、送信者の匿名性と構成ブロックのセキュリティという代償によって、効率的なverifiabilityが得られる。ＳｔＥは、verifiabilityという代償によって、安価な構成を用いて、よりよいプライバシーを実現できる。
【００３２】
当業者には言うまでもなく、ＥｔＳとＳｔＥの欠点を回避しつつ長所を組み合わせるソリューションが必要である。本発明はかかるソリューションを提供するものである。
【先行技術文献】
【特許文献】
【００３３】
【特許文献１】米国特許出願公開第２００５／２４０７６２号明細書
【非特許文献】
【００３４】
【非特許文献１】Laila El Aimani著「Design and Analysis ofOpaque Signatures」（Dissertation RheinischenFriedrich-Wilhelms-Universitat Bonn(http://hss.ulb.uni-bonn.de/2011/2541/2541.pdf)）
【非特許文献２】Laila El Aimani著「Efficient ConfirmerSignatures from the "Signature of a Commitment" Paradigm」（ProvSec 2010: 87-101）
【非特許文献３】Taher El Gamal著「A Public Key Cryptosystemand a Signature Scheme Based on Discrete Logarithms」（CRYPTO1984:10-18）
【非特許文献４】Paillier著「Public-Key Cryptosystems Based onComposite Degree Residuosity Classes」（EUROCRYPT 1999:223-238）
【非特許文献５】Dan Boneh, Xavier Boyen, Hovav Shacham著「ShortGroup Signatures」（CRYPTO 2004: 41-55）
【非特許文献６】Oded Goldreich, Silvio Micali, Avi Wigderson著「How to Prove all NP-Statements in Zero-Knowledge, and a Methodologyof Cryptographic Protocol Design」（CRYPTO 1986: 171-185）
【発明の概要】
【００３５】
第１の態様では、本発明は平文mをsigncryptする方法に関する。装置は、第１の暗号化アルゴリズムと第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得し；乱数ｒと、カプセル化アルゴリズムと、第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成し、秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成し、前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得し、前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成し、前記signcryptionを出力する。
【００３６】
第１の好ましい実施形態において、上記装置は、さらに、第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する。
【００３７】
第２の態様では、本発明は、受信した、平文mのsigncryptionを逆signcryptする方法に関する。signcryptionは第１の暗号文eとカプセル化cと、第２の暗号文e_dとを含む。装置は、第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、第１の公開鍵に対応する第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号し、逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、第２の公開鍵Kpkに対応する第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出し、第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復し、検証アルゴリズムと、前記署名の生成に用いられた秘密署名鍵Sskに対応する公開署名鍵Spkとを用いて、前記署名sが正しいか検証する。
【００３８】
第１の好ましい実施形態では、前記装置は、さらに、前記平文mと前記暗号文eの復号と、前記第２の暗号文e_dの復号とが等しいまたは等しくないとの知識を、及び前記復号が前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であることを証明する。
【００３９】
第３の態様では、本発明は平文mをsigncryptするsigncryption装置に関する。signcryption装置は、第１の暗号化アルゴリズムと第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得する手段と、乱数ｒと、カプセル化アルゴリズムと、第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成する手段と、秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成する手段と、前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得する手段と、前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成する手段と、前記signcryptionを出力する手段と、を有する。
【００４０】
第１の好ましい実施形態では、第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する手段をさらに有する。
【００４１】
第４の態様では、本発明は、受信した、平文mのsigncryptionをunsigncryptするsigncryption検証装置装置に関する。前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含む。前記signcryption検証装置は、第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、第１の公開鍵に対応する第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号する手段と、逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、第２の公開鍵Kpkに対応する第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出す手段と、第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復する手段と、検証アルゴリズムと、前記署名の生成に用いられた秘密署名鍵Sskに対応する公開署名鍵Spkとを用いて、前記署名sが正しいか検証する手段とを有する。
【００４２】
第１の好ましい実施形態では、前記平文mの復号と前記暗号文eとが等しいまたは等しくないとの知識と、署名sが前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であるかどうかとを証明する手段をさらに有する。
【００４３】
第５の態様では、本発明は、プロセッサにより実行されると、第１の態様の方法の任意の実施形態の方法を実行する命令を記憶した記憶媒体に関する。
【００４４】
第６の態様では、本発明は、プロセッサにより実行されると、第２の態様の方法の任意の実施形態の方法を実行する命令を記憶した記憶媒体に関する。
【図面の簡単な説明】
【００４５】
添付した図面を参照して、限定的でない例示により、本発明の好ましい特徴をここに説明する。
【図１】すでに説明したように、従来技術のＫＥＭ／ＤＥＭパラダイム方式を示す図である。
【図２】本発明の好ましい実施形態によるsigncryption方法を示す。
【図３】本発明の好ましい実施形態によるsigncryptionシステムを示す。
【発明を実施するための形態】
【００４６】
本発明の主要な発明的アイデアは、まず、signcryptする平文を公開鍵暗号方式を用いて暗号化し、次に、生成された暗号文に変形ＳｔＥを適用することよりなる。この変形ＳｔＥと暗号文との結果が、その平文の新しいsigncryptionを構成する。
【００４７】
ある意味で、この手法はＥｔＳとＳｔＥの組み合わせと見ることができる。そのため、「encrypt_then_sign_then_encrypt」（ＥｔＳｔＥ）と呼ぶことができる。
【００４８】
本発明の好ましい実施形態によるsigncryption（ＳＣ）方法を図２に示す。この方法は、第１の暗号化方式E=(E.Keygen,
E.Encrypt, E.Decrypt)と、署名方式S=(S.Keygen, S.Sign,
S.Verify)と、いわゆるＫＥＭ／ＤＥＭパラダイムの第２の暗号化方式とを用いる。この第２の暗号化方式は、実際には、鍵カプセル化及びセッション鍵生成方式K=(K.Keygen, K.Encapsulate, K.Decapsulate)と第２の暗号化方式D=(D.Encrypt, D.Decrypt)とを含む。第２の暗号化方式は対称である。
【００４９】
signcryption方式ＳＣは次の通りである。
【００５０】
まず、必要な鍵を生成する。E.Keygenを呼び(Epk,Esk)を求め、S.Keygenを呼び(Spk,Ssk)を求め、K.Keygenを呼び(Kpk,Ksk)を求める。送信者の鍵ペアを(Spk,Ssk)に設定し、受信者の鍵ペアを({Epk, Kpk},{Esk,Ksk})に設定する。言うまでもなく、このステップは、鍵の配布を含むが、本発明の範囲外であり、どんな好適な方法を用いても良い。送信者と受信者が自分たち独自の鍵ペアを生成することが好ましい。仮定として、送信者と受信者は方法ステップを実行するのに必要な鍵を有しているものとする。
【００５１】
送信者は第１の暗号化アルゴリズムを用いて、Epkで平文mを暗号化し、暗号文e、すなわちe=E.Encrypt(m)を得る（ステップＳ１）。送信者は、カプセル化アルゴリズムとKpkとを用いて、鍵kとそのカプセル化c、すなわち(c,k)=K.Encapsulate()とを生成する（ステップＳ２）。次に、送信者は、Sskを用いて（e, c）の署名s=S.sign(e,
c)を生成する（ステップＳ３）。最後に、送信者は、第２の暗号化方式を用いて、鍵kでsを暗号化する。すなわち、e_kd=D.Encrypt(s)（ステップＳ４）。mのsigncryptionは(e, c,
e_d)により構成される（ステップＳ５）。
【００５２】
次に、送信者は、signcryption(e,c,e_d)を受信者に送信する（ステップＳ６）。
【００５３】
受信者はＥｓｋを用いてeを復号し、mすなわちm=E.Decrypt(e)を求める（ステップＳ７）。次に、受信者はKskを用いてcからk、すなわちk=K.Decapsulate(c)を読み出し（ステップＳ８）、鍵kを用いてe_dを復号することによりs、すなわちs=D.Decrypt(e_d)を回復する（ステップＳ９）。最後に、受信者はSpkを用いて、S.Verify(s)を用いて(e,c)の署名が正しいかチェックする（ステップＳ１０）。
【００５４】
送信者はeの復号に関する知識を証明でき、e_dが、カプセル化の鍵を用いたcとeの連結の正しい署名を暗号化してものであることを証明できる。受信者は、mがeの復号であること（または、復号でないこと）を証明できる。受信者は、さらに、(c,e_d)の復号の知識を証明し、この復号が(e,c)の正当なまたは正当でない署名よりなることを証明する。
【００５５】
上記の構成が効率的に実現できるのは、基礎となる暗号化方式が同形であり、用いられる署名方式が「クラスＳ」の署名クラスに、すなわちメッセージmと公開鍵pkがあるとき、pkとmに対する署名sとを有する者がこの署名sの知識を効率的に証明できるような、署名の知識の効率的な証明ができる署名クラスに属する場合である。「クラスＳ」は、Laila El Aimani著「On Generic Constructions of
Designated Confirmer Signatures」（INDOCRYPT 2009:
343-362）で定義されている。
【００５６】
かかるクラスは、今までに提案されよく使われているほとんどの署名を包含し、例えばRSA-FDH [Mihir Bellare, Phillip Rogaway: Random Oracles are
Practical: A Paradigm for Designing Efficient Protocols. ACM Conference on
Computer and Communications Security 1993: 62-73]：
１.RSA.Keygen:ＲＳＡモジュラスＮとＲＳＡ鍵(pk=e,sk=d)を生成する。ビットストリングをZNの要素にマッピングする衝突耐性のあるハッシュ関数ｈを考えよ。
２.RSA.Sign(m):mの署名をs=h(m)d mod Nとして計算する。
３.RSA.verify(m,s):se=h(m) mod Nであるかチェックする。
【００５７】
すぐに分かることは、sを有する者が、h(m)のe番目のルートの知識の証明をすることにより、sの知識を証明できることである。
【００５８】
図３は、本発明の好ましい実施形態によるsigncryptionシステム１００を示す。システム１００は、送信器１１０と受信器１２０とを有し、各々は、他の装置と通信するように構成された少なくとも１つのインタフェースユニット１１１、１２１と、少なくとも１つのプロセッサ（「プロセッサ」）１１２、１２２と、データを記憶するように構成された、アキュムレータや中間計算結果などの少なくとも１つのメモリ１１３、１２３とを有する。送信器１１０のプロセッサ１１２は、本発明の方法の実施形態により平文をsigncryptするように構成され、受信器１２０のプロセッサ１２２は、本発明の方法の実施形態によりsigncryptionを復号し検証するように構成されている。ＣＤ−ＲＯＭやＤＶＤなどの第１のコンピュータプログラム製品１１４は、送信器１１０のプロセッサ１１２により実行されたとき、本発明のいずれかの実施形態による平文のsigncryptionを実行する命令を記憶している。ＣＤ−ＲＯＭやＤＶＤなどの第２のコンピュータプログラム製品１２４は、送信器１２０のプロセッサ１２２により実行されたとき、本発明のいずれかの実施形態によりsigncryptionを復号し検証する命令を記憶している。
言うまでもなく、本signcryption方法は、従来のsigncryption方法と比較すると、性能がよく、特にverifiabilityに関する性能がよく、それと同時に高いセキュリティを提供する。
【００５９】
この改善は、この構成ではＥｔＳとＳｔＥのメリットを組み合わせつつ、両者の欠点を回避していることによる。
【００６０】
Verifiability
本発明の方法を用いて取得したsigncryption(e, c, e_d)の正当性を証明するには、送信器は：
１.eの復号に関する知識を提供し、
２.(c,e_d)の復号に関する知識と、この復号がcとeの連結の正しい署名であることを証明しなければならない。
【００６１】
両方の証明は、用いる暗号化方式が「クラスＥ」に属し、用いる署名方式が「クラスＳ」に属するとき、効率的に実行できる。これらは両方とも、上記の証明プロトコルとともに、[Laila El Aimani著「On Generic Constructions
of Designated Confirmer Signatures」（INDOCRYPT 2009:
343-362）]に説明されている。
【００６２】
ＳｔＥパラダイムでは、（メッセージmの）signcryptionは、(c,e)の形式であり、送信器は、復号(c,e)の知識と、この復号の第１部分がcと復号の残り部分（すなわち、m）との連結の正しい署名であることを証明する必要がある。これは理論的観点からは可能であるが、これを実現する効率的な方法は現在のところ知られていない。受信器のプロトコル、すなわち確認／拒絶プロトコルにも同じことが当てはまる。
【００６３】
よりよいプライバシ
本方法のsigncryptionは２つの暗号文を有し、攻撃者は暗号化されていないデジタル署名を有していない。これにより２つの方法でプライバシが向上する。第１に、ＥｔＳパラダイムに反して、indistinguishability性に影響せずに、「安価な」セキュリティ要件で、基礎となる署名方式を用いることができる。第２に、（ＥｔＳではsigncryptionに含まれるデジタル署名が正当か否か暗号文で誰でもチェックできるのに反して、）（第２の暗号化方式が匿名である場合、）signcryptionの送信者がsigncryptionに係わったか否かチェックできない。
【００６４】
明細書、特許請求の範囲、及び図面に開示した各特徴は、独立に設けることもできるし、適切に組み合わせて設けることもできる。ハードウェアで実施されると説明した機能はソフトウェアでも実施できるし、その逆の場合もある。特許請求の範囲に示す参照符号は例示であり、請求項の範囲を限定するものではない。
【技術分野】
【０００１】
本発明は概して暗号に関し、特にsigncryptionに関する。
【背景技術】
【０００２】
このセクションは、以下に説明して特許請求する本発明の様々な態様に関連する様々な態様の技術を読者に紹介することを意図するものである。この説明は、本発明の様々な態様の理解を容易にする背景情報を読者に提供する役に立つはずである。従って、言うまでもなく、これらの記載は上記を考慮して読むべきであり、先行技術として認める（admissions of prior art）ものではない。
【０００３】
多くの異なる暗号方式がある。Laila El Aimaniは、非特許文献１において、いくつかの暗号方式を説明しており、特に強固で否定できない署名、すなわちエンティティとの協力なくしては検証をできない署名を説明している。この論文では、筆者は基本的に基本的暗号からかかる署名をどう構成するか研究している。彼女は、従来のパラダイム（例えば、Encrypt_then_SignやCommit_then_Encrypt_and_Sign）では、リーズナブルなセキュリティレベルを満たすために、高価な暗号が必要であることを示している。次に、彼女は、少し調整するだけで、安価な暗号で構成できるようになり、得られる署名の効率（例えば、コスト、帯域幅、検証可能性）にもよいインパクトを与えることを示している。しかし、署名は、署名されるメッセージを暗号化するものではない。
【０００４】
多くの実生活のアプリケーションには伝送データの秘密性と信ぴょう性／インテグリティの両方が必要なので、署名と暗号の機能を両方とも提供する暗号メカニズムであるいわゆるsigncryptionは、ますます広がりを見せている。一例として、投票者のプライバシーを保証するため暗号化が必要であり、同時に投票センターが暗号化された投票が投票者のものであることを確認する必要がある電子選挙がある。
【０００５】
かかるメカニズムを基本的暗号プリミティブから構成するのは、専用の一体的構成と比較して、分析しやすい方式を実現できるので、暗号技術の分野では慣用されている。基本的暗号プリミティブからこれらのメカニズムを実現するのに用いられる、最も良く使われる先行技術のパラダイムは、「encrypt_then_sign」(ＥｔＳ)パラダイムと「sign_then_encrypt」(ＳｔＥ)パラダイムである。
【０００６】
Encrypt_then_sign（ＥｔＳ）
送信者は、公開鍵と秘密鍵のペア（Spk, Ssk）を有し、受信者は異なる公開鍵と秘密鍵のペア（Epk, Esk）を有する。
【０００７】
送信者は、受信者の公開鍵Epkを用いて平文mを暗号化して、暗号文eを得る。次に、送信者の秘密鍵Sskを用いて暗号文eに署名し、署名sを得る。ペア（e, s）が平文mのsigncryptionを構成する。
【０００８】
その時送信者は、暗号文eの基礎となるメッセージに関する知識を提供することもできる。当業者には言うまでもなく、これは、用いる暗号方式が「クラスＥ」であれば、効率的に行える（非特許文献２参照。）この論文は、必要なプロトコルも、Commit_then_Encrypt_and_Signパラダイムによる確認者署名のセキュリティプルーフとともに説明している。確認者署名をセキュアにするため、このパラダイムは高価な暗号を使わなければならないことが示されている。しかし、このパラダイムは微調整により非常に安価な暗号でも使えるようになり、多くの実際的な構成が得られる。この論文は、さらに、この手法の具体的な場合、すなわちEncrypt_then_Signを検討しており、このソリューションを用いた確認者署名の実際的な実現方法を提示している。しかし、この研究のプリミティブでは、署名されるメッセージを暗号化できない。）クラスＥは、準同形暗号方式により構成され、暗号文がメッセージを暗号化することを証明する効率的プロトコルを受け入れる。かかる暗号方式の例としては、ElGamal暗号（非特許文献３参照）、Paillier暗号（非特許文献４参照）、Linear Diffie-Hellman KEM/DEM（非特許文献５参照）がある。
【０００９】
受信者は送信者の公開鍵Spkを用いて、暗号文eの署名sが正しいかチェックする。そして、署名が正しければ、受信者は、受信者の秘密鍵Ｅｓｋを用いて暗号文eを復号して、平文mを得る。
【００１０】
受信者は、いつでも誰にでも、平文mが暗号文eを復号したものである（または復号したものではない）ことを証明できる。これは、秘密鍵を開示せずに行えることが好ましい。ＥｔＳでは、かかる証明は、「confirm/deny protocols」と呼ばれるが、暗号文があるメッセージを暗号化したものであることを証明することとなる。これらの証明は、ある暗号文があるメッセージを暗号化したものであるかチェックすることが困難な場合に、すなわち使われる暗号化方式が基礎となるメッセージに基づき暗号文を区別することを困難にする識別不能性（indistinguishability）特性を満たす場合に、意味がある。一般的に、２つのメッセージとそのうち一方の暗号文とがあるとき、どちらのメッセージがその暗号文に対応するか、分からない。signcryption構成のセキュリティでは、基礎となる暗号の識別不能性が必要なので、上記のプルーフを効率的に実行させる暗号方式を検討しなければならない。ここで再び、クラスＥの暗号方式は、非特許文献２に記載されているように、この目標を達成している。
【００１１】
Sign_then_encrypt（ＳｔＥ）
ＥｔＳのように、送信者は公開鍵と秘密鍵のペア（Spk, Ssk）を有し、受信者は異なる公開鍵と秘密鍵のペア（Epk, Esk）を有する。
【００１２】
ＳｔＥは、従来技術の署名方法と、従来技術の署名暗号化方法とを用いて、簡単に実現できる。
【００１３】
特許文献１はSign_then_Encryptパラダイムを用いてメッセージをsigncryptする他の一ソリューションを説明している。このアイデアは、まず、署名するメッセージの署名をＲＳＡを用いて作成し、次に、再びＲＳＡを用いて、異なる鍵ペアで、作成した署名を暗号化する。その結果が問題のメッセージのsigncryptionとなる。このsigncryptionのde-signcrypt（すなわち復号と検証）は、まずsigncryptionを復号し、出力される署名を符号で検証し、最後にその符号の基礎であるメッセージを回復することにより行う。このソリューションは、検証機能を提供しないように見える。すなわちメッセージが無ければ、作成されたsigncryptionの適格性を効率的に証明できないように見える。確かに、このソリューションの効率的な検証は、検証を容易にする代数的性質を破壊するハッシュ関数とＸＯＲ演算とがあるため、妥当とは思えなさそうである。
【００１４】
ＳｔＥを実施する他の一方法は、デジタル署名方式と暗号方式とからsigncryption方式を構成することである。これは２つのメカニズム、すなわちセッション鍵を生成するメカニズムである鍵カプセル化メカニズム（ＫＥＭ）と、対称鍵暗号化方式であるデータカプセル化メカニズム（ＤＥＭ）との組み合わせである。
【００１５】
ＫＥＭは３つのアルゴリズム（鍵生成、カプセル化、逆カプセル化（decapsulation））により構成される。鍵生成は鍵ペア（pk，sk）を生成する。カプセル化は、pkを用いて、鍵ｋとそのカプセル化cを生成する。逆カプセル化（decapsulation）は、秘密鍵skを用いて、鍵のカプセル化から鍵を読み出す。一例は、ＥｌＧａｍａｌ暗号方式を基礎としたＫＥＭである。
【００１６】
ＤＥＭーデータカプセル化メカニズム−は、データを暗号化するが、通常は対称鍵暗号アルゴリズムを用いる。
【００１７】
ＳｔＥは図１に示されている。乱数ｒ、ＫＥＭのカプセル化アルゴリズム、及び公開鍵pkを用いて、セッション鍵ｋとそのカプセル化cとを求める。送信者は、その秘密鍵Sskを用いて、平文mとカプセル化cとを連結したものに署名して、署名s（図示せず）を得る。ＤＥＭ暗号化アルゴリズムとセッション鍵ｋとを用いて、（m，s）を暗号化し、eを求める。ペア（c,
e）は平文mのsigncryptionを構成する。（c, e）を「unsigncrypt」するには、ＫＥＭの逆カプセル化アルゴリズムと秘密鍵とを用いて、セッション鍵kのカプセル化cからセッション鍵kを回復する。次に、ＤＥＭの復号アルゴリズムとセッション鍵kとを用いて、eを復号して（m，s）を求める。最後に、送信者の公開鍵を用いて、署名sの正しさを検証する。
【００１８】
送信者は、さらに、求めたsigncryptionの正しさを証明する必要がある。ＳｔＥでは、この証明により、eの復号文が分かり、この復号文はsigncryptされたメッセージと、cと連結されたこのメッセージの署名と連結である。
【００１９】
この証明は、理論的観点から妥当である（非特許文献６参照）。しかし、証明すべきデータはビット列であり代数的要素ではないので、効率的にどう証明するかは分からない。
【００２０】
ＫＥＭ／ＤＥＭ暗号化方式の一例はＥｌＧａｍａｌ暗号である：
１.ElGamal.Setup。元ｇから生成された、情報的に書かれた群Ｇを考える。群Ｇは有限群であり、位数はｄであるとする。
【００２１】
２.ElGamal.Keygen。鍵生成アルゴリズムは、入力がセキュリティパラメータであり、出力がZdの整数xである。群の元はy=gxである。鍵のペアは（sk=x, pk=y）である。
【００２２】
３.ElGamal.Encrypt(m)。［第１ステップ：ＫＥＭカプセル化アルゴリズム］：Zdのランダムなrを用いて、鍵k=yrとそのカプセル化c=grとを生成する。［第２ステップ：ＤＥＭ暗号化アルゴリズム］：mを暗号化しe=m・k。［最終的出力］：（c, e）がmの暗号を構成する。
【００２３】
４.ElGamal.Decrypt(c, e)。［第１ステップ：ＫＥＭ逆カプセル化アルゴリズム］：ｘを用いて、k=cx=(gr)x=(gx)r=yrとして、cから鍵kを回復する。［第２ステップ：ＤＥＭ復号アルゴリズム］：m=c・k-１としてmを回復する。
【００２４】
最後に、構成の正しさを効率的に証明するため、（ＫＥＭ／ＤＥＭパラダイムから得られる）用いる暗号化方式が前述の「クラスＥ」になることが必要である。すなわち、暗号化が同形であり、ある暗号文があるメッセージの暗号文であることを証明する効率的な証明ができることが必要である。ＥｌＧａｍａｌ暗号はこれを満たす。
【００２５】
一般的に、signcryptionが検証可能であるためには次の特性が必要である。
【００２６】
１.不可鍛性（unforgeability）：（必ずしも敵対者によりコントロールされていなくても）メッセージの送信者のふりをすることが計算的に実現不可能である。
【００２７】
２.区別性（indistinguishability）：メッセージに関してそのsigncryptionから何らかの情報を推測することが計算的に実現不可能である。
【００２８】
３.検証可能性（verifiability）：signcryptionの正しさを効率的に証明できる可能性。
【００２９】
電子選挙の例をもう一度考えるが、投票センターは投票者から「signcrypt」された投票の正しさの証明を必要とする。また、投票を復号するtrustされたパーティ（受信者）は、例えば、後で問題にならないように、送信者が問題の投票をしたのだということを証明しなければならないだろう。そのため、受信者の秘密鍵を開示せずにかかる証明を提供する効率的な手段により、受信者を支援することが望ましい。
【００３０】
これらの特性を考慮して、ＥｔＳとＳｔＥは次を実行する：
ＥｔＳはverifiabilityに関してよい比較ができるが、それは単に送信者が暗号文の復号に関する知識を証明する必要があるからである。また、受信者はメッセージが暗号文の復号である、または復号でないことを証明しなければならない。かかる証明は、同形暗号と呼ばれる特殊な暗号クラスを考えた場合、容易に実行できる。しかし、indistinguishabilityを実現するためには、ＥｔＳは基礎となる署名方式が最高のセキュリティnotionを満たすことを、すなわち、敵対者が署名を取得したかも知れないメッセージに対し、新しい署名を取得するのが困難であることを非公式的に示す、選択されたメッセージ攻撃の下での強いunforgeabilityを要求する。かかる必要性は、署名方式が上記の要件を満たさない場合、署名されたメッセージに新しいsigncryptionを生成する可能性により正当化される。かかる可能性は、よく使われるほとんどの攻撃モデルにおいて、indistinguishability adversaryにメッセージを読み出すスキを与える。
【００３１】
ＳｔＥは、基礎となる署名方式に高いsecurity notionsは必要としない。この場合、敵対者はデジタル署名を有していないことが明確だからである。ＳｔＥに好意的な他の議論は、ＳｔＥが送信者に完全な匿名性を提供することである。メッセージｍのsigncryptionは暗号文である。一方、ＥｔＳでは、送信者がsigncryption（e，s）に係わったか、単に（送信者の公開鍵を用いて）暗号文eのデジタル署名の正しさをチェックすることにより、誰でもチェックできる。しかし、verifiabilityはハードルとなる。上記手法は（用いた署名方式の）署名アルゴリズムを、用いたカプセル化と連結してsigncryptするメッセージに適用する。さらに、得られる署名を問題のメッセージと連結したものの暗号化をする。暗号化された署名とメッセージに関する知識の証明をするため、できたsigncryptionの正しさを証明するには、署名の同形性と暗号方式の同形性とを利用する必要がある。結果として、用いる暗号化と署名の方式は、ビットストリングではなく、代数的構造が既知の集合の要素に作用する必要がある。
まとめると、ＥｔＳにより、送信者の匿名性と構成ブロックのセキュリティという代償によって、効率的なverifiabilityが得られる。ＳｔＥは、verifiabilityという代償によって、安価な構成を用いて、よりよいプライバシーを実現できる。
【００３２】
当業者には言うまでもなく、ＥｔＳとＳｔＥの欠点を回避しつつ長所を組み合わせるソリューションが必要である。本発明はかかるソリューションを提供するものである。
【先行技術文献】
【特許文献】
【００３３】
【特許文献１】米国特許出願公開第２００５／２４０７６２号明細書
【非特許文献】
【００３４】
【非特許文献１】Laila El Aimani著「Design and Analysis ofOpaque Signatures」（Dissertation RheinischenFriedrich-Wilhelms-Universitat Bonn(http://hss.ulb.uni-bonn.de/2011/2541/2541.pdf)）
【非特許文献２】Laila El Aimani著「Efficient ConfirmerSignatures from the "Signature of a Commitment" Paradigm」（ProvSec 2010: 87-101）
【非特許文献３】Taher El Gamal著「A Public Key Cryptosystemand a Signature Scheme Based on Discrete Logarithms」（CRYPTO1984:10-18）
【非特許文献４】Paillier著「Public-Key Cryptosystems Based onComposite Degree Residuosity Classes」（EUROCRYPT 1999:223-238）
【非特許文献５】Dan Boneh, Xavier Boyen, Hovav Shacham著「ShortGroup Signatures」（CRYPTO 2004: 41-55）
【非特許文献６】Oded Goldreich, Silvio Micali, Avi Wigderson著「How to Prove all NP-Statements in Zero-Knowledge, and a Methodologyof Cryptographic Protocol Design」（CRYPTO 1986: 171-185）
【発明の概要】
【００３５】
第１の態様では、本発明は平文mをsigncryptする方法に関する。装置は、第１の暗号化アルゴリズムと第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得し；乱数ｒと、カプセル化アルゴリズムと、第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成し、秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成し、前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得し、前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成し、前記signcryptionを出力する。
【００３６】
第１の好ましい実施形態において、上記装置は、さらに、第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する。
【００３７】
第２の態様では、本発明は、受信した、平文mのsigncryptionを逆signcryptする方法に関する。signcryptionは第１の暗号文eとカプセル化cと、第２の暗号文e_dとを含む。装置は、第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、第１の公開鍵に対応する第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号し、逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、第２の公開鍵Kpkに対応する第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出し、第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復し、検証アルゴリズムと、前記署名の生成に用いられた秘密署名鍵Sskに対応する公開署名鍵Spkとを用いて、前記署名sが正しいか検証する。
【００３８】
第１の好ましい実施形態では、前記装置は、さらに、前記平文mと前記暗号文eの復号と、前記第２の暗号文e_dの復号とが等しいまたは等しくないとの知識を、及び前記復号が前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であることを証明する。
【００３９】
第３の態様では、本発明は平文mをsigncryptするsigncryption装置に関する。signcryption装置は、第１の暗号化アルゴリズムと第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得する手段と、乱数ｒと、カプセル化アルゴリズムと、第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成する手段と、秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成する手段と、前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得する手段と、前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成する手段と、前記signcryptionを出力する手段と、を有する。
【００４０】
第１の好ましい実施形態では、第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する手段をさらに有する。
【００４１】
第４の態様では、本発明は、受信した、平文mのsigncryptionをunsigncryptするsigncryption検証装置装置に関する。前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含む。前記signcryption検証装置は、第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、第１の公開鍵に対応する第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号する手段と、逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、第２の公開鍵Kpkに対応する第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出す手段と、第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復する手段と、検証アルゴリズムと、前記署名の生成に用いられた秘密署名鍵Sskに対応する公開署名鍵Spkとを用いて、前記署名sが正しいか検証する手段とを有する。
【００４２】
第１の好ましい実施形態では、前記平文mの復号と前記暗号文eとが等しいまたは等しくないとの知識と、署名sが前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であるかどうかとを証明する手段をさらに有する。
【００４３】
第５の態様では、本発明は、プロセッサにより実行されると、第１の態様の方法の任意の実施形態の方法を実行する命令を記憶した記憶媒体に関する。
【００４４】
第６の態様では、本発明は、プロセッサにより実行されると、第２の態様の方法の任意の実施形態の方法を実行する命令を記憶した記憶媒体に関する。
【図面の簡単な説明】
【００４５】
添付した図面を参照して、限定的でない例示により、本発明の好ましい特徴をここに説明する。
【図１】すでに説明したように、従来技術のＫＥＭ／ＤＥＭパラダイム方式を示す図である。
【図２】本発明の好ましい実施形態によるsigncryption方法を示す。
【図３】本発明の好ましい実施形態によるsigncryptionシステムを示す。
【発明を実施するための形態】
【００４６】
本発明の主要な発明的アイデアは、まず、signcryptする平文を公開鍵暗号方式を用いて暗号化し、次に、生成された暗号文に変形ＳｔＥを適用することよりなる。この変形ＳｔＥと暗号文との結果が、その平文の新しいsigncryptionを構成する。
【００４７】
ある意味で、この手法はＥｔＳとＳｔＥの組み合わせと見ることができる。そのため、「encrypt_then_sign_then_encrypt」（ＥｔＳｔＥ）と呼ぶことができる。
【００４８】
本発明の好ましい実施形態によるsigncryption（ＳＣ）方法を図２に示す。この方法は、第１の暗号化方式E=(E.Keygen,
E.Encrypt, E.Decrypt)と、署名方式S=(S.Keygen, S.Sign,
S.Verify)と、いわゆるＫＥＭ／ＤＥＭパラダイムの第２の暗号化方式とを用いる。この第２の暗号化方式は、実際には、鍵カプセル化及びセッション鍵生成方式K=(K.Keygen, K.Encapsulate, K.Decapsulate)と第２の暗号化方式D=(D.Encrypt, D.Decrypt)とを含む。第２の暗号化方式は対称である。
【００４９】
signcryption方式ＳＣは次の通りである。
【００５０】
まず、必要な鍵を生成する。E.Keygenを呼び(Epk,Esk)を求め、S.Keygenを呼び(Spk,Ssk)を求め、K.Keygenを呼び(Kpk,Ksk)を求める。送信者の鍵ペアを(Spk,Ssk)に設定し、受信者の鍵ペアを({Epk, Kpk},{Esk,Ksk})に設定する。言うまでもなく、このステップは、鍵の配布を含むが、本発明の範囲外であり、どんな好適な方法を用いても良い。送信者と受信者が自分たち独自の鍵ペアを生成することが好ましい。仮定として、送信者と受信者は方法ステップを実行するのに必要な鍵を有しているものとする。
【００５１】
送信者は第１の暗号化アルゴリズムを用いて、Epkで平文mを暗号化し、暗号文e、すなわちe=E.Encrypt(m)を得る（ステップＳ１）。送信者は、カプセル化アルゴリズムとKpkとを用いて、鍵kとそのカプセル化c、すなわち(c,k)=K.Encapsulate()とを生成する（ステップＳ２）。次に、送信者は、Sskを用いて（e, c）の署名s=S.sign(e,
c)を生成する（ステップＳ３）。最後に、送信者は、第２の暗号化方式を用いて、鍵kでsを暗号化する。すなわち、e_kd=D.Encrypt(s)（ステップＳ４）。mのsigncryptionは(e, c,
e_d)により構成される（ステップＳ５）。
【００５２】
次に、送信者は、signcryption(e,c,e_d)を受信者に送信する（ステップＳ６）。
【００５３】
受信者はＥｓｋを用いてeを復号し、mすなわちm=E.Decrypt(e)を求める（ステップＳ７）。次に、受信者はKskを用いてcからk、すなわちk=K.Decapsulate(c)を読み出し（ステップＳ８）、鍵kを用いてe_dを復号することによりs、すなわちs=D.Decrypt(e_d)を回復する（ステップＳ９）。最後に、受信者はSpkを用いて、S.Verify(s)を用いて(e,c)の署名が正しいかチェックする（ステップＳ１０）。
【００５４】
送信者はeの復号に関する知識を証明でき、e_dが、カプセル化の鍵を用いたcとeの連結の正しい署名を暗号化してものであることを証明できる。受信者は、mがeの復号であること（または、復号でないこと）を証明できる。受信者は、さらに、(c,e_d)の復号の知識を証明し、この復号が(e,c)の正当なまたは正当でない署名よりなることを証明する。
【００５５】
上記の構成が効率的に実現できるのは、基礎となる暗号化方式が同形であり、用いられる署名方式が「クラスＳ」の署名クラスに、すなわちメッセージmと公開鍵pkがあるとき、pkとmに対する署名sとを有する者がこの署名sの知識を効率的に証明できるような、署名の知識の効率的な証明ができる署名クラスに属する場合である。「クラスＳ」は、Laila El Aimani著「On Generic Constructions of
Designated Confirmer Signatures」（INDOCRYPT 2009:
343-362）で定義されている。
【００５６】
かかるクラスは、今までに提案されよく使われているほとんどの署名を包含し、例えばRSA-FDH [Mihir Bellare, Phillip Rogaway: Random Oracles are
Practical: A Paradigm for Designing Efficient Protocols. ACM Conference on
Computer and Communications Security 1993: 62-73]：
１.RSA.Keygen:ＲＳＡモジュラスＮとＲＳＡ鍵(pk=e,sk=d)を生成する。ビットストリングをZNの要素にマッピングする衝突耐性のあるハッシュ関数ｈを考えよ。
２.RSA.Sign(m):mの署名をs=h(m)d mod Nとして計算する。
３.RSA.verify(m,s):se=h(m) mod Nであるかチェックする。
【００５７】
すぐに分かることは、sを有する者が、h(m)のe番目のルートの知識の証明をすることにより、sの知識を証明できることである。
【００５８】
図３は、本発明の好ましい実施形態によるsigncryptionシステム１００を示す。システム１００は、送信器１１０と受信器１２０とを有し、各々は、他の装置と通信するように構成された少なくとも１つのインタフェースユニット１１１、１２１と、少なくとも１つのプロセッサ（「プロセッサ」）１１２、１２２と、データを記憶するように構成された、アキュムレータや中間計算結果などの少なくとも１つのメモリ１１３、１２３とを有する。送信器１１０のプロセッサ１１２は、本発明の方法の実施形態により平文をsigncryptするように構成され、受信器１２０のプロセッサ１２２は、本発明の方法の実施形態によりsigncryptionを復号し検証するように構成されている。ＣＤ−ＲＯＭやＤＶＤなどの第１のコンピュータプログラム製品１１４は、送信器１１０のプロセッサ１１２により実行されたとき、本発明のいずれかの実施形態による平文のsigncryptionを実行する命令を記憶している。ＣＤ−ＲＯＭやＤＶＤなどの第２のコンピュータプログラム製品１２４は、送信器１２０のプロセッサ１２２により実行されたとき、本発明のいずれかの実施形態によりsigncryptionを復号し検証する命令を記憶している。
言うまでもなく、本signcryption方法は、従来のsigncryption方法と比較すると、性能がよく、特にverifiabilityに関する性能がよく、それと同時に高いセキュリティを提供する。
【００５９】
この改善は、この構成ではＥｔＳとＳｔＥのメリットを組み合わせつつ、両者の欠点を回避していることによる。
【００６０】
Verifiability
本発明の方法を用いて取得したsigncryption(e, c, e_d)の正当性を証明するには、送信器は：
１.eの復号に関する知識を提供し、
２.(c,e_d)の復号に関する知識と、この復号がcとeの連結の正しい署名であることを証明しなければならない。
【００６１】
両方の証明は、用いる暗号化方式が「クラスＥ」に属し、用いる署名方式が「クラスＳ」に属するとき、効率的に実行できる。これらは両方とも、上記の証明プロトコルとともに、[Laila El Aimani著「On Generic Constructions
of Designated Confirmer Signatures」（INDOCRYPT 2009:
343-362）]に説明されている。
【００６２】
ＳｔＥパラダイムでは、（メッセージmの）signcryptionは、(c,e)の形式であり、送信器は、復号(c,e)の知識と、この復号の第１部分がcと復号の残り部分（すなわち、m）との連結の正しい署名であることを証明する必要がある。これは理論的観点からは可能であるが、これを実現する効率的な方法は現在のところ知られていない。受信器のプロトコル、すなわち確認／拒絶プロトコルにも同じことが当てはまる。
【００６３】
よりよいプライバシ
本方法のsigncryptionは２つの暗号文を有し、攻撃者は暗号化されていないデジタル署名を有していない。これにより２つの方法でプライバシが向上する。第１に、ＥｔＳパラダイムに反して、indistinguishability性に影響せずに、「安価な」セキュリティ要件で、基礎となる署名方式を用いることができる。第２に、（ＥｔＳではsigncryptionに含まれるデジタル署名が正当か否か暗号文で誰でもチェックできるのに反して、）（第２の暗号化方式が匿名である場合、）signcryptionの送信者がsigncryptionに係わったか否かチェックできない。
【００６４】
明細書、特許請求の範囲、及び図面に開示した各特徴は、独立に設けることもできるし、適切に組み合わせて設けることもできる。ハードウェアで実施されると説明した機能はソフトウェアでも実施できるし、その逆の場合もある。特許請求の範囲に示す参照符号は例示であり、請求項の範囲を限定するものではない。
【特許請求の範囲】
【請求項１】
装置により平文mをsigncryptする方法であって、前記装置において、
第１の暗号化アルゴリズムと受信者の第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得するステップと、
乱数ｒと、カプセル化アルゴリズムと、前記受信者の第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成するステップと、
送信者の秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成するステップと、
前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得するステップと、
前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成するステップと、
前記signcryptionを出力するステップと、を有する方法。
【請求項２】
第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明するステップをさらに有する、請求項１に記載の方法。
【請求項３】
受信した、平文mのsigncryptionを装置によりunsigncryptする方法であって、前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含み、前記方法は前記装置において、
第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、signcryptionの受信者の第１の公開鍵に対応する前記受信者の第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号するステップと、
逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、前記受信者の第２の公開鍵Kpkに対応する前記受信者の第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出すステップと、
第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復するステップと、
検証アルゴリズムと、前記署名の生成に用いられた前記送信者の秘密署名鍵Sskに対応する、前記signcryptionの送信者の公開署名鍵Spkとを用いて、前記署名sが正しいか検証するステップと、を有する方法。
【請求項４】
前記平文mと前記暗号文eの復号と、前記第２の暗号文e_dの復号とが等しいまたは等しくないとの知識を、及び前記復号が前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であることを証明するステップをさらに有する、請求項３に記載の方法。
【請求項５】
平文mをsigncryptするsigncryption装置であって、
第１の暗号化アルゴリズムと受信者の第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得する手段と、
乱数ｒと、カプセル化アルゴリズムと、前記受信者の第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成する手段と、
送信者の秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成する手段と、
前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得する手段と、
前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成する手段と、
前記signcryptionを出力する手段と、を有するsigncryption装置。
【請求項６】
第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する手段をさらに有する、請求項５に記載のsigncryption装置。
【請求項７】
受信した、平文mのsigncryptionをunsigncryptするsigncryption検証装置装置であって、前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含み、前記signcryption検証装置は、
第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、signcryptionの受信者の第１の公開鍵に対応する前記受信者の第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号する手段と、
逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、前記受信者の第２の公開鍵Kpkに対応する前記受信者の第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出す手段と、
第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復する手段と、
検証アルゴリズムと、前記署名の生成に用いられた前記送信者の秘密署名鍵Sskに対応する、前記signcryptionの送信者の公開署名鍵Spkとを用いて、前記署名sが正しいか検証する手段と、を有するsigncryption検証装置装置。
【請求項８】
前記平文mの復号と前記暗号文eとが等しいまたは等しくないとの知識と、署名sが前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であるかどうかとを証明する手段をさらに有する、請求項７に記載のsigncryption検証装置。
【請求項９】
プロセッサにより実行されたとき、請求項１または２いずれか一項に記載の方法を実行する命令を記憶した記憶媒体。
【請求項１０】
プロセッサにより実行されたとき、請求項３または４いずれか一項に記載の方法を実行する命令を記憶した記憶媒体。
【請求項１】
装置により平文mをsigncryptする方法であって、前記装置において、
第１の暗号化アルゴリズムと受信者の第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得するステップと、
乱数ｒと、カプセル化アルゴリズムと、前記受信者の第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成するステップと、
送信者の秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成するステップと、
前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得するステップと、
前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成するステップと、
前記signcryptionを出力するステップと、を有する方法。
【請求項２】
第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明するステップをさらに有する、請求項１に記載の方法。
【請求項３】
受信した、平文mのsigncryptionを装置によりunsigncryptする方法であって、前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含み、前記方法は前記装置において、
第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、signcryptionの受信者の第１の公開鍵に対応する前記受信者の第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号するステップと、
逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、前記受信者の第２の公開鍵Kpkに対応する前記受信者の第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出すステップと、
第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復するステップと、
検証アルゴリズムと、前記署名の生成に用いられた前記送信者の秘密署名鍵Sskに対応する、前記signcryptionの送信者の公開署名鍵Spkとを用いて、前記署名sが正しいか検証するステップと、を有する方法。
【請求項４】
前記平文mと前記暗号文eの復号と、前記第２の暗号文e_dの復号とが等しいまたは等しくないとの知識を、及び前記復号が前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であることを証明するステップをさらに有する、請求項３に記載の方法。
【請求項５】
平文mをsigncryptするsigncryption装置であって、
第１の暗号化アルゴリズムと受信者の第１の公開鍵Epkを用いて、前記平文mを暗号化して、第１の暗号文eを取得する手段と、
乱数ｒと、カプセル化アルゴリズムと、前記受信者の第２の公開鍵Kpkとを用いて、セッション鍵kと、前記セッション鍵kのカプセル化cとを生成する手段と、
送信者の秘密署名鍵Sskを用いて、署名アルゴリズムで、前記第１の暗号文eと前記カプセル化cとの署名sを生成する手段と、
前記セッション鍵kを用いて、第２の暗号化アルゴリズムで、前記署名sを暗号化して、第２の暗号文e_dを取得する手段と、
前記第１の暗号文eと、前記カプセル化cと、前記第２の暗号文e_dから前記signcryptionを構成する手段と、
前記signcryptionを出力する手段と、を有するsigncryption装置。
【請求項６】
第１の暗号文eの復号の知識と、前記第２の暗号文e_dが前記カプセル化cの鍵を用いたカプセル化cの正しい署名と前記第１の暗号文eを暗号化していることを証明する手段をさらに有する、請求項５に記載のsigncryption装置。
【請求項７】
受信した、平文mのsigncryptionをunsigncryptするsigncryption検証装置装置であって、前記signcryptionは第１の暗号文eと、カプセル化cと、第２の暗号文e_dとを含み、前記signcryption検証装置は、
第１の復号アルゴリズムと、前記第１の暗号文eの暗号化に使われた、signcryptionの受信者の第１の公開鍵に対応する前記受信者の第１の秘密鍵Eskとを用いて、前記第１の暗号文eを復号する手段と、
逆カプセル化アルゴリズムと、セッション鍵kのカプセル化に用いられた、前記受信者の第２の公開鍵Kpkに対応する前記受信者の第２の秘密鍵Kskとを用いて、前記カプセル化cを逆カプセル化することにより、セッション鍵kを読み出す手段と、
第２の復号アルゴリズムと前記セッション鍵kとを用いて前記第２の暗号文e_dを復号することにより署名sを回復する手段と、
検証アルゴリズムと、前記署名の生成に用いられた前記送信者の秘密署名鍵Sskに対応する、前記signcryptionの送信者の公開署名鍵Spkとを用いて、前記署名sが正しいか検証する手段と、を有するsigncryption検証装置装置。
【請求項８】
前記平文mの復号と前記暗号文eとが等しいまたは等しくないとの知識と、署名sが前記第１の暗号文eと前記カプセル化cの正しいデジタル署名であるかどうかとを証明する手段をさらに有する、請求項７に記載のsigncryption検証装置。
【請求項９】
プロセッサにより実行されたとき、請求項１または２いずれか一項に記載の方法を実行する命令を記憶した記憶媒体。
【請求項１０】
プロセッサにより実行されたとき、請求項３または４いずれか一項に記載の方法を実行する命令を記憶した記憶媒体。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１３−４８４１７（Ｐ２０１３−４８４１７Ａ）
【公開日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−１８７４３２（Ｐ２０１２−１８７４３２）
【出願日】平成２４年８月２８日（２０１２．８．２８）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公開日】平成２５年３月７日（２０１３．３．７）
【国際特許分類】
【出願番号】特願２０１２−１８７４３２（Ｐ２０１２−１８７４３２）
【出願日】平成２４年８月２８日（２０１２．８．２８）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]