説明

メッセージ写像を用いてメッセージサイズを縮小する暗号化方式及び署名方式

【課題】本発明のいくつかの実施形態によれば、暗号化方式が短い暗号文を生成するように、暗号化前にメッセージを処理する。
【解決手段】メッセージ処理は、メッセージを、短い暗号文を生成する別のメッセージに写像する写像(610)と見なすことができる。写像は、少なくとも、(場合によってはエンコードされた)メッセージ(H(M))が、例えば短いメッセージの集合[0,h?]などの制限集合内にあれば、可逆である。本発明のいくつかの実施形態において、署名を短い署名に写像することによって、短い署名を提供する。写像(810)は、少なくとも、署名を生成するのに用いる元のメッセージ(H(M))が短ければ、可逆である。サインクリプション、集合署名、及びリング署名の出力も縮小される。

【発明の詳細な説明】
【技術分野】
【0001】
本出願は、2003年10月31日に出願された合衆国仮出願第60/515,982号の優先権を主張し、参照により本明細書に含む。
【0002】
本発明は、コンピュータネットワーク上の安全な通信を含む暗号化及び安全な通信に関する。本発明は、暗号化されたメッセージ、署名、その他の暗号情報のサイズを縮小するのに用いることができる。
【背景技術】
【0003】
暗号化されたメッセージ(「暗号文」)や署名等の暗号情報は、ネットワーク上で又は電子記憶媒体によりメールで受信者に送られる。暗号化を安全なものにするために、暗号文は、それに対応する暗号化されていない「プレーンテキスト」よりもかなり長くなることがある。同様に、署名は、該署名が生成されるメッセージよりもかなり長くなることがある。従って、望ましくはセキュリティを損なうことなく、暗号文や署名のサイズ(「帯域幅」)を縮小することが望ましい。
【0004】
図1乃至図5に、ネットワーク120によって相互接続されたコンピュータシステム110(図1)間における暗号文及び署名の生成及び転送を示している。図2は、暗号文cを得るために「プレーンテキスト」メッセージMに対してシステム110が実行する暗号化処理のフローチャートである。適切な暗号化の前に、メッセージMは、値H(M)にエンコードされる(ステップ210)。エンコードは、異なる暗号化演算における同じメッセージMに対して、異なるエンコードされたメッセージH(M)、よって異なる暗号文cを得ることができるように、いくつかのパディング及び/又はランダムビットをメッセージMに加えてもよい。これにより、攻撃者が同じ暗号化方式により得られる異なる暗号文を傍受した場合に、攻撃者が復号化方式を推測(「戻換」)するのは難しくなる。
【0005】
ステップ220で、エンコードされたメッセージH(M)を暗号化して、暗号文cを得る。ステップ230で、暗号文をネットワーク120を通じて他のシステム110に送信する。
【0006】
復号化処理(図3)は、暗号化の逆である。暗号文cは、受信者システム110によって受信され(ステップ304)、復号化されてエンコードされたメッセージH(M)が復元される(ステップ310)。エンコードされたメッセージは、デコードされ(ステップ320)、元のメッセージMが復元される。
【0007】
図2において、エンコードステップ210と暗号化220とは、別個のステップとして示している。なぜなら、エンコード方式210及びデコード320(図3)は、公開されることがあるが、復号化310や場合により暗号化220は、秘密情報(例えば秘密鍵)に依拠しているからである。また、ステップ210と220との組み合わせを示すのに「暗号化」という表現を用いるのは適切であり、ステップ310と320との組み合わせに「復号化」という表現を用いるのは適切であり、また/或いは、エンコードステップ210とデコード320を省略すると言っても適切である。
【0008】
図4に、システム110が実行する署名生成を示す。ステップ410で、メッセージMをH(M)にエンコードし、ステップ420で、エンコードされたメッセージを処理して(署名して)、署名s(M)を得る。署名s(M)をネットワーク120を通じて受信者システム110に送信する(ステップ430)。受信者システム110は、図5に示すように署名を検証する。ステップ504で署名を受信し、ステップ510で処理して、エンコードされたメッセージH(M)を復元する。エンコードされたメッセージをデコードして(ステップ520)、元のメッセージMを取得し、あるテストを行って該メッセージMが確かに署名されたメッセージであるかどうか検証する。例えば、元のメッセージを別の送信で受信者システム110に提供して、ステップ520で復元したメッセージと比較することができる。いくつかの実施形態においては、メッセージはデコードせず、メッセージを復元することなく検証を実行することができる。
【0009】
図4及び図5において、エンコードステップ410とステップ520とのデコードは、別個の動作として示しているが、ステップ410と420との組み合わせに「署名」という表現を用いるのも適切であり、ステップ510と520との組み合わせに「検証」という表現を用いるのも適切であり、また/或いは、エンコードステップ410とステップ520のデコード部分を省略すると言っても適切である。
【0010】
公開鍵暗号化方式において、鍵所有者(システム110の1つのユーザ)は、2つの鍵、公開鍵(他者にも広く配信してもよい)と秘密鍵とを所有する。暗号化されたメッセージを鍵所有者に送信するために、送信者(別のシステム110のユーザ)は、図2のステップ220で、鍵所有者の公開鍵を用いてメッセージを暗号化し、暗号文を鍵所有者に送信する。エンコード方式及びデコード方式(図2及び図3のステップ210、320)は、公開されていてもよい。鍵所有者は、ステップ320でその秘密鍵を用いて、暗号文を復号化する。暗号化方式が安全であるために、秘密鍵を所有しない者が送信された暗号文を復号化することは不可能でなければならない。
【0011】
公開鍵署名方式において、鍵所有者は、同様に公開鍵及び秘密鍵を使用する。ステップ420(図4)で、鍵所有者は、特定の方法でメッセージに秘密鍵を適用することによって、該メッセージに署名する。検証者は、(図5のステップ510で)鍵所有者の公開鍵を署名に適用し、(ステップ520で)ある特定の条件が満たされているかをチェックすることによって、鍵所有者がメッセージに署名したことを確認してもよい。署名方式が安全であるために、鍵所有者の秘密鍵を所有しない者が、鍵所有者が実際に署名したことがないメッセージについて、鍵所有者の署名を偽造することは不可能でなければならない。
【0012】
公開鍵サインクリプション(public−key signcryption)方式において、望ましくは、送信者が署名と暗号文を別々に送信した場合よりも、サインクリプション送信(signcryption transmission)が少ない帯域幅を消費するように、送信者(システム110のユーザ)は、送信者の秘密鍵でメッセージMをエンコードし署名し(図4のステップ420参照)、次に受信者の公開鍵で、署名されたメッセージs(M)を暗号化する(図2のステップ220参照)。(別のシステム110の)受信者は、その秘密鍵でサインクリプションを復号化し、送信者の公開鍵で送信者の署名を検証する。
【0013】
公開鍵集合署名(public−key aggregate signature)方式において、それぞれ公開鍵{PK,…,PK}を有する署名者の集合{S,…,S}は、彼らの集合署名−すなわち、各署名者SがメッセージMに署名したことを検証するのに必要なビットストリング−が「短」かく、望ましくは、各署名者がそれぞれのメッセージに別々に署名した場合よりも少ない帯域幅を消費するように、それぞれのメッセージ{M,…,M}に署名する。集合署名は、公開鍵{PK,…,PK}を用いて検証される。
【0014】
公開鍵リング署名(public−key ring signature)方式において、署名者Sは、Sが一員である署名者の集合{S,…,S}(すなわちS∈{S,…,S})を任意に選ぶことができ、検証者は誰であるかを確定できないが、{S,…,S}の少なくとも1人の署名者がメッセージに署名したことを検証者に確信させる、メッセージに対する「リング署名」を生成する。従って、署名者Sは、可能性のある署名者の「リング」内で限定的な匿名性を有する。検証者は、公開鍵{PK,…,PK}を用いてリング署名を検証する。通常、可能性のある署名者がz人のリング署名は、z個の別々の署名と同じ長さであり、従って、基礎となる署名方式の帯域幅効率が良いことは不可欠である。
【0015】
1976年に、Diffie及びHellmanは、公開鍵暗号化及び署名方式という概念を発表したが、具体的な実例を見つけることはできなかった。Rivest、Shamir及びAdlemanは、A Method for Obtaining Digital Signatures and Public−Key Cryptosystems(Communications of the ACM,v.21 n.2,p.120−126,1978)という論文で、最初の公開鍵暗号化及び署名方式(今では「RSA」方式として知られている)を提案したが、参照により本明細書に含まれる。
【0016】
概略を言えば、RSA暗号化方式は、以下のとおりである。鍵所有者は、合成(すなわち非素数の)整数法N=pqを生成する。ここで、p及びqは、大きい素数である(例えば512ビット)。鍵所有者は、また、φ(N)=(p−1)*(q−1)を計算する。最後に、鍵所有者は、ed≡1(mod φ(N))となるように、共に1よりも大きい整数e及びdを計算する。鍵所有者は、その公開鍵として(N,e)を公開し、pとqとdを秘密にしておく。
【0017】
メッセージMを暗号化するために、送信者は、以下の「リスト1」に列挙した演算を実行する。
【0018】
リスト1:RSA暗号化
Mを[0,N−1]の整数mとして表現し、次に、暗号文c≡m(mod N)を設定する。
【0019】
リスト1の終了。
【0020】
暗号文を復号化するために、鍵所有者は、以下の演算を実行する。
【0021】
リスト2:RSA復号化
≡med≡m(mod N)を計算する。
【0022】
リスト2の終了
暗号文は[1,N]の数であり、およそlogNビットの長さであることに注意されたい。この復号化は、メッセージエンコードを仮定していないが、メッセージエンコードを使用することもできる。
【0023】
RSA署名方式について、鍵所有者は、その鍵をRSA暗号化におけるように生成する。適切にエンコードされたメッセージm∈[1,N]に署名するために、鍵所有者は、以下の演算を実行する。
【0024】
リスト3:RSA署名
s=m(mod N)を計算する。
【0025】
リスト3の終了
検証者は、鍵所有者の公開鍵を用いて、以下の演算を実行することにより署名sを確認することができる。
【0026】
リスト4:RSA署名
≡m(mod N)かどうかチェックする。
【0027】
リスト4の終了
この場合も、署名は、およそlogNビットの長さである。
【0028】
Rabinは、Digitalized Signatures and Public−Key Functions as Intractable as Factorization (MIT/LCS/TR−212,MIT Laboratory for Computer Science,Massachusetts Institute of Technology,USA 1979)という論文で、少し違った暗号化方式及び署名方式を提案したが、参照により本明細書に含まれる。この方式において、鍵所有者は、RSAにおけるように法Nを生成し、その公開鍵を(N,e)に設定する。適切にエンコードされたメッセージmに対し、暗号文はc=m(mod N)である点で、暗号化もまたRSAと同じである。暗号文は、およそlogNビットである。しかしながら、Rabinの方式では、特定の値e=2を使用する。これには2つの理由がある。第1に、e=2に設定すると、非常に高速な暗号化及び署名検証が可能になる。第2に、法Nを因数分解するのは難しいと仮定して、e=2に設定すると、その結果生じる方式は解読するのが難しいことを証明することができる。(適切なエンコードを用いて)因数分解をRabinの方式に変形することは当技術において公知である。
【0029】
以下、OAEP+メッセージエンコードを含むRabin暗号化方式について説明する。基礎となる暗号化方式が解読しにくいものと仮定して、OAEP+エンコードは、ランダムオラクルモデルにおいて、適応的選択暗号文攻撃に対して証明可能なセキュリティをもたらす。
【0030】
OAEP+エンコード方式では、(図2のステップ210で)以下の式(1)によって定義される3つのハッシュ関数を用いる。
【数1】

【0031】
ここで、m,k,kは、所定の正の整数のセキュリティパラメータである。iごとに、式{0,1}は、長さiの全ての0と1のストリング(「ビットストリング」)の集合を示す。同式は、また、i以下の長さの全てのビットストリングの集合を示す。ストリング長がiよりも短い場合、該ストリングは左側に0を付け加えて長さiにすることができる。式(1)のこのH関数は、中間値に使用して、メッセージエンコードを計算するためのものであり、図2のステップ210に示すエンコードされたメッセージH(M)と混同すべきではない。高いセキュリティを得るために、数量
【数2】

【0032】
と、
【数3】

【0033】
は、ごくわずかであるべきだが、正の整数であればうまくいく。n=m+k+kであれば、望ましくは2<N<2+2n−1となるようにNを選択する。メッセージM∈{0,1}を暗号化するために、送信者は、以下の演算を実行する。
【0034】
リスト5:Rabin‐OAEP暗号化手順
(ステップ210(図2)は、以下のステップ1乃至3に対応する。)
1.任意の
【数4】

【0035】
を選択する。
【0036】
2.
【数5】

【0037】
及び
【数6】

【0038】
を設定する。ここで、二重縦棒の記号“‖”は、ストリング連結を示す。
【0039】
3.nビットストリングである、x←s‖tを設定する(xは、図2のステップ210の最終的にエンコードされた値H(M)に対応する)。
【0040】
4.ステップ220:暗号文c←x(mod N)を計算する。ここで、ビットストリングxは、1つの数として解釈する。x=x…xn−1に関し、該数は、x+x*2+…+Xn−1*2n−1である。
【0041】
リスト5の終了。
【0042】
復号化のために、受信者は、以下の演算を実行する。
【0043】
リスト6:Rabin−OAEP復号化手順
1.ステップ310(図3):Nを法とするcのモジュラ平方根を計算する(図3のステップ310)。お分かりのように、Nは、2つの素数の積であるので、cは、4つのモジュラ平方根x,x,x,xまで持つことができ、ここでx=−xであり、x=−xである。x及びxの少なくとも1つと、x及びxの少なくとも1つは、n以下のビットを有する。一般性を失うことなく、x及びxのそれぞれは、n以下のビットを有するものとする。
【0044】
2.ステップ320:受信者は、
【数7】

【0045】
と、
【数8】

【0046】
について、各候補x(i=1,3)を、s‖tに構文解析し、次に、
【数9】

【0047】
について、sを、
【数10】

【0048】
に構文解析する。i=1,3ごとに、受信者は、
【数11】

【0049】
及び
【数12】

【0050】
を計算し、
【数13】

【0051】
かどうかテストする。条件が満たされる唯一のiが存在する場合、受信者は、正確なプレーンテキストとしてMを出力し、そうでなければ(かかるiがない場合や、i=1とi=3の両方に対し条件が満たされる場合)、受信者は、復号化の失敗を示す。
【0052】
リスト6の終了。
【0053】
以下、全領域ハッシュを用いたメッセージ復元によるRabin署名方式について説明する。「全領域ハッシュ」という表現は、ハッシュ関数(1がそれぞれ最大値m,k,kと同じ長さの値を持つことができることを意味する。エンコードや、さらにはモジュラ平方根の計算に対し様々なアプローチが可能である。以下の説明は、可能なアプローチの1つにすぎない。上記のRabin暗号化に関する関連パラメータを、p≡3(mod 8)及びq≡7(mod 8)という付加的な制約で定義すると、署名者は、以下の演算を実行する。
【0054】
リスト7:Rabin−OAEP署名手順
エンコードステップ410(図4)は、以下のステップ1乃至2に対応する。
【0055】
1.任意の
【数14】

【0056】
を選択する。
【0057】
2.
【数15】

【0058】
及び
【数16】

【0059】
を設定する。
【0060】
3.nビットの整数である、y←s′‖s″‖tを設定する。値yは、図4のH(M)に対応する。署名ステップ420(図4)は、以下のステップ4乃至11に対応する。
【0061】
4.u←y(q+1)/4(mod q)を計算する。
【0062】
5.
【数17】

【0063】
であれば、e←1に設定し、そうでなければ、e←−1に設定する。
【0064】
6.u←(ey)(p+1)/4(mod p)を計算する。
【0065】
7.
【数18】

【0066】
であれば、f←1に設定し、そうでなければ、f←2に設定する。
【0067】
8.v←f(3q−5)/4(mod q)とv←f(3p−5)/4(mod p)を計算する。
【0068】
9.w←v+q(qp−2(v−v)mod p)を計算する。
【0069】
10.2w<Nであれば、x←wに設定し、そうでなければ、x←N−wに設定する。数xは、ey/f(mod N)の平方根である。
【0070】
11.署名(e,f,r,x)を出力する。
【0071】
リスト7の終了。
【0072】
(3q−5)/4(mod q)、2(3p−5)/4(mod p)、及びqp−2(mod p)の値は、事前に計算できる。従って、リスト7のステップ8及び9は、署名時間にほとんど何も付加しない。署名は、以下のように検証される。
【0073】
リスト8:Rabin−OAEP検証手順
1.ステップ510(図5):ytmp←e(mod N)を計算する。
【0074】
2.ステップ520:ytmpがnビットであることを確認し、ytmpを、
【数19】

【0075】
に構文解析し、
【数20】

【0076】
及び、
【数21】

【0077】
を計算し、
【数22】

【0078】
であることを確認する。
【0079】
リスト8の終了。
【0080】
メッセージM=Mtmpは、検証処理中に復元されることに注意されたい。
【0081】
リスト5乃至8の暗号化方式及び署名方式は、因数分解と同じくらい証明可能に安全である(本説明ではプルーフは省略されているが)。これらの方式は、計算上非常に効率的ではあるが、暗号文と署名のビット長は、およそlogNであることにさらに注目されたい。最新の因数分解方式に対して安全であるために、Nは、少なくとも1024ビットであるべきである。
【0082】
Rabin署名を用いるリング署名方式が、R.L.Rivest、A.Shamir及びT.Tauman著、How to Leak a Secret(Proc.of Asiacrypt 2001,552−565頁)という論文で提案されており、参照により本明細書に含まれる。概略を言えば、公開法{N,…,N}を有する署名者{S,…,S}に対し、この論文は、以下のようなリング署名を提案する。
【0083】
リスト9:リング署名
リング署名は、(x′,…,x′)であり、式
【数23】

【0084】
を満たす。ここで、
【数24】

【0085】
であり、v及びwは、所定のビットストリングであり、Cは、「結合関数」である。
【0086】
リスト9の終了。
【0087】
この論文は、以下の結合関数を推奨している。
【数25】

【0088】
ここで、Eは、鍵kを用いた対称暗号化方式である。(対称暗号化方式は、暗号化と復号化の両方に同じ鍵を用いる。メッセージMは、暗号文E(M)に暗号化される)。
【0089】
彼らの方式は、また、法Nが異なるビット長を有することを避けるうまいやり方を用いる。gが、関数
【数26】

【0090】
を示すものとする。
【数27】

【0091】
に設定する代わりに、定義域{0,1}に関して、yを定義し、ここで、2は、どの法よりもはるかに大きい。具体的に、
リスト10:リング署名のための2乗
x′=q+r∈[0,2−1]に関し、(q+1)N≦2であれば、y=q+g(r)であり、
そうでなければ、y=x′である。
【0092】
リスト10の終了。
【0093】
ここで、qは、Nでx′を整数除法した商であり、rは余りである。bが十分に大きい限り、(q+1)N>2である全てのyの割合は無視できるので、写像x→yは、Nを法とする2乗とほとんど区別が付かない作用をする。
【0094】
これらの考慮すべき事柄を念頭において、リング署名は、以下のように生成される(Sは、「真の」署名者であるとする)。
【0095】
リスト11:リング署名
1.k=H(M)を計算する。ここで、Mは、署名するメッセージであり、Hは、ハッシュ関数である。
【0096】
2.任意のv∈{0,1}を選択する。
【0097】
3.j≠iごとに、
3A.j≠iに対し任意のx′∈{0,1}を選択する。
【0098】
3B.リスト10におけるようにyを計算する。
【0099】
4.
【数28】

【0100】
となるように、yを計算する。
【0101】
5.Nについての秘密の知識を用いて、リスト10の写像によってx′がyに写像されるようにx′を計算する。
【0102】
6.リング署名(x′,…,x′,v)を出力する。
【0103】
リスト11の終了。
【0104】
ステップ4に関して、
【数29】

【0105】
であることに注目されたい。
【0106】
次に、
【数30】

【0107】
であることに注目されたい。
【0108】
一般的に、
【数31】

【0109】
であり、リング署名者は、この式を用いて、yの値からyを計算する(j≠iである)。x′を計算するために、リング署名者は、
【数32】

【0110】
を計算する。これは、基本的には、単にモジュラ平方根の計算である。yのいくつかの値は、実際にはそれらの約4分の3は、モジュラ平方根を持たない。この場合、yがNを法とする平方剰余となるまで、ステップ3を再び実行しなければならない。
【0111】
リスト12:リング署名検証。
【0112】
1.k=H(M)を計算する。全てのjについて、リスト10の写像を逆にすることによって、x′からyのそれぞれの値を計算する。
【0113】
2.
【数33】

【0114】
であることを確認する。
【0115】
リスト12の終了。
【0116】
上述の暗号化方式及び署名方式において、暗号文と署名は、logN≧1024ビット長である。復号化や署名検証は、完全な暗号文や署名を必要とするので、これらのように長い暗号文や署名は、特に、損失をこうむりやすいチャネル上で問題を生じることがある。また、長い暗号文や署名は、暗号文や署名が複数のパケットにわたって分割されるパケットフラグメンテーションに関する問題に遭遇する可能性が高い。また、短い署名や暗号文は、送信するのに電力効率がよい。K.Barr及びK.Asanovic著、Energy Aware Lossless Data Compression(Proc.of MobiSys 2003)によれば、単一ビットの無線送信は、32ビットの計算の1000倍以上のエネルギーがかかることがある。バッテリー電源式コンピュータシステムにおいては、無線送信に必要なエネルギー消費は深刻なネックになることがある。また、信号干渉は、所定の領域においてバッテリー電源式システムによって無線送信できるデータ量に物理的制限を設ける。
【0117】
セキュリティの観点から、Rabinの方式は、因数分解と同じくらい解読するのが難しいことが証明できるという非常に望ましい性質を有し、これは可能であれば保持すべき性質である。従って、logNビット法を因数分解するのは難解であることを仮定した、しかし、暗号文は、logNビットよりもかなり短い、証明可能に安全である暗号化方式が必要である。また、署名がlogNビットよりもかなり短い証明可能に安全な署名方式も必要である。さらに、署名方式は、望ましくは、Rabin署名のメッセージ復元特性を保持すべきである。
【0118】
また、因数分解に基づくが、Rabinの暗号化及び署名方式の拡張を用いる方式よりも帯域幅効率が良い、例えば、サインクリプション、集合署名、リング署名などの先進の暗号化方式も必要である。
【発明の開示】
【発明が解決しようとする課題】
【0119】
この項では、本発明のいくつかの特徴を要約する。他の特徴は、後の項で説明する。本発明は、添付の請求項により定義され、該請求項は、参照によりこの項に含まれる。
【課題を解決するための手段】
【0120】
本発明のいくつかの実施形態によれば、暗号化の前にメッセージを処理して、暗号文を短くする。典型的な処理を、図6のステップ610に示す。ステップ210(エンコード)、220(暗号化)及び230(送信)は、図2のようであることがある。特に、暗号化方式220は、ある所定長に等しい長さ(例えば、N−1以下の数の長さ、ここで、Nは、Rabin暗号化の場合の法である)の暗号文や、より短い暗号文や、場合によっては、より長い暗号文を提供することができる。ステップ210(エンコード)の後、写像ステップ610を実行して、エンコードされたメッセージH(M)を所定の集合Bの中間数bに写像する。写像はπと示す。集合Bは、暗号化方式220がそれについて短い暗号文を生成するあるメッセージの集合である。
【0121】
いくつかの実施形態では、ステップ220でRabin暗号化方式を使用する、すなわちc=b(mod N)。いくつかの実施形態において、B=BN,Q={x∈[1,N]:x(mod N)∈Q}であり、ここで、Qは、Nを法とする全ての整数の真部分集合である。いくつかの実施形態では、Qは、h′−h<Nとなるような、ある整数h,h′に関する部分値域[h,h′]である。これらのQに関し、集合BN,Qは、BN,h,h′と示す。従って、BN,h,h′={x∈[1,N]:h≦x(mod N)≦h′}。
【0122】
Nを法とする全ての整数の集合Zの数は、公知の方法で円の上の点として示すことができる。部分値域[h,h′]は、集合{h,h+1,…h′}か、集合{h′,h′+1,…h}かである。曖昧さを避けるために、本明細書中、異なる意味が明白に記載されているか、文脈から明らかである場合を除いて、[h,h′]は、2つの部分値域の内、一番小さいものであるとする。特に、h′は、hよりも小さい数によって示すことがある。例えば、h=N−1=−1(mod N)で、h′=1であるならば、[h,h′]={N−1,N,1}={N−1,0,1}である。
【0123】
h′−hが与えられると、数h,h′にとってよい選択は、h=0又は−h=h′である。なぜなら、幅h′−hの部分値域の内、0に近い部分値域は、最も短いビット長の数を有するからである。
【0124】
いくつかの実施形態において、BN,QがBN,Q={x∈[0,N/2]:x(mod N)∈Q}か、BN,Q={x∈Z*:x(mod N)∈Q}によって置き換えられる場合、同様の結果が得られる。ここで、Z*は、Nを法として可逆である(すなわち、Nに対し公約数を持たない)全ての整数の集合x∈[0,N/2]である。Q=[h,h′]であれば、BN,Qは、BN,h,h′と示され、BN,Qは、BN,h,h′と示される。
【0125】
いくつかの実施形態において、h″<Nのある区間[0,h″]において、エンコードされたメッセージH(M)は、短いメッセージである。また、写像πをステップ610でプレーンテキストMに適用してMをbに写像することで、エンコードステップ210(図6)は省略することができる。プレーンテキストMは、[0,h″]に含まれることがある。用語に関して、写像ステップ210が存在しても、プレーンテキストMをある数b∈Bに変換するステップ210、610の組み合わせを述べるのに「エンコード」という表現を用いることができる。
【0126】
復号化(図7)は、暗号化処理の逆となることがある。(図3のように)短い暗号文cは、ステップ304で受信者が受信し、ステップ310で復号化して中間メッセージb∈Bを復元する。復号化方式310では、ある所定長に等しい長さ(例えば、N−1以下の数の長さ、ここでNはRabin復号化の場合の法である)の暗号文や、より短い暗号文や、場合によってはより長い暗号文を復号化することができる。ステップ710で逆写像π−1を適用して、bをH(M)に写像する。次に、H(M)をデコードして(ステップ320)プレーンテキストMを復元する。
【0127】
本発明のいくつかの実施形態において、短い署名が提供される。図8に、1つの署名方式の実施形態を示す。図4のように、ステップ410で、メッセージMをH(M)にエンコードする。いくつかの実施形態において、メッセージH(M)は、上述の部分値域[h,h′]にある。ステップ420で、署名方式を適用してメッセージに署名し、中間署名bを得る。この署名方式(例えばモジュラ平方根計算)は、所定の長さ以下の長さや、場合によっては、より長い全てのメッセージH(M)に適応する。ステップ410、420は、先行技術におけるようなものであっても良いし、そうでなくてもよい。いくつかの実施形態は、OAEP+エンコードのRabin署名を用いる。しかしながら、中間署名bは、上述のタイプの集合Bにある。いくつかの実施形態において、これは、メッセージMを、エンコードH(M)がBに署名を有するメッセージの集合に限定することによって得られる。いくつかの実施形態において、エンコードされたメッセージH(M)は、短く(ある所定の長さよりも短い)、例えば、あるh″<Nに関してH(M)∈[0,h″]であり、署名方式420では、短いメッセージを集合Bに写像する。中間署名bは、長いビットストリングであってもよいことに注目されたい。
【0128】
ステップ810で、写像θを適用して中間署名bを、短い署名sに写像する。ステップ430で、署名sを受信者に送信する。
【0129】
署名検証を、図9に示す。ステップ504で、短い署名sは、受信者コンピュータシステム110で受信される。ステップ910で、逆写像θ−1を適用して、中間署名bを復元する。ステップ510、520で、検証を実行する。例えば、ステップ510で、中間署名を処理してH(M)を復元することができる。ステップ520で、図5のステップ520におけるように検証を実行することができる。ステップ510、520の方法は、ある所定長に等しい長さ(例えば数N−1の長さ、ここで、Nは、法である)のメッセージH(M)の署名や、より短いメッセージH(M)の署名や、場合によっては、より長いメッセージH(M)の署名を検証するのに適している。
【0130】
いくつかの実施形態において、集合Bは、全てのメッセージの集合よりも濃度が低いが、Bの個々のメッセージは、エンコードされたメッセージH(M)よりも長いことがある。このため、写像π−1とθは、一般的に圧縮と呼び、写像πとθ−1は、復元と呼ぶ。本発明は、実際の圧縮又は復元が起こる場合、すなわち、写像π−1又はθが各数をそれより短い数に写像するか、写像π又はθ−1が各数をそれより長い数に写像する実施形態に限定されない。
【0131】
いくつかの公開鍵暗号化及び署名の実施形態において、暗号文と署名のサイズは、通常のlogNビットではなく、最大でも約2/3logNビットである。同時に、圧縮及び署名方式のセキュリティは、かなり大きい(logN)ビットの数Nを因数分解することに基づく。
【0132】
いくつかの実施形態において、h′−hが、約8*N2/3以上である時、小さい定数cに関して、写像θは、BN,h,h′内の数を長さc+log(h′−h)のビットストリングに写像する。いくつかの実施形態では、c≦3である。いくつかの実施形態において、写像πは長さ−c+log(h′−h)のビットストリングを、BN,h,h′内の数に写像する。ここで、cは、小さい定数である。いくつかの実施形態において、c=log5≦3である。いくつかの公開鍵暗号化及び署名の実施形態において、両写像は、公開されている。すなわち、写像と、それらの逆は、秘密情報を必要とすることなく効率的に計算することができる。
【0133】
いくつかの実施形態において、帯域幅縮小サインクリプション方式を提供する。送信者は、送信者の公開鍵Nと受信者の公開鍵Nに関連して用いられる、例えば、θやθなどの、2つのバージョンのθ写像を使用する。NとNは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、サインクリプションは、構造(c+log(h′−h))ビット長である。このサインクリプションは、同時に、受信者が解読できるようにメッセージを暗号化し、メッセージに対する送信者の署名を含める。受信者は、送信者の公開鍵を用いて検証することができる。
【0134】
いくつかの実施形態において、帯域幅縮小集合署名方式を提供する。署名者{S,…,S}は、公開鍵{N,…,N}を有し、メッセージ{M,…,M}に順に署名する。これは、署名者Sが、Si−1からsi−1を受信した後にMの署名sを生成することを意味する。鍵Nは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、各si−1は、Bの要素の(θi−1によって)圧縮された表現であり、ここで、Bは、iに依存することもあればそうでないこともある。例えば、Bは、BN,h,h′であることもある。ここで、N、h及びh′は、iに依存することもあればそうでないこともあり、sは、基本的に[h,h′]の数のNを法とする圧縮平方根として計算される。その数は、si−1とMに依存する。
【0135】
いくつかの実施形態において、帯域幅縮小リング署名方式を提供する。いくつかの実施形態において、Rivest‐Shamir‐Taumanリング署名方式が、本発明の圧縮方式を、本発明の他の手法と組み合わせて用いて、上記リスト9の
【数34】

【0136】
の値を短くできるようにすることによって改良されている。
【0137】
本発明の他の特徴や利点について、以下に述べる。本発明は、添付の請求項によって定義される。
【発明を実施するための最良の形態】
【0138】
1.前置き
後の説明では、いくつかの数学的表記を用いるが、その多くを便宜上ここに集める。{0,1}*を全てのビットストリングの集合を示すものとし、{0,1}を長さnの全てのビットストリングの集合を示すものとする。後者の表現は、また、n以下の長さの全てのビットストリングの集合を示す。ストリング長が、nよりも小さい場合、該ストリングは、左側に0を付け加えることで長さnにすることができる。通常、Hは、暗号ハッシュ関数及び/又はエンコードされたメッセージを示す。例えば、SHA‐1やMD5など、様々な暗号ハッシュ関数が、当技術で公知である(例えば、RFC‐2104,Request for Comments,Networking Working Group,H.Krawczyk et al.,HMAC:Keyed‐Hashing for Message Authentication,1997年2月、参照により本明細書に含む、を参照)。ハッシュ関数が耐衝突性であること、すなわち、H(m)=H(m)となるようなm≠mを見つけるのが計算上難しいことが望ましい。
【0139】
実数rに関して、
【数35】

【0140】
は、rの天井、すなわち、r以上の最小の整数値を示す。同様に、
【数36】

【0141】
は、rの床、すなわち、r以下の最大の整数値を示す。最後に
【数37】

【0142】
は、rに最も近い整数を示す。記号‖は、連結を示す。
【0143】
本明細書中、Nは、整数法を示す。有効なセキュリティのために、Nは、因数分解が計算上難しいものであるべきである。実際には、Nを2つの大きい素数p及びq、例えば、各々512ビット、の積として生成することが多い。しかしながら、暗号文献に見られるように、d>1として、N=pqに設定すると、効率的利点があることが多い。本発明の方式では、Nは、任意の形式をとれる。しかしながら、後の説明では、便宜上、N=pqとする。
【0144】
「格子」は、基底ベクトルの集合の整数線形結合として生成することができる全てのベクトルの集合からなる。例えば、(a,b)及び(c,d)が二次元空間において2つの基底ベクトルである場合、それらによって生成される格子は、ベクトル{(ka+kc,kb+kd):k,k∈Z}の集合である。Zは、全ての整数の集合である。
【0145】
2.追加の前置き:BN,h,h′内の数の分布
Nを法とする平方剰余が一様に分布していたならば、BN,h,h′は、およそh′−h個の数を含むと予想される。差し当たりBN,h,h′が、h′−h個の数を含むとすれば、情報理論の観点から、
【数38】

【0146】
ビットを用いて、BN,h,h′内の各数を一意に示すことは可能である。しかしながら、BN,h,h′内の数は、ランダムに見えるように、区間[1,N/2]にわたって分散しており、従って、効率的に、つまり、計算の複雑性が小さい定数cに対し最大でO((logN))である方法を用いて、ある数の一意の表示を計算することができるかは少しも明らかではない。(文字cは、定数と暗号文の両方に用いるが、これら2つの使用は混同すべきでない)。
【0147】
N,h,h′の局所分布の解析
効率的に計算でき可逆であるBN,h,h′内の数の簡潔な表示を作成するために、BN,h,h′内の数がどのように[1,N/2]に分布しているかを理解するのが望ましい。この分布は、参照により本明細書に含まれる、B.Vallee著、Provably Fast Integer Factoring with Quasi‐Uniform Small Quadratic Residues(Proc.of STOC 1989,98‐106ページ)によって、因数分解問題(数Nの素因数を見つける問題)に関連して、−h=h′=4N2/3について研究されている。Valleeは、−h=h′=4N2/3について、BN,h,h′内の数の分布を解析した。彼女の観測を用いて、証明可能に低い計算の複雑性を有する(複雑性は、やはりまだ高くて、非常に大きい数(例えば、1024ビット)を因数分解することはできないが)因数分解方式が、B=BN,h,h′から「擬一様に」数を抜き出すサブルーチンを用いて、すなわち、ある定数cについて、所定の数が引き出される確率が、他の数が選択される確率のc倍以内であるようにして、開発された。
【0148】
Valleeは(本発明によって利用されるような)圧縮方式を開発しておらず、確かに、Valleeの因数分解方式の論考では、かかる圧縮方式は無意味であるようだが、ValleeのBN,h,h′の分布についての観測は有用である。Valleeの観測のいくつかを以下に列挙する。
【0149】
Farey数列:
オーダーkのFarey数列Fは、a=0を除いて、1≦a≦b≦k及びgcd(a,b)=1である、分数
【数39】

【0150】
の昇列
【数40】

【0151】
である。“gcd”の表現は、最大公約数を表す。
【0152】
Farey数列の性質は、以下の定理で表される。
【0153】
定理1.
において、
【数41】

【0154】

【数42】

【0155】
が連続していれば、bi+1−ai+1=1である。
【0156】
Farey数列に関する他の有用な定理は、以下のとおりである。
【0157】
定理2.
において、
【数43】

【0158】

【数44】

【0159】
が連続していれば、b+bi+1>Kである。
【0160】
Farey数列は、自然に、Farey被覆の概念につながる。
【0161】
Farey被覆:
区間[0,N/2]のオーダーkのFarey被覆は、開Farey区間I(a,b)の集合であり、ここでi=0,1,2,…であり、各区間I(a,b)は、中心
【数45】

【0162】
と、半径
【数46】

【0163】
とを有し、ここで、a=0を除いて、1≦a≦b≦k及びgcd(a,b)=1である。
【0164】
図10Aは、Farey被覆を示している。
【0165】
上記定理1及び2を用いて、[0,N/2]内の全ての実数が少なくとも1つの、多くて2つのFarey区間によって被覆されていることを容易に証明できる。
【0166】
後の論述は、また、(図10Bに示す)Farey分割を用いるが、Farey被覆と密接な関係がある。
【0167】
Farey分割:
区間[0,N/2]のオーダーkのFarey分割は、区間
【数47】

【0168】
の集合であり、ここで、i=0,1,2,…であり、a=a−1=b−1=0を除いて、1≦a≦b≦k、gcd(a,b)=1である。
【0169】
Farey分割区間は、左側で閉じているが(端点を含む)、右側で閉じており左側で開いていると定義することもできる。(ここで、区間は交わらず、0を被覆しないように定義されるが、これは必然ではない。)
区間J(a,b)は、N/2に隣接する小さい区間を除く[0,N/2]の全てを被覆する分割を形成し、図10BではJ(a,b)として示し、ここで、fは、a,bに対する最大のi添数である。従って、a=b=1である。af+1=bf+1=0と定義するならば、J(a,b)は、一般式(8)により定義できる。
【0170】
再び定理1及び2を用いることによって、I(a,b)がJ(a,b)を含むことを証明することができる。また、区間I(a,b)は、区間J(a,b)の2倍以内の幅である。
【0171】
Farey数列は、BN,h,h′内の整数の[0,N/2]内の分布に密接な関係がある。特に、Bの連続する要素間の空隙は、小さい分母bの有理数aN/2bに近い大きな変分がある。しかしながら、aN/2bを中心とするもっと広い値域を考えると、B要素の分布は「一様になる」、すなわち、該区間のB要素の数と、Bが一様に分布していた場合に予測される数との比率は、1に近づく。概略を言うと、固まりが無視できるようになるのに必要な区間幅は、bに反比例し、従って、上記で定義したFarey区間とBの要素の分布との関係である。
【0172】
Valleeは、以下の定理を証明した。
【0173】
定理3.
−h=h′=4N2/3と、
【数48】

【0174】
に関し、部分集合BN,h,h′とオーダーkのFarey被覆は、準独立である。
【0175】
準独立という用語は、以下のように定義される。部分集合XとZ(Zは、Nを法とする全ての整数の集合を示す)の被覆Y={Y}は、全てのjについて、集合XとYが、ある正の定数lとlに対し(l,l)独立である、すなわち
【数49】

【0176】
であれば、準独立である。Pは、集合Zについての一様確率測度である。h′=4N2/3であり、Fareyオーダーk=1/4N1/3であるBN,h,h′に関し、Valleeは、
【数50】

【0177】
と、l=4が満たされることを証明する。
【0178】
この定理を証明するためのValleeの方法は、ある意味、建設的である。Bの要素がFarey区間内で、すなわち「局所的に」どのように構成されているかを詳しく見ることによって、Valleeは、区間のB要素の数について上限及び下限を与える、これらの要素の概略計数を提供することができる。この概略計数を用いて、Valleeは、「擬一様に」Farey区間に存在するBから要素を選択する方法を提供する。形式上、一様確率Pと、Zの部分集合X内の値を有する有限集合Uに対し定義される抜き出し方式Cは、全てのx∈Xに関し、
【数51】

【0179】
であれば、(l,l)一様(又は擬一様)であるといわれる。Bの要素が、擬一様にFarey区間中に分布しているとすれば、これは直接「擬一様に」[1,N]内のBから要素を選択する「大域的な」方式につながる。
【0180】
擬一様な分布で、Farey区間I(a,b)にあるBN,h,h′内の数を選択したいものとする。
【数52】

【0181】
Valleeは、h′=4N2/3としてBN,h,h′∩I(a,b)に存在する整数
【数53】

【0182】
を、これらの整数を2つの特定の放物線の間にある二次元の格子における点に関連付けることによって簡潔に特徴付けている。図11において、区間{u:x=x+u∈I(a,b)}は、1104で示し、2つの放物線は、1110、1120で示す。
【0183】
xが、BN,h,h′内にあるならば、
【数54】

【0184】
である。さて、L(x)をベクトル(1,2x)及び(0,N)によって生成する格子とする。すると、(u,w)∈L(x)及び、
【数55】

【0185】
となるようなwが存在するとき、x=x+uは、まさにBN,h,h′に存在する。
【0186】
条件(11)は、(u,w)が、式
【数56】

【0187】
(これは、図11の放物線1110である)と、
【数57】

【0188】
(放物線1120)によって定義される放物線1110、1120の間にあることを意味している。
【0189】
xが、I(a,b)にあるならば、
【数58】

【0190】
であり、ここで
【数59】

【0191】
であり、記号‖は、絶対値を示す。従って、BN,h,h′とI(a,b)の両方にある各整数x=x+uは、
【数60】

【0192】
内の格子点に対応する。
【0193】
図11において、P(a,b)の点を十字形により1121で示し、残りの格子L(x)点を円により1122で示す。
【0194】
L(x)のどの格子点が放物線1110、1120の間にあるかを計算するのは、かなり複雑なタスクのように思えるかもしれない。幸い、Valleeが述べるように、基底ベクトルがそれぞれ短く、一方の基底ベクトルは「準水平」で、他方は「準垂直」であるL(x)の格子基底を見つけることができる。基底は、(r,s)であり、
【数61】

【数62】

【0195】
である。
【0196】
≦kであり、ここで
【数63】

【0197】
であることを思い出されたい。
【0198】
Valleeは、以下を証明している
定理4.
P(a,b)の全ての点は、ある有理指数v∈[0,h′/4bN+2h′b/N]に関する縦座標w−vN/bで縦軸wと交差するrに平行な線上にあり、ここで
【数64】

【0199】
である。連続する指数vは、1だけ異なる。
【0200】
これらの線は、図11において1124で示す。
【0201】
次に、Valleeは、rに平行な準水平線1124をそれらの指数vによって数え、次に各線1124上のP(a,b)の点の数を数えるか概算することによって、P(a,b)の点を大まかに数える。
【0202】
特に、Valleeは、2つの放物線の間の空間を「胸部」1130、「脚部」1140、「足部」1150に分割する4つの「特別」指数を定義している。2つの放物線の間の空間が、上端が連結された2つの「脚部」1140のように見える形をどのように形成することができ、上部1130が「胸部」であり、「足部」1150は、「脚部」がFarey区間I(a,b)の端に接触するところに形成されることが容易にわかる。胸部、脚部、足部の領域の境界は、rベクトルに平行な線1160によって定められる。特別指数は、以下のように定義される。
【0203】
定義1:
は、定義域の第1(最小)指数である。
【0204】
脚部の第1指数であるvは、4hb/N以上の最小指数である。
【0205】
脚部の最終指数であるvは、h′/4bNよりも小さい最大指数である。
【0206】
(足部1150の)vは、h′/(4bN)+2h′b/Nよりも小さい最大指数である。
【0207】
≦k=N/h′なので、胸部1130は、最大4つの線を含み、足部1150は、最大2つの線を含む。従って、P(a,b)の点を数える際、いくつの点が胸部と足部にあるかの正確な計算をすぐに得ることができる。しかしながら、脚部は、非常に長いことがあり、(Nが無限になるにつれてオーダーN1/3で)O(N1/3)の線まで含むことがある。幸い、Valleeは、以下の定理を証明できた。
【0208】
定理5(「脚部定理」):
脚部の指数vの線1124上のP(a,b)の点の数n(v)は、
【数65】

【0209】
を満たす。
【0210】
以下、値
【数66】

【0211】
は、Valleeの下限と呼び、
【数67】

【0212】
は、Valleeの上限と呼ぶ。
【0213】
VLB及びVUB境界は、脚部のP(a,b)の格子点の総数の上限下限を得るのに用いることができ、a≦bである全ての正の整数a及びbに対し有効な以下の不等式を用いる。
【数68】

【数69】

【0214】
脚部定理を用いて、たとえ脚部1140が多数の線1124を有することがあっても、各線1124上で左から右へ点を数えることによって、P(a,b)の格子点について概算できる。点は、最初に胸部、次に足部、その次に脚部で数えられる。胸部、足部、脚部の領域のそれぞれにおいて、点は、その領域の一番上の線1124で最初に数えられ、次にその下の線、というふうに数えられる。この概算を用いて、所定のFarey区間に擬一様に存在するBN,h,h′から数を抜き出すことができる。
【0215】
Valleeの擬一様抜き出し方式
Valleeは、以下の「大域的」抜き出し方式で上記結果を使用したが、−h=h′=4N2/3について、BN,h,h′の数を擬一様に選択する。以下、nは、胸部1130の点の数を示し、nは、足部1150の点の数を示し、nc+f=nc+(胸部と足部の点の総数)であり、nは、脚部1140の点の数を示す。
【0216】
リスト13:Valleeの擬一様抜き出し方式
1.場所をランダムに選択する。任意の整数x∈選択した一様分布の[1,N]を選ぶ。
【0217】
2.Farey区間を決定する。連分数を用いて、xがJ(a,b)にある(a,b)を計算し、ここでJ(a,b)は、オーダーk=1/4N1/3の区間[0,N/2)のFarey分割区間である。
【0218】
3.P(a,b)の点の数を概算する。
【数70】

【0219】
を計算し、胸部と足部の点の数nc+fを正確に数え、Valleeの下限(15)及び式(17)を用いて脚部における点の数について概算nを得る。
【0220】
4.P(a,b)から点を選ぶ。整数t∈擬一様の[1,nc+f+n]をランダムに選択する。t≦nc+fであれば、胸部又は足部から適切な点を出力する。そうでなければ、各線がValleeの下限に接触していれば、式(17)を用いて、どの準水平線1124が脚部の点数(t−nc+f)を含んでいるかを決定し、一様分布のその線上のP(a,b)の点をランダムに選択する。
【0221】
5.P(a,b)から選択した点からx′を計算する。(u,w)を前ステップによって出力した格子点とする。x′=x+uに設定する。x′を出力する。
【0222】
リスト13の終了。
【0223】
x′∈BN,h,h′であり、x′は、xと同じFarey区間にあることに注目されたい。Farey区間は、幅が様々である。I(a,b)が直径
【数71】

【0224】
を有し、1≦b≦kであることを思い起こされたい。最初の2つのステップにおいて、広いFarey区間が選択される可能性が高いが、広いFarey区間は、より多くのB要素を含むので、選択したFarey区間の特定のB要素は、そのFarey区間が広ければ、選ばれる確率が低い。結局、これらの要因は「平衡」し、大域的な擬一様抜き出し方式を可能にする。
【0225】
参照により本明細書に含まれる「J.‐S.Coronの論文、Security Proof for Partial‐Domain Hash Signature Schemes (proc.of Crypto 2002,LNCS 2442,613‐626頁、Springer‐Verlag,2002)」において、Coronは、Valleeの方式を拡張して、εを正の定数として、
【数72】

【0226】
について、BN,h,h′の抜き出し方式を作り出した。該方式では、一様と統計的に区別が付かない分布、つまり、一様分布からの統計的距離が最大で
【数73】

【0227】
である分布の要素を抜き出す。このような改良により、Coronは、「部分領域ハッシュ」署名方式のセキュリティを証明することができる。この方式では、署名は、基本的にBN,h,h′内の数のモジュラ平方根である。しかしながら、Coronの部分領域ハッシュ署名方式において、署名は短くない。署名は、(logN)ビットの数で表される。対照的に、本発明のいくつかの実施形態においては、可逆圧縮θ(図8、ステップ810)をCoron部分領域ハッシュ署名に適用して、帯域幅を縮小した部分領域ハッシュ署名を得る。
【0228】
Valleeのように、Coronは、2つの放物線1110、1120(図11)の間にある格子点を考慮する。しかしながら、Coronは、I(a,b)ではなく局所領域J(a,b)を考慮し、異なる準水平線を用いて2つの放物線の間の値域を分割する。Coronは、Valleeのように、vとvを定義するが、vとvは、I(a,b)の端に接触する前にいずれの放物線とも交わらない(従って、J(a,b)の端を通り過ぎる)最初と最後の線の指数である。vとvの値は、
【数74】

【0229】
と、(h′−h)b/Nに近い。vの値は、少し異なって定義され、
【数75】

【0230】
に近くなるのは、Coronは、h′がN/kに必ずしも等しくない場合を考慮しているからである。Coronは、単にvからvまでの指数を有する線上の格子点を抜き出すので、vからv又はvからvまでの指数を有する線上の点が選ばれる可能性はない。しかしながら、Coronが考慮するパラメータ、すなわち、
【数76】

【0231】
と、
【数77】

【0232】
と、
【数78】

【0233】
について、除外された格子点の部分は、無視できるものであり、この抜き出し方式は、一様に非常に近い。εの値は、望ましくは、
【数79】

【0234】
が非常に小さくなるように選択する。
【0235】
3.本発明のいくつかの実施形態‐圧縮
さて、本発明に転じると、本発明のいくつかの実施形態では、BN,h,h′内の数と、定数cがゼロに近いn=c+log(h′−h)として、{0,1}のビットストリングとの間の写像を提供する、圧縮及び復元方式π,θ,π−1,θ−1を用いる。これらの写像は順列ではない。しかしながら、各写像又は、その逆の下の要素の像は小さい一定の基数を有するので、写像はここでは「準順列」と呼ぶ。
【0236】
形式上、集合X及びYと定数(l,l,l,l)に関し、
全てのx∈Xについて、{π(x,r):r∈R}の基数が[l,l]にあり、
全てのy∈Yについて、{x:∃r with π(x,r)=y}の基数が[l,l]にある場合、π:XxR→Yを(l,l,l,l)の準順列と定義する(19)。
【0237】
上記で、Rは、補助集合である。例えば、πをランダム化したい場合、ランダムビットのソースとして用いてもよい。Rの目的は、単に、πを、(たとえ単一のx∈Xに対し複数の出力が存在することがあっても)所定の入力に対し単一の出力である、実際の「写像」にすることである。Rは、空であることもある。実際の順列は、(l,l,l,l)の準順列であることに注意されたい。
【0238】
図6乃至9において、集合Rは、陰的である。Rは、ランダムビットのソースになることがある。
【0239】
以下、2つの準順列について説明する。1つは、発明者がおそらく暗号化により適していると考えたものであり、もう1つは、発明者がおそらく署名により適していると考えたものである。しかしながら、本発明は、暗号化又は署名に関連して一方の又は他方の準順列に限定されない。
【0240】
小さい非負定数c及びcに対し、
【数80】

【0241】
を、暗号化により適していることがある準順列とし、
【数81】

【0242】
を、署名により適していることがある準順列とする。π及びθの両方は、以下に、より詳細に説明するように、効率的に計算可能であり、効率的に可逆である、すなわち、トラップドア情報なしでも、π(x,r)又はθ(x,r)からxの可能性のある値を復元することは容易である。
【0243】
3.1 短いストリングをB要素に写像する(π準順列)
本発明のいくつかの実施形態による図6及び7の方式に関し、π及びπ−1を計算するための方法を次に説明する。基本的に、πは、短いビットストリングを、該ビットストリングがFarey区間とそのFarey区間内の「アドレス」を特定するものと解釈し、該ビットストリングをそのFarey区間内のアドレスを有するB要素に写像することによって、B要素に写像する。短いビットストリングは、あるh″<Nについて、ある区間[0,h″]の数である。その逆であるπ−1は、基本的に、B要素のFarey区間と、そのFarey区間内のアドレスとを決定することによって計算され、B要素は、次に、その区間/アドレスの組み合わせを示すビットストリングに写像する。
【0244】
この方法は、以下の観測を用いる。Valleeの定理3及び5と、不等式(15)及び(16)は、Fareyオーダー
【数82】

【0245】
という条件で、また、定理5と式(15)〜(16)において、変数h′が(h′−h)/2に置き換えられるという条件で、−h=h′=4N2/3だけでなく、全てのh,h′に有効である。また、定理5は、置換なしでも依然有効である。
【0246】
図12に、ビットストリングxを、特定の狭いNを法とする区間におけるモジュラ平方数を有する数x′に写像するπ写像を示す。ステップ1270は、ビットストリングxに対応するFarey区間(以下にかなり詳細に論じる)を計算することを含む。ステップ1280は、該Farey区間の各端のビットストリングを計算することを含む。ステップ1290は、Farey区間について、xをB要素に対するx′に写像することを含み、該区間の計数は、最初と最後のビットストリングの間のxの計数に対応する。
【0247】
復元及び圧縮関数は、以下の事実を利用する。「広い」Farey区間のB要素に関し、該区間を特定するには少数のビットが必要であるが、該要素の該区間内の位置を特定するには多くのビットが必要である。全体としては、ビットの数は「平衡する」。π準順列の典型的な実施形態の詳細を、以下に述べる。πの定義(19)に関して、その値を後に測定するあるパラメータh″について、X=[0,h″]である。{0,1}のビットストリングは、上述の[0,2n−1−1]の整数と解釈できることに注意されたい。
【0248】
以下のように仮定する。
【0249】
仮定1:h,h′を整数とする。いくつかの実施形態において、
【数83】

【0250】
である。J(a,b)を、区間[0,N/2]に関するオーダー
【数84】

【0251】
のFarey分割の区間とする。I(a,b)を、区間[0,N/2]に関する同じオーダーkのFarey区間とする。J(a,b)を、区間[0,N/2]の同じオーダーkの、Farey「拡張」分割区間、すなわち区間J(a,b)を含むものとする。
【0252】
リスト14‐π(x,r)の計算(図12参照):
1.ステップ1270(図12):
【数85】

【0253】
を計算して区間[0,h″]を[0,N/2]に写像し、結果がJ(a,b)に含まれる(a,b)を決定する。このステップもまた図11に示される。
【0254】
2.ステップ1280:
【数86】

【0255】
が、I(a,b)にある[0,h″]の最小整数であるxleftと、
【数87】

【0256】
がI(a,b)にある[0,h″]の最大整数であるxrightを計算する。ステップ1290は、以下のステップ3乃至5に対応する。
【0257】
3.胸部と足部の格子点P(a,b)の数である、nc+f=n+nを計算する。脚部の点の数のVLB下限(15)であるnを計算する。(以下に説明するように、数h″は、nc+f+n≧xright−xleftとなるように選択すべきである。)
4.Valleeの計数や他の計数を用いて(以下の計算注記1を参照)、x−xleftに対応する1つの格子点(u,w)(いくつかあることがある)を選択する。具体的には、
4A.
【数88】

【0258】
内の整数を選ぶ。
【0259】
4B.c≦n+nであれば、胸部又は足部に計数cを有する格子点(u,w)を選ぶ(すなわち、胸部と足部の点が一緒に数えられているとき)。
【0260】
4C.そうでなければ、vごとに、sを、指数が最大vである準水平線1124(図11)上の脚部格子点の数の下限とする。値sはVLB値(15)を用いて計算することができる。VLB値を付加してs推定値を得ることができ、又は、不等式(17)を用いて、右側の積分としてsを計算することができる。sv−1<c−nc+f≦sとなるようにvを計算する。nを、指数vの線1124上の格子点の数とし、n′をValleeの下限推定値(15)とする。整数
【数89】

【0261】
を選択し、(u,w)を線上のP(a,b)のc′番目の点に設定する。
【0262】
5.x′=x+uに設定し、ここで
【数90】

【0263】
である。x′を出力する。
【0264】
リスト14の終了。
【0265】
計算注記1。
【0266】
リスト14で用いられる値n,nや、他の値を計算するのに多くの方法がある。1つの例は、以下のとおりである。各線1124は、形式βr+αs
の点の集合であり、ここで、αは、固定整数であり、βは、全ての実数をとる。α=0に関し、対応する線1124(図11で1124.0と示す)は、原点(x=w=0)を通過し、縦線u=0との切片1294を見つけることができる。線u=0は、放物線1110、1120の対称軸である。定理4を用いて、対応する指数v=v[0]が求められる。次に、他の全ての指数vは、1整数だけv[0]と異なるため見つけることができ、線u=0に対する線1124の切片1294は、それらのw値がN/bだけ線1124.0切片のw値と異なるため見つけることができる。特に、定義1の特別指数とそれに対応する切片1294を求めることができ、胸部と足部の全ての線1124についてv値とw切片値を見つけることができる。
【0267】
胸部及び足部における線1124ごとに、等式(20)のための対応するα値を、その線の切片1294から求めることができ、次に、その切片1294のβ値を見つけることができる。このβ値をβinと示す。格子L(x)点は、βの整数値に対応する。格子点は、例えば
【数91】

【0268】
、すなわちβinに最も近い整数から始めて、その線上で横に移動することできる。各点の座標は、定義(12)にはめ込んで、点がP(a,b)に属するかどうかを決定することができ、このように、P(a,b)の点は、n又はnの一部として数えることができる。線を右に移動し(β>βin)、ある点と放物線1120の外側で遭遇した場合(すなわちx+w+u>h′)、右方向の移動を止めることができる。同様に、線を左に移動し、点と放物線1120の外側で遭遇した場合、左方向の移動を止めることができる。P(a,b)点は、また、他の順序で数えることもでき、例えば、各線1124の一番左の点から始めて、右に進んでもよい。一番左の点は、対応する等式(20)と放物線1110、1120の等式から解析的に見つけることができる。これらの実施形態は限定的なものではない。
【0269】
リスト14のステップ4Bで、c≦n+nであれば、c番目の点は、胸部と足部の線1124を数え、各線上の点を数えることによって見つけることができる。胸部と足部の線1124は、ある順序で横に移動することができ、例えば、胸部からv指数が増加する順で始めたり、その他の順序でもよい。各線1124上の点は、その線の対応する点
【数92】

【0270】
から始めて、又は他の順序で数えることができる。本発明は、特定の点の順序付けに限定されない。
【0271】
同様に、ステップ4Cで、脚部のある線1124に関してパラメータn,n′,c′を決定する時、その線上のP(a,b)のc′番目の点は、その線の対応する点
【数93】

【0272】
から始めて、又は他の順序で、格子点を横に移動することによって見つけることができる。いくつかの実施形態において、ステップ4B、4Cの計数順序は、π写像の特徴であり、π−1を計算するとき(以下リスト15で説明するように)と同じ順序である。他の実施形態において、所定のπ写像に関して、点の計数は、式(19)のrパラメータに対応するようにランダムである。さらに他の実施形態において、計数は、ランダムではないが、xに依存する(例えば、n,nや、xに依存する他の値)。
【0273】
リスト14において、計数がランダムであろうとなかろうと、出力x′は、乱数c,c′の関数である。他の実施形態において、数c,c′は、確定的に選択される。例えば、ステップ4A、4Cに示すそれぞれ対応する区間の第1の整数に選ぶことができる。或いは、cを単にx−xleftに選ぶことができ、xrightの計算を省略することができる。或いは、cをxright‐xleftに選ぶことができる。同様に、c′は、c−nc+f−sv−1に選ぶことができる。その他のランダムな又はランダムでない選択も可能である。リスト14の特定の方式は、以下に説明するように、c,c′が一様にランダムに選択されるならば、ランダムオラクルによる適応的選択メッセージ攻撃の下での対応する暗号化方式の証明できるセキュリティにより、有利である。
【0274】
計算注記1の終了。
【0275】
π(x,r)を計算する際、rを、確定的に又はランダムビットのソースとして用いることで、c及びc′の値を選択する。S={x′∈I(a,b)|∃r with π(x,r)=x′}とするならば、集合Sは、I(a,b)の分割を形成し、これは、I(a,b)の各B要素に選択される可能性があることを意味することに注目されたい。また、xとrを一様に選択して、π(x,r)を出力する場合、擬一様にBの整数を選択することに注目されたい。
【0276】
点の計数において、次に、胸部と足部のn+n=nc+fの点を、1からn+nまである順序で数える。脚部の点は、多数の点が同じ数を共有することがあるという意味で「大まかに」数えられる。脚部の点は、Valleeの下限を満たすかのように数え、特にSを計算する。このSの値は、個々の線についてのValleeの推定値である式(17)において積分を計算することによって容易に計算することができる。脚部の準水平線1124は、Valleeの下限推定値よりも多くの点を含むことが多い。その場合、計数において、かかる線上の隣接する点は、1つの数を共有することがある。
【0277】
図13は、B要素x′を[0,h″]の数xに写像する逆写像π−1を示す。ステップ1320で、Farey区間又はFarey分割区間を求め、これは、B要素x′に対応する。ステップ1330で、[0,h″]のビットストリングを計算し、図11の写像1270の逆である写像により、区間の各端に対応する。ステップ1340で、x′を[0,h″]のビットストリングxに写像し、ステップ1330で得たビットストリング間の計数は、区間のx′の計数に対応する。
【0278】
以下のリスト15では、(Farey分割区間ではなく)Farey区間を用いる時の詳細を説明する。x′=π(x,r)とすると、本発明の典型的な実施形態では、xの1つ又は2つの可能な値を復元する。(上記)仮定1が当てはまるものとする。
【0279】
リスト15‐π−1(x′,r)の計算:
1.ステップ1320:x′:I(a,b)とおそらくI(ai+1,bi+1)を含むFarey区間を決定する。
【0280】
2.ステップ1330:
【数94】

【0281】
が、I(a,b)にある[0,h″]の最小の整数であるxleftと、
【数95】

【0282】
が、I(a,b)にある[0,h″]の最大の整数であるxrightとを計算する。ステップ1340は、以下のステップ3乃至7に対応する。
【0283】
3.P(a,b)の胸部及び足部の格子点の数であるnc+fと、脚部の点の数の下限VLB(15)であるnとを計算する。
【0284】
4.
【数96】

【0285】
とu=x′−xから、格子点(u,w)を復元する。具体的に、格子L(x)は、ベクトル(1,2x)及び(0,N)によって生成されるので、ある整数αに対して、各格子点(u,w)が等式w=2xu+αNを満たさなければならないことは容易にわかる。‖h′−h‖<N(仮定1に鑑み、大きいNに対して当てはまらなければならない)と仮定すれば、所定のuが放物線1110、1120の間にある格子点は1つだけある。この格子点は、放物線の間の領域を定める不等式(11)を用いて計算することができる。例えば、α=0(w=2xu)から始めて、不等式(11)が満たされるまでαを増加及び/又は減少することができる。
【0286】
5.Valleeの下限計数又は他の計数(計算注記1を参照)を用いて、x−xleft、従ってxの値を復元する。具体的に、
5A.(u,w)が、胸部又は足部のt番目の点であれば、c=tに設定する。(胸部及び足部の点は、リスト14におけるように一緒に数えられる。計算注記1を参照)。
【0287】
5B.そうでなければ、(u,w)を含む線1124の指数vを計算する。c′の値を計算し、ここで、(u,w)は、線上のc′番目の点である。nを指数vの線上の格子点の数とし、n′をValleeの下限推定値VLB(15)とし、sv−1をvよりも小さい指数の準水平線1124(図11)上の脚部格子点の数の下限とする。値sv−1は、線1124ごとにVLB値(15)を用いて計算することができる。これらの値を足してsv−1推定値を得ることができ、又は、不等式(17)を用いて、右側の積分としてsv−1を計算することができる。
【数97】

【0288】
となるように、cの値を計算する。
【0289】
6.
【数98】

【0290】
となるように、x−xleftの値を計算する。x=xleft+(x−xleft)を計算する。
【0291】
7.xを出力する。
【0292】
リスト15の終了。
【0293】
上記の計算注記1を参照されたい。
【0294】
x′がI(a,b)とI(ai+1,bi+1)の両方にある場合、ステップ2乃至6を繰り返して、I(ai+1,bi+1)に対応するxの値を得ることができる。このように、上記の方式では、x′を含む1Farey区間につき、ちょうど1つ、xの値を、2つまで出力する。従って、l=1でありl=2である。エンコードされた値x=H(M)(図6、ステップ210)が、両出力x=π−1に当てはまらないある性質を確実に満たすようにすることによって、正確な値を選択することができる。例えば、エンコードx=H(M)は、H(M)のいくつかのビットのいくつかをチェックすることを含むことがある。或いは、ステップ1320でどのFarey区間を選ぶべきかの曖昧さを解決する何らかの方法があってもよい。
【0295】
少し変更した方法を用いて、π(x,r)が一意逆を確実に有するようにすることは難しくない。特に、x′が確実にJ(a,b)内にあるようにすることで一意逆を実現することができ、それは、P(a,b)についてのValleeの擬一様計数方法を、
【数99】

【0296】
の1つに適用することで確実にすることができる。この場合、P(a,b)は「一様でない」足部と脚部とを有するが、それでも、擬一様計数は、基本的に同じ方法を用いることで可能である。
【0297】
パラメータの設定:前述のように、暗号化方式には、π準順列がより適していることがある。準順列のパラメータ、特に、h′−hの値とh″の値とを設定するために、暗号化方式とできるだけ両立するために準順列が持つべき性質について考慮することがある。望ましくは、πは、一意可逆であるかほぼそうであるべきである。上述のように、l=2だが、I(a,b)ではなく区間J(a,b)を考慮することによって、l=1を実現することができる。また、各B要素(おそらくそれらの無視できる一部は除く)が少なくとも1つの逆を有するようにしたい。その理由は、一様確率でxを選択し、次にπ(x,r)を計算することからなるB要素抜き出し方式が「優れた」抜き出し方式であれば、暗号化方式のセキュリティが因数分解に関連する、セキュリティプルーフが通るということである。擬一様抜き出し方式を得るために、lは、少なくとも1であるべきである。
【0298】
とlの値は、π準順列の下で、xの像のサイズを制約する。各エンコードされたプレーンテキストは、B要素に写像可能であるべきなので、lは、望ましくは少なくとも1であるべきである。(しかしながら、これが当てはまらないようにパラメータを選択することは可能である)。lの値は、他のパラメータの値を考えると、できるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算を提示するが、具体的なパラメータを示している。
【0299】
c+f+n≧xright−xleft、すなわち、P(a,b)の点の数の下限が、I(a,b)に対応付けられるビットストリングの数よりも大きくなるようにパラメータを選択することは、lが、望みどおり、少なくとも1になることを確実にする。
【数100】

【0300】
であることに注意されたい。ここで、後者の項は、h′−h=N/2kであるので、I(a,b)の直径である。これは、
【数101】

【0301】
であることを意味する。さて、Valleeが使用したパラメータについて考えてみよう。Valleeは、−h=h′=4N2/3の場合を考慮したので、h′−h=8N2/3である。このh′−hの値について、Valleeは、
【数102】

【0302】
の下限を証明した。従って、
【数103】

【0303】
ならば、xright−xleft−1<nc+f+nである。n推定値が整数である限り、これは、望むとおり、xright−xleft−1≦nc+f+nであることを意味する。
【数104】

【0304】
に設定することで、lとlが少なくとも1であることを検証できる。
【0305】
他方、胸部と足部における点の数についてのValleeの上限は、lの値が上限を定められるのを可能にする。(nがまだ、脚部の点の数についての下限推定値VLBであることを思い起こされたい)。Valleeの計算は、nc+f+nが、
【数105】

【0306】
によって上限が定められるのを可能にする。これにより、h″の選択された値について、cの可能な値の数を8によって上限を定めることができ、ここで、cは、リスト14のステップ4で選択した数である。また、リスト14のステップ4で選択した数であるc′の、最大で
【数106】

【0307】
(Valleeの脚部定理を参照)の可能な値がある。従って、lは、最大8x4=32である。このように、h′−h=8N2/3
【数107】

【0308】
について、(1,32,1,2)準順列を得る。
【0309】
暗号文は、[h、h′]にあり、プレーンテキストは、[1,h″](又は[0,h″−1])にあるので、ここで、
【数108】

【0310】
であり、およそ
【数109】

【0311】
ビット、すなわち、丸めを考慮すると最大で3ビットの暗号文拡張だけが見込める。性能に関して、π(x,r)又はπ−1(x,r)の計算には、O(logN)ビットの演算が必要なだけであり、暗号化及び復号化の複雑性に、ほとんど何も付加しない。
【0312】
h′−hとh″の間の5の因数は、h′−h=8N2/3に対するValleeの下限の「ゆるさ」の結果である。h′−hのより大きい値、例えば、Coronが考慮したもの等について、下限は、より厳密な概算となる。従って、h′−hのより大きい値について、π準順列は、さらに小さい暗号文拡張を暗号化方式に与える。
【0313】
3.2 B要素を短いストリングに写像する(θ準順列)
θ準順列は、π準順列の逆に類似している。この場合も、圧縮及び復元方式は、ValleeのFarey区間の分析によって与えられるB要素の分布について公知の情報を用いる。
【0314】
帯域幅縮小署名方式を用いる本発明の典型的な実施形態に関して、より詳細に説明するように、θ準順列は、例えば、Coronによって安全性が証明されたものなど、通常のRabin部分領域ハッシュ署名を損失なしに、すなわち、通常の署名を圧縮された署名から完全に復元できるように、圧縮できるようにする。この圧縮方式は、セキュリティの減少を必要としない。典型的な実施形態の詳細な説明を続ける。
【0315】
上記仮定1が当てはまるものとする。
【0316】
リスト16‐Bのあるx′について[0,h″]のx=θ(x′,r)を計算する(図13参照):
1.ステップ1320:x′がJ(a,b)にある(a,b)を決定する。
【0317】
2.ステップ1330:
【数110】

【0318】
が、J(a,b)にある[0,h″]の最小の整数であるxleftと、
【数111】

【0319】
が、J(a,b)にある[0,h″]の最大の整数であるxrightを計算する。ステップ1340は、以下のステップ3乃至5に対応する。
【0320】
3.P(a,b)の胸部及び足部の格子点の数、nc+fと、脚部の点の数についての上限VUB(16)、nとを計算する。(nc+f+n≦xright−xleftを望む。)
4.Valleeの計数か他の計数(計算注記1参照)を用いて、x′に対応付けられた格子点(u,w)に対応するxright−xleft(いくつかあることがある)の1つの整数を選択する。具体的には、
4A.(u,w)が胸部又は足部のt番目の点であれば、c=tに設定する。
【0321】
4B.そうでなければ、sを、指数が最大でvの準水平線1124(図11)上の脚部格子点の数についての上限とする。値sは、線1124ごとにVUB値(16)を用いて計算することができる。これらの値を足してs推定値を得ることができ、又は、不等式(18)を用いて、右側の式としてsを計算することができる。(u,w)を含む線の指数vを計算する。nを、指数vの線上の格子点の数とし、n′=s−sv−1を、Valleeの上限推定値VUB(16)とする。x′が、線上のt番目の格子点であるとする。整数
【数112】

【0322】
を選択する。
【0323】
5.整数
【数113】

【0324】
を選択する。x=xleft+c′に設定する。
【0325】
リスト16の終了。
【0326】
計数についての考察を含む計算注記1は、π及びπ−1に当てはまるように、θ及びθ−1写像に当てはまる。
【0327】
θ(x′,r)を計算するのに、rを確定的に、又は、ランダムビットのソースとして用いて、cとc′の値を選択する。[0,h″]においてx=θ(x′,r)とすると、Bのx′の値を以下のように復元することができる。
【0328】
リスト17‐θ−1(x)を計算する(図12):
1.ステップ1270:
【数114】

【0329】
が、J(a,b)にある(a,b)を決定する。
【0330】
2.ステップ1280:
【数115】

【0331】
が、J(a,b)にある[0,h″]の最小の整数であるxleftと、
【数116】

【0332】
が、J(a,b)にある[0,h″]の最大の整数であるxrightを計算する。
【0333】
ステップ1290(以下のステップ3乃至5)。
【0334】
3.P(a,b)の胸部及び足部の格子点の数、nc+fと、脚部の点の数についての上限VUB(16)、nとを計算する。
【0335】
4.c′=x−xleftを計算する。c′とnc+f+nから、
【数117】

【0336】
となるように値cを計算する。c≦nc+fであれば、(u,w)を胸部又は足部のc番目の点とする。そうでなければ、c∈(nc+f+sv−1,nc+f+s)となるように、指数vを計算し、ここで、sは、リスト16、ステップ4Bにおけるように定義される。また、(リスト16におけるように定義される)tの値を計算し、(u,w)を指数vの準水平線1124上のt番目の点とする。
【0337】
5.
【数118】

【0338】
に設定する。
【0339】
リスト17の終了。
【0340】
計数についての考察を含む計算注記1は、リスト16に当てはまる。
【0341】
パラメータの設定。θ準順列は、おそらく署名方式により適しているので、h′−hの値とh″の値を選択するのに、署名方式にできるだけ有用となるのに準順列が含むべき性質について考慮しなければならない。例えば、θは、一意可逆であるかほとんどそうであるべきである。しかしながら、図9のステップ510で、多数の候補から正確なH(M)値を認識したり、そうでなければ、ステップ520で、検証を認識するのが可能であれば、一意可逆は、必要ではない。一実施形態において、lとlは、両方とも1に等しい。すなわち、各ビットストリングxは、その逆としてちょうど1つのB要素x′を有する。lが少なくとも1つであることは適切である。すなわち、各B要素は、その圧縮として少なくとも1つの短いビットストリングを有するべきである。前述のように、他のパラメータの値を考慮すると、lはできるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算は、具体的なパラメータを示している。
【0342】
c+f+n≦xright−xleftとなるように、すなわち、P(a,b)の点の数の上限が、J(a,b)に対応付けられたビットストリングの数よりも小さくなるように、パラメータを選択することで、各B要素に一意に対応付けられる少なくとも1つのビットストリングが確実に存在することになる。
【数119】

【0343】
であることに注目されたい。ここで、後者の項は、I(a,b)の直径であり、少なくともJ(a,b)の直径である。このことは、
【数120】

【0344】
であることを意味する。
【0345】
さて、Coronが用いたパラメータについて考えてみる。Coronは、
【数121】

【0346】
の場合を考慮した。これらの値について、Coronは、
【数122】

【0347】
の上限を証明した。ここで、jは、J(a,b)の整数の数である。従って、
【数123】

【0348】
であれば、xright−xleft+1>nc+f+nである。n推定値が整数である限り、望みどおり、xright−xleft≧nc+f+nとなる。従って、
【数124】

【0349】
に設定してもよく、ここで、最大値は、全てのiに取って代わる。
【0350】
他方、Coronは、また、下限
【数125】

【0351】
を証明する。これにより、c′について可能な値の数の上限をおよそ
【数126】

【0352】
に定めることができ、Nとεの標準値に対して最大で2である。また、cについて可能な値の数は、およそ
【数127】

【0353】
によって上限を定められ、Coronのパラメータに対し同じく最大で2である。従って、lは、最大で2・2=4であり、(1,4,1,1)準順列を得る。しかしながら、B要素の無視できる部分だけは複数の像を有する。
【0354】
4.暗号化/復号化方式
本発明のπ変換を図6の方式において用いることで、暗号文のサイズの縮小を可能にすることによって、(上述の)Rabin‐OAEP+等のRabinに基づく暗号化方式を改良することができる。
【0355】
以下、πN,h,h′という表現は、集合BN,h,h′への写像πを示し、θN,h,h′は、集合BN,h,h′からの写像θを示す。
【0356】
リスト18‐暗号化(図6):
1.ステップ210:メッセージMのエンコードである、x=H(M)を計算する。
【0357】
2.ステップ610:x′=πN,h,h′(x,r)∈[0,N/2]を計算する。
【0358】
3.ステップ220:y=x′(mod N)を計算する。ここで、文字yをcの代わりに暗号文に用いて、本明細書におけるcの他の使用との混同を避ける。
【0359】
4.ステップ230:yを暗号文として出力する。
【0360】
リスト18の終了。
【0361】
リスト19‐復号化(図7):
1.ステップ310:x′≡y(mod N)となるように、各x′∈[0,N/2]を計算する。図7において数x′はbと示す。[0,N/2]にはかかるx′が少なくとも1つ存在するのは、x′=y(mod N)でありx′が[0,N/2]になければ、x′はN−x′に設定することができるからであり、この新しいx′値は[0,N/2]にあり、x′=y(mod N)を満たす。
【0362】
2.ステップ320:
【数128】

【0363】
を計算する。かかるx値は、いくつかあることがある。これらの値は、図7のH(M)に対応する。
【0364】
3.ステップ330:メッセージエンコードを取り消して、メッセージMが正確にエンコードされているか確認する。
【0365】
4.Mが正確にエンコードされていない場合、x′の別の値を試してみる。x′の全ての値が試されているならば、復号化が失敗したことを示す。
【0366】
リスト19の終了。
【0367】
リスト14、15、18、19による、π写像を含むRabin暗号化方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でπ写像がないのと同じくらい安全であることを示すことができる。参照により本明細書に含まれる「Craig Gentry著、How to compress Rabin Ciphertexts and Signatures (and More),Proc.of Crypto 2004,M.Franklin(Ed.),Lecture Notes in Computer Science 3152,pp.179−200,Springer,2004」を参照されたい。
【0368】
π準順列は、N,h及びh′の特定の値に依存することに注意されたい。従って、ある意味、h及びh′は、公開鍵の一部であり、送信者は、暗号化を実行するのにそれが必要である。RSAやRabin暗号化と共に用いることができる当技術において公知の様々なエンコード方式は、本発明の帯域幅縮小暗号化方式においても用いることができる。以下、帯域幅縮小暗号化方式の詳細を示すが、上記リスト5及び6のRabin‐OAEP+の説明に類似している。上述のように、メッセージエンコードは、式(1)により上記定義したハッシュ関数を利用する。非帯域幅縮小Rabin‐OAEP+(リスト5及び6)において、
【数129】

【0369】
であったが、本発明の帯域幅縮小暗号化方式においては、式(21)に示したValleeのパラメータに関するh″の値に従って、
【数130】

【0370】
に設定するのが適切である。いくつかの実施形態において、Valleeのパラメータにおけるように、h′−hは、およそ8N2/3である。もちろん、nを大きくする、例えば、logNにまですることができるが、エンコードしたプレーンテキストが、
【数131】

【0371】
よりも大きくなければならない場合を除いて、それは必須ではない。
【0372】
メッセージM∈{0,1}を暗号化するために、送信者は、以下の演算を実行する(図6参照)。
【0373】
リスト20‐暗号化。
【0374】
図6のステップ210は、以下のステップ1乃至3に対応する。
【0375】
1.任意の
【数132】

【0376】
を選択する。
【0377】
2.
【数133】

【0378】
を設定する。
【0379】
3.nビットストリング、x←s‖tを設定する。
【0380】
4.ステップ610:x′=π(x,r)∈[0,N/2]を計算する。
【0381】
5.ステップ220:暗号文c←x′(mod N)を計算する。
【0382】
リスト20の終了。
【0383】
x′は、モジュラ平方数が非常に狭い値域(すなわち、[h,h′])にある整数であるので、cの
【数134】

【0384】
最下位ビットだけを実際に送信するだけでよく、暗号文を「短く」することに注目されたい。h′−h=8N2/3に対し、暗号文は、およそ
【数135】

【0385】
ビットである。
【0386】
復号化するために、受信者は、以下のステップを実行する(図7参照)。
【0387】
リスト21−復号化
1.ステップ310:cのモジュラ平方根
【数136】

【0388】

【数137】

【0389】
とを計算する。
【数138】

【0390】
の少なくとも1つと、
【数139】

【0391】
の少なくとも1つは、[0,N/2]にある。一般性を失うことなく、
【数140】

【0392】
は、[0,N/2]にあるものと仮定することができる。
【0393】
2.候補
【数141】

【0394】
ごとに、
2A.ステップ710:
【数142】

【0395】
を計算する。
【0396】
2B.ステップ320:
【数143】

【0397】
と、
【数144】

【0398】
について、xをs‖tに構文解析し、次に、
【数145】

【0399】
と、
【数146】

【0400】
について、s
【数147】

【0401】
に構文解析する。iごとに、
【数148】

【0402】
と、
【数149】

【0403】
とを計算し、
【数150】

【0404】
かどうかテストする。条件が満たされる一意のiが存在する場合、Mを正確なプレーンテキストとして出力し、そうでなければ、復号化の失敗を示す。
【0405】
リスト21の終了。
【0406】
セキュリティのプルーフの概略を述べるのに、上記の帯域幅縮小暗号化方式を解読することは、法Nを因数分解するのと同じくらい難しいことを(例えば、「ランダムオラクルモデル」を用いて)証明できる。例えば、時間tでアドバンテージεで暗号化方式を解読するアルゴリズムAが存在するものとし、ここで、アドバンテージは、Aが選択した2つのプレーンテキスト、MとM、のどちらが特定の暗号文によって暗号化されているかを正確に推測できる確率(マイナス1/2)と定義する。次に、Aとのインタラクションを通じて得た知識を用いることによって、Nを因数分解できる第2のアルゴリズムBを構成することができる。例えば、以下の「ゲーム」を考えてみる。
【0407】
挑戦者は、因数分解する法NをBに与える。Bは、Nをその公開鍵であると述べ、フェーズ1で、Aが、Aの選択した暗号文メッセージcの復号化を要求することができるようにする。さて、Bは、秘密鍵を知らないので、Bは、実際に復号化できない。しかしながら、Bは、暗号ハッシュ関数G,H及びH′(1)の出力を制御する。これは、ランダムオラクルモデルである。ハッシュ関数は、「ゲーム」のエンティティが制御してもよいオラクルとみなされる。Aは、Aの選択したメッセージMのハッシュ関数値をBに問い合わせる。Bが同じメッセージMについて、以前に、この問合せを受信していれば、Bは、以前と同じハッシュ関数値を返す。そうでなければ、Bは、ランダムにハッシュ関数値を生成する。Aは、このハッシュ関数値を用いてMを暗号文cに暗号化し、Bにcを復号化するように要求する。
【0408】
Bがハッシュ関数を制御するので、また、Aは(無視できる確率を除いて)ハッシュを問合せることなく有効にエンコードされた暗号文を作成することができないので、Bは、(例えば)AがH′に入力するMの値など、Aのハッシュ関数への入力Mを「見る」ことになる。この知識を用いて、Bは、圧倒的に高い確率でAの復号化の問合せに正確に返答するこができる。フェーズ1の終わりに、Aは、それについてテストされたいメッセージMとMを選択し、Bは、ランダムにあるビットb∈{0,1}を選択し、Mを暗号化する暗号文c(「挑戦暗号文」)を返信する。Bは、ハッシュ関数の制御を用いて、この暗号文を巧妙に「間に合わせに作る」ので、cのモジュラ平方根
【数151】

【0409】
がわかる。「フェーズ2」で、Aは、挑戦暗号文以外の復号化すべき暗号文をさらに要求することができる。最終的に、推測b′∈{0,1}を出力し、b=b′であればゲームに勝利する。ハッシュの問合せをさらに行って、再びBがこれらのハッシュ関数への入力を「見る」ことができるようしない限り、Aは、せいぜいわずかなアドバンテージしか有さない。
【0410】
Aが確かにcのモジュラ平方根
【数152】

【0411】
を計算すれば、
【数153】

【0412】
である可能性があるので、
【数154】

【0413】
は、Nの自明ではない因数を与える。確かに、xとrを一様に計算し(ハッシュ関数はxに対し一様出力を与えるものとする)、次に、x′=π(x,r)を計算することからなる抜き出し方式が擬一様抜き出し方式であれば、Bが、どのモジュラ平方根を知っているかをAが推測する可能性は低いことを意味する。従って、Aは、間違って推測することが多く、そのハッシュの問合せにより、Nの自明ではない因数を計算するのに必要な情報をBに与える可能性が高い(擬一様抜き出し方式について、Valleeの値を
【数155】

【0414】
とすると、少なくとも
【数156】

【0415】
の可能性)。
【0416】
5.署名方式
本発明のθ変換を用いて、署名を損失なしに圧縮できるようにすることによって、Coronが安全であると証明した部分領域ハッシュ署名などの、Rabinに基づく署名方式を改良することができる。基本的なアプローチは、以下のとおりである。
【0417】
リスト22‐署名(図8も参照):
1.図8のステップ410:メッセージMのエンコード、y∈[h,h′]を計算する。
【0418】
図8のステップ420は、以下のステップ2及び3に対応する。
【0419】
2.eyがNを法とする平方数となるように、e∈{−2、−1,1,2}を計算し、ey(mod N)を計算する。yは、Nを法とする平方根を持たないことがあるが、(Nが2つの素数の積とすると)−2*y,−y,y,2*yのいずれかは、常にNを法とする平方根を有するので、eで乗算がなされる。
【0420】
3.x′≡ey(mod N)となるように、x′∈[0,N/2]を計算する。「通常の」署名は、(x′,e)である。
【0421】
4.図8のステップ810:eが正であれば、x=θN,eh,eh′(x′,r)を計算し、eが負であれば、x=θN,eh′,eh(x′,r)を計算する。圧縮された署名は(x,e)である。
【0422】
リスト22の終了。
【0423】
リスト23-検証(図9参照):
1.ステップ910(図9):eが正であれば、
【数157】

【0424】
を計算し、eが負であれば、
【数158】

【0425】
を計算する。
【0426】
2.ステップ510:y=H(M)/e(mod N)を計算する。
【0427】
3.ステップ520:y∈[h,h′]であり、メッセージMのエンコードであるか確認する。
【0428】
リスト23の終了。
【0429】
θ準順列は、N,h,h′及びeの特定の値に依存することに注意されたい。従って、ある意味では、hとh′は、公開鍵の一部であり、検証者は、署名を検証するのにそれが必要である。RSAやRabin署名と共に用いることができる当技術で公知の様々なエンコード方式は、本発明の帯域幅縮小署名方式においても用いることができ、その逆もまた同様である。eの値は、2ビットで表現することができる。eに様々な値を用いることができるが、eを小さくしておくことは適切である。
【0430】
リスト16、17、22、23による、θ写像を含むRabin署名方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でπ写像がないのと同じくらい安全であることを示すことができる。上述のCraig Gentry著の論文、How to compress Rabin Ciphertexts and Signatures (and More)を参照されたい。
【0431】
以下、より詳細な帯域幅縮小署名方式を示すが、前述の全領域ハッシュ署名方式の説明と類似している(リスト7及び8参照)。メッセージ復元が可能な特定のエンコード方式を使用する。前述のように、上記式(1)により与えられる暗号ハッシュ関数を使用する。非帯域幅縮小署名方式(リスト7及び8)においては、
【数159】

【0432】
であったが、帯域幅縮小署名方式には、Coronのパラメータに従って、
【数160】

【0433】
とするのが望ましい。この場合も、nを
【数161】

【0434】
ビットよりも大きく設定することができるが、ある理由で、エンコードされたメッセージが
【数162】

【0435】
ビットよりも長くなければならない場合を除いて、これは望ましくない。素数P≡3(mod 8)及びq≡7(mod 8)についてN=pqとなるようにNを生成する際、署名者は、以下の演算を実行する。
【0436】
リスト24‐署名(図8):
図8のエンコードステップ410:
1.任意の
【数163】

【0437】
を選択する。
【0438】
2.
【数164】

【0439】
を設定する。
【0440】
3.nビット整数、y←s′‖s″‖tを設定する。
【0441】
図8の署名ステップ420:
4.u←y(q+1)/4(mod q)を計算する。
【0442】
5.
【数165】

【0443】
であれば、e←1に、そうでなければ、e←−1に設定する。
【0444】
6.u←(ey)(p+1)/4(mod p)を計算する。
【0445】
7.
【数166】

【0446】
であれば、f←1に、そうでなければ、f←2に設定する。
【0447】
8.v←f(3q−5)/4(mod q)、及びv←f(3q−5)/4(mod p)を計算する。
【0448】
9.w←v+q(qp−2(v−v)mod p)を計算する。
【0449】
10.2w<Nであれば、x′←wに、そうでなければ、x′←N−wに設定する。
【0450】
短い署名の生成(図8のステップ810):
11.eが正であれば、x=θN,eh,eh′(x′,r′)を計算し、eが負であれば、x=θN,eh′,eh(x′,r′)を計算する。
【0451】
12.署名(e,f,r,x)を出力する。
【0452】
リスト24の終了。
【0453】
この場合も、2(3q−5)/4(mod q)、2(3p−5)/4(mod P)及びqp−2(mod p)の値は事前に計算できるので、ステップ8及び9は、署名時間にほとんど何も付加しない。
【0454】
リスト25‐検証(図9):
1.ステップ910:eが正であれば、
【数167】

【0455】
を計算し、eが負であれば
【数168】

【0456】
を計算する。
【0457】
2.ステップ510、520:
【数169】

【0458】
を計算し、ytmpがnビットであることを確認し、ytmp
【数170】

【0459】
に構文解析し、
【数171】

【0460】
を計算し、
【数172】

【0461】
であることを確認する。
【0462】
リスト25の終了。
【0463】
検証処理中にメッセージMが復元されることに注意されたい。また、圧縮θ(リスト24のステップ11)は、「通常の」Rabin署名(e,f,x′)が生成された後に、署名処理の終わりにやっと出てくることに注目されたい。
【0464】
セキュリティのプルーフは、Coronが提供したような「通常の」部分領域ハッシュ署名方式に対するセキュリティのプルーフから容易に得られる。ある攻撃者Aが、帯域幅縮小方式において偽造ができるならば、非帯域幅縮小方式に対する別の攻撃者Bは、単にθ−1をAの偽造に適用することで、非帯域幅縮小方式において偽造することができることは明らかである。Bは、Aの署名の問合せを挑戦者に中継し、次に挑戦者の応答に対し、それらをAに中継する前にθを適用することによって、該署名の問合せに容易に応答するふりをすることができる。
【0465】
6.サインクリプション方式
本発明のいくつかの実施形態によるサインクリプション方式において、望ましくは、サインクリプションの送信が、送信者が署名と暗号文を別々に送信した場合よりも少ない帯域幅を消費するように、送信者は、同時に、自身の秘密鍵を用いてメッセージに署名し、受信者の公開鍵を用いてそれを暗号化する。受信者は、その秘密鍵でサインクリプションを復号化し、送信者の公開鍵を用いて送信者の署名を検証する。送信者の公開法をN又はN(A)で示し、送信者のh,h′パラメータをそれぞれh及びh′で、又はh(A)及びh′(A)で示す。受信者の公開法をN又はN(B)で示し、受信者のh,h′パラメータをそれぞれh及びh′で、又はh(B)及びh′(B)で示す。一実施形態は以下のとおりである(図6、8及び14参照)。
【0466】
リスト26‐サインクリプション(図14):
1.図14のステップ410(エンコード):メッセージMのエンコード、y∈[h,h′]を計算する。ステップ420(以下のステップ2、3)。
【0467】
2.eyがNを法とする平方数となるように、e∈{−2,−1,1,2}を計算する。
【0468】
3.x′≡ey(mod N)となるように、x′∈[0,N/2]を計算する。
【0469】
4.ステップ810:eが正であれば、短い署名
【数173】

【0470】
を計算し、eが負であれば、
【数174】

【0471】
を計算する。
【0472】
5.ステップ1410:x″∈[0,N/2]として、eが正であれば、
【数175】

【0473】
を計算し、eが負であれば、
【数176】

【0474】
を計算する。
【0475】
6.ステップ1420:c=x″(mod N)を計算する。サインクリプションは、eとc、又はeとcの省略形とからなる(cの省略形とは、cよりも少ないビットで表現することができ、それからcを求めることができる数であり、例としてc−hや、cのある数の最下位ビットを含む)。
【0476】
リスト26の終了。
【0477】
θ準順列は、N,eの特定の値と、h及びh′の値に依存し、ユーザA及びBによって異なることがあることに注意されたい。従って、いくつかの実施形態では、hとh′は、公開鍵の一部であり、受信者は、署名を検証し、メッセージを復号化するのにそれが必要である。異なる署名者は、hとh′に異なる値を用いることができるが、簡潔にするために同じであるのが望ましい。様々なエンコード方式が当技術において公知であり、1つの方式を以下に詳細に説明する。eの値は、2ビットで表現することができる。eに様々な値を用いることができるが、eを小さくしておくことが望ましい。「cの省略形」(例えば、
【数177】

【0478】
ビットで表現することができる、c−h)を、h及びh′と一緒に用いて、cの完全な値を復元することができるので、サインクリプションは「短い」。
【0479】
リスト27‐アンサインクリプション(Unsigncryption)(図15参照):
1.ステップ1510(復号化):x″≡c(mod N)となるように、x″∈[0,N/2]の2つの値を計算する。
【0480】
2.ステップ1520:eが正であれば、
【数178】

【0481】
を計算し、eが負であれば、
【数179】

【0482】
を計算する。
【0483】
3.ステップ1530:eが正であれば、
【数180】

【0484】
を計算し、eが負であれば、
【数181】

【0485】
を計算する。
【0486】
4.ステップ1540:y=x′/e(mod N)を計算する。
【0487】
5.ステップ1550:メッセージエンコードを取り消してMを復元し、メッセージMが正確にエンコードされているか確認する。Mが正確にエンコードされていなければ、x″の他の値を試してみる。x″の両方の値を試しているならば、復号化が失敗したことを示す。
【0488】
リスト27の終了。
【0489】
アンサインクリプションにおいて、図14のステップ810におけるθの計算でサインクリプター(signcrypter)が用いるrの特定の値を、アンサインクリプター(unsigncrypter)は知らない。しかしながら、θ準順列にパラメータを望ましく選択するために、B要素の無視できる部分だけが複数の像を有するので、出力は一意になる可能性が高い(rから独立している)。しかし、必要ならば、サインクリプターは、どのrの値を用いたかを示す少数の追加ビットを送信することができる。
【0490】
図14のステップ410の典型的なエンコードは、以下のとおりである。m,k,kをセキュリティパラメータとする。
【数182】

【0491】

【数183】

【0492】
の数量は、ごくわずかであるべきだが、必然ではない。n=m+k+kとする。望ましくは、法NとNは、ほぼ同じ数のビットを有し、帯域幅縮小署名方式におけるように、
【数184】

【0493】
である。NとNのサイズが異なるならば、
【数185】

【0494】
となるように、nを設定することができる。この場合も、nをさらに大きく設定することはできるが、そうすることは最適ではない。以下の暗号ハッシュ関数を定義する。
【数186】

【数187】

【0495】
このH関数(メッセージエンコードの計算用の中間値)は、図14のステップ410に示す、最終的なエンコードされたメッセージを表すH(M)関数と混同するべきではない。
【0496】
図14のステップ410で、yを計算するために、ここで、yは、メッセージM∈{0,1}のエンコードであるが、サインクリプターは、
1.任意の
【数188】

【0497】
を選択する。
【0498】
2.t=H(r‖M)及び
【数189】

【0499】
に設定する。
【0500】
3.y=s‖tに設定する。
【0501】
ステップ1550で(図15)、アンサインクリプターは、yをs及びtに構文解析し、
【数190】

【0502】
からrとMを復元し、t=H(r‖M)であることを確認する。セキュリティプルーフは、基本的に、前述の、暗号化方式と署名方式のセキュリティプルーフを組み合わせたものである。さらに、帯域幅縮小署名方式に関連して上記に述べたモジュラ平方根の計算への数論的アプローチは、サインクリプション/アンサインクリプションと共に用いることができる。
【0503】
いくつかのサインクリプション実施形態において、署名と暗号化の順序を逆にする。すなわち、送信者は、まず、受信者の公開鍵を用いてメッセージを暗号化し、次に送信者の秘密鍵を用いてメッセージに署名する。受信者は、署名を検証し、暗号化されたメッセージを復元し、次にメッセージを復号化する。リスト26、27に類似した方法を、演算の順序を適切に変更して用いることができる。
【0504】
7.集合署名方式
本発明のいくつかの実施形態による集合署名方式において、それぞれ公開鍵法{N,…,N}を有する署名者の集合{S,…,S}は、それらの集合署名、すなわち、各SがMに署名したことを検証するのに必要なビットストリングが「短く」、各署名者がそれぞれのメッセージに別々に署名した場合よりも少ない帯域幅を最適に消費するように、それぞれのメッセージ{M,…,M}に署名する。本発明のいくつかの実施形態において、メッセージは、順に署名され、これは、署名者Sが、Si−1からsi−1を受信した後に、Mについて署名sを生成することを意味する。いくつかの実施形態において、Nは、全てほぼ同じビット長を有する。Nのビット長に関する考慮事項は、本発明のサインクリプションの実施形態に関して前述したのと基本的に同じである。
【0505】
各si−1は、
【数191】

【0506】
の要素の、(
【数192】

【0507】
により)圧縮した表示であり(図8のステップ810に注目)、sは、基本的に、[h,h′]の数のNを法とする圧縮平方根として計算される(ステップ420、810)。その数は、si−1とMとに依存する。(以後、署名者は、それぞれ異なる値のh及びh′を用いることができるが、便宜上、このことは表記において示さない)。集合署名は、公開鍵{N,…,N}を用いて検証される。具体的に、このアプローチは、以下のとおりである。fを後述する関数とする。Nは、N(i)とも示す。i番目の署名者は、以下の演算を実行する。
【0508】
リスト28‐集合署名(図8参照):
0.s=dに設定する。ここで、dは、所定の固定値である(任意の値)。
【0509】
1.i=1からi=zについて、以下を行う。
【0510】
1A.ステップ410:y=f(si−1,N,M,…,N,M)∈[h,h′]を計算する。
【0511】
ステップ420(以下のステップ1B及び1C):
1B.eがNを法とする平方数となるように、e=e(i)∈{−2,−1,1,2}を計算する。H(M)=e(mod N)を計算する。
【0512】
1C.ステップ420:
【数193】

【0513】
となるように、
【数194】

【0514】
を計算する。
【0515】
1D.ステップ810:eが正であれば、s=θN(i),e(i)h,,e(i)h′(s,r)を計算し、eが負であれば、s=θN(i),e(i)h′,e(i)h(s,r)を計算する。
【0516】
2.集合署名(s,e,・・・s,e)を出力する。
【0517】
リスト28の終了。
【0518】
i番目の署名者は、sを生成する前に、(i−1)番目の署名者がそれ自身の署名を集合した後の結果である、si−1の値を受信することに注目されたい。サインクリプション方式におけるように、署名者は、それぞれ、hとh′に異なる値を用いることができるが、簡潔にするためには同じであることが望ましい。関数fについては、本発明が利用する検証の概要を述べた後に説明する。
【0519】
リスト29‐検証(図9参照):
1.i=zからi=1について、以下を行う。
【0520】
1A.ステップ910:eが正であれば、s′=θ−1N(i),e(i)h,e(i)h′(s)を計算し、eが負であれば、s′=θ−1N(i),e(i)h′,e(i)h(s)を計算する。
【0521】
1B.ステップ510:
【数195】

【0522】
を計算する。
【0523】
1C.ステップ520:y=f(si−1,N,M,…,N,M)からsi−1を計算する。
【0524】
2.ステップ520:ステップ1B‐2で計算したsがdに等しいことを確認する。
【0525】
リスト29の終了。
【0526】
関数fは、集合署名処理において効率的に計算可能なだけでなく、検証処理においても効率的に可逆であるべきである。可逆であるとは、si−1が、f(si−1,N,M,…,N,M)と、N,M,…,N,Mの値から導き出せるべきであるという意味においてである。かかる関数の候補の1つは、f(si−1,N,M,…,N,M)=si−1・H(N,M,…,N,M)である。ここで、“・”は、加算やXORなどの何らかの容易に可逆である2項演算である。
【0527】
この方式のセキュリティを証明するのに問題があることがある。1つの理由として、鍵とメッセージの固定集合(N,M,…,N,M)に対する集合署名要素si−1には、可能性のある値が多くあり、シミュレータ(すなわち、暗号化の項4の言語のアルゴリズムB)が、sに関するsi−1の全ての可能性のある値についての攻撃者の署名の問合せに返答することができるように、シミュレータが、H(N,M,…,N,M)の単一の値を「間に合わせに作る」ことはおそらく不可能であることがある。ここで、Hは、Nを法とする整数集合の値を有するあるハッシュ関数である。
【0528】
この問題に対処するために、fを計算する別のアプローチを用いることがあり、
【数196】

【0529】
を計算し、ここで、Eは、対称暗号化方式であり、対称暗号鍵kは、あるハッシュ関数Hについて、k=H(N,M)(又は、必要なら、k=H(N,M,…,N,M)として計算する。fが可逆であることは容易にわかる。
【数197】

【0530】
とN及びMを与えられると、k=H(N,M)、次に、
【数198】

【0531】
を計算することができる。ここで、
【数199】

【0532】
は、鍵kの下の対称復号である。このセキュリティプルーフは、ランダム応答を返すオラクルのように、暗号ハッシュ関数がふるまうことを装うランダムオラクルモデルを用いるのではなく、ある対の鍵/メッセージについてランダム暗号文を返すオラクルのように暗号(対称暗号化方式)がふるまうことを装う理想暗号モデルを用いている。参照により本明細書に含まれる「M.Bellare、D.Pointcheval及びP.Rogaway著、“Authenticated Key Exchange Secure Against Dictionary Attacks”,in Proc.of Eurocrypt 2000,B.Preneel(Ed.),Lecture Notes in Computer Science 1807,pp.139−155」を参照されたい。
【0533】
理想暗号モデルにより、シミュレータは、鍵やメッセージだけでなくsi−1にも依存する問合せ応答を行うことができ、シミュレータは、その応答をより自由に「間に合わせに作る」ことができる。最適には、対称暗号化方式Eは、暗号文を拡張することなく、si−1の長さ、すなわち、およそ(2/3+ε)logビットのストリングを暗号化できるので、集合署名のサイズは、より多くの署名が集合されるにつれて著しく大きくなることはない。
【0534】
fを計算する上記方法はもちろん、θ圧縮関数を使用しない(すなわち、図8のステップ810を省略した)モジュラ2乗に基づく逐次集合署名方式を作成するのに用いることができる。
【0535】
8.リング署名方式
本発明のいくつかの実施形態の帯域幅縮小リング署名方式において、署名者Sは、Sがメンバーである署名者の集合{S,…,S}を選択して、検証者が、誰であるかは定められないけれども、{S,…,S}の少なくとも1人の署名者がメッセージに署名したことを検証者に確信させる、メッセージの「リング署名」を生成することができる。署名者Sは、従って、可能性のある署名者の「リング」内で限定された匿名性を有する。
【0536】
いくつかの実施形態において、署名者は、検証者がリング署名を検証するのに用いる公開法{N,…,N}を有する。リング署名は、集合的にCk,v{y,…,y}を満たすzのストリング{x,…,x}を含み、ここで、
【数200】

【数201】

【0537】
であり、v及びwは、所定のビットストリングであり、Cは、「結合関数」である。本発明のいくつかの実施形態の帯域幅縮小リング署名方式は、前述のθ準順列を用いることによって、また、法Nが異なるサイズを有することに対処するより帯域幅効率のよい方法を用いることによって、Rivest‐Shamir‐Tauman方式におけるよりも短いリング署名を実現している。
【0538】
Rivest‐Shamir‐Tauman方式(リスト10、11)において、
【数202】

【0539】
について、(q+1)N≦2であれば、y=q+g(r)を計算し、そうでなければ、
【数203】

【0540】
を計算する。ここで、gは、関数
【数204】

【0541】
を示し、bは、所定の定数である。bが十分に大きい限り、(q+1)N>2であるyの割合は、無視できるものであるので、x′のyへの写像は、Nを法とする2乗とほとんど区別できない振る舞いをする。残念ながら、bをこれほど大きいものに選ぶことは(全ての法の対数よりもはるかに大きい)、また、帯域幅効率が悪い。
【数205】

【0542】
について、
【数206】

【0543】
を計算するほうが帯域幅効率がよい。ここで、
【数207】

【0544】
本発明のいくつかの実施形態において、θ準順列に関し、bが
【数208】

【0545】
の約3分の2になるように、
【数209】

【0546】
を用いて、さらによく行うことができる。従って、あるxに対し、
【数210】

【0547】

【数211】

【0548】
とを計算することがある。結合関数は、やはり、
【数212】

【0549】
となることができ、ここで、Eは、鍵kを用いる対称暗号化方式である。
【0550】
が「真の」署名者であるとすれば、本発明のいくつかの実施形態におけるリング署名は、以下のように生成される。
【0551】
リスト30‐リング署名:
1.k=H(M)を計算する。ここで、Mは、署名するメッセージであり、Hは、ハッシュ関数である。
【0552】
2.任意のv∈{0,1}を選択する。
【0553】
3.j≠iごとに、
3A.任意の
【数213】

【0554】
を選択する。これは、C.Gentryの前述の論文において述べられているように、ランダムに一様に行うことができる。
【0555】
3B.y=g(x′)を計算する。
【0556】
4.
【数214】

【0557】
となるように、yを計算する。
【0558】
5.Nについての秘密知識を用いて、
【数215】

【0559】
となるように、
【数216】

【0560】
を計算する。
【0561】
6.全てのjについて、
【数217】

【0562】
を計算する。リスト16を参照(r値はランダムなことがあり、異なるjに対し異なることがある)。
【0563】
7.リング署名(x,…,x,v)を出力する。
【0564】
リスト30の終了。
【0565】
前述のように(リスト11)、リング署名者は、等式
【数218】

【0566】
を用いて、yの値からyを計算することができる(j≠iである)。yのいくつかの値、実際に約4分の3は、モジュラ平方根を持たない。この場合、yがNを法とする平方剰余となるまでステップ5を再び実行しなければならない。
【0567】
リスト31‐リング署名の検証:
1.k=H(M)を計算する。
【0568】
2.全てのjについて、
【数219】

【0569】
を計算する。
【0570】
3.
【数220】

【0571】
であることを確認する。
【0572】
リスト31の終了。
【0573】
上述の他の方式におけるように、リスト30のステップ6Bにおけるrは余剰ビットのソースであり、準順列の呼出しごとにランダムに、又は、準順列の他の入力(例えば、x′)に、確定的にしかし予測不可能に依存するように選ばれる。また、各署名者は、hとh′に異なる値を用いることができるが、各署名者のhとh′の値は、リング署名の検証に必要である(従って、ある意味では、公開鍵の一部である)ので、いくつかの実施形態において、全ての署名者は、同じ値を用いる。
【0574】
9.他の方式と拡張
本発明のいくつかの実施形態の圧縮及び復元方式は、暗号化、署名、集合署名、及びリング署名以外の暗号のコンテキストで有益である。例えば、本発明の圧縮及び復元方式を利用する閾値暗号化及び復号化は、暗号文のサイズが小さければより効率的になることがある。また、他の署名方式(例えば、Fiat‐Shamirのバージョン、特に、アイデンティティに基づくバージョン)や、他のアイデンティティに基づく暗号化方式(例えばCockの暗号化方式を利用するものなど)において、署名者は短い(アイデンティティに基づく)公開鍵や秘密鍵(後者はB要素)を持つことができる。さらに、モジュラ平方数を送信することに基づく識別方式は、本発明を適用することで同様に改良される。A.Fiat及びA.Shamir著、“How to Prove Yourself:Practical Solutions to Identification and Signature Problems”in Proc.of Crypt 1986,Lecture Notes in Computer Science 263,pp.186−194.Springer,1986と、U.Feige、A.Fiat及びA.Shamir著、“Zero‐Knowledge Proofs of Identity”in Jour.of Cryptology(1),pp.77‐94(1988)と、C.Cocks著、An Identity Based Encryption Scheme Based on Quadratic Residues”in Proc.of Cryptography and Coding 2001,Lecture Notes in Computer Science 2260,Springer(2001)と、A.Menezes、P.van Oorschot及びScott Vanstone著、Handbook of Applied Cryptography,Chapter 10,http://www.cacr.math.uwaterloo.ca/hac/で入手可能、を参照されたい。さらに、本発明の圧縮及び復元方式は、セキュリティがモジュラ平方根を計算することに基づく方式に対し、大域的な帯域幅効率を向上する。
【0575】
Fareyの区間に基づく圧縮及び復元方式を用いずに帯域幅縮小方式を実現することもできる。以下、本発明のかかる2つの実施形態、暗号化方式及び署名方式、を説明する。両方とも、ある状況下では、圧縮及び復元に基づく本発明の実施形態よりもさらに大きい帯域幅縮小を享受するものである(しかし、証明可能なセキュリティを失う可能性など、他の望ましい性質を犠牲にするかもしれない)。
【0576】
Coppersmithの方式を通常のRabin署名(リスト7、8)又は通常の低指数RSA署名(リスト3及び4)に適用することによって、(おそらく)帯域幅を縮小した署名方式を得ることができる。D.J.Bernstein著、“Proving Tight Security for Standard Rabin‐Williams Signatures”,http://cr.yp.to/djb.htmlで入手可能、と、D.Bleichenbacher著、“Compressed Rabin Signatures”in Proc.of CT−RSA 2004,Lecture Notes in Computer Science 2964,pp.126−128.Springer,2004と、D.Coppersmith著、“Finding a Small Root of a Univariate Modular Equation”in Proc.of Eurocrypt 1996, Lecture Notes in Computer Science,pp.155‐165.Springer‐Verlag,1996、とを参照されたい。例えば、eを、Nを法とするRabin又はRSA署名方式の公開指数とし、xを、リスト3又は7におけるように得られる通常の署名とする。Coppersmithの方式では、誰でも(Nについてのトラップドア情報を必要とすることなく)、(例えば)、x(mod N)とxの
【数221】

【0577】
最上位ビットとから、x∈[1,N]を復元することができる。従って、Rabin署名(e=2)について、図4の方法は以下のように変更することができる。
【0578】
リスト32:
1.ステップ410:H(M)を計算する。Hは、全領域関数、すなわちその値域が[1,N]である関数(例えばリスト7を参照)であることもあれば、部分領域ハッシュ関数、すなわちその値域が[1,N]の真部分集合である関数であることもある。
【0579】
2.ステップ420:x=H(M)(mod N)となるように署名x=s(M)を計算する。
【0580】
3.ステップ430:xの
【数222】

【0581】
最上位ビットを送信する。また、H(M)かH(M)を復元するのに十分な何らかの情報を送信する。
【0582】
リスト32の終了。
【0583】
しかしながら、H(M)を復元するのに十分な情報も送信しなければならないので、xの最上位ビットだけを送信することによって実現できる圧縮は、少し非現実的である。ステップ430で、H(M)自体を送信しなければならないならば、この署名方式は、明らかに望ましいメッセージ復元特性を有していない。
【0584】
N,h,h′内の数を見つけるための発見的方法を用いることによって、帯域幅縮小暗号化方式を得ることができる。ここで、h′は
【数223】

【0585】
と同じくらい小さいことがある。しかしながら、発見的抜き出し方式を用いた結果生じる暗号化方式は、証明可能なセキュリティを享受するものではない。発見的に、集合S=BN,h,h′により図10のセキュリティプルーフモデルを用いるために、
【数224】

【0586】
について、BN,h,h′内の数を以下のように生成することができる。
【0587】
リスト33:
1.任意の
【数225】

【0588】

【数226】

【0589】
を選択する。
【0590】
2.
【数227】

【0591】
を計算する。
【0592】
3.x=x′+bを計算する。
【0593】
リスト33の終了。
【数228】

【0594】
について、
【数229】

【0595】
であることを容易に示すことができる。これらの観測は、以下の暗号化方式につながる。
【0596】
リスト34:
1.メッセージを(a,b)にエンコードする。ここで、aは、メッセージの最初の2εlogNビットであり、bは、残りのビットであり、2εlogN,2εlogNは、最も近い整数に切り下げている。
【0597】
2.リスト33におけるようにxを計算する。
【0598】
3.暗号文をc=x(mod N)に設定する。
【0599】
リスト34の終了。
【数230】

【0600】
の適切なε,εについて、(a,b)を、従ってメッセージを、以下のように復元することができる。
【0601】
リスト35.
1.xをcのモジュラ平方根として計算する。
【0602】
2.
【数231】

【0603】
を計算する。
【0604】
リスト35の終了。
【0605】
この方式の考えられる1つの不利点は、因数分解から証明可能な縮小を提供するのがおそらく難しいということである。
【0606】
多くの暗号化方式及び署名方式におけるように、プロトコルの計算複雑性を増すことによって、帯域幅のさらなる縮小‐小さい定数cについて約c log log Nビット(本明細書中、特に断りのない限り、対数は底2である)‐を実現することができる。例えば、単に最終c log log Nビットを送信しないことによって、暗号文のサイズをさらに減少することができる。デクリプター(decrypter)は単に、復号化方式を、必要ならば、
【数232】

【0607】
回まで繰り返すことによって、それらの最終ビットを推測すればよい。同様に、エンクリプター(encrypter)は、一時的な暗号文が最終的に全て0である最終c log log Nビットを有するように、一時的暗号ごとに異なる乱数度を用いて、暗号化方式を期待される(logN)回行うことができ、その場合、それらのビットを送信する必要はない。署名及び検証に同様のシナリオが当てはまる。
【0608】
10.システムと構成要素
帯域幅を縮小した暗号化、署名、サインクリプション、集合署名、及びリング署名方式と、圧縮及び復元方式とは、図1のコンピュータシステム110及びネットワーク120を使用して実現することができる。各システム110は、ネットワーク(図示せず)によって相互接続された多数のコンピュータシステムを含む分散システムであってもよいしそうでなくてもよい。各システム110は、本発明の方式を実行するための、例えば半導体、磁気、光、又は他の種類の記憶装置などの公知の又は考案したコンピュータ可読媒体(図示せず)に記憶したコンピュータ命令を実行するようにプログラム化した、1つ又は複数の処理装置(図示せず)を含むことがある。さらに、又はその代わりに、各システム110は、本発明の方式を実行するためのハードワイヤード回路を含むことがある。ネットワーク120はインターネット及び/又は無線通信ネットワークや、任意の種類の通信が送信される他の種類のネットワークであることがある。本発明の方式を実現するコンピュータ命令は、ケーブル、電波、又は他の手段で、物理的信号(例えば電磁信号)に組み込まれて、システム110へ又はシステム110から送信することができる。信号は、搬送波で変調してもしなくてもよい。
【0609】
コンピュータシステム110は、本発明の暗号化、署名、サインクリプション、集合署名、又はリング署名の実施形態において用いられる公開鍵に関連する、真正性や所有権や属性を証明するための公開鍵証明書を提供することができる、サーバ証明要素(「証明者」)として使用することがある。証明者は公開鍵を別のシステム110に送信することができる。また、証明者110は、権限保持者が使用するための公開鍵及び秘密鍵を生成し、それらを圧縮暗号化形式で別のシステム110に送信することによって権限保持者に提供することができる。非証明者システム110は、証明者システム110を通じて、又は直接に、暗号文や署名を互いに送信することができる。暗号文や署名はまた、電子媒体(例えばディスク)で非電子的に(例えば通常のメールによって)転送することができる。
【0610】
いくつかの実施形態において得られる付加的な特徴が、C.Gentryによる前述の論文、How to Compress Rabin Ciphertexts and Signatures (and More)に述べられている。
【0611】
本発明は、上述の実施形態に限定されるものではない。例えば、上述の方法や、セキュリティプルーフは、集合BN,h,h′やBN,h,h′に拡張することができる。BN,h,h′はBN,h,h′からなり、BN,h,h′,BN,h,h′内の数のNを法とする負数は、1以外のNに関する公約数を有する数を除くが、Nが2つの素数の積であれば、かかる数の集合は非常に小さいことに注意されたい。いくつかの実施形態は集合BN,Q,BN,Q,BN,Qを用い、ここでQは[h,h′]以外である。特に、Qは[h,h′],(h,h′)又は(h,h′)であることがある。また、BN,Qはx=0を含まないように、すなわち{x∈[1,N]:x(mod N)∈Q}と定義することができる。本発明はセキュリティプルーフが有効である方式に限定されない。上記で、ビットストリングx=x…xn−1について、それに対応する数がx+x*2+…+xn−1*2n−1となるように、ビットストリングは数に対応付けられていたが、他の数値表現を用いることもできる。他の実施形態や変更例は、添付の請求項によって定義する本発明の範囲内にある。
【図面の簡単な説明】
【0612】
【図1】両先行技術の暗号化方式と本発明のいくつかの実施形態と共に使用するのに適したシステムのブロック図を示す。
【図2】先行技術の暗号化方式のフローチャートを示す。
【図3】先行技術の復号化方式のフローチャートを示す。
【図4】先行技術の署名方式のフローチャートを示す。
【図5】先行技術の署名検証方式のフローチャートを示す。
【図6】本発明のいくつかの実施形態による暗号化方式のフローチャートを示す。
【図7】本発明のいくつかの実施形態による復号化方式のフローチャートを示す。
【図8】本発明のいくつかの実施形態による署名方式のフローチャートを示す。
【図9】本発明のいくつかの実施形態による署名検証方式のフローチャートを示す。
【図10】Farey被覆及びFarey分割を示す。
【図11】本発明のいくつかの実施形態で用いる圧縮及び復元方式のいくつかの特徴を説明するグラフを示す。
【図12】本発明のいくつかの実施形態による復元方式のフローチャートを示す。
【図13】本発明のいくつかの実施形態による圧縮方式のフローチャートを示す。
【図14】本発明のいくつかの実施形態によるサインクリプション方式のフローチャートを示す。
【図15】本発明のいくつかの実施形態によるサインクリプション検証方式のフローチャートを示す。

【特許請求の範囲】
【請求項1】
(i)少なくとも、第1の所定長に等しい長さの暗号文やより短い暗号文を少なくとも提供する暗号化方式か、(ii)少なくとも、前記第1の所定長に等しい長さのメッセージの署名やより短いメッセージの署名を検証する署名検証方式かのどちらかである第1の方式を用いて、暗号化又は署名検証を実行するためのコンピュータ方式であって、
該方式は、コンピュータシステムにより第1のメッセージについて前記暗号化又は前記検証を実行することを含み、
前記第1のメッセージについての前記暗号化又は検証は、
(1)前記第1のメッセージについて、(i)前記第1の方式により、前記第1の所定長よりも短い暗号文に暗号化可能であるか、(ii)前記第1の所定長よりも短いメッセージのみの署名を含むかのどちらかである、所定のメッセージ集合内の第1の中間メッセージを決定し、
(2)前記第1の方式を適用して、前記第1の方式により、前記第1の中間メッセージについて暗号化又は署名検証を実行することを含み、
前記メッセージの全ては、所定の合成法Nを法とする整数として表すことができ、
前記演算(2)は、Nを法とする前記第1の中間メッセージから得られる数の平方数を計算することを含むことを特徴とするコンピュータ方式。
【請求項2】
前記法Nは、2つの素数の積であることを特徴とする請求項1に記載の方式。
【請求項3】
前記第1のメッセージは、前記第1の所定長よりも短いことを特徴とする請求項1に記載の方式。
【請求項4】
前記第1のメッセージは、全てが数h″の長さ以下の長さのメッセージである複数の第1のメッセージの1つであり、前記h″の長さは、前記第1の所定長よりも短く、前記演算(1)及び(2)は、異なる第1のメッセージを異なるメッセージに変換する変換を形成することを特徴とする請求項3に記載の方式。
【請求項5】
前記メッセージの全ては、整数として表すことができ、
前記演算(1)は、
(1A)前記第1のメッセージを、所定の区間有限集合内の区間(「第1の中間メッセージ区間」)に対応付け、
(1B)前記第1の中間メッセージを、前記第1の中間メッセージ区間内の整数となるように選択することを特徴とする請求項1に記載の方式。
【請求項6】
前記演算(1A)は、前記所定の区間有限集合内の区間にメッセージを対応付ける対応付け方式を用いて、前記第1のメッセージを対応付け、
前記対応付け方式は、少なくともいくつかの異なるメッセージを同一区間に対応付けることができることを特徴とする請求項5に記載の方式。
【請求項7】
前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項5に記載の方式。
【請求項8】
前記演算(2)は、所定の法Nを法とする前記第1の中間メッセージから得られる数の平方数を計算することを含み、
前記平方数は、(h,h′),[h,h′],(h,h′),[h,h′]の1つである所定の区間Q内にあり、
h及びh′は、所定の数であり、
前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダー
【数1】

の区間[0,N/2)に関するものであることを特徴とする請求項7に記載の方式。
【請求項9】
h′−h<8N2/3+1であることを特徴とする請求項8に記載の方式。
【請求項10】
前記第1のメッセージは、
【数2】

以下の数であることを特徴とする請求項9に記載の方式。
【請求項11】
前記演算(2)は、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージの前記暗号化を実行し、
前記演算(2)は、暗号文を提供し、
前記方式は、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージに署名する署名方式を用いて、前記暗号文に署名することをさらに含み、
前記署名演算は、
(3)前記署名方式を、前記暗号文又は前記暗号文から得られるメッセージに適用して、第2の中間メッセージを取得し、
(4)前記第2の中間メッセージについて、前記第2の所定長よりも短い署名メッセージを決定することを含むことを特徴とする請求項1に記載の方式。
【請求項12】
前記演算(2)は、前記署名検証を実行し、
前記演算(2)は、その署名が前記第1のメッセージであるメッセージM1を提供し、
前記方式は、少なくとも、第2の所定長に等しい長さの暗号文やより短い暗号文を復号化する復号化方式を用いて、前記メッセージM1を復号化することをさらに含み、
前記メッセージM1は、前記第2の所定長以下の長さのメッセージの所定の真部分値域内にあり、
前記復号化演算は、
(3)前記復号化方式を前記メッセージM1又は前記メッセージM1から得られるメッセージに適用して、第2の中間メッセージを取得し、
(4)前記第2の中間メッセージについて、前記第2の所定長よりも短い第2のメッセージを決定することを含むことを特徴とする請求項1に記載の方式。
【請求項13】
前記演算(2)は、署名検証を実行し、
前記第1のメッセージは、第2のメッセージの署名であるか、前記第2のメッセージの前記署名から得られるものであり、
前記方式は、前記演算(1)の前に、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージについて、メッセージをそれらの署名から取得する第2の方式を用いて、前記第2のメッセージから前記第1のメッセージを取得することをさらに含み、
前記第1のメッセージを取得することは、
(3)前記第2のメッセージから得られるメッセージについて、前記第2の所定長以下であるメッセージのみの署名を含む所定のメッセージ集合内の第2の中間メッセージを決定し、
(4)前記第2の方式を前記第2の中間メッセージに適用することを含むことを特徴とする請求項1に記載の方式。
【請求項14】
前記演算(2)はリング署名検証を実行し、前記第1のメッセージは複数の構成要素を含むリング署名を形成し、
前記演算(1)は、前記構成要素ごとに、所定長よりも短いメッセージのみの署名を含む所定の各メッセージ集合内の各第1の中間メッセージを決定することを含むことを特徴とする請求項1に記載の方式。
【請求項15】
(i)少なくとも、第1の所定長に等しい長さの暗号文やより短い暗号文を復号化する復号化方式か、(ii)少なくとも、前記第1の所定長に等しい長さのメッセージやより短いメッセージに署名する署名方式かのどちらかである第1の方式を用いて、復号化又は署名生成を実行するためのコンピュータ方式であって、 該方式は、コンピュータシステムによりメッセージM1について前記復号化又は前記署名生成を実行することを含み、
前記メッセージM1は、前記第1の所定長以下の長さのメッセージの所定の真部分値域内にあり、
前記復号化又は前記署名生成は、
(1)前記第1の方式を前記メッセージM1に適用して、第1の中間メッセージを取得し、
(2)前記第1の中間メッセージについて、前記第1の所定長よりも短い第1のメッセージを決定することを含み、
前記メッセージの全ては、所定の合成法Nを法とする整数として表すことができ、前記演算(1)は、Nを法とする前記メッセージM1から得られる数の平方根を計算することを含むことを特徴とするコンピュータ方式。
【請求項16】
前記法は、2つの素数の積であることを特徴とする請求項15に記載の方式。
【請求項17】
前記メッセージの全ては、整数として表すことができ、
前記演算(2)は、
(2A)前記第1の中間メッセージを、所定の区間有限集合内の区間(「第1のメッセージ区間」)に対応付け、
(2B)前記第1のメッセージを前記第1のメッセージ区間内の整数となるように選択することを含むことを特徴とする請求項15に記載の方式。
【請求項18】
前記演算(2A)は、前記所定の区間有限集合内の区間にメッセージを対応付ける対応付け方式を用いて、前記第1の中間メッセージを対応付け、
前記対応付け方式は、異なるメッセージを同一区間に対応付けることができることを特徴とする請求項17に記載の方式。
【請求項19】
前記区間は、所定の写像下のFarey区間又はFarey分割区間の像であることを特徴とする請求項17に記載の方式。
【請求項20】
前記所定の写像は、線形であることを特徴とする請求項19に記載の方式。
【請求項21】
前記演算(1)は、所定の法Nを法とする前記メッセージM1から得られる数の平方根を計算することを含み、
前記メッセージM1は、(h,h′),[h,h′],(h,h′),[h,h′]の1つである所定の区間Q内にあり、
h及びh′は、所定の数であり、
前記Farey区間又はFarey分割区間は、整数に丸められるオーダー
【数3】

の区間[0,N/2)に関するものであることを特徴とする請求項20に記載の方式。
【請求項22】
h′−h<8N2/3+1であることを特徴とする請求項21に記載の方式。
【請求項23】
前記第1のメッセージは、
【数4】

以下の数であることを特徴とする請求項22に記載の方式。
【請求項24】
前記演算(1)は、署名生成を実行し、
前記第1の中間メッセージは、署名であり、
前記方式は、少なくとも、第2の所定長に等しい長さの暗号文やより短い暗号文を提供する暗号化方式である第2の方式を用いて暗号化を実行することをさらに含み、
前記暗号化は、
(3)前記第1のメッセージから得られるメッセージについて、前記第2の方式により、前記第2の所定長よりも短い暗号文に暗号化可能である所定のメッセージ集合内の第2の中間メッセージを決定し、
(4)前記第2の方式を適用して、前記第2の方式により前記第2の中間メッセージについて暗号化を実行することを含むことを特徴とする請求項15に記載の方式。
【請求項25】
前記演算(1)は、復号化を実行し、
前記方式は、少なくとも、第2の所定長に等しい長さのメッセージの署名やより短いメッセージの署名を検証する署名検証方式である第2の方式を用いて署名検証を実行することをさらに含み、
前記方式は、コンピュータシステムにより前記第1のメッセージについて前記検証を実行することを含み、
前記第1のメッセージについての前記検証は、
(3)前記第1のメッセージから得られるメッセージについて、前記第2の所定長よりも短いメッセージのみの署名を含む所定のメッセージ集合内の第2の中間メッセージを決定し、
(4)前記第2の方式を適用して、前記第2の方式により前記第2の中間メッセージについて署名検証を実行することを含むことを特徴とする請求項15に記載の方式。
【請求項26】
前記演算(1)は、署名生成を実行し、
前記第1の中間メッセージは、第1の署名であり、
前記方式は、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージに署名する第2の方式を用いて前記第1のメッセージに署名することをさらに含み、
前記第1のメッセージに署名することは、
(3)前記第1のメッセージ又は前記第1のメッセージから得られるメッセージに前記第2の方式を適用して、第2の中間メッセージを取得し、
(4)前記第2の中間メッセージについて、前記第2の所定長よりも短い署名メッセージを決定することを含むことを特徴とする請求項15に記載の方式。
【請求項27】
前記演算(1)は、リング署名生成を実行し、
前記第1の中間メッセージは、複数の構成要素を含む署名を形成し、
前記演算(2)は、前記構成要素ごとに、前記構成要素に対応する所定長よりも短いメッセージを決定することを含むことを特徴とする請求項15に記載の方式。
【請求項28】
所定の合成法Nを法とする整数として表すことができる第1のメッセージについて、Nを法とする前記整数の全ての集合Zの所定の真部分値域内に、Nを法とする平方数が存在するメッセージ集合内の第2のメッセージを決定するためのコンピュータ方式であって、
前記第1のメッセージを前記第2のメッセージに写像することは、
(1)前記第1のメッセージを、所定の区間有限集合内の区間(「第2のメッセージ区間」)に対応付け、
(2)前記第2のメッセージを前記第2のメッセージ区間内の整数となるように選択することを含むことを特徴とするコンピュータ方式。
【請求項29】
前記法は、2つの素数の積であることを特徴とする請求項28に記載の方式。
【請求項30】
前記第1のメッセージは、全てが数h″以下の長さの複数のメッセージの1つであり、
前記数h″は、Nよりも小さいことを特徴とする請求項28に記載の方式。
【請求項31】
前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項28に記載の方式。
【請求項32】
前記所定の真部分値域は、(h,h′),[h,h′],(h,h′),[h,h′]の1つであり、
h及びh′は、所定の数であり、
前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダー
【数5】

の区間[0,N/2)に関するものであることを特徴とする請求項28に記載の方式。
【請求項33】
h′−h<8N2/3+1であることを特徴とする請求項32に記載の方式。
【請求項34】
前記第1のメッセージは、
【数6】

以下の数であることを特徴とする請求項33に記載の方式。
【請求項35】
Nを法とする前記第2のメッセージを2乗して、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージを暗号化することをさらに含むことを特徴とする請求項28に記載の方式。
【請求項36】
前記第1のメッセージは、署名又は署名のエンコードを表し、
前記方式は、Nを法とする前記第2のメッセージを2乗して前記署名を検証することをさらに含むことを特徴とする請求項28に記載の方式。
【請求項37】
所定の合成法Nを法とする整数として表すことができる第1のメッセージを、Nを法とする前記整数の全ての集合Zの所定の真部分値域内に、Nを法とする平方数が存在するメッセージ集合内の第2のメッセージから取得するためのコンピュータ方式であって、
前記方式は、
(1)前記第2のメッセージを、所定の区間有限集合内の区間(「第1のメッセージ区間」)に対応付け、
(2)前記第1のメッセージを前記第1のメッセージ区間内の整数となるように選択することを含むことを特徴とするコンピュータ方式。
【請求項38】
前記法は、2つの素数の積であることを特徴とする請求項37に記載の方式。
【請求項39】
前記第1のメッセージは、全てが数h″の長さ以下の長さの複数のメッセージの1つであり、
前記数h″は、Nよりも小さいことを特徴とする請求項37に記載の方式。
【請求項40】
前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項37に記載の方式。
【請求項41】
前記所定の真部分値域は、(h,h′),[h,h′],(h,h′),[h,h′]の1つであり、
h及びh′は、所定の数であり、
前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダー
【数7】

の区間[0,N/2)に関するものであることを特徴とする請求項40に記載の方式。
【請求項42】
h′−h<8N2/3+1であることを特徴とする請求項41に記載の方式。
【請求項43】
前記第1のメッセージは、
【数8】

以下の数であることを特徴とする請求項42に記載の方式。
【請求項44】
第3のメッセージのNを法とする平方根を計算して、前記第2のメッセージを計算することをさらに含み、
前記第3のメッセージは、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージに対応する暗号文であることを特徴とする請求項37に記載の方式。
【請求項45】
第3のメッセージ又は前記第3のメッセージから得られるメッセージのNを法とする平方根を計算して、前記第2のメッセージを取得することをさらに含み、
前記第1のメッセージは、前記第3のメッセージ又は前記第3のメッセージにエンコードされたメッセージに対応する署名であることを特徴とする請求項37に記載の方式。
【請求項46】
請求項1に記載の方式を実行するためのコンピュータシステム。
【請求項47】
請求項1に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。
【請求項48】
請求項1に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。
【請求項49】
請求項15に記載の方式を実行するためのコンピュータシステム。
【請求項50】
請求項15に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。
【請求項51】
請求項15に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。
【請求項52】
請求項28に記載の方式を実行するためのコンピュータシステム。
【請求項53】
請求項28に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。
【請求項54】
請求項28に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。
【請求項55】
請求項37に記載の方式を実行するためのコンピュータシステム。
【請求項56】
請求項37に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。
【請求項57】
請求項37に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10A】
image rotate

【図10B】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate


【公表番号】特表2007−510380(P2007−510380A)
【公表日】平成19年4月19日(2007.4.19)
【国際特許分類】
【出願番号】特願2006−538330(P2006−538330)
【出願日】平成16年10月29日(2004.10.29)
【国際出願番号】PCT/US2004/036053
【国際公開番号】WO2005/043326
【国際公開日】平成17年5月12日(2005.5.12)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Fターム(参考)】