"i少なくとも、第1の所定長に等しい長さの暗号文やより短い暗号文を少なくとも提供する暗号化方式か、ii少なくとも、前記第1の所定長に等しい長さのメッセージの署名やより短いメッセージの署名を検証する署名検証方式かのどちらかである第1の方式を用いて、暗号化又は署名検証を実行するためのコンピュータ方式であって、該方式は、コンピュータシステムにより第1のメッセージについて前記暗号化又は前記検証を実行することを含み、前記第1のメッセージについての前記暗号化又は検証は、1前記第1のメッセージについて、i前記第1の方式により、前記第1の所定長よりも短い暗号文に暗号化可能であるか、ii前記第1の所定長よりも短いメッセージのみの署名を含むかのどちらかである、所定のメッセージ集合内の第1の中間メッセージを決定し、2前記第1の方式を適用して、前記第1の方式により、前記第1の中間メッセージについて暗号化又は署名検証を実行することを含み、前記メッセージの全ては、所定の合成法Nを法とする整数として表すことができ、前記演算2は、Nを法とする前記第1の中間メッセージから得られる数の平方数を計算することを含むことを特徴とするコンピュータ方式。前記法Nは、2つの素数の積であることを特徴とする請求項1に記載の方式。前記第1のメッセージは、前記第1の所定長よりも短いことを特徴とする請求項1に記載の方式。前記第1のメッセージは、全てが数h′′の長さ以下の長さのメッセージである複数の第1のメッセージの1つであり、前記h′′の長さは、前記第1の所定長よりも短く、前記演算1及び2は、異なる第1のメッセージを異なるメッセージに変換する変換を形成することを特徴とする請求項3に記載の方式。前記メッセージの全ては、整数として表すことができ、前記演算1は、1A前記第1のメッセージを、所定の区間有限集合内の区間第1の中間メッセージ区間に対応付け、1B前記第1の中間メッセージを、前記第1の中間メッセージ区間内の整数となるように選択することを特徴とする請求項1に記載の方式。前記演算1Aは、前記所定の区間有限集合内の区間にメッセージを対応付ける対応付け方式を用いて、前記第1のメッセージを対応付け、前記対応付け方式は、少なくともいくつかの異なるメッセージを同一区間に対応付けることができることを特徴とする請求項5に記載の方式。前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項5に記載の方式。前記演算2は、所定の法Nを法とする前記第1の中間メッセージから得られる数の平方数を計算することを含み、前記平方数は、h,h′,[h,h′],h,h′,[h,h′]の1つである所定の区間Q内にあり、h及びh′は、所定の数であり、前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダーの区間[0,N/2に関するものであることを特徴とする請求項7に記載の方式。h′-h<8N2/31であることを特徴とする請求項8に記載の方式。前記第1のメッセージは、以下の数であることを特徴とする請求項9に記載の方式。前記演算は、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージの前記暗号化を実行し、前記演算は、暗号文を提供し、前記方式は、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージに署名する署名方式を用いて、前記暗号文に署名することをさらに含み、前記署名演算は、3前記署名方式を、前記暗号文又は前記暗号文から得られるメッセージに適用して、第2の中間メッセージを取得し、4前記第2の中間メッセージについて、前記第2の所定長よりも短い署名メッセージを決定することを含むことを特徴とする請求項1に記載の方式。前記演算2は、前記署名検証を実行し、前記演算2は、その署名が前記第1のメッセージであるメッセージM1を提供し、前記方式は、少なくとも、第2の所定長に等しい長さの暗号文やより短い暗号文を復号化する復号化方式を用いて、前記メッセージM1を復号化することをさらに含み、前記メッセージM1は、前記第2の所定長以下の長さのメッセージの所定の真部分値域内にあり、前記復号化演算は、3前記復号化方式を前記メッセージM1又は前記メッセージM1から得られるメッセージに適用して、第2の中間メッセージを取得し、4前記第2の中間メッセージについて、前記第2の所定長よりも短い第2のメッセージを決定することを含むことを特徴とする請求項1に記載の方式。前記演算は、署名検証を実行し、前記第1のメッセージは、第2のメッセージの署名であるか、前記第2のメッセージの前記署名から得られるものであり、前記方式は、前記演算の前に、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージについて、メッセージをそれらの署名から取得する第2の方式を用いて、前記第2のメッセージから前記第1のメッセージを取得することをさらに含み、前記第1のメッセージを取得することは、3前記第2のメッセージから得られるメッセージについて、前記第2の所定長以下であるメッセージのみの署名を含む所定のメッセージ集合内の第2の中間メッセージを決定し、4前記第2の方式を前記第2の中間メッセージに適用することを含むことを特徴とする請求項1に記載の方式。前記演算はリング署名検証を実行し、前記第1のメッセージは複数の構成要素を含むリング署名を形成し、前記演算1は、前記構成要素ごとに、所定長よりも短いメッセージのみの署名を含む所定の各メッセージ集合内の各第1の中間メッセージを決定することを含むことを特徴とする請求項1に記載の方式。i少なくとも、第1の所定長に等しい長さの暗号文やより短い暗号文を復号化する復号化方式か、ii少なくとも、前記第1の所定長に等しい長さのメッセージやより短いメッセージに署名する署名方式かのどちらかである第1の方式を用いて、復号化又は署名生成を実行するためのコンピュータ方式であって、該方式は、コンピュータシステムによりメッセージM1について前記復号化又は前記署名生成を実行することを含み、前記メッセージM1は、前記第1の所定長以下の長さのメッセージの所定の真部分値域内にあり、前記復号化又は前記署名生成は、1前記第1の方式を前記メッセージM1に適用して、第1の中間メッセージを取得し、2前記第1の中間メッセージについて、前記第1の所定長よりも短い第1のメッセージを決定することを含み、前記メッセージの全ては、所定の合成法Nを法とする整数として表すことができ、前記演算1は、Nを法とする前記メッセージM1から得られる数の平方根を計算することを含むことを特徴とするコンピュータ方式。前記法は、2つの素数の積であることを特徴とする請求項15に記載の方式。前記メッセージの全ては、整数として表すことができ、前記演算は、2A前記第1の中間メッセージを、所定の区間有限集合内の区間第1のメッセージ区間に対応付け、2B前記第1のメッセージを前記第1のメッセージ区間内の整数となるように選択することを含むことを特徴とする請求項15に記載の方式。前記演算は、前記所定の区間有限集合内の区間にメッセージを対応付ける対応付け方式を用いて、前記第1の中間メッセージを対応付け、前記対応付け方式は、異なるメッセージを同一区間に対応付けることができることを特徴とする請求項17に記載の方式。前記区間は、所定の写像下のFarey区間又はFarey分割区間の像であることを特徴とする請求項17に記載の方式。前記所定の写像は、線形であることを特徴とする請求項19に記載の方式。前記演算は、所定の法Nを法とする前記メッセージM1から得られる数の平方根を計算することを含み、前記メッセージM1は、h,h′,[h,h′],h,h′,[h,h′]の1つである所定の区間Q内にあり、h及びh′は、所定の数であり、前記Farey区間又はFarey分割区間は、整数に丸められるオーダーの区間[0,N/2に関するものであることを特徴とする請求項20に記載の方式。h′-h<8N2/31であることを特徴とする請求項21に記載の方式。前記第1のメッセージは、以下の数であることを特徴とする請求項22に記載の方式。前記演算1は、署名生成を実行し、前記第1の中間メッセージは、署名であり、前記方式は、少なくとも、第2の所定長に等しい長さの暗号文やより短い暗号文を提供する暗号化方式である第2の方式を用いて暗号化を実行することをさらに含み、前記暗号化は、3前記第1のメッセージから得られるメッセージについて、前記第2の方式により、前記第2の所定長よりも短い暗号文に暗号化可能である所定のメッセージ集合内の第2の中間メッセージを決定し、4前記第2の方式を適用して、前記第2の方式により前記第2の中間メッセージについて暗号化を実行することを含むことを特徴とする請求項15に記載の方式。前記演算は、復号化を実行し、前記方式は、少なくとも、第2の所定長に等しい長さのメッセージの署名やより短いメッセージの署名を検証する署名検証方式である第2の方式を用いて署名検証を実行することをさらに含み、前記方式は、コンピュータシステムにより前記第1のメッセージについて前記検証を実行することを含み、前記第1のメッセージについての前記検証は、3前記第1のメッセージから得られるメッセージについて、前記第2の所定長よりも短いメッセージのみの署名を含む所定のメッセージ集合内の第2の中間メッセージを決定し、4前記第2の方式を適用して、前記第2の方式により前記第2の中間メッセージについて署名検証を実行することを含むことを特徴とする請求項15に記載の方式。前記演算1は、署名生成を実行し、前記第1の中間メッセージは、第1の署名であり、前記方式は、少なくとも、第2の所定長に等しい長さのメッセージやより短いメッセージに署名する第2の方式を用いて前記第1のメッセージに署名することをさらに含み、前記第1のメッセージに署名することは、3前記第1のメッセージ又は前記第1のメッセージから得られるメッセージに前記第2の方式を適用して、第2の中間メッセージを取得し、4前記第2の中間メッセージについて、前記第2の所定長よりも短い署名メッセージを決定することを含むことを特徴とする請求項15に記載の方式。前記演算は、リング署名生成を実行し、前記第1の中間メッセージは、複数の構成要素を含む署名を形成し、前記演算は、前記構成要素ごとに、前記構成要素に対応する所定長よりも短いメッセージを決定することを含むことを特徴とする請求項15に記載の方式。所定の合成法Nを法とする整数として表すことができる第1のメッセージについて、Nを法とする前記整数の全ての集合ZNの所定の真部分値域内に、Nを法とする平方数が存在するメッセージ集合内の第2のメッセージを決定するためのコンピュータ方式であって、前記第1のメッセージを前記第2のメッセージに写像することは、1前記第1のメッセージを、所定の区間有限集合内の区間第2のメッセージ区間に対応付け、2前記第2のメッセージを前記第2のメッセージ区間内の整数となるように選択することを含むことを特徴とするコンピュータ方式。前記法は、2つの素数の積であることを特徴とする請求項28に記載の方式。前記第1のメッセージは、全てが数h′′以下の長さの複数のメッセージの1つであり、前記数h′′は、Nよりも小さいことを特徴とする請求項28に記載の方式。前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項28に記載の方式。前記所定の真部分値域は、h,h′,[h,h′],h,h′,[h,h′]の1つであり、h及びh′は、所定の数であり、前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダーの区間[0,N/2に関するものであることを特徴とする請求項28に記載の方式。h′-h<8N2/31であることを特徴とする請求項32に記載の方式。前記第1のメッセージは、以下の数であることを特徴とする請求項33に記載の方式。Nを法とする前記第2のメッセージを2乗して、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージを暗号化することをさらに含むことを特徴とする請求項28に記載の方式。前記第1のメッセージは、署名又は署名のエンコードを表し、前記方式は、Nを法とする前記第2のメッセージを2乗して前記署名を検証することをさらに含むことを特徴とする請求項28に記載の方式。所定の合成法Nを法とする整数として表すことができる第1のメッセージを、Nを法とする前記整数の全ての集合ZNの所定の真部分値域内に、Nを法とする平方数が存在するメッセージ集合内の第2のメッセージから取得するためのコンピュータ方式であって、前記方式は、1前記第2のメッセージを、所定の区間有限集合内の区間第1のメッセージ区間に対応付け、2前記第1のメッセージを前記第1のメッセージ区間内の整数となるように選択することを含むことを特徴とするコンピュータ方式。前記法は、2つの素数の積であることを特徴とする請求項37に記載の方式。前記第1のメッセージは、全てが数h′′の長さ以下の長さの複数のメッセージの1つであり、前記数h′′は、Nよりも小さいことを特徴とする請求項37に記載の方式。前記区間は、Farey区間又はFarey分割区間であることを特徴とする請求項37に記載の方式。前記所定の真部分値域は、h,h′,[h,h′],h,h′,[h,h′]の1つであり、h及びh′は、所定の数であり、前記Farey区間又は前記Farey分割区間は、整数に丸められるオーダーの区間[0,N/2に関するものであることを特徴とする請求項40に記載の方式。h′-h<8N2/31であることを特徴とする請求項41に記載の方式。前記第1のメッセージは、以下の数であることを特徴とする請求項42に記載の方式。第3のメッセージのNを法とする平方根を計算して、前記第2のメッセージを計算することをさらに含み、前記第3のメッセージは、前記第1のメッセージ又は前記第1のメッセージにエンコードされたメッセージに対応する暗号文であることを特徴とする請求項37に記載の方式。第3のメッセージ又は前記第3のメッセージから得られるメッセージのNを法とする平方根を計算して、前記第2のメッセージを取得することをさらに含み、前記第1のメッセージは、前記第3のメッセージ又は前記第3のメッセージにエンコードされたメッセージに対応する署名であることを特徴とする請求項37に記載の方式。請求項1に記載の方式を実行するためのコンピュータシステム。請求項1に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。請求項1に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。請求項15に記載の方式を実行するためのコンピュータシステム。請求項15に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。請求項15に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。請求項28に記載の方式を実行するためのコンピュータシステム。請求項28に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。請求項28に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。請求項37に記載の方式を実行するためのコンピュータシステム。請求項37に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とするコンピュータ可読媒体。請求項37に記載の方式を実行することができる1つ又は複数のコンピュータ命令を含むことを特徴とする物理的信号。この項では、本発明のいくつかの特徴を要約する。他の特徴は、後の項で説明する。本発明は、添付の請求項により定義され、該請求項は、参照によりこの項に含まれる。本発明のいくつかの実施形態によれば、暗号化の前にメッセージを処理して、暗号文を短くする。典型的な処理を、図6のステップ610に示す。ステップ210エンコード、220暗号化及び230送信は、図2のようであることがある。特に、暗号化方式220は、ある所定長に等しい長さ例えば、N-1以下の数の長さ、ここで、Nは、Rabin暗号化の場合の法であるの暗号文や、より短い暗号文や、場合によっては、より長い暗号文を提供することができる。ステップ210エンコードの後、写像ステップ610を実行して、エンコードされたメッセージHMを所定の集合Bの中間数bに写像する。写像はπと示す。集合Bは、暗号化方式220がそれについて短い暗号文を生成するあるメッセージの集合である。いくつかの実施形態では、ステップ220でRabin暗号化方式を使用する、すなわちc=b2modN。いくつかの実施形態において、B=BN,Q={x∈[1,N]:x2modN∈Q}であり、ここで、Qは、Nを法とする全ての整数の真部分集合である。いくつかの実施形態では、Qは、h′-h<Nとなるような、ある整数h,h′に関する部分値域[h,h′]である。これらのQに関し、集合BN,Qは、BN,h,h′と示す。従って、BN,h,h′={x∈[1,N]:h≦x2modN≦h′}。Nを法とする全ての整数の集合ZNの数は、公知の方法で円の上の点として示すことができる。部分値域[h,h′]は、集合{h,h1,...h′}か、集合{h′,h′1,...h}かである。曖昧さを避けるために、本明細書中、異なる意味が明白に記載されているか、文脈から明らかである場合を除いて、[h,h′]は、2つの部分値域の内、一番小さいものであるとする。特に、h′は、hよりも小さい数によって示すことがある。例えば、h=N-1=-1modNで、h′=1であるならば、[h,h′]={N-1,N,1}={N-1,0,1}である。h′-hが与えられると、数h,h′にとってよい選択は、h=0又は-h=h′である。なぜなら、幅h′-hの部分値域の内、0に近い部分値域は、最も短いビット長の数を有するからである。いくつかの実施形態において、BN,QがB2N,Q={x∈[0,N/2]:x2modN∈Q}か、BZN,Q={x∈ZN:x2modN∈Q}によって置き換えられる場合、同様の結果が得られる。ここで、ZNは、Nを法として可逆であるすなわち、Nに対し公約数を持たない全ての整数の集合x∈[0,N/2]である。Q=[h,h′]であれば、B2N,Qは、B2N,h,h′と示され、BZN,Qは、BZN,h,h′と示される。いくつかの実施形態において、h′′<Nのある区間[0,h′′]において、エンコードされたメッセージHMは、短いメッセージである。また、写像πをステップ610でプレーンテキストMに適用してMをbに写像することで、エンコードステップ210図6は省略することができる。プレーンテキストMは、[0,h′′]に含まれることがある。用語に関して、写像ステップ210が存在しても、プレーンテキストMをある数b∈Bに変換するステップ210、610の組み合わせを述べるのにエンコードという表現を用いることができる。復号化図7は、暗号化処理の逆となることがある。図3のように短い暗号文cは、ステップ304で受信者が受信し、ステップ310で復号化して中間メッセージb∈Bを復元する。復号化方式310では、ある所定長に等しい長さ例えば、N-1以下の数の長さ、ここでNはRabin復号化の場合の法であるの暗号文や、より短い暗号文や、場合によってはより長い暗号文を復号化することができる。ステップ710で逆写像π-1を適用して、bをHMに写像する。次に、HMをデコードしてステップ320プレーンテキストMを復元する。本発明のいくつかの実施形態において、短い署名が提供される。図8に、1つの署名方式の実施形態を示す。図4のように、ステップ410で、メッセージMをHMにエンコードする。いくつかの実施形態において、メッセージHMは、上述の部分値域[h,h′]にある。ステップ420で、署名方式を適用してメッセージに署名し、中間署名bを得る。この署名方式例えばモジュラ平方根計算は、所定の長さ以下の長さや、場合によっては、より長い全てのメッセージHMに適応する。ステップ410、420は、先行技術におけるようなものであっても良いし、そうでなくてもよい。いくつかの実施形態は、OAEPエンコードのRabin署名を用いる。しかしながら、中間署名bは、上述のタイプの集合Bにある。いくつかの実施形態において、これは、メッセージMを、エンコードHMがBに署名を有するメッセージの集合に限定することによって得られる。いくつかの実施形態において、エンコードされたメッセージHMは、短くある所定の長さよりも短い、例えば、あるh′′<Nに関してHM∈[0,h′′]であり、署名方式420では、短いメッセージを集合Bに写像する。中間署名bは、長いビットストリングであってもよいことに注目されたい。ステップ810で、写像θを適用して中間署名bを、短い署名sに写像する。ステップ430で、署名sを受信者に送信する。署名検証を、図9に示す。ステップ504で、短い署名sは、受信者コンピュータシステム110で受信される。ステップ910で、逆写像θ-1を適用して、中間署名bを復元する。ステップ510、520で、検証を実行する。例えば、ステップ510で、中間署名を処理してHMを復元することができる。ステップ520で、図5のステップ520におけるように検証を実行することができる。ステップ510、520の方法は、ある所定長に等しい長さ例えば数N-1の長さ、ここで、Nは、法であるのメッセージHMの署名や、より短いメッセージHMの署名や、場合によっては、より長いメッセージHMの署名を検証するのに適している。いくつかの実施形態において、集合Bは、全てのメッセージの集合よりも濃度が低いが、Bの個々のメッセージは、エンコードされたメッセージHMよりも長いことがある。このため、写像π-1とθは、一般的に圧縮と呼び、写像πとθ-1は、復元と呼ぶ。本発明は、実際の圧縮又は復元が起こる場合、すなわち、写像π-1又はθが各数をそれより短い数に写像するか、写像π又はθ-1が各数をそれより長い数に写像する実施形態に限定されない。いくつかの公開鍵暗号化及び署名の実施形態において、暗号文と署名のサイズは、通常のlog2Nビットではなく、最大でも約2/3log2Nビットである。同時に、圧縮及び署名方式のセキュリティは、かなり大きいlog2Nビットの数Nを因数分解することに基づく。いくつかの実施形態において、h′-hが、約8N2/3以上である時、小さい定数c1に関して、写像θは、B2N,h,h′内の数を長さc1log2h′-hのビットストリングに写像する。いくつかの実施形態では、c1≦3である。いくつかの実施形態において、写像πは長さ-c2log2h′-hのビットストリングを、B2N,h,h′内の数に写像する。ここで、c2は、小さい定数である。いくつかの実施形態において、c2=log25≦3である。いくつかの公開鍵暗号化及び署名の実施形態において、両写像は、公開されている。すなわち、写像と、それらの逆は、秘密情報を必要とすることなく効率的に計算することができる。いくつかの実施形態において、帯域幅縮小サインクリプション方式を提供する。送信者は、送信者の公開鍵NAと受信者の公開鍵NBに関連して用いられる、例えば、θAやθBなどの、2つのバージョンのθ写像を使用する。NAとNBは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、サインクリプションは、構造c1log2h′-hビット長である。このサインクリプションは、同時に、受信者が解読できるようにメッセージを暗号化し、メッセージに対する送信者の署名を含める。受信者は、送信者の公開鍵を用いて検証することができる。いくつかの実施形態において、帯域幅縮小集合署名方式を提供する。署名者{S1,...,SZ}は、公開鍵{N1,...,NZ}を有し、メッセージ{M1,...,MZ}に順に署名する。これは、署名者Siが、Si-1からsi-1を受信した後にMiの署名siを生成することを意味する。鍵Niは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、各si-1は、Bの要素のθi-1によって圧縮された表現であり、ここで、Bは、iに依存することもあればそうでないこともある。例えば、Bは、B2N,h,h′であることもある。ここで、N、h及びh′は、iに依存することもあればそうでないこともあり、siは、基本的に[h,h′]の数のNiを法とする圧縮平方根として計算される。その数は、si-1とMiに依存する。いくつかの実施形態において、帯域幅縮小リング署名方式を提供する。いくつかの実施形態において、Rivest‐Shamir‐Taumanリング署名方式が、本発明の圧縮方式を、本発明の他の手法と組み合わせて用いて、上記リスト9のの値を短くできるようにすることによって改良されている。本発明の他の特徴や利点について、以下に述べる。本発明は、添付の請求項によって定義される。1.前置き後の説明では、いくつかの数学的表記を用いるが、その多くを便宜上ここに集める。{0,1}を全てのビットストリングの集合を示すものとし、{0,1}nを長さnの全てのビットストリングの集合を示すものとする。後者の表現は、また、n以下の長さの全てのビットストリングの集合を示す。ストリング長が、nよりも小さい場合、該ストリングは、左側に0を付け加えることで長さnにすることができる。通常、Hは、暗号ハッシュ関数及び/又はエンコードされたメッセージを示す。例えば、SHA‐1やMD5など、様々な暗号ハッシュ関数が、当技術で公知である例えば、RFC‐2104,RequestforComments,NetworkingWorkingGroup,H.Krawczyketal.,HMAC:Keyed‐HashingforMessageAuthentication,1997年2月、参照により本明細書に含む、を参照。ハッシュ関数が耐衝突性であること、すなわち、Hm1=Hm2となるようなm1≠m2を見つけるのが計算上難しいことが望ましい。実数rに関して、は、rの天井、すなわち、r以上の最小の整数値を示す。同様に、は、rの床、すなわち、r以下の最大の整数値を示す。最後には、rに最も近い整数を示す。記号∥は、連結を示す。本明細書中、Nは、整数法を示す。有効なセキュリティのために、Nは、因数分解が計算上難しいものであるべきである。実際には、Nを2つの大きい素数p及びq、例えば、各々512ビット、の積として生成することが多い。しかしながら、暗号文献に見られるように、d>1として、N=pdqに設定すると、効率的利点があることが多い。本発明の方式では、Nは、任意の形式をとれる。しかしながら、後の説明では、便宜上、N=pqとする。格子は、基底ベクトルの集合の整数線形結合として生成することができる全てのベクトルの集合からなる。例えば、a,b及びc,dが二次元空間において2つの基底ベクトルである場合、それらによって生成される格子は、ベクトル{k1ak2c,k1bk2d:k1,k2∈Z}の集合である。Zは、全ての整数の集合である。2.追加の前置き:B2N,h,h′内の数の分布Nを法とする平方剰余が一様に分布していたならば、B2N,h,h′は、およそh′-h個の数を含むと予想される。差し当たりB2N,h,h′が、h′-h個の数を含むとすれば、情報理論の観点から、ビットを用いて、B2N,h,h′内の各数を一意に示すことは可能である。しかしながら、B2N,h,h′内の数は、ランダムに見えるように、区間[1,N/2]にわたって分散しており、従って、効率的に、つまり、計算の複雑性が小さい定数cに対し最大でOlogNcである方法を用いて、ある数の一意の表示を計算することができるかは少しも明らかではない。文字cは、定数と暗号文の両方に用いるが、これら2つの使用は混同すべきでない。B2N,h,h′の局所分布の解析効率的に計算でき可逆であるB2N,h,h′内の数の簡潔な表示を作成するために、B2N,h,h′内の数がどのように[1,N/2]に分布しているかを理解するのが望ましい。この分布は、参照により本明細書に含まれる、B.Vallee著、ProvablyFastIntegerFactoringwithQuasi‐UniformSmallQuadraticResiduesProc.ofSTOC1989,98‐106ページによって、因数分解問題数Nの素因数を見つける問題に関連して、-h=h′=4N2/3について研究されている。Valleeは、-h=h′=4N2/3について、B2N,h,h′内の数の分布を解析した。彼女の観測を用いて、証明可能に低い計算の複雑性を有する複雑性は、やはりまだ高くて、非常に大きい数例えば、1024ビットを因数分解することはできないが因数分解方式が、B=B2N,h,h′から擬一様に数を抜き出すサブルーチンを用いて、すなわち、ある定数cについて、所定の数が引き出される確率が、他の数が選択される確率のc倍以内であるようにして、開発された。Valleeは本発明によって利用されるような圧縮方式を開発しておらず、確かに、Valleeの因数分解方式の論考では、かかる圧縮方式は無意味であるようだが、ValleeのB2N,h,h′の分布についての観測は有用である。Valleeの観測のいくつかを以下に列挙する。Farey数列:オーダーkのFarey数列Fkは、a1=0を除いて、1≦ai≦bi≦k及びgcdai,bi=1である、分数の昇列である。gcdの表現は、最大公約数を表す。Farey数列の性質は、以下の定理で表される。定理1.Fkにおいて、とが連続していれば、biai1-aibi1=1である。Farey数列に関する他の有用な定理は、以下のとおりである。定理2.Fkにおいて、とが連続していれば、bibi1>Kである。Farey数列は、自然に、Farey被覆の概念につながる。Farey被覆:区間[0,N/2]のオーダーkのFarey被覆は、開Farey区間Iai,biの集合であり、ここでi=0,1,2,...であり、各区間Iai,biは、中心と、半径とを有し、ここで、a1=0を除いて、1≦ai≦bi≦k及びgcdai,bi=1である。図10Aは、Farey被覆を示している。上記定理1及び2を用いて、[0,N/2]内の全ての実数が少なくとも1つの、多くて2つのFarey区間によって被覆されていることを容易に証明できる。後の論述は、また、図10Bに示すFarey分割を用いるが、Farey被覆と密接な関係がある。Farey分割:区間[0,N/2]のオーダーkのFarey分割は、区間の集合であり、ここで、i=0,1,2,...であり、a0=a-1=b-1=0を除いて、1≦ai≦bi≦k、gcdai,bi=1である。Farey分割区間は、左側で閉じているが端点を含む、右側で閉じており左側で開いていると定義することもできる。ここで、区間は交わらず、0を被覆しないように定義されるが、これは必然ではない。区間Jai,biは、N/2に隣接する小さい区間を除く[0,N/2]の全てを被覆する分割を形成し、図10BではJaf,bfとして示し、ここで、fは、ai,biに対する最大のi添数である。従って、af=bf=1である。af1=bf1=0と定義するならば、Jaf,bfは、一般式8により定義できる。再び定理1及び2を用いることによって、Iai,biがJai,biを含むことを証明することができる。また、区間Iai,biは、区間Jai,biの2倍以内の幅である。Farey数列は、B2N,h,h′内の整数の[0,N/2]内の分布に密接な関係がある。特に、Bの連続する要素間の空隙は、小さい分母biの有理数aiN/2biに近い大きな変分がある。しかしながら、aiN/2biを中心とするもっと広い値域を考えると、B要素の分布は一様になる、すなわち、該区間のB要素の数と、Bが一様に分布していた場合に予測される数との比率は、1に近づく。概略を言うと、固まりが無視できるようになるのに必要な区間幅は、biに反比例し、従って、上記で定義したFarey区間とBの要素の分布との関係である。Valleeは、以下の定理を証明した。定理3.-h=h′=4N2/3と、に関し、部分集合B2N,h,h′とオーダーkのFarey被覆は、準独立である。準独立という用語は、以下のように定義される。部分集合XとZNZNは、Nを法とする全ての整数の集合を示すの被覆Y={Yj}は、全てのjについて、集合XとYjが、ある正の定数l1とl2に対しl1,l2独立である、すなわちであれば、準独立である。Pは、集合ZNについての一様確率測度である。h′=4N2/3であり、Fareyオーダーk=1/4N1/3であるB2N,h,h′に関し、Valleeは、と、l2=4が満たされることを証明する。この定理を証明するためのValleeの方法は、ある意味、建設的である。Bの要素がFarey区間内で、すなわち局所的にどのように構成されているかを詳しく見ることによって、Valleeは、区間のB要素の数について上限及び下限を与える、これらの要素の概略計数を提供することができる。この概略計数を用いて、Valleeは、擬一様にFarey区間に存在するBから要素を選択する方法を提供する。形式上、一様確率Pと、ZNの部分集合X内の値を有する有限集合Uに対し定義される抜き出し方式Cは、全てのx∈Xに関し、であれば、l1,l2一様又は擬一様であるといわれる。Bの要素が、擬一様にFarey区間中に分布しているとすれば、これは直接擬一様に[1,N]内のBから要素を選択する大域的な方式につながる。擬一様な分布で、Farey区間Iai,biにあるB2N,h,h′内の数を選択したいものとする。Valleeは、h′=4N2/3としてB2N,h,h′∩Iai,biに存在する整数を、これらの整数を2つの特定の放物線の間にある二次元の格子における点に関連付けることによって簡潔に特徴付けている。図11において、区間{u:x=x0u∈Iai,bi}は、1104で示し、2つの放物線は、1110、1120で示す。xが、B2N,h,h′内にあるならば、である。さて、Lx0をベクトル1,2x0及び0,Nによって生成する格子とする。すると、u,w∈Lx0及び、となるようなwが存在するとき、x=x0uは、まさにB2N,h,h′に存在する。条件11は、u,wが、式これは、図11の放物線1110であると、放物線1120によって定義される放物線1110、1120の間にあることを意味している。xが、Iai,biにあるならば、であり、ここでであり、記号∥は、絶対値を示す。従って、B2N,h,h′とIai,biの両方にある各整数x=x0uは、内の格子点に対応する。図11において、Pai,biの点を十字形により1121で示し、残りの格子Lx0点を円により1122で示す。Lx0のどの格子点が放物線1110、1120の間にあるかを計算するのは、かなり複雑なタスクのように思えるかもしれない。幸い、Valleeが述べるように、基底ベクトルがそれぞれ短く、一方の基底ベクトルは準水平で、他方は準垂直であるLx0の格子基底を見つけることができる。基底は、r,sであり、である。bi≦kであり、ここでであることを思い出されたい。Valleeは、以下を証明している定理4.Pai,biの全ての点は、ある有理指数v∈[0,h′2/4biN2h′bi/N]に関する縦座標w0-vN/biで縦軸wと交差するrに平行な線上にあり、ここでである。連続する指数vは、1だけ異なる。これらの線は、図11において1124で示す。次に、Valleeは、rに平行な準水平線1124をそれらの指数vによって数え、次に各線1124上のPai,biの点の数を数えるか概算することによって、Pai,biの点を大まかに数える。特に、Valleeは、2つの放物線の間の空間を胸部1130、脚部1140、足部1150に分割する4つの特別指数を定義している。2つの放物線の間の空間が、上端が連結された2つの脚部1140のように見える形をどのように形成することができ、上部1130が胸部であり、足部1150は、脚部がFarey区間Iai,biの端に接触するところに形成されることが容易にわかる。胸部、脚部、足部の領域の境界は、rベクトルに平行な線1160によって定められる。特別指数は、以下のように定義される。定義1:v0は、定義域の第1最小指数である。脚部の第1指数であるv1は、4hbi/N以上の最小指数である。脚部の最終指数であるv2は、h′2/4biNよりも小さい最大指数である。足部1150のv3は、h′2/4biN2h′bi/Nよりも小さい最大指数である。bi≦k=N/h′なので、胸部1130は、最大4つの線を含み、足部1150は、最大2つの線を含む。従って、Pai,biの点を数える際、いくつの点が胸部と足部にあるかの正確な計算をすぐに得ることができる。しかしながら、脚部は、非常に長いことがあり、Nが無限になるにつれてオーダーN1/3でON1/3の線まで含むことがある。幸い、Valleeは、以下の定理を証明できた。定理5脚部定理:脚部の指数vの線1124上のPai,biの点の数nvは、を満たす。以下、値は、Valleeの下限と呼び、は、Valleeの上限と呼ぶ。VLB及びVUB境界は、脚部のPai,biの格子点の総数の上限下限を得るのに用いることができ、a≦bである全ての正の整数a及びbに対し有効な以下の不等式を用いる。脚部定理を用いて、たとえ脚部1140が多数の線1124を有することがあっても、各線1124上で左から右へ点を数えることによって、Pai,biの格子点について概算できる。点は、最初に胸部、次に足部、その次に脚部で数えられる。胸部、足部、脚部の領域のそれぞれにおいて、点は、その領域の一番上の線1124で最初に数えられ、次にその下の線、というふうに数えられる。この概算を用いて、所定のFarey区間に擬一様に存在するB2N,h,h′から数を抜き出すことができる。Valleeの擬一様抜き出し方式Valleeは、以下の大域的抜き出し方式で上記結果を使用したが、-h=h′=4N2/3について、B2N,h,h′の数を擬一様に選択する。以下、ncは、胸部1130の点の数を示し、nfは、足部1150の点の数を示し、ncf=ncnf胸部と足部の点の総数であり、nlは、脚部1140の点の数を示す。リスト13:Valleeの擬一様抜き出し方式1.場所をランダムに選択する。任意の整数x∈選択した一様分布の[1,N]を選ぶ。2.Farey区間を決定する。連分数を用いて、xがJai,biにあるai,biを計算し、ここでJai,biは、オーダーk=1/4N1/3の区間[0,N/2のFarey分割区間である。3.Pai,biの点の数を概算する。を計算し、胸部と足部の点の数ncfを正確に数え、Valleeの下限15及び式17を用いて脚部における点の数について概算nlを得る。4.Pai,biから点を選ぶ。整数t∈擬一様の[1,ncfnl]をランダムに選択する。t≦ncfであれば、胸部又は足部から適切な点を出力する。そうでなければ、各線がValleeの下限に接触していれば、式17を用いて、どの準水平線1124が脚部の点数t-ncfを含んでいるかを決定し、一様分布のその線上のPai,biの点をランダムに選択する。5.Pai,biから選択した点からx′を計算する。u,wを前ステップによって出力した格子点とする。x′=x0uに設定する。x′を出力する。リスト13の終了。x′∈B2N,h,h′であり、x′は、xと同じFarey区間にあることに注目されたい。Farey区間は、幅が様々である。Iai,biが直径を有し、1≦bi≦kであることを思い起こされたい。最初の2つのステップにおいて、広いFarey区間が選択される可能性が高いが、広いFarey区間は、より多くのB要素を含むので、選択したFarey区間の特定のB要素は、そのFarey区間が広ければ、選ばれる確率が低い。結局、これらの要因は平衡し、大域的な擬一様抜き出し方式を可能にする。参照により本明細書に含まれるJ.‐S.Coronの論文、SecurityProofforPartial‐DomainHashSignatureSchemesproc.ofCrypto2002,LNCS2442,613‐626頁、Springer‐Verlag,2002において、Coronは、Valleeの方式を拡張して、εを正の定数として、について、B2N,h,h′の抜き出し方式を作り出した。該方式では、一様と統計的に区別が付かない分布、つまり、一様分布からの統計的距離が最大でである分布の要素を抜き出す。このような改良により、Coronは、部分領域ハッシュ署名方式のセキュリティを証明することができる。この方式では、署名は、基本的にB2N,h,h′内の数のモジュラ平方根である。しかしながら、Coronの部分領域ハッシュ署名方式において、署名は短くない。署名は、log2Nビットの数で表される。対照的に、本発明のいくつかの実施形態においては、可逆圧縮θ図8、ステップ810をCoron部分領域ハッシュ署名に適用して、帯域幅を縮小した部分領域ハッシュ署名を得る。Valleeのように、Coronは、2つの放物線1110、1120図11の間にある格子点を考慮する。しかしながら、Coronは、Iai,biではなく局所領域Jai,biを考慮し、異なる準水平線を用いて2つの放物線の間の値域を分割する。Coronは、Valleeのように、v0とv3を定義するが、v1とv2は、Iai,biの端に接触する前にいずれの放物線とも交わらない従って、Jai,biの端を通り過ぎる最初と最後の線の指数である。v1とv2の値は、と、h′-hbi/Nに近い。v3の値は、少し異なって定義され、に近くなるのは、Coronは、h′がN/kに必ずしも等しくない場合を考慮しているからである。Coronは、単にv1からv2までの指数を有する線上の格子点を抜き出すので、v0からv1又はv2からv3までの指数を有する線上の点が選ばれる可能性はない。しかしながら、Coronが考慮するパラメータ、すなわち、と、と、について、除外された格子点の部分は、無視できるものであり、この抜き出し方式は、一様に非常に近い。εの値は、望ましくは、が非常に小さくなるように選択する。3.本発明のいくつかの実施形態‐圧縮さて、本発明に転じると、本発明のいくつかの実施形態では、B2N,h,h′内の数と、定数cがゼロに近いn=c1log2h′-hとして、{0,1}nのビットストリングとの間の写像を提供する、圧縮及び復元方式π,θ,π-1,θ-1を用いる。これらの写像は順列ではない。しかしながら、各写像又は、その逆の下の要素の像は小さい一定の基数を有するので、写像はここでは準順列と呼ぶ。形式上、集合X及びYと定数l1,l2,l3,l4に関し、全てのx∈Xについて、{πx,r:r∈R}の基数が[l1,l2]にあり、全てのy∈Yについて、{x:∃rwithπx,r=y}の基数が[l3,l4]にある場合、π:XxR→Yをl1,l2,l3,l4の準順列と定義する19。上記で、Rは、補助集合である。例えば、πをランダム化したい場合、ランダムビットのソースとして用いてもよい。Rの目的は、単に、πを、たとえ単一のx∈Xに対し複数の出力が存在することがあっても所定の入力に対し単一の出力である、実際の写像にすることである。Rは、空であることもある。実際の順列は、l,l,l,lの準順列であることに注意されたい。図6乃至9において、集合Rは、陰的である。Rは、ランダムビットのソースになることがある。以下、2つの準順列について説明する。1つは、発明者がおそらく暗号化により適していると考えたものであり、もう1つは、発明者がおそらく署名により適していると考えたものである。しかしながら、本発明は、暗号化又は署名に関連して一方の又は他方の準順列に限定されない。小さい非負定数c1及びc2に対し、を、暗号化により適していることがある準順列とし、を、署名により適していることがある準順列とする。π及びθの両方は、以下に、より詳細に説明するように、効率的に計算可能であり、効率的に可逆である、すなわち、トラップドア情報なしでも、πx,r又はθx,rからxの可能性のある値を復元することは容易である。3.1短いストリングをB要素に写像するπ準順列本発明のいくつかの実施形態による図6及び7の方式に関し、π及びπ-1を計算するための方法を次に説明する。基本的に、πは、短いビットストリングを、該ビットストリングがFarey区間とそのFarey区間内のアドレスを特定するものと解釈し、該ビットストリングをそのFarey区間内のアドレスを有するB要素に写像することによって、B要素に写像する。短いビットストリングは、あるh′′<Nについて、ある区間[0,h′′]の数である。その逆であるπ-1は、基本的に、B要素のFarey区間と、そのFarey区間内のアドレスとを決定することによって計算され、B要素は、次に、その区間/アドレスの組み合わせを示すビットストリングに写像する。この方法は、以下の観測を用いる。Valleeの定理3及び5と、不等式15及び16は、Fareyオーダーという条件で、また、定理5と式15~16において、変数h′がh′-h/2に置き換えられるという条件で、-h=h′=4N2/3だけでなく、全てのh,h′に有効である。また、定理5は、置換なしでも依然有効である。図12に、ビットストリングxを、特定の狭いNを法とする区間におけるモジュラ平方数を有する数x′に写像するπ写像を示す。ステップ1270は、ビットストリングxに対応するFarey区間以下にかなり詳細に論じるを計算することを含む。ステップ1280は、該Farey区間の各端のビットストリングを計算することを含む。ステップ1290は、Farey区間について、xをB要素に対するx′に写像することを含み、該区間の計数は、最初と最後のビットストリングの間のxの計数に対応する。復元及び圧縮関数は、以下の事実を利用する。広いFarey区間のB要素に関し、該区間を特定するには少数のビットが必要であるが、該要素の該区間内の位置を特定するには多くのビットが必要である。全体としては、ビットの数は平衡する。π準順列の典型的な実施形態の詳細を、以下に述べる。πの定義19に関して、その値を後に測定するあるパラメータh′′について、X=[0,h′′]である。{0,1}nのビットストリングは、上述の[0,2n-1-1]の整数と解釈できることに注意されたい。以下のように仮定する。仮定1:h,h′を整数とする。いくつかの実施形態において、である。Jai,biを、区間[0,N/2]に関するオーダーのFarey分割の区間とする。Iai,biを、区間[0,N/2]に関する同じオーダーkのFarey区間とする。Jai,biを、区間[0,N/2]の同じオーダーkの、Farey拡張分割区間、すなわち区間Jaf,bfを含むものとする。リスト14‐πx,rの計算図12参照:1.ステップ1270図12:を計算して区間[0,h′′]を[0,N/2]に写像し、結果がJai,biに含まれるai,biを決定する。このステップもまた図11に示される。2.ステップ1280:が、Iai,biにある[0,h′′]の最小整数であるxleftと、がIai,biにある[0,h′′]の最大整数であるxrightを計算する。ステップ1290は、以下のステップ3乃至5に対応する。3.胸部と足部の格子点Pai,biの数である、ncf=ncnfを計算する。脚部の点の数のVLB下限15であるnlを計算する。以下に説明するように、数h′′は、ncfnl≧xright-xleftとなるように選択すべきである。4.Valleeの計数や他の計数を用いて以下の計算注記1を参照、x-xleftに対応する1つの格子点u,wいくつかあることがあるを選択する。具体的には、4A.内の整数を選ぶ。4B.c≦ncnfであれば、胸部又は足部に計数cを有する格子点u,wを選ぶすなわち、胸部と足部の点が一緒に数えられているとき。4C.そうでなければ、vごとに、svを、指数が最大vである準水平線1124図11上の脚部格子点の数の下限とする。値svはVLB値15を用いて計算することができる。VLB値を付加してsv推定値を得ることができ、又は、不等式17を用いて、右側の積分としてsvを計算することができる。sv-1<c-ncf≦svとなるようにvを計算する。nvを、指数vの線1124上の格子点の数とし、n′vをValleeの下限推定値15とする。整数を選択し、u,wを線上のPai,biのc′番目の点に設定する。5.x′=x0uに設定し、ここでである。x′を出力する。リスト14の終了。計算注記1。リスト14で用いられる値nc,nfや、他の値を計算するのに多くの方法がある。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/biだけ線1124.0切片のw値と異なるため見つけることができる。特に、定義1の特別指数とそれに対応する切片1294を求めることができ、胸部と足部の全ての線1124についてv値とw切片値を見つけることができる。胸部及び足部における線1124ごとに、等式20のための対応するα値を、その線の切片1294から求めることができ、次に、その切片1294のβ値を見つけることができる。このβ値をβinと示す。格子Lx0点は、βの整数値に対応する。格子点は、例えば、すなわちβinに最も近い整数から始めて、その線上で横に移動することできる。各点の座標は、定義12にはめ込んで、点がPai,biに属するかどうかを決定することができ、このように、Pai,biの点は、nc又はnfの一部として数えることができる。線を右に移動しβ>βin、ある点と放物線1120の外側で遭遇した場合すなわちx02wu2>h′、右方向の移動を止めることができる。同様に、線を左に移動し、点と放物線1120の外側で遭遇した場合、左方向の移動を止めることができる。Pai,bi点は、また、他の順序で数えることもでき、例えば、各線1124の一番左の点から始めて、右に進んでもよい。一番左の点は、対応する等式20と放物線1110、1120の等式から解析的に見つけることができる。これらの実施形態は限定的なものではない。リスト14のステップ4Bで、c≦ncnfであれば、c番目の点は、胸部と足部の線1124を数え、各線上の点を数えることによって見つけることができる。胸部と足部の線1124は、ある順序で横に移動することができ、例えば、胸部からv指数が増加する順で始めたり、その他の順序でもよい。各線1124上の点は、その線の対応する点から始めて、又は他の順序で数えることができる。本発明は、特定の点の順序付けに限定されない。同様に、ステップ4Cで、脚部のある線1124に関してパラメータnv,n′v,c′を決定する時、その線上のPai,biのc′番目の点は、その線の対応する点から始めて、又は他の順序で、格子点を横に移動することによって見つけることができる。いくつかの実施形態において、ステップ4B、4Cの計数順序は、π写像の特徴であり、π-1を計算するとき以下リスト15で説明するようにと同じ順序である。他の実施形態において、所定のπ写像に関して、点の計数は、式19のrパラメータに対応するようにランダムである。さらに他の実施形態において、計数は、ランダムではないが、xに依存する例えば、nc,nfや、xに依存する他の値。リスト14において、計数がランダムであろうとなかろうと、出力x′は、乱数c,c′の関数である。他の実施形態において、数c,c′は、確定的に選択される。例えば、ステップ4A、4Cに示すそれぞれ対応する区間の第1の整数に選ぶことができる。或いは、cを単にx-xleftに選ぶことができ、xrightの計算を省略することができる。或いは、cをxright‐xleftに選ぶことができる。同様に、c′は、c-ncf-sv-1に選ぶことができる。その他のランダムな又はランダムでない選択も可能である。リスト14の特定の方式は、以下に説明するように、c,c′が一様にランダムに選択されるならば、ランダムオラクルによる適応的選択メッセージ攻撃の下での対応する暗号化方式の証明できるセキュリティにより、有利である。計算注記1の終了。πx,rを計算する際、rを、確定的に又はランダムビットのソースとして用いることで、c及びc′の値を選択する。Sx={x′∈Iai,bi|∃rwithπx,r=x′}とするならば、集合Sxは、Iai,biの分割を形成し、これは、Iai,biの各B要素に選択される可能性があることを意味することに注目されたい。また、xとrを一様に選択して、πx,rを出力する場合、擬一様にBの整数を選択することに注目されたい。点の計数において、次に、胸部と足部のncnf=ncfの点を、1からncnfまである順序で数える。脚部の点は、多数の点が同じ数を共有することがあるという意味で大まかに数えられる。脚部の点は、Valleeの下限を満たすかのように数え、特にSvを計算する。このSvの値は、個々の線についてのValleeの推定値である式17において積分を計算することによって容易に計算することができる。脚部の準水平線1124は、Valleeの下限推定値よりも多くの点を含むことが多い。その場合、計数において、かかる線上の隣接する点は、1つの数を共有することがある。図13は、B要素x′を[0,h′′]の数xに写像する逆写像π-1を示す。ステップ1320で、Farey区間又はFarey分割区間を求め、これは、B要素x′に対応する。ステップ1330で、[0,h′′]のビットストリングを計算し、図11の写像1270の逆である写像により、区間の各端に対応する。ステップ1340で、x′を[0,h′′]のビットストリングxに写像し、ステップ1330で得たビットストリング間の計数は、区間のx′の計数に対応する。以下のリスト15では、Farey分割区間ではなくFarey区間を用いる時の詳細を説明する。x′=πx,rとすると、本発明の典型的な実施形態では、xの1つ又は2つの可能な値を復元する。上記仮定1が当てはまるものとする。リスト15‐π-1x′,rの計算:1.ステップ1320:x′:Iai,biとおそらくIai1,bi1を含むFarey区間を決定する。2.ステップ1330:が、Iai,biにある[0,h′′]の最小の整数であるxleftと、が、Iai,biにある[0,h′′]の最大の整数であるxrightとを計算する。ステップ1340は、以下のステップ3乃至7に対応する。3.Pai,biの胸部及び足部の格子点の数であるncfと、脚部の点の数の下限VLB15であるnlとを計算する。4.とu=x′-x0から、格子点u,wを復元する。具体的に、格子Lx0は、ベクトル1,2x0及び0,Nによって生成されるので、ある整数αに対して、各格子点u,wが等式w=2x0uαNを満たさなければならないことは容易にわかる。∥h′-h∥<N仮定1に鑑み、大きいNに対して当てはまらなければならないと仮定すれば、所定のuが放物線1110、1120の間にある格子点は1つだけある。この格子点は、放物線の間の領域を定める不等式11を用いて計算することができる。例えば、α=0w=2x0uから始めて、不等式11が満たされるまでαを増加及び/又は減少することができる。5.Valleeの下限計数又は他の計数計算注記1を参照を用いて、x-xleft、従ってxの値を復元する。具体的に、5A.u,wが、胸部又は足部のt番目の点であれば、c=tに設定する。胸部及び足部の点は、リスト14におけるように一緒に数えられる。計算注記1を参照。5B.そうでなければ、u,wを含む線1124の指数vを計算する。c′の値を計算し、ここで、u,wは、線上のc′番目の点である。nvを指数vの線上の格子点の数とし、n′vをValleeの下限推定値VLB15とし、sv-1をvよりも小さい指数の準水平線1124図11上の脚部格子点の数の下限とする。値sv-1は、線1124ごとにVLB値15を用いて計算することができる。これらの値を足してsv-1推定値を得ることができ、又は、不等式17を用いて、右側の積分としてsv-1を計算することができる。となるように、cの値を計算する。6.となるように、x-xleftの値を計算する。x=xleftx-xleftを計算する。7.xを出力する。リスト15の終了。上記の計算注記1を参照されたい。x′がIai,biとIai1,bi1の両方にある場合、ステップ2乃至6を繰り返して、Iai1,bi1に対応するxの値を得ることができる。このように、上記の方式では、x′を含む1Farey区間につき、ちょうど1つ、xの値を、2つまで出力する。従って、l3=1でありl4=2である。エンコードされた値x=HM図6、ステップ210が、両出力x=π-1に当てはまらないある性質を確実に満たすようにすることによって、正確な値を選択することができる。例えば、エンコードx=HMは、HMのいくつかのビットのいくつかをチェックすることを含むことがある。或いは、ステップ1320でどのFarey区間を選ぶべきかの曖昧さを解決する何らかの方法があってもよい。少し変更した方法を用いて、πx,rが一意逆を確実に有するようにすることは難しくない。特に、x′が確実にJai,bi内にあるようにすることで一意逆を実現することができ、それは、Pai,biについてのValleeの擬一様計数方法を、の1つに適用することで確実にすることができる。この場合、PJai,biは一様でない足部と脚部とを有するが、それでも、擬一様計数は、基本的に同じ方法を用いることで可能である。パラメータの設定:前述のように、暗号化方式には、π準順列がより適していることがある。準順列のパラメータ、特に、h′-hの値とh′′の値とを設定するために、暗号化方式とできるだけ両立するために準順列が持つべき性質について考慮することがある。望ましくは、πは、一意可逆であるかほぼそうであるべきである。上述のように、l4=2だが、Iai,biではなく区間Jai,biを考慮することによって、l4=1を実現することができる。また、各B要素おそらくそれらの無視できる一部は除くが少なくとも1つの逆を有するようにしたい。その理由は、一様確率でxを選択し、次にπx,rを計算することからなるB要素抜き出し方式が優れた抜き出し方式であれば、暗号化方式のセキュリティが因数分解に関連する、セキュリティプルーフが通るということである。擬一様抜き出し方式を得るために、l3は、少なくとも1であるべきである。l1とl2の値は、π準順列の下で、xの像のサイズを制約する。各エンコードされたプレーンテキストは、B要素に写像可能であるべきなので、l1は、望ましくは少なくとも1であるべきである。しかしながら、これが当てはまらないようにパラメータを選択することは可能である。l2の値は、他のパラメータの値を考えると、できるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算を提示するが、具体的なパラメータを示している。ncfnl≧xright-xleft、すなわち、Pai,biの点の数の下限が、Iai,biに対応付けられるビットストリングの数よりも大きくなるようにパラメータを選択することは、l3が、望みどおり、少なくとも1になることを確実にする。であることに注意されたい。ここで、後者の項は、h′-h=N/2kであるので、Iai,biの直径である。これは、であることを意味する。さて、Valleeが使用したパラメータについて考えてみよう。Valleeは、-h=h′=4N2/3の場合を考慮したので、h′-h=8N2/3である。このh′-hの値について、Valleeは、の下限を証明した。従って、ならば、xright-xleft-1<ncfnlである。nl推定値が整数である限り、これは、望むとおり、xright-xleft-1≦ncfnlであることを意味する。に設定することで、l3とl1が少なくとも1であることを検証できる。他方、胸部と足部における点の数についてのValleeの上限は、l2の値が上限を定められるのを可能にする。nlがまだ、脚部の点の数についての下限推定値VLBであることを思い起こされたい。Valleeの計算は、ncfnlが、によって上限が定められるのを可能にする。これにより、h′′の選択された値について、cの可能な値の数を8によって上限を定めることができ、ここで、cは、リスト14のステップ4で選択した数である。また、リスト14のステップ4で選択した数であるc′の、最大でValleeの脚部定理を参照の可能な値がある。従って、l2は、最大8x4=32である。このように、h′-h=8N2/3とについて、1,32,1,2準順列を得る。暗号文は、[h、h′]にあり、プレーンテキストは、[1,h′′]又は[0,h′′-1]にあるので、ここで、であり、およそビット、すなわち、丸めを考慮すると最大で3ビットの暗号文拡張だけが見込める。性能に関して、πx,r又はπ-1x,rの計算には、Olog2Nビットの演算が必要なだけであり、暗号化及び復号化の複雑性に、ほとんど何も付加しない。h′-hとh′′の間の5の因数は、h′-h=8N2/3に対するValleeの下限のゆるさの結果である。h′-hのより大きい値、例えば、Coronが考慮したもの等について、下限は、より厳密な概算となる。従って、h′-hのより大きい値について、π準順列は、さらに小さい暗号文拡張を暗号化方式に与える。3.2B要素を短いストリングに写像するθ準順列θ準順列は、π準順列の逆に類似している。この場合も、圧縮及び復元方式は、ValleeのFarey区間の分析によって与えられるB要素の分布について公知の情報を用いる。帯域幅縮小署名方式を用いる本発明の典型的な実施形態に関して、より詳細に説明するように、θ準順列は、例えば、Coronによって安全性が証明されたものなど、通常のRabin部分領域ハッシュ署名を損失なしに、すなわち、通常の署名を圧縮された署名から完全に復元できるように、圧縮できるようにする。この圧縮方式は、セキュリティの減少を必要としない。典型的な実施形態の詳細な説明を続ける。上記仮定1が当てはまるものとする。リスト16‐Bのあるx′について[0,h′′]のx=θx′,rを計算する図13参照:1.ステップ1320:x′がJai,biにあるai,biを決定する。2.ステップ1330:が、Jai,biにある[0,h′′]の最小の整数であるxleftと、が、Jai,biにある[0,h′′]の最大の整数であるxrightを計算する。ステップ1340は、以下のステップ3乃至5に対応する。3.Pai,biの胸部及び足部の格子点の数、ncfと、脚部の点の数についての上限VUB16、nlとを計算する。ncfnl≦xright-xleftを望む。4.Valleeの計数か他の計数計算注記1参照を用いて、x′に対応付けられた格子点u,wに対応するxright-xleftいくつかあることがあるの1つの整数を選択する。具体的には、4A.u,wが胸部又は足部のt番目の点であれば、c=tに設定する。4B.そうでなければ、svを、指数が最大でvの準水平線1124図11上の脚部格子点の数についての上限とする。値svは、線1124ごとにVUB値16を用いて計算することができる。これらの値を足してsv推定値を得ることができ、又は、不等式18を用いて、右側の式としてsvを計算することができる。u,wを含む線の指数vを計算する。nvを、指数vの線上の格子点の数とし、n′v=sv-sv-1を、Valleeの上限推定値VUB16とする。x′が、線上のt番目の格子点であるとする。整数を選択する。5.整数を選択する。x=xleftc′に設定する。リスト16の終了。計数についての考察を含む計算注記1は、π及びπ-1に当てはまるように、θ及びθ-1写像に当てはまる。θx′,rを計算するのに、rを確定的に、又は、ランダムビットのソースとして用いて、cとc′の値を選択する。[0,h′′]においてx=θx′,rとすると、Bのx′の値を以下のように復元することができる。リスト17‐θ-1xを計算する図12:1.ステップ1270:が、Jai,biにあるai,biを決定する。2.ステップ1280:が、Jai,biにある[0,h′′]の最小の整数であるxleftと、が、Jai,biにある[0,h′′]の最大の整数であるxrightを計算する。ステップ1290以下のステップ3乃至5。3.Pai,biの胸部及び足部の格子点の数、ncfと、脚部の点の数についての上限VUB16、nlとを計算する。4.c′=x-xleftを計算する。c′とncfnlから、となるように値cを計算する。c≦ncfであれば、u,wを胸部又は足部のc番目の点とする。そうでなければ、c∈ncfsv-1,ncfsvとなるように、指数vを計算し、ここで、svは、リスト16、ステップ4Bにおけるように定義される。また、リスト16におけるように定義されるtの値を計算し、u,wを指数vの準水平線1124上のt番目の点とする。5.に設定する。リスト17の終了。計数についての考察を含む計算注記1は、リスト16に当てはまる。パラメータの設定。θ準順列は、おそらく署名方式により適しているので、h′-hの値とh′′の値を選択するのに、署名方式にできるだけ有用となるのに準順列が含むべき性質について考慮しなければならない。例えば、θは、一意可逆であるかほとんどそうであるべきである。しかしながら、図9のステップ510で、多数の候補から正確なHM値を認識したり、そうでなければ、ステップ520で、検証を認識するのが可能であれば、一意可逆は、必要ではない。一実施形態において、l3とl4は、両方とも1に等しい。すなわち、各ビットストリングxは、その逆としてちょうど1つのB要素x′を有する。l1が少なくとも1つであることは適切である。すなわち、各B要素は、その圧縮として少なくとも1つの短いビットストリングを有するべきである。前述のように、他のパラメータの値を考慮すると、l2はできるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算は、具体的なパラメータを示している。ncfnl≦xright-xleftとなるように、すなわち、Pai,biの点の数の上限が、Jai,biに対応付けられたビットストリングの数よりも小さくなるように、パラメータを選択することで、各B要素に一意に対応付けられる少なくとも1つのビットストリングが確実に存在することになる。であることに注目されたい。ここで、後者の項は、Iai,biの直径であり、少なくともJai,biの直径である。このことは、であることを意味する。さて、Coronが用いたパラメータについて考えてみる。Coronは、の場合を考慮した。これらの値について、Coronは、の上限を証明した。ここで、jiは、Jai,biの整数の数である。従って、であれば、xright-xleft1>ncfnlである。nl推定値が整数である限り、望みどおり、xright-xleft≧ncfnlとなる。従って、に設定してもよく、ここで、最大値は、全てのiに取って代わる。他方、Coronは、また、下限を証明する。これにより、c′について可能な値の数の上限をおよそに定めることができ、Nとεの標準値に対して最大で2である。また、cについて可能な値の数は、およそによって上限を定められ、Coronのパラメータに対し同じく最大で2である。従って、l2は、最大で22=4であり、1,4,1,1準順列を得る。しかしながら、B要素の無視できる部分だけは複数の像を有する。4.暗号化/復号化方式本発明のπ変換を図6の方式において用いることで、暗号文のサイズの縮小を可能にすることによって、上述のRabin‐OAEP等のRabinに基づく暗号化方式を改良することができる。以下、πN,h,h′という表現は、集合B2N,h,h′への写像πを示し、θN,h,h′は、集合B2N,h,h′からの写像θを示す。リスト18‐暗号化図6:1.ステップ210:メッセージMのエンコードである、x=HMを計算する。2.ステップ610:x′=πN,h,h′x,r∈[0,N/2]を計算する。3.ステップ220:y=x′2modNを計算する。ここで、文字yをcの代わりに暗号文に用いて、本明細書におけるcの他の使用との混同を避ける。4.ステップ230:yを暗号文として出力する。リスト18の終了。リスト19‐復号化図7:1.ステップ310:x′2≡ymodNとなるように、各x′∈[0,N/2]を計算する。図7において数x′はbと示す。[0,N/2]にはかかるx′が少なくとも1つ存在するのは、x′2=ymodNでありx′が[0,N/2]になければ、x′はN-x′に設定することができるからであり、この新しいx′値は[0,N/2]にあり、x′2=ymodNを満たす。2.ステップ320:を計算する。かかるx値は、いくつかあることがある。これらの値は、図7のHMに対応する。3.ステップ330:メッセージエンコードを取り消して、メッセージMが正確にエンコードされているか確認する。4.Mが正確にエンコードされていない場合、x′の別の値を試してみる。x′の全ての値が試されているならば、復号化が失敗したことを示す。リスト19の終了。リスト14、15、18、19による、π写像を含むRabin暗号化方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でπ写像がないのと同じくらい安全であることを示すことができる。参照により本明細書に含まれるCraigGentry著、HowtocompressRabinCiphertextsandSignaturesandMore,Proc.ofCrypto2004,M.FranklinEd.,LectureNotesinComputerScience3152,pp.179-200,Springer,2004を参照されたい。π準順列は、N,h及びh′の特定の値に依存することに注意されたい。従って、ある意味、h及びh′は、公開鍵の一部であり、送信者は、暗号化を実行するのにそれが必要である。RSAやRabin暗号化と共に用いることができる当技術において公知の様々なエンコード方式は、本発明の帯域幅縮小暗号化方式においても用いることができる。以下、帯域幅縮小暗号化方式の詳細を示すが、上記リスト5及び6のRabin‐OAEPの説明に類似している。上述のように、メッセージエンコードは、式1により上記定義したハッシュ関数を利用する。非帯域幅縮小Rabin‐OAEPリスト5及び6において、であったが、本発明の帯域幅縮小暗号化方式においては、式21に示したValleeのパラメータに関するh′′の値に従って、に設定するのが適切である。いくつかの実施形態において、Valleeのパラメータにおけるように、h′-hは、およそ8N2/3である。もちろん、nを大きくする、例えば、log2Nにまですることができるが、エンコードしたプレーンテキストが、よりも大きくなければならない場合を除いて、それは必須ではない。メッセージM∈{0,1}mを暗号化するために、送信者は、以下の演算を実行する図6参照。リスト20‐暗号化。図6のステップ210は、以下のステップ1乃至3に対応する。1.任意のを選択する。2.を設定する。3.nビットストリング、x←s∥tを設定する。4.ステップ610:x′=πx,r∈[0,N/2]を計算する。5.ステップ220:暗号文c←x′2modNを計算する。リスト20の終了。x′は、モジュラ平方数が非常に狭い値域すなわち、[h,h′]にある整数であるので、cの最下位ビットだけを実際に送信するだけでよく、暗号文を短くすることに注目されたい。h′-h=8N2/3に対し、暗号文は、およそビットである。復号化するために、受信者は、以下のステップを実行する図7参照。リスト21-復号化1.ステップ310:cのモジュラ平方根ととを計算する。の少なくとも1つと、の少なくとも1つは、[0,N/2]にある。一般性を失うことなく、は、[0,N/2]にあるものと仮定することができる。2.候補ごとに、2A.ステップ710:を計算する。2B.ステップ320:と、について、xiをsi∥tiに構文解析し、次に、と、について、siをに構文解析する。iごとに、と、とを計算し、かどうかテストする。条件が満たされる一意のiが存在する場合、Miを正確なプレーンテキストとして出力し、そうでなければ、復号化の失敗を示す。リスト21の終了。セキュリティのプルーフの概略を述べるのに、上記の帯域幅縮小暗号化方式を解読することは、法Nを因数分解するのと同じくらい難しいことを例えば、ランダムオラクルモデルを用いて証明できる。例えば、時間tAでアドバンテージεAで暗号化方式を解読するアルゴリズムAが存在するものとし、ここで、アドバンテージは、Aが選択した2つのプレーンテキスト、M0とM1、のどちらが特定の暗号文によって暗号化されているかを正確に推測できる確率マイナス1/2と定義する。次に、Aとのインタラクションを通じて得た知識を用いることによって、Nを因数分解できる第2のアルゴリズムBを構成することができる。例えば、以下のゲームを考えてみる。挑戦者は、因数分解する法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を復号化するように要求する。Bがハッシュ関数を制御するので、また、Aは無視できる確率を除いてハッシュを問合せることなく有効にエンコードされた暗号文を作成することができないので、Bは、例えばAがH′に入力するMの値など、Aのハッシュ関数への入力Mを見ることになる。この知識を用いて、Bは、圧倒的に高い確率でAの復号化の問合せに正確に返答するこができる。フェーズ1の終わりに、Aは、それについてテストされたいメッセージM0とM1を選択し、Bは、ランダムにあるビットb∈{0,1}を選択し、Mbを暗号化する暗号文c挑戦暗号文を返信する。Bは、ハッシュ関数の制御を用いて、この暗号文を巧妙に間に合わせに作るので、cのモジュラ平方根がわかる。フェーズ2で、Aは、挑戦暗号文以外の復号化すべき暗号文をさらに要求することができる。最終的に、推測b′∈{0,1}を出力し、b=b′であればゲームに勝利する。ハッシュの問合せをさらに行って、再びBがこれらのハッシュ関数への入力を見ることができるようしない限り、Aは、せいぜいわずかなアドバンテージしか有さない。Aが確かにcのモジュラ平方根を計算すれば、である可能性があるので、は、Nの自明ではない因数を与える。確かに、xとrを一様に計算しハッシュ関数はxに対し一様出力を与えるものとする、次に、x′=πx,rを計算することからなる抜き出し方式が擬一様抜き出し方式であれば、Bが、どのモジュラ平方根を知っているかをAが推測する可能性は低いことを意味する。従って、Aは、間違って推測することが多く、そのハッシュの問合せにより、Nの自明ではない因数を計算するのに必要な情報をBに与える可能性が高い擬一様抜き出し方式について、Valleeの値をとすると、少なくともの可能性。5.署名方式本発明のθ変換を用いて、署名を損失なしに圧縮できるようにすることによって、Coronが安全であると証明した部分領域ハッシュ署名などの、Rabinに基づく署名方式を改良することができる。基本的なアプローチは、以下のとおりである。リスト22‐署名図8も参照:1.図8のステップ410:メッセージMのエンコード、y∈[h,h′]を計算する。図8のステップ420は、以下のステップ2及び3に対応する。2.eyがNを法とする平方数となるように、e∈{-2、-1,1,2}を計算し、eymodNを計算する。yは、Nを法とする平方根を持たないことがあるが、Nが2つの素数の積とすると-2y,-y,y,2yのいずれかは、常にNを法とする平方根を有するので、eで乗算がなされる。3.x′2≡eymodNとなるように、x′∈[0,N/2]を計算する。通常の署名は、x′,eである。4.図8のステップ810:eが正であれば、x=θN,eh,eh′x′,rを計算し、eが負であれば、x=θN,eh′,ehx′,rを計算する。圧縮された署名はx,eである。リスト22の終了。リスト23検証図9参照:1.ステップ910図9:eが正であれば、を計算し、eが負であれば、を計算する。2.ステップ510:y=HM/emodNを計算する。3.ステップ520:y∈[h,h′]であり、メッセージMのエンコードであるか確認する。リスト23の終了。θ準順列は、N,h,h′及びeの特定の値に依存することに注意されたい。従って、ある意味では、hとh′は、公開鍵の一部であり、検証者は、署名を検証するのにそれが必要である。RSAやRabin署名と共に用いることができる当技術で公知の様々なエンコード方式は、本発明の帯域幅縮小署名方式においても用いることができ、その逆もまた同様である。eの値は、2ビットで表現することができる。eに様々な値を用いることができるが、eを小さくしておくことは適切である。リスト16、17、22、23による、θ写像を含むRabin署名方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でπ写像がないのと同じくらい安全であることを示すことができる。上述のCraigGentry著の論文、HowtocompressRabinCiphertextsandSignaturesandMoreを参照されたい。以下、より詳細な帯域幅縮小署名方式を示すが、前述の全領域ハッシュ署名方式の説明と類似しているリスト7及び8参照。メッセージ復元が可能な特定のエンコード方式を使用する。前述のように、上記式1により与えられる暗号ハッシュ関数を使用する。非帯域幅縮小署名方式リスト7及び8においては、であったが、帯域幅縮小署名方式には、Coronのパラメータに従って、とするのが望ましい。この場合も、nをビットよりも大きく設定することができるが、ある理由で、エンコードされたメッセージがビットよりも長くなければならない場合を除いて、これは望ましくない。素数P≡3mod8及びq≡7mod8についてN=pqとなるようにNを生成する際、署名者は、以下の演算を実行する。リスト24‐署名:図8のエンコードステップ410:1.任意のを選択する。2.を設定する。3.nビット整数、y←s′∥s′′∥tを設定する。図8の署名ステップ420:4.uq←yq1/4modqを計算する。5.であれば、ey←1に、そうでなければ、ey←-1に設定する。6.up←eyyp1/4modpを計算する。7.であれば、fy←1に、そうでなければ、fy←2に設定する。8.vq←fy3q-5/4uqmodq、及びvp←fy3q-5/4upmodpを計算する。9.w←vqqqp-2vp-vqmodpを計算する。10.2w<Nであれば、x′←wに、そうでなければ、x′←N-wに設定する。短い署名の生成図8のステップ810:11.eが正であれば、x=θN,eh,eh′x′,r′を計算し、eが負であれば、x=θN,eh′,ehx′,r′を計算する。12.署名ey,fy,r,xを出力する。リスト24の終了。この場合も、23q-5/4modq、23p-5/4modP及びqp-2modpの値は事前に計算できるので、ステップ8及び9は、署名時間にほとんど何も付加しない。リスト25‐検証図9:1.ステップ910:eが正であれば、を計算し、eが負であればを計算する。2.ステップ510、520:を計算し、ytmpがnビットであることを確認し、ytmpをに構文解析し、を計算し、であることを確認する。リスト25の終了。検証処理中にメッセージMが復元されることに注意されたい。また、圧縮θリスト24のステップ11は、通常のRabin署名ey,fy,x′が生成された後に、署名処理の終わりにやっと出てくることに注目されたい。セキュリティのプルーフは、Coronが提供したような通常の部分領域ハッシュ署名方式に対するセキュリティのプルーフから容易に得られる。ある攻撃者Aが、帯域幅縮小方式において偽造ができるならば、非帯域幅縮小方式に対する別の攻撃者Bは、単にθ-1をAの偽造に適用することで、非帯域幅縮小方式において偽造することができることは明らかである。Bは、Aの署名の問合せを挑戦者に中継し、次に挑戦者の応答に対し、それらをAに中継する前にθを適用することによって、該署名の問合せに容易に応答するふりをすることができる。6.サインクリプション方式本発明のいくつかの実施形態によるサインクリプション方式において、望ましくは、サインクリプションの送信が、送信者が署名と暗号文を別々に送信した場合よりも少ない帯域幅を消費するように、送信者は、同時に、自身の秘密鍵を用いてメッセージに署名し、受信者の公開鍵を用いてそれを暗号化する。受信者は、その秘密鍵でサインクリプションを復号化し、送信者の公開鍵を用いて送信者の署名を検証する。送信者の公開法をNA又はNAで示し、送信者のh,h′パラメータをそれぞれhA及びh′Aで、又はhA及びh′Aで示す。受信者の公開法をNB又はNBで示し、受信者のh,h′パラメータをそれぞれhB及びh′Bで、又はhB及びh′Bで示す。一実施形態は以下のとおりである図6、8及び14参照。リスト26‐サインクリプション図14:1.図14のステップ410エンコード:メッセージMのエンコード、y∈[hA,h′A]を計算する。ステップ420以下のステップ2、3。2.eyがNAを法とする平方数となるように、e∈{-2,-1,1,2}を計算する。3.x′2≡eymodNAとなるように、x′∈[0,NA/2]を計算する。4.ステップ810:eが正であれば、短い署名を計算し、eが負であれば、を計算する。5.ステップ1410:x′′∈[0,N/2]として、eが正であれば、を計算し、eが負であれば、を計算する。6.ステップ1420:c=x′′2modNBを計算する。サインクリプションは、eとc、又はeとcの省略形とからなるcの省略形とは、cよりも少ないビットで表現することができ、それからcを求めることができる数であり、例としてc-hや、cのある数の最下位ビットを含む。リスト26の終了。θ準順列は、N,eの特定の値と、h及びh′の値に依存し、ユーザA及びBによって異なることがあることに注意されたい。従って、いくつかの実施形態では、hとh′は、公開鍵の一部であり、受信者は、署名を検証し、メッセージを復号化するのにそれが必要である。異なる署名者は、hとh′に異なる値を用いることができるが、簡潔にするために同じであるのが望ましい。様々なエンコード方式が当技術において公知であり、1つの方式を以下に詳細に説明する。eの値は、2ビットで表現することができる。eに様々な値を用いることができるが、eを小さくしておくことが望ましい。cの省略形例えば、ビットで表現することができる、c-hを、h及びh′と一緒に用いて、cの完全な値を復元することができるので、サインクリプションは短い。リスト27‐アンサインクリプションUnsigncryption図15参照:1.ステップ1510復号化:x′′2≡cmodNBとなるように、x′′∈[0,NB/2]の2つの値を計算する。2.ステップ1520:eが正であれば、を計算し、eが負であれば、を計算する。3.ステップ1530:eが正であれば、を計算し、eが負であれば、を計算する。4.ステップ1540:y=x′2/emodNAを計算する。5.ステップ1550:メッセージエンコードを取り消してMを復元し、メッセージMが正確にエンコードされているか確認する。Mが正確にエンコードされていなければ、x′′の他の値を試してみる。x′′の両方の値を試しているならば、復号化が失敗したことを示す。リスト27の終了。アンサインクリプションにおいて、図14のステップ810におけるθの計算でサインクリプターsigncrypterが用いるrの特定の値を、アンサインクリプターunsigncrypterは知らない。しかしながら、θ準順列にパラメータを望ましく選択するために、B要素の無視できる部分だけが複数の像を有するので、出力は一意になる可能性が高いrから独立している。しかし、必要ならば、サインクリプターは、どのrの値を用いたかを示す少数の追加ビットを送信することができる。図14のステップ410の典型的なエンコードは、以下のとおりである。m,k0,k1をセキュリティパラメータとする。との数量は、ごくわずかであるべきだが、必然ではない。n=mk0k1とする。望ましくは、法NAとNBは、ほぼ同じ数のビットを有し、帯域幅縮小署名方式におけるように、である。NAとNBのサイズが異なるならば、となるように、nを設定することができる。この場合も、nをさらに大きく設定することはできるが、そうすることは最適ではない。以下の暗号ハッシュ関数を定義する。このH関数メッセージエンコードの計算用の中間値は、図14のステップ410に示す、最終的なエンコードされたメッセージを表すHM関数と混同するべきではない。図14のステップ410で、yを計算するために、ここで、yは、メッセージM∈{0,1}mのエンコードであるが、サインクリプターは、1.任意のを選択する。2.t=Hr∥M及びに設定する。3.y=s∥tに設定する。ステップ1550で図15、アンサインクリプターは、yをs及びtに構文解析し、からrとMを復元し、t=Hr∥Mであることを確認する。セキュリティプルーフは、基本的に、前述の、暗号化方式と署名方式のセキュリティプルーフを組み合わせたものである。さらに、帯域幅縮小署名方式に関連して上記に述べたモジュラ平方根の計算への数論的アプローチは、サインクリプション/アンサインクリプションと共に用いることができる。いくつかのサインクリプション実施形態において、署名と暗号化の順序を逆にする。すなわち、送信者は、まず、受信者の公開鍵を用いてメッセージを暗号化し、次に送信者の秘密鍵を用いてメッセージに署名する。受信者は、署名を検証し、暗号化されたメッセージを復元し、次にメッセージを復号化する。リスト26、27に類似した方法を、演算の順序を適切に変更して用いることができる。7.集合署名方式本発明のいくつかの実施形態による集合署名方式において、それぞれ公開鍵法{N1,...,NZ}を有する署名者の集合{S1,...,SZ}は、それらの集合署名、すなわち、各SiがMiに署名したことを検証するのに必要なビットストリングが短く、各署名者がそれぞれのメッセージに別々に署名した場合よりも少ない帯域幅を最適に消費するように、それぞれのメッセージ{M1,...,MZ}に署名する。本発明のいくつかの実施形態において、メッセージは、順に署名され、これは、署名者Siが、Si-1からsi-1を受信した後に、Miについて署名siを生成することを意味する。いくつかの実施形態において、Niは、全てほぼ同じビット長を有する。Niのビット長に関する考慮事項は、本発明のサインクリプションの実施形態に関して前述したのと基本的に同じである。各si-1は、の要素の、により圧縮した表示であり図8のステップ810に注目、siは、基本的に、[h,h′]の数のNiを法とする圧縮平方根として計算されるステップ420、810。その数は、si-1とMiとに依存する。以後、署名者は、それぞれ異なる値のh及びh′を用いることができるが、便宜上、このことは表記において示さない。集合署名は、公開鍵{N1,...,NZ}を用いて検証される。具体的に、このアプローチは、以下のとおりである。fを後述する関数とする。Niは、Niとも示す。i番目の署名者は、以下の演算を実行する。リスト28‐集合署名図8参照:0.s0=dに設定する。ここで、dは、所定の固定値である任意の値。1.i=1からi=zについて、以下を行う。1A.ステップ410:yi=fsi-1,Ni,Mi,...,N1,M1∈[h,h′]を計算する。ステップ420以下のステップ1B及び1C:1B.eiyiがNiを法とする平方数となるように、ei=eii∈{-2,-1,1,2}を計算する。HM=eiyiを計算する。1C.ステップ420:となるように、を計算する。1D.ステップ810:eiが正であれば、si=θNi,eih,,eih′si,rを計算し、eiが負であれば、si=θNi,eih′,eihsi,rを計算する。2.集合署名s1,e1,sz,ezを出力する。リスト28の終了。i番目の署名者は、siを生成する前に、i-1番目の署名者がそれ自身の署名を集合した後の結果である、si-1の値を受信することに注目されたい。サインクリプション方式におけるように、署名者は、それぞれ、hとh′に異なる値を用いることができるが、簡潔にするためには同じであることが望ましい。関数fについては、本発明が利用する検証の概要を述べた後に説明する。リスト29‐検証図9参照:1.i=zからi=1について、以下を行う。1A.ステップ910:eiが正であれば、si′=θ-1Ni,eih,eih′siを計算し、eiが負であれば、si′=θ-1Ni,eih′,eihsiを計算する。1B.ステップ510:を計算する。1C.ステップ520:yi=fsi-1,Ni,Mi,...,N1,M1からsi-1を計算する。2.ステップ520:ステップ1B‐2で計算したs0がdに等しいことを確認する。リスト29の終了。関数fは、集合署名処理において効率的に計算可能なだけでなく、検証処理においても効率的に可逆であるべきである。可逆であるとは、si-1が、fsi-1,Ni,Mi,...,N1,M1と、Ni,Mi,...,N1,M1の値から導き出せるべきであるという意味においてである。かかる関数の候補の1つは、fsi-1,Ni,Mi,...,N1,M1=si-1HiNi,Mi,...,N1,M1である。ここで、は、加算やXORなどの何らかの容易に可逆である2項演算である。この方式のセキュリティを証明するのに問題があることがある。1つの理由として、鍵とメッセージの固定集合Ni,Mi,...,N1,M1に対する集合署名要素si-1には、可能性のある値が多くあり、シミュレータすなわち、暗号化の項4の言語のアルゴリズムBが、siに関するsi-1の全ての可能性のある値についての攻撃者の署名の問合せに返答することができるように、シミュレータが、HiNi,Mi,...,N1,M1の単一の値を間に合わせに作ることはおそらく不可能であることがある。ここで、Hiは、Niを法とする整数集合の値を有するあるハッシュ関数である。この問題に対処するために、fを計算する別のアプローチを用いることがあり、を計算し、ここで、Eは、対称暗号化方式であり、対称暗号鍵kiは、あるハッシュ関数Hiについて、ki=HiNi,Mi又は、必要なら、ki=HiNi,Mi,...,N1,M1として計算する。fが可逆であることは容易にわかる。とNi及びMiを与えられると、ki=HiNi,Mi、次に、を計算することができる。ここで、は、鍵kiの下の対称復号である。このセキュリティプルーフは、ランダム応答を返すオラクルのように、暗号ハッシュ関数がふるまうことを装うランダムオラクルモデルを用いるのではなく、ある対の鍵/メッセージについてランダム暗号文を返すオラクルのように暗号対称暗号化方式がふるまうことを装う理想暗号モデルを用いている。参照により本明細書に含まれるM.Bellare、D.Pointcheval及びP.Rogaway著、AuthenticatedKeyExchangeSecureAgainstDictionaryAttacks,inProc.ofEurocrypt2000,B.PreneelEd.,LectureNotesinComputerScience1807,pp.139-155を参照されたい。理想暗号モデルにより、シミュレータは、鍵やメッセージだけでなくsi-1にも依存する問合せ応答を行うことができ、シミュレータは、その応答をより自由に間に合わせに作ることができる。最適には、対称暗号化方式Eは、暗号文を拡張することなく、si-1の長さ、すなわち、およそ2/3εlog2Niビットのストリングを暗号化できるので、集合署名のサイズは、より多くの署名が集合されるにつれて著しく大きくなることはない。fを計算する上記方法はもちろん、θ圧縮関数を使用しないすなわち、図8のステップ810を省略したモジュラ2乗に基づく逐次集合署名方式を作成するのに用いることができる。8.リング署名方式本発明のいくつかの実施形態の帯域幅縮小リング署名方式において、署名者Siは、Siがメンバーである署名者の集合{S1,...,SZ}を選択して、検証者が、誰であるかは定められないけれども、{S1,...,SZ}の少なくとも1人の署名者がメッセージに署名したことを検証者に確信させる、メッセージのリング署名を生成することができる。署名者Siは、従って、可能性のある署名者のリング内で限定された匿名性を有する。いくつかの実施形態において、署名者は、検証者がリング署名を検証するのに用いる公開法{N1,...,NZ}を有する。リング署名は、集合的にCk,v{y1,...,yZ}を満たすzのストリング{x1,...,xZ}を含み、ここで、であり、v及びwは、所定のビットストリングであり、Cは、結合関数である。本発明のいくつかの実施形態の帯域幅縮小リング署名方式は、前述のθ準順列を用いることによって、また、法Niが異なるサイズを有することに対処するより帯域幅効率のよい方法を用いることによって、Rivest‐Shamir‐Tauman方式におけるよりも短いリング署名を実現している。Rivest‐Shamir‐Tauman方式リスト10、11において、について、qi1Ni≦2bであれば、yi=qiNigiriを計算し、そうでなければ、を計算する。ここで、giは、関数を示し、bは、所定の定数である。bが十分に大きい限り、qi1Ni>2bであるyiの割合は、無視できるものであるので、x′iのyiへの写像は、Niを法とする2乗とほとんど区別できない振る舞いをする。残念ながら、bをこれほど大きいものに選ぶことは全ての法の対数よりもはるかに大きい、また、帯域幅効率が悪い。について、を計算するほうが帯域幅効率がよい。ここで、本発明のいくつかの実施形態において、θ準順列に関し、bがの約3分の2になるように、を用いて、さらによく行うことができる。従って、あるxiに対し、ととを計算することがある。結合関数は、やはり、となることができ、ここで、Ekは、鍵kを用いる対称暗号化方式である。Siが真の署名者であるとすれば、本発明のいくつかの実施形態におけるリング署名は、以下のように生成される。リスト30‐リング署名:1.k=HMを計算する。ここで、Mは、署名するメッセージであり、Hは、ハッシュ関数である。2.任意のv∈{0,1}bを選択する。3.j≠iごとに、3A.任意のを選択する。これは、C.Gentryの前述の論文において述べられているように、ランダムに一様に行うことができる。3B.yj=gjx′jを計算する。4.となるように、yiを計算する。5.Niについての秘密知識を用いて、となるように、を計算する。6.全てのjについて、を計算する。リスト16を参照r値はランダムなことがあり、異なるjに対し異なることがある。7.リング署名x1,...,xz,vを出力する。リスト30の終了。前述のようにリスト11、リング署名者は、等式を用いて、yjの値からyiを計算することができるj≠iである。yjのいくつかの値、実際に約4分の3は、モジュラ平方根を持たない。この場合、yjがNjを法とする平方剰余となるまでステップ5を再び実行しなければならない。リスト31‐リング署名の検証:1.k=HMを計算する。2.全てのjについて、を計算する。3.であることを確認する。リスト31の終了。上述の他の方式におけるように、リスト30のステップ6Bにおけるrは余剰ビットのソースであり、準順列の呼出しごとにランダムに、又は、準順列の他の入力例えば、x′jに、確定的にしかし予測不可能に依存するように選ばれる。また、各署名者は、hとh′に異なる値を用いることができるが、各署名者のhとh′の値は、リング署名の検証に必要である従って、ある意味では、公開鍵の一部であるので、いくつかの実施形態において、全ての署名者は、同じ値を用いる。9.他の方式と拡張本発明のいくつかの実施形態の圧縮及び復元方式は、暗号化、署名、集合署名、及びリング署名以外の暗号のコンテキストで有益である。例えば、本発明の圧縮及び復元方式を利用する閾値暗号化及び復号化は、暗号文のサイズが小さければより効率的になることがある。また、他の署名方式例えば、Fiat‐Shamirのバージョン、特に、アイデンティティに基づくバージョンや、他のアイデンティティに基づく暗号化方式例えばCockの暗号化方式を利用するものなどにおいて、署名者は短いアイデンティティに基づく公開鍵や秘密鍵後者はB要素を持つことができる。さらに、モジュラ平方数を送信することに基づく識別方式は、本発明を適用することで同様に改良される。A.Fiat及びA.Shamir著、HowtoProveYourself:PracticalSolutionstoIdentificationandSignatureProblemsinProc.ofCrypt1986,LectureNotesinComputerScience263,pp.186-194.Springer,1986と、U.Feige、A.Fiat及びA.Shamir著、Zero‐KnowledgeProofsofIdentityinJour.ofCryptology1,pp.77‐941988と、C.Cocks著、AnIdentityBasedEncryptionSchemeBasedonQuadraticResiduesinProc.ofCryptographyandCoding2001,LectureNotesinComputerScience2260,Springer2001と、A.Menezes、P.vanOorschot及びScottVanstone著、HandbookofAppliedCryptography,Chapter10,http://www.cacr.math.uwaterloo.ca/hac/で入手可能、を参照されたい。さらに、本発明の圧縮及び復元方式は、セキュリティがモジュラ平方根を計算することに基づく方式に対し、大域的な帯域幅効率を向上する。Fareyの区間に基づく圧縮及び復元方式を用いずに帯域幅縮小方式を実現することもできる。以下、本発明のかかる2つの実施形態、暗号化方式及び署名方式、を説明する。両方とも、ある状況下では、圧縮及び復元に基づく本発明の実施形態よりもさらに大きい帯域幅縮小を享受するものであるしかし、証明可能なセキュリティを失う可能性など、他の望ましい性質を犠牲にするかもしれない。Coppersmithの方式を通常のRabin署名リスト7、8又は通常の低指数RSA署名リスト3及び4に適用することによって、おそらく帯域幅を縮小した署名方式を得ることができる。D.J.Bernstein著、ProvingTightSecurityforStandardRabin‐WilliamsSignatures,http://cr.yp.to/djb.htmlで入手可能、と、D.Bleichenbacher著、CompressedRabinSignaturesinProc.ofCT-RSA2004,LectureNotesinComputerScience2964,pp.126-128.Springer,2004と、D.Coppersmith著、FindingaSmallRootofaUnivariateModularEquationinProc.ofEurocrypt1996,LectureNotesinComputerScience,pp.155‐165.Springer‐Verlag,1996、とを参照されたい。例えば、eを、Nを法とするRabin又はRSA署名方式の公開指数とし、xを、リスト3又は7におけるように得られる通常の署名とする。Coppersmithの方式では、誰でもNについてのトラップドア情報を必要とすることなく、例えば、x2とxの最上位ビットとから、x∈[1,N]を復元することができる。従って、Rabin署名e=2について、図4の方法は以下のように変更することができる。リスト32:1.ステップ410:HMを計算する。Hは、全領域関数、すなわちその値域が[1,N]である関数例えばリスト7を参照であることもあれば、部分領域ハッシュ関数、すなわちその値域が[1,N]の真部分集合である関数であることもある。2.ステップ420:x2=HMmodNとなるように署名x=sMを計算する。3.ステップ430:xの最上位ビットを送信する。また、HMかHMを復元するのに十分な何らかの情報を送信する。リスト32の終了。しかしながら、HMを復元するのに十分な情報も送信しなければならないので、xの最上位ビットだけを送信することによって実現できる圧縮は、少し非現実的である。ステップ430で、HM自体を送信しなければならないならば、この署名方式は、明らかに望ましいメッセージ復元特性を有していない。B2N,h,h′内の数を見つけるための発見的方法を用いることによって、帯域幅縮小暗号化方式を得ることができる。ここで、h′はと同じくらい小さいことがある。しかしながら、発見的抜き出し方式を用いた結果生じる暗号化方式は、証明可能なセキュリティを享受するものではない。発見的に、集合S=B2N,h,h′により図10のセキュリティプルーフモデルを用いるために、について、B2N,h,h′内の数を以下のように生成することができる。リスト33:1.任意のとを選択する。2.を計算する。3.x=x′bを計算する。リスト33の終了。について、であることを容易に示すことができる。これらの観測は、以下の暗号化方式につながる。リスト34:1.メッセージをa,bにエンコードする。ここで、aは、メッセージの最初の2εalog2Nビットであり、bは、残りのビットであり、2εalog2N,2εblog2Nは、最も近い整数に切り下げている。2.リスト33におけるようにxを計算する。3.暗号文をc=x2modNに設定する。リスト34の終了。の適切なεa,εbについて、a,bを、従ってメッセージを、以下のように復元することができる。リスト35.1.xをcのモジュラ平方根として計算する。2.を計算する。リスト35の終了。この方式の考えられる1つの不利点は、因数分解から証明可能な縮小を提供するのがおそらく難しいということである。多くの暗号化方式及び署名方式におけるように、プロトコルの計算複雑性を増すことによって、帯域幅のさらなる縮小‐小さい定数cについて約cloglogNビット本明細書中、特に断りのない限り、対数は底2である‐を実現することができる。例えば、単に最終cloglogNビットを送信しないことによって、暗号文のサイズをさらに減少することができる。デクリプターdecrypterは単に、復号化方式を、必要ならば、回まで繰り返すことによって、それらの最終ビットを推測すればよい。同様に、エンクリプターencrypterは、一時的な暗号文が最終的に全て0である最終cloglogNビットを有するように、一時的暗号ごとに異なる乱数度を用いて、暗号化方式を期待されるlogNc回行うことができ、その場合、それらのビットを送信する必要はない。署名及び検証に同様のシナリオが当てはまる。10.システムと構成要素帯域幅を縮小した暗号化、署名、サインクリプション、集合署名、及びリング署名方式と、圧縮及び復元方式とは、図1のコンピュータシステム110及びネットワーク120を使用して実現することができる。各システム110は、ネットワーク図示せずによって相互接続された多数のコンピュータシステムを含む分散システムであってもよいしそうでなくてもよい。各システム110は、本発明の方式を実行するための、例えば半導体、磁気、光、又は他の種類の記憶装置などの公知の又は考案したコンピュータ可読媒体図示せずに記憶したコンピュータ命令を実行するようにプログラム化した、1つ又は複数の処理装置図示せずを含むことがある。さらに、又はその代わりに、各システム110は、本発明の方式を実行するためのハードワイヤード回路を含むことがある。ネットワーク120はインターネット及び/又は無線通信ネットワークや、任意の種類の通信が送信される他の種類のネットワークであることがある。本発明の方式を実現するコンピュータ命令は、ケーブル、電波、又は他の手段で、物理的信号例えば電磁信号に組み込まれて、システム110へ又はシステム110から送信することができる。信号は、搬送波で変調してもしなくてもよい。コンピュータシステム110は、本発明の暗号化、署名、サインクリプション、集合署名、又はリング署名の実施形態において用いられる公開鍵に関連する、真正性や所有権や属性を証明するための公開鍵証明書を提供することができる、サーバ証明要素証明者として使用することがある。証明者は公開鍵を別のシステム110に送信することができる。また、証明者110は、権限保持者が使用するための公開鍵及び秘密鍵を生成し、それらを圧縮暗号化形式で別のシステム110に送信することによって権限保持者に提供することができる。非証明者システム110は、証明者システム110を通じて、又は直接に、暗号文や署名を互いに送信することができる。暗号文や署名はまた、電子媒体例えばディスクで非電子的に例えば通常のメールによって転送することができる。いくつかの実施形態において得られる付加的な特徴が、C.Gentryによる前述の論文、HowtoCompressRabinCiphertextsandSignaturesandMoreに述べられている。本発明は、上述の実施形態に限定されるものではない。例えば、上述の方法や、セキュリティプルーフは、集合BN,h,h′やBZN,h,h′に拡張することができる。BN,h,h′はB2N,h,h′からなり、B2N,h,h′,BZN,h,h′内の数のNを法とする負数は、1以外のNに関する公約数を有する数を除くが、Nが2つの素数の積であれば、かかる数の集合は非常に小さいことに注意されたい。いくつかの実施形態は集合BN,Q,B2N,Q,BZN,Qを用い、ここでQは[h,h′]以外である。特に、Qは[h,h′],h,h′又はh,h′であることがある。また、B2N,Qはx=0を含まないように、すなわち{x∈[1,N]:x2modN∈Q}と定義することができる。本発明はセキュリティプルーフが有効である方式に限定されない。上記で、ビットストリングx=x0x1...xn-1について、それに対応する数がx0x12...xn-12n-1となるように、ビットストリングは数に対応付けられていたが、他の数値表現を用いることもできる。他の実施形態や変更例は、添付の請求項によって定義する本発明の範囲内にある。"