(57)【特許請求の範囲】
【請求項１】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、メッセージを暗号化する暗号化装置であって、
暗号化すべき第１メッセージを取得する取得手段と、
複数の値によって構成される所定セットに含まれる第１値を前記第１メッセージから決定し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外である第１決定手段と、
第２値を決定するために、前記第１値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記第２値の平方数の法Ｎが前記第１所定範囲内であるマッピング手段と、
前記第２値の平方数の法Ｎに等しい第３値を計算する計算手段と、
少なくとも前記第１メッセージが暗号化された暗号文を前記第３値から決定し、前記暗号文の長さは前記第３値の長さに応じて定められる第２決定手段とを備えることを特徴とする暗号化装置。
【請求項２】
前記所定セットは、区間であり、
前記マッピング手段は、
前記所定セットを第１所定区間にマッピングする第１マッピングにおいてＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間が前記第１値の写像を含むように、前記第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を決定する手段と、
前記所定セットに含まれる前記第１値の数列に対応する前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間に含まれる数列を有する整数として、前記第２値を決定する手段とを有することを特徴とする請求項１に記載の暗号化装置。
【請求項３】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、暗号文を復号化する復号化装置であって、
少なくとも第１メッセージが暗号化された第１暗号値を前記暗号文から決定し、前記第１暗号値は、前記第１所定範囲に含まれる第１決定手段と、
前記第１暗号値から取得される値の平方根の法Ｎと等しい第１復号値を前記第１暗号値から計算する計算手段と、
複数の値によって構成される所定セットに含まれる第２復号値を決定するために、前記第１復号値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるマッピング手段と、
前記第２復号値から前記第１メッセージを決定する第２決定手段とを備えることを特徴とする復号化装置。
【請求項４】
前記マッピング手段は、
前記第１復号値を含む第１対応区間を前記第１復号値から決定し、前記第１対応区間は、第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間である手段と、
前記第１対応区間に含まれる前記第１復号値の数列から前記第２復号値を決定する手段とを有することを特徴とする請求項３に記載の復号化装置。
【請求項５】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、メッセージに電子的に署名する署名装置であって、
電子的に署名すべき第１メッセージを取得する取得手段と、
前記第１所定範囲に含まれる第１メッセージ値を前記第１メッセージから決定する決定手段と、
第１署名値から取得される値の平方根の法Ｎと等しい前記第１署名値を前記第１メッセージ値から計算する計算手段と、
複数の値によって構成される所定セットに含まれる第２署名値を決定するために、前記第１署名値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるマッピング手段とを備えることを特徴とする署名装置。
【請求項６】
前記マッピング手段は、
前記第１署名値を含む第１対応区間を前記第１署名値から決定し、前記第１対応区間は、第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間である手段と、
前記第１対応区間に含まれる前記第１署名値の数列から前記第２署名値を決定する手段とを有することを特徴とする請求項５に記載の署名装置。
【請求項７】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、電子署名を検証する検証装置であって、
メッセージＭの署名として用いるべき第１電子署名を取得する取得手段と、
複数の値によって構成される所定セットに含まれる第１値を前記第１電子署名から決定し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外である決定手段と、
第２値を決定するために、前記第１値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記第２値の平方数の法Ｎが前記第１所定範囲内であるマッピング手段と、
前記第１所定範囲に含まれる第３値を、前記第２値の平方数の法Ｎに基づいて計算する計算手段と、
前記第１電子署名が前記メッセージＭの署名として正しいか否かを判定する判定手段とを備えることを特徴とする検証装置。
【請求項８】
前記所定セットは、区間であり、
前記マッピング手段は、
前記所定セットを第１所定区間にマッピングする第１マッピングにおいてＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間が前記第１値の写像を含むように、前記第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を決定する手段と、
前記所定セットに含まれる前記第１値の数列に対応する前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間に含まれる数列を有する整数として、前記第２値を決定する手段とを有することを特徴とする請求項７に記載の検証装置。
【請求項９】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１所定区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項２に記載の暗号化装置。
【請求項１０】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項９に記載の暗号化装置。
【請求項１１】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項１０に記載の暗号化装置。
【請求項１２】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１対応区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項４に記載の復号化装置。
【請求項１３】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項１２に記載の復号化装置。
【請求項１４】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項１３に記載の復号化装置。
【請求項１５】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１対応区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項６に記載の署名装置。
【請求項１６】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項１５に記載の署名装置。
【請求項１７】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項１６に記載の署名装置。
【請求項１８】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１所定区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項８に記載の検証装置。
【請求項１９】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項１８に記載の検証装置。
【請求項２０】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項１９に記載の検証装置。
【請求項２１】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、メッセージを暗号化する暗号化方法であって、
装置の取得手段が、暗号化すべき第１メッセージを取得するステップと、
前記装置の第１決定手段が、複数の値によって構成される所定セットに含まれる第１値を前記第１メッセージから決定し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるステップと、
前記装置のマッピング手段が、第２値を決定するために、前記第１値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記第２値の平方数の法Ｎが前記第１所定範囲内であるステップと、
前記装置の計算手段が、前記第２値の平方数の法Ｎに等しい第３値を計算するステップと、
前記装置の第２決定手段が、少なくとも前記第１メッセージが暗号化された暗号文を前記第３値から決定し、前記暗号文の長さは前記第３値の長さに応じて定められるステップとを備えることを特徴とする暗号化方法。
【請求項２２】
前記所定セットは、区間であり、
前記マッピング手段が、前記所定セットを第１所定区間にマッピングする第１マッピングにおいてＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間が前記第１値の写像を含むように、前記第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を決定するステップと、
前記マッピング手段が、前記所定セットに含まれる前記第１値の数列に対応する前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間に含まれる数列を有する整数として、前記第２値を決定するステップとを備えることを特徴とする請求項２１に記載の暗号化方法。
【請求項２３】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、暗号文を復号化する復号化方法であって、
装置の第１決定手段が、少なくとも第１メッセージが暗号化された第１暗号値を前記暗号文から決定し、前記第１暗号値は、前記第１所定範囲に含まれるステップと、
前記装置の計算手段が、前記第１暗号値から取得される値の平方根の法Ｎと等しい第１復号値を前記第１暗号値から計算するステップと、
前記装置のマッピング手段が、複数の値によって構成される所定セットに含まれる第２復号値を決定するために、前記第１復号値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるステップと、
前記装置の第２決定手段が、前記第２復号値から前記第１メッセージを決定するステップとを備えることを特徴とする復号化方法。
【請求項２４】
前記マッピング手段が、前記第１復号値を含む第１対応区間を前記第１復号値から決定し、前記第１対応区間は、第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間であるステップと、
前記マッピング手段が、前記第１対応区間に含まれる前記第１復号値の数列から前記第２復号値を決定するステップとを備えることを特徴とする請求項２３に記載の復号化方法。
【請求項２５】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、メッセージに電子的に署名する署名方法であって、
装置の取得手段が、電子的に署名すべき第１メッセージを取得するステップと、
前記装置の決定手段が、前記第１所定範囲に含まれる第１メッセージ値を前記第１メッセージから決定するステップと、
前記装置の計算手段が、第１署名値から取得される値の平方根の法Ｎと等しい前記第１署名値を前記第１メッセージ値から計算するステップと、
前記装置のマッピング手段が、複数の値によって構成される所定セットに含まれる第２署名値を決定するために、前記第１署名値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるステップとを備えることを特徴とする署名方法。
【請求項２６】
前記マッピング手段が、前記第１署名値を含む第１対応区間を前記第１署名値から決定し、前記第１対応区間は、第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間であるステップと、
前記マッピング手段が、前記第１対応区間に含まれる前記第１署名値の数列から前記第２署名値を決定するステップとを備えることを特徴とする請求項２５に記載の署名方法。
【請求項２７】
所定合成数の法Ｎと、１からＮまでの数の範囲よりも短い第１所定範囲とを用いて、電子署名を検証する検証方法であって、
装置の取得手段が、メッセージＭの署名として用いるべき第１電子署名を取得するステップと、
前記装置の決定手段が、複数の値によって構成される所定セットに含まれる第１値を前記第１電子署名から決定し、前記所定セットは、少なくとも１つの値を含み、前記少なくとも１つの値の平方数の法Ｎが前記第１所定範囲外であるステップと、
前記装置のマッピング手段が、第２値を決定するために、前記第１値に対して、Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を用いた所定マッピングを適用し、前記第２値の平方数の法Ｎが前記第１所定範囲内であるステップと、
前記装置の計算手段が、前記第１所定範囲に含まれる第３値を、前記第２値の平方数の法Ｎに基づいて計算するステップと、
前記装置の判定手段が、前記第１電子署名が前記メッセージＭの署名として正しいか否かを判定するステップとを備えることを特徴とする検証方法。
【請求項２８】
前記所定セットは、区間であり、
前記マッピング手段が、前記所定セットを第１所定区間にマッピングする第１マッピングにおいてＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間が前記第１値の写像を含むように、前記第１所定区間用のＦａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間を決定するステップと、
前記マッピング手段が、前記所定セットに含まれる前記第１値の数列に対応する前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間に含まれる数列を有する整数として、前記第２値を決定するステップとを備えることを特徴とする請求項２７に記載の検証方法。
【請求項２９】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１所定区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項２２に記載の暗号化方法。
【請求項３０】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項２９に記載の暗号化方法。
【請求項３１】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項３０に記載の暗号化方法。
【請求項３２】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１対応区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項２４に記載の復号化方法。
【請求項３３】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項３２に記載の復号化方法。
【請求項３４】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項３３に記載の復号化方法。
【請求項３５】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１対応区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項２６に記載の署名方法。
【請求項３６】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項３５に記載の署名方法。
【請求項３７】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項３６に記載の署名方法。
【請求項３８】
前記第１所定範囲は、（ｈ，ｈ’）、［ｈ，ｈ’），（ｈ，ｈ’］、［ｈ，ｈ’］のいずれかであり、
ｈ及びｈ’は、所定数であり、
前記第１所定区間は、［０，Ｎ／２］であり、
前記Ｆａｒｅｙ区間或いはＦａｒｅｙ拡張分割区間は、ｋ＝２Ｎ／（ｈ’−ｈ）の順で巡回する整数であることを特徴とする請求項２８に記載の検証方法。
【請求項３９】
ｈ’−ｈ＜８Ｎ２／３＋１の関係が満たされることを特徴とする請求項３８に記載の検証方法。
【請求項４０】
所定セットは、２（ｈ’−ｈ）／５の長さの区間であることを特徴とする請求項３９に記載の検証方法。
【請求項４１】
請求項２１に記載のステップをコンピュータに実行させることを特徴とする暗号化プログラム。
【請求項４２】
請求項２３に記載のステップをコンピュータに実行させることを特徴とする復号化プログラム。
【請求項４３】
請求項２５に記載のステップをコンピュータに実行させることを特徴とする署名プログラム。
【請求項４４】
請求項２７に記載のステップをコンピュータに実行させることを特徴とする検証プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００３年１０月３１日に出願された合衆国仮出願第６０／５１５，９８２号の優先権を主張し、参照により本明細書に含む。
【０００２】
本発明は、コンピュータネットワーク上の安全な通信を含む暗号化及び安全な通信に関する。本発明は、暗号化されたメッセージ、署名、その他の暗号情報のサイズを縮小するのに用いることができる。
【背景技術】
【０００３】
暗号化されたメッセージ（「暗号文」）や署名等の暗号情報は、ネットワーク上で又は電子記憶媒体によりメールで受信者に送られる。暗号化を安全なものにするために、暗号文は、それに対応する暗号化されていない「プレーンテキスト」よりもかなり長くなることがある。同様に、署名は、該署名が生成されるメッセージよりもかなり長くなることがある。従って、望ましくはセキュリティを損なうことなく、暗号文や署名のサイズ（「帯域幅」）を縮小することが望ましい。
【０００４】
図１乃至図５に、ネットワーク１２０によって相互接続されたコンピュータシステム１１０（図１）間における暗号文及び署名の生成及び転送を示している。図２は、暗号文ｃを得るために「プレーンテキスト」メッセージＭに対してシステム１１０が実行する暗号化処理のフローチャートである。適切な暗号化の前に、メッセージＭは、値Ｈ（Ｍ）にエンコードされる（ステップ２１０）。エンコードは、異なる暗号化演算における同じメッセージＭに対して、異なるエンコードされたメッセージＨ（Ｍ）、よって異なる暗号文ｃを得ることができるように、いくつかのパディング及び／又はランダムビットをメッセージＭに加えてもよい。これにより、攻撃者が同じ暗号化方式により得られる異なる暗号文を傍受した場合に、攻撃者が復号化方式を推測（「戻換」）するのは難しくなる。
【０００５】
ステップ２２０で、エンコードされたメッセージＨ（Ｍ）を暗号化して、暗号文ｃを得る。ステップ２３０で、暗号文をネットワーク１２０を通じて他のシステム１１０に送信する。
【０００６】
復号化処理（図３）は、暗号化の逆である。暗号文ｃは、受信者システム１１０によって受信され（ステップ３０４）、復号化されてエンコードされたメッセージＨ（Ｍ）が復元される（ステップ３１０）。エンコードされたメッセージは、デコードされ（ステップ３２０）、元のメッセージＭが復元される。
【０００７】
図２において、エンコードステップ２１０と暗号化２２０とは、別個のステップとして示している。なぜなら、エンコード方式２１０及びデコード３２０（図３）は、公開されることがあるが、復号化３１０や場合により暗号化２２０は、秘密情報（例えば秘密鍵）に依拠しているからである。また、ステップ２１０と２２０との組み合わせを示すのに「暗号化」という表現を用いるのは適切であり、ステップ３１０と３２０との組み合わせに「復号化」という表現を用いるのは適切であり、また／或いは、エンコードステップ２１０とデコード３２０を省略すると言っても適切である。
【０００８】
図４に、システム１１０が実行する署名生成を示す。ステップ４１０で、メッセージＭをＨ（Ｍ）にエンコードし、ステップ４２０で、エンコードされたメッセージを処理して（署名して）、署名ｓ（Ｍ）を得る。署名ｓ（Ｍ）をネットワーク１２０を通じて受信者システム１１０に送信する（ステップ４３０）。受信者システム１１０は、図５に示すように署名を検証する。ステップ５０４で署名を受信し、ステップ５１０で処理して、エンコードされたメッセージＨ（Ｍ）を復元する。エンコードされたメッセージをデコードして（ステップ５２０）、元のメッセージＭを取得し、あるテストを行って該メッセージＭが確かに署名されたメッセージであるかどうか検証する。例えば、元のメッセージを別の送信で受信者システム１１０に提供して、ステップ５２０で復元したメッセージと比較することができる。いくつかの実施形態においては、メッセージはデコードせず、メッセージを復元することなく検証を実行することができる。
【０００９】
図４及び図５において、エンコードステップ４１０とステップ５２０とのデコードは、別個の動作として示しているが、ステップ４１０と４２０との組み合わせに「署名」という表現を用いるのも適切であり、ステップ５１０と５２０との組み合わせに「検証」という表現を用いるのも適切であり、また／或いは、エンコードステップ４１０とステップ５２０のデコード部分を省略すると言っても適切である。
【００１０】
公開鍵暗号化方式において、鍵所有者（システム１１０の１つのユーザ）は、２つの鍵、公開鍵（他者にも広く配信してもよい）と秘密鍵とを所有する。暗号化されたメッセージを鍵所有者に送信するために、送信者（別のシステム１１０のユーザ）は、図２のステップ２２０で、鍵所有者の公開鍵を用いてメッセージを暗号化し、暗号文を鍵所有者に送信する。エンコード方式及びデコード方式（図２及び図３のステップ２１０、３２０）は、公開されていてもよい。鍵所有者は、ステップ３２０でその秘密鍵を用いて、暗号文を復号化する。暗号化方式が安全であるために、秘密鍵を所有しない者が送信された暗号文を復号化することは不可能でなければならない。
【００１１】
公開鍵署名方式において、鍵所有者は、同様に公開鍵及び秘密鍵を使用する。ステップ４２０（図４）で、鍵所有者は、特定の方法でメッセージに秘密鍵を適用することによって、該メッセージに署名する。検証者は、（図５のステップ５１０で）鍵所有者の公開鍵を署名に適用し、（ステップ５２０で）ある特定の条件が満たされているかをチェックすることによって、鍵所有者がメッセージに署名したことを確認してもよい。署名方式が安全であるために、鍵所有者の秘密鍵を所有しない者が、鍵所有者が実際に署名したことがないメッセージについて、鍵所有者の署名を偽造することは不可能でなければならない。
【００１２】
公開鍵サインクリプション（ｐｕｂｌｉｃ−ｋｅｙ  ｓｉｇｎｃｒｙｐｔｉｏｎ）方式において、望ましくは、送信者が署名と暗号文を別々に送信した場合よりも、サインクリプション送信（ｓｉｇｎｃｒｙｐｔｉｏｎ  ｔｒａｎｓｍｉｓｓｉｏｎ）が少ない帯域幅を消費するように、送信者（システム１１０のユーザ）は、送信者の秘密鍵でメッセージＭをエンコードし署名し（図４のステップ４２０参照）、次に受信者の公開鍵で、署名されたメッセージｓ（Ｍ）を暗号化する（図２のステップ２２０参照）。（別のシステム１１０の）受信者は、その秘密鍵でサインクリプションを復号化し、送信者の公開鍵で送信者の署名を検証する。
【００１３】
公開鍵集合署名（ｐｕｂｌｉｃ−ｋｅｙ  ａｇｇｒｅｇａｔｅ  ｓｉｇｎａｔｕｒｅ）方式において、それぞれ公開鍵｛ＰＫ１，…，ＰＫｚ｝を有する署名者の集合｛Ｓ１，…，Ｓｚ｝は、彼らの集合署名−すなわち、各署名者ＳｉがメッセージＭｉに署名したことを検証するのに必要なビットストリング−が「短」かく、望ましくは、各署名者がそれぞれのメッセージに別々に署名した場合よりも少ない帯域幅を消費するように、それぞれのメッセージ｛Ｍ１，…，Ｍｚ｝に署名する。集合署名は、公開鍵｛ＰＫ１，…，ＰＫｚ｝を用いて検証される。
【００１４】
公開鍵リング署名（ｐｕｂｌｉｃ−ｋｅｙ  ｒｉｎｇ  ｓｉｇｎａｔｕｒｅ）方式において、署名者Ｓｉは、Ｓｉが一員である署名者の集合｛Ｓ１，…，Ｓｚ｝（すなわちＳｉ∈｛Ｓ１，…，Ｓｚ｝）を任意に選ぶことができ、検証者は誰であるかを確定できないが、｛Ｓ１，…，Ｓｚ｝の少なくとも１人の署名者がメッセージに署名したことを検証者に確信させる、メッセージに対する「リング署名」を生成する。従って、署名者Ｓｉは、可能性のある署名者の「リング」内で限定的な匿名性を有する。検証者は、公開鍵｛ＰＫ１，…，ＰＫｚ｝を用いてリング署名を検証する。通常、可能性のある署名者がｚ人のリング署名は、ｚ個の別々の署名と同じ長さであり、従って、基礎となる署名方式の帯域幅効率が良いことは不可欠である。
【００１５】
１９７６年に、Ｄｉｆｆｉｅ及びＨｅｌｌｍａｎは、公開鍵暗号化及び署名方式という概念を発表したが、具体的な実例を見つけることはできなかった。Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ及びＡｄｌｅｍａｎは、Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，ｖ．２１  ｎ．２，ｐ．１２０−１２６，１９７８）という論文で、最初の公開鍵暗号化及び署名方式（今では「ＲＳＡ」方式として知られている）を提案したが、参照により本明細書に含まれる。
【００１６】
概略を言えば、ＲＳＡ暗号化方式は、以下のとおりである。鍵所有者は、合成（すなわち非素数の）整数法Ｎ＝ｐｑを生成する。ここで、ｐ及びｑは、大きい素数である（例えば５１２ビット）。鍵所有者は、また、φ（Ｎ）＝（ｐ−１）＊（ｑ−１）を計算する。最後に、鍵所有者は、ｅｄ≡１（ｍｏｄ  φ（Ｎ））となるように、共に１よりも大きい整数ｅ及びｄを計算する。鍵所有者は、その公開鍵として（Ｎ，ｅ）を公開し、ｐとｑとｄを秘密にしておく。
【００１７】
メッセージＭを暗号化するために、送信者は、以下の「リスト１」に列挙した演算を実行する。
【００１８】
リスト１：ＲＳＡ暗号化
Ｍを［０，Ｎ−１］の整数ｍとして表現し、次に、暗号文ｃ≡ｍｅ（ｍｏｄ  Ｎ）を設定する。
【００１９】
リスト１の終了。
【００２０】
暗号文を復号化するために、鍵所有者は、以下の演算を実行する。
【００２１】
リスト２：ＲＳＡ復号化
ｃｄ≡ｍｅｄ≡ｍ（ｍｏｄ Ｎ）を計算する。
【００２２】
リスト２の終了
暗号文は［１，Ｎ］の数であり、およそｌｏｇ２Ｎビットの長さであることに注意されたい。この復号化は、メッセージエンコードを仮定していないが、メッセージエンコードを使用することもできる。
【００２３】
ＲＳＡ署名方式について、鍵所有者は、その鍵をＲＳＡ暗号化におけるように生成する。適切にエンコードされたメッセージｍ∈［１，Ｎ］に署名するために、鍵所有者は、以下の演算を実行する。
【００２４】
リスト３：ＲＳＡ署名
ｓ＝ｍｄ（ｍｏｄ Ｎ）を計算する。
【００２５】
リスト３の終了
検証者は、鍵所有者の公開鍵を用いて、以下の演算を実行することにより署名ｓを確認することができる。
【００２６】
リスト４：ＲＳＡ署名
ｓｅ≡ｍ（ｍｏｄ Ｎ）かどうかチェックする。
【００２７】
リスト４の終了
この場合も、署名は、およそｌｏｇ２Ｎビットの長さである。
【００２８】
Ｒａｂｉｎは、Ｄｉｇｉｔａｌｉｚｅｄ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｆｕｎｃｔｉｏｎｓ  ａｓ  Ｉｎｔｒａｃｔａｂｌｅ  ａｓ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  （ＭＩＴ／ＬＣＳ／ＴＲ−２１２，ＭＩＴ  Ｌａｂｏｒａｔｏｒｙ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ，ＵＳＡ  １９７９）という論文で、少し違った暗号化方式及び署名方式を提案したが、参照により本明細書に含まれる。この方式において、鍵所有者は、ＲＳＡにおけるように法Ｎを生成し、その公開鍵を（Ｎ，ｅ）に設定する。適切にエンコードされたメッセージｍに対し、暗号文はｃ＝ｍｅ（ｍｏｄ Ｎ）である点で、暗号化もまたＲＳＡと同じである。暗号文は、およそｌｏｇ２Ｎビットである。しかしながら、Ｒａｂｉｎの方式では、特定の値ｅ＝２を使用する。これには２つの理由がある。第１に、ｅ＝２に設定すると、非常に高速な暗号化及び署名検証が可能になる。第２に、法Ｎを因数分解するのは難しいと仮定して、ｅ＝２に設定すると、その結果生じる方式は解読するのが難しいことを証明することができる。（適切なエンコードを用いて）因数分解をＲａｂｉｎの方式に変形することは当技術において公知である。
【００２９】
以下、ＯＡＥＰ＋メッセージエンコードを含むＲａｂｉｎ暗号化方式について説明する。基礎となる暗号化方式が解読しにくいものと仮定して、ＯＡＥＰ＋エンコードは、ランダムオラクルモデルにおいて、適応的選択暗号文攻撃に対して証明可能なセキュリティをもたらす。
【００３０】
ＯＡＥＰ＋エンコード方式では、（図２のステップ２１０で）以下の式（１）によって定義される３つのハッシュ関数を用いる。
【数１】
0005412626.tif 000002
【００３１】
ここで、ｍ，ｋ０，ｋ１は、所定の正の整数のセキュリティパラメータである。ｉごとに、式｛０，１｝ｉは、長さｉの全ての０と１のストリング（「ビットストリング」）の集合を示す。同式は、また、ｉ以下の長さの全てのビットストリングの集合を示す。ストリング長がｉよりも短い場合、該ストリングは左側に０を付け加えて長さｉにすることができる。式（１）のこのＨ関数は、中間値に使用して、メッセージエンコードを計算するためのものであり、図２のステップ２１０に示すエンコードされたメッセージＨ（Ｍ）と混同すべきではない。高いセキュリティを得るために、数量
【数２】
0005412626.tif 000003
【００３２】
と、
【数３】
0005412626.tif 000004
【００３３】
は、ごくわずかであるべきだが、正の整数であればうまくいく。ｎ＝ｍ＋ｋ０＋ｋ１であれば、望ましくは２ｎ＜Ｎ＜２ｎ＋２ｎ−１となるようにＮを選択する。メッセージＭ∈｛０，１｝ｍを暗号化するために、送信者は、以下の演算を実行する。
【００３４】
リスト５：Ｒａｂｉｎ‐ＯＡＥＰ暗号化手順
（ステップ２１０（図２）は、以下のステップ１乃至３に対応する。）
１．任意の
【数４】
0005412626.tif 000005
【００３５】
を選択する。
【００３６】
２．
【数５】
0005412626.tif 000006
【００３７】
及び
【数６】
0005412626.tif 000007
【００３８】
を設定する。ここで、二重縦棒の記号“‖”は、ストリング連結を示す。
【００３９】
３．ｎビットストリングである、ｘ←ｓ‖ｔを設定する（ｘは、図２のステップ２１０の最終的にエンコードされた値Ｈ（Ｍ）に対応する）。
【００４０】
４．ステップ２２０：暗号文ｃ←ｘ２（ｍｏｄ Ｎ）を計算する。ここで、ビットストリングｘは、１つの数として解釈する。ｘ＝ｘ０ｘ１…ｘｎ−１に関し、該数は、ｘ０＋ｘ１*２＋…＋Ｘｎ−１*２ｎ−１である。
【００４１】
リスト５の終了。
【００４２】
復号化のために、受信者は、以下の演算を実行する。
【００４３】
リスト６：Ｒａｂｉｎ−ＯＡＥＰ復号化手順
１．ステップ３１０（図３）：Ｎを法とするｃのモジュラ平方根を計算する（図３のステップ３１０）。お分かりのように、Ｎは、２つの素数の積であるので、ｃは、４つのモジュラ平方根ｘ１，ｘ２，ｘ３，ｘ４まで持つことができ、ここでｘ１＝−ｘ２であり、ｘ３＝−ｘ４である。ｘ１及びｘ２の少なくとも１つと、ｘ３及びｘ４の少なくとも１つは、ｎ以下のビットを有する。一般性を失うことなく、ｘ１及びｘ３のそれぞれは、ｎ以下のビットを有するものとする。
【００４４】
２．ステップ３２０：受信者は、
【数７】
0005412626.tif 000008
【００４５】
と、
【数８】
0005412626.tif 000009
【００４６】
について、各候補ｘｉ（ｉ＝１，３）を、ｓｉ‖ｔｉに構文解析し、次に、
【数９】
0005412626.tif 000010
【００４７】
について、ｓｉを、
【数１０】
0005412626.tif 000011
【００４８】
に構文解析する。ｉ＝１，３ごとに、受信者は、
【数１１】
0005412626.tif 000012
【００４９】
及び
【数１２】
0005412626.tif 000013
【００５０】
を計算し、
【数１３】
0005412626.tif 000014
【００５１】
かどうかテストする。条件が満たされる唯一のｉが存在する場合、受信者は、正確なプレーンテキストとしてＭｉを出力し、そうでなければ（かかるｉがない場合や、ｉ＝１とｉ＝３の両方に対し条件が満たされる場合）、受信者は、復号化の失敗を示す。
【００５２】
リスト６の終了。
【００５３】
以下、全領域ハッシュを用いたメッセージ復元によるＲａｂｉｎ署名方式について説明する。「全領域ハッシュ」という表現は、ハッシュ関数（１がそれぞれ最大値ｍ，ｋ１，ｋ０と同じ長さの値を持つことができることを意味する。エンコードや、さらにはモジュラ平方根の計算に対し様々なアプローチが可能である。以下の説明は、可能なアプローチの１つにすぎない。上記のＲａｂｉｎ暗号化に関する関連パラメータを、ｐ≡３（ｍｏｄ  ８）及びｑ≡７（ｍｏｄ  ８）という付加的な制約で定義すると、署名者は、以下の演算を実行する。
【００５４】
リスト７：Ｒａｂｉｎ−ＯＡＥＰ署名手順
エンコードステップ４１０（図４）は、以下のステップ１乃至２に対応する。
【００５５】
１．任意の
【数１４】
0005412626.tif 000015
【００５６】
を選択する。
【００５７】
２．
【数１５】
0005412626.tif 000016
【００５８】
及び
【数１６】
0005412626.tif 000017
【００５９】
を設定する。
【００６０】
３．ｎビットの整数である、ｙ←ｓ′‖ｓ″‖ｔを設定する。値ｙは、図４のＨ（Ｍ）に対応する。署名ステップ４２０（図４）は、以下のステップ４乃至１１に対応する。
【００６１】
４．ｕｑ←ｙ（ｑ＋１）／４（ｍｏｄ  ｑ）を計算する。
【００６２】
５．
【数１７】
0005412626.tif 000018
【００６３】
であれば、ｅｙ←１に設定し、そうでなければ、ｅｙ←−１に設定する。
【００６４】
６．ｕｐ←（ｅｙｙ）（ｐ＋１）／４（ｍｏｄ  ｐ）を計算する。
【００６５】
７．
【数１８】
0005412626.tif 000019
【００６６】
であれば、ｆｙ←１に設定し、そうでなければ、ｆｙ←２に設定する。
【００６７】
８．ｖｑ←ｆｙ（３ｑ−５）／４ｕｑ（ｍｏｄ  ｑ）とｖｐ←ｆｙ（３ｐ−５）／４ｕｐ（ｍｏｄ  ｐ）を計算する。
【００６８】
９．ｗ←ｖｑ＋ｑ（ｑｐ−２（ｖｐ−ｖｑ）ｍｏｄ  ｐ）を計算する。
【００６９】
１０．２ｗ＜Ｎであれば、ｘ←ｗに設定し、そうでなければ、ｘ←Ｎ−ｗに設定する。数ｘは、ｅｙｙ／ｆｙ（ｍｏｄ Ｎ）の平方根である。
【００７０】
１１．署名（ｅｙ，ｆｙ，ｒ，ｘ）を出力する。
【００７１】
リスト７の終了。
【００７２】
２（３ｑ−５）／４（ｍｏｄ  ｑ）、２（３ｐ−５）／４（ｍｏｄ  ｐ）、及びｑｐ−２（ｍｏｄ  ｐ）の値は、事前に計算できる。従って、リスト７のステップ８及び９は、署名時間にほとんど何も付加しない。署名は、以下のように検証される。
【００７３】
リスト８：Ｒａｂｉｎ−ＯＡＥＰ検証手順
１．ステップ５１０（図５）：ｙｔｍｐ←ｅｙｆｙｘ２（ｍｏｄ Ｎ）を計算する。
【００７４】
２．ステップ５２０：ｙｔｍｐがｎビットであることを確認し、ｙｔｍｐを、
【数１９】
0005412626.tif 000020
【００７５】
に構文解析し、
【数２０】
0005412626.tif 000021
【００７６】
及び、
【数２１】
0005412626.tif 000022
【００７７】
を計算し、
【数２２】
0005412626.tif 000023
【００７８】
であることを確認する。
【００７９】
リスト８の終了。
【００８０】
メッセージＭ＝Ｍｔｍｐは、検証処理中に復元されることに注意されたい。
【００８１】
リスト５乃至８の暗号化方式及び署名方式は、因数分解と同じくらい証明可能に安全である（本説明ではプルーフは省略されているが）。これらの方式は、計算上非常に効率的ではあるが、暗号文と署名のビット長は、およそｌｏｇ２Ｎであることにさらに注目されたい。最新の因数分解方式に対して安全であるために、Ｎは、少なくとも１０２４ビットであるべきである。
【００８２】
Ｒａｂｉｎ署名を用いるリング署名方式が、Ｒ．Ｌ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＴ．Ｔａｕｍａｎ著、Ｈｏｗ  ｔｏ  Ｌｅａｋ  ａ  Ｓｅｃｒｅｔ（Ｐｒｏｃ．ｏｆ  Ａｓｉａｃｒｙｐｔ  ２００１，５５２−５６５頁）という論文で提案されており、参照により本明細書に含まれる。概略を言えば、公開法｛Ｎ１，…，Ｎｚ｝を有する署名者｛Ｓ１，…，Ｓｚ｝に対し、この論文は、以下のようなリング署名を提案する。
【００８３】
リスト９：リング署名
リング署名は、（ｘ′１，…，ｘ′ｚ）であり、式
【数２３】
0005412626.tif 000024
【００８４】
を満たす。ここで、
【数２４】
0005412626.tif 000025
【００８５】
であり、ｖ及びｗは、所定のビットストリングであり、Ｃは、「結合関数」である。
【００８６】
リスト９の終了。
【００８７】
この論文は、以下の結合関数を推奨している。
【数２５】
0005412626.tif 000026
【００８８】
ここで、Ｅｋは、鍵ｋを用いた対称暗号化方式である。（対称暗号化方式は、暗号化と復号化の両方に同じ鍵を用いる。メッセージＭは、暗号文Ｅｋ（Ｍ）に暗号化される）。
【００８９】
彼らの方式は、また、法Ｎｉが異なるビット長を有することを避けるうまいやり方を用いる。ｇｉが、関数
【数２６】
0005412626.tif 000027
【００９０】
を示すものとする。
【数２７】
0005412626.tif 000028
【００９１】
に設定する代わりに、定義域｛０，１｝ｂに関して、ｙｉを定義し、ここで、２ｂは、どの法よりもはるかに大きい。具体的に、
リスト１０：リング署名のための２乗
ｘ′ｉ＝ｑｉＮｉ＋ｒｉ∈［０，２ｂ−１］に関し、（ｑｉ＋１）Ｎｉ≦２ｂであれば、ｙｉ＝ｑｉＮｉ＋ｇｉ（ｒｉ）であり、
そうでなければ、ｙｉ＝ｘ′ｉである。
【００９２】
リスト１０の終了。
【００９３】
ここで、ｑｉは、Ｎｉでｘ′ｉを整数除法した商であり、ｒｉは余りである。ｂが十分に大きい限り、（ｑｉ＋１）Ｎｉ＞２ｂである全てのｙｉの割合は無視できるので、写像ｘｉ→ｙｉは、Ｎｉを法とする２乗とほとんど区別が付かない作用をする。
【００９４】
これらの考慮すべき事柄を念頭において、リング署名は、以下のように生成される（Ｓｉは、「真の」署名者であるとする）。
【００９５】
リスト１１：リング署名
１．ｋ＝Ｈ（Ｍ）を計算する。ここで、Ｍは、署名するメッセージであり、Ｈは、ハッシュ関数である。
【００９６】
２．任意のｖ∈｛０，１｝ｂを選択する。
【００９７】
３．ｊ≠ｉごとに、
３Ａ．ｊ≠ｉに対し任意のｘ′ｊ∈｛０，１｝ｂを選択する。
【００９８】
３Ｂ．リスト１０におけるようにｙｊを計算する。
【００９９】
４．
【数２８】
0005412626.tif 000029
【０１００】
となるように、ｙｉを計算する。
【０１０１】
５．Ｎｉについての秘密の知識を用いて、リスト１０の写像によってｘ′ｉがｙｉに写像されるようにｘ′ｉを計算する。
【０１０２】
６．リング署名（ｘ′１，…，ｘ′ｚ，ｖ）を出力する。
【０１０３】
リスト１１の終了。
【０１０４】
ステップ４に関して、
【数２９】
0005412626.tif 000030
【０１０５】
であることに注目されたい。
【０１０６】
次に、
【数３０】
0005412626.tif 000031
【０１０７】
であることに注目されたい。
【０１０８】
一般的に、
【数３１】
0005412626.tif 000032
【０１０９】
であり、リング署名者は、この式を用いて、ｙｊの値からｙｉを計算する（ｊ≠ｉである）。ｘ′ｉを計算するために、リング署名者は、
【数３２】
0005412626.tif 000033
【０１１０】
を計算する。これは、基本的には、単にモジュラ平方根の計算である。ｙｉのいくつかの値は、実際にはそれらの約４分の３は、モジュラ平方根を持たない。この場合、ｙｉがＮｉを法とする平方剰余となるまで、ステップ３を再び実行しなければならない。
【０１１１】
リスト１２：リング署名検証。
【０１１２】
１．ｋ＝Ｈ（Ｍ）を計算する。全てのｊについて、リスト１０の写像を逆にすることによって、ｘ′ｊからｙｊのそれぞれの値を計算する。
【０１１３】
２．
【数３３】
0005412626.tif 000034
【０１１４】
であることを確認する。
【０１１５】
リスト１２の終了。
【０１１６】
上述の暗号化方式及び署名方式において、暗号文と署名は、ｌｏｇ２Ｎ≧１０２４ビット長である。復号化や署名検証は、完全な暗号文や署名を必要とするので、これらのように長い暗号文や署名は、特に、損失をこうむりやすいチャネル上で問題を生じることがある。また、長い暗号文や署名は、暗号文や署名が複数のパケットにわたって分割されるパケットフラグメンテーションに関する問題に遭遇する可能性が高い。また、短い署名や暗号文は、送信するのに電力効率がよい。Ｋ．Ｂａｒｒ及びＫ．Ａｓａｎｏｖｉｃ著、Ｅｎｅｒｇｙ  Ａｗａｒｅ  Ｌｏｓｓｌｅｓｓ  Ｄａｔａ  Ｃｏｍｐｒｅｓｓｉｏｎ（Ｐｒｏｃ．ｏｆ  ＭｏｂｉＳｙｓ  ２００３）によれば、単一ビットの無線送信は、３２ビットの計算の１０００倍以上のエネルギーがかかることがある。バッテリー電源式コンピュータシステムにおいては、無線送信に必要なエネルギー消費は深刻なネックになることがある。また、信号干渉は、所定の領域においてバッテリー電源式システムによって無線送信できるデータ量に物理的制限を設ける。
【０１１７】
セキュリティの観点から、Ｒａｂｉｎの方式は、因数分解と同じくらい解読するのが難しいことが証明できるという非常に望ましい性質を有し、これは可能であれば保持すべき性質である。従って、ｌｏｇ２Ｎビット法を因数分解するのは難解であることを仮定した、しかし、暗号文は、ｌｏｇ２Ｎビットよりもかなり短い、証明可能に安全である暗号化方式が必要である。また、署名がｌｏｇ２Ｎビットよりもかなり短い証明可能に安全な署名方式も必要である。さらに、署名方式は、望ましくは、Ｒａｂｉｎ署名のメッセージ復元特性を保持すべきである。
【０１１８】
また、因数分解に基づくが、Ｒａｂｉｎの暗号化及び署名方式の拡張を用いる方式よりも帯域幅効率が良い、例えば、サインクリプション、集合署名、リング署名などの先進の暗号化方式も必要である。
【発明の概要】
【発明が解決しようとする課題】
【０１１９】
この項では、本発明のいくつかの特徴を要約する。他の特徴は、後の項で説明する。本発明は、添付の請求項により定義され、該請求項は、参照によりこの項に含まれる。
【課題を解決するための手段】
【０１２０】
本発明のいくつかの実施形態によれば、暗号化の前にメッセージを処理して、暗号文を短くする。典型的な処理を、図６のステップ６１０に示す。ステップ２１０（エンコード）、２２０（暗号化）及び２３０（送信）は、図２のようであることがある。特に、暗号化方式２２０は、ある所定長に等しい長さ（例えば、Ｎ−１以下の数の長さ、ここで、Ｎは、Ｒａｂｉｎ暗号化の場合の法である）の暗号文や、より短い暗号文や、場合によっては、より長い暗号文を提供することができる。ステップ２１０（エンコード）の後、写像ステップ６１０を実行して、エンコードされたメッセージＨ（Ｍ）を所定の集合Ｂの中間数ｂに写像する。写像はπと示す。集合Ｂは、暗号化方式２２０がそれについて短い暗号文を生成するあるメッセージの集合である。
【０１２１】
いくつかの実施形態では、ステップ２２０でＲａｂｉｎ暗号化方式を使用する、すなわちｃ＝ｂ２（ｍｏｄ Ｎ）。いくつかの実施形態において、Ｂ＝ＢＮ，Ｑ＝｛ｘ∈［１，Ｎ］：ｘ２（ｍｏｄ Ｎ）∈Ｑ｝であり、ここで、Ｑは、Ｎを法とする全ての整数の真部分集合である。いくつかの実施形態では、Ｑは、ｈ′−ｈ＜Ｎとなるような、ある整数ｈ，ｈ′に関する部分値域［ｈ，ｈ′］である。これらのＱに関し、集合ＢＮ，Ｑは、ＢＮ，ｈ，ｈ′と示す。従って、ＢＮ，ｈ，ｈ′＝｛ｘ∈［１，Ｎ］：ｈ≦ｘ２（ｍｏｄ Ｎ）≦ｈ′｝。
【０１２２】
Ｎを法とする全ての整数の集合ＺＮの数は、公知の方法で円の上の点として示すことができる。部分値域［ｈ，ｈ′］は、集合｛ｈ，ｈ＋１，…ｈ′｝か、集合｛ｈ′，ｈ′＋１，…ｈ｝かである。曖昧さを避けるために、本明細書中、異なる意味が明白に記載されているか、文脈から明らかである場合を除いて、［ｈ，ｈ′］は、２つの部分値域の内、一番小さいものであるとする。特に、ｈ′は、ｈよりも小さい数によって示すことがある。例えば、ｈ＝Ｎ−１＝−１（ｍｏｄ Ｎ）で、ｈ′＝１であるならば、［ｈ，ｈ′］＝｛Ｎ−１，Ｎ，１｝＝｛Ｎ−１，０，１｝である。
【０１２３】
ｈ′−ｈが与えられると、数ｈ，ｈ′にとってよい選択は、ｈ＝０又は−ｈ＝ｈ′である。なぜなら、幅ｈ′−ｈの部分値域の内、０に近い部分値域は、最も短いビット長の数を有するからである。
【０１２４】
いくつかの実施形態において、ＢＮ，ＱがＢ２Ｎ，Ｑ＝｛ｘ∈［０，Ｎ／２］：ｘ２（ｍｏｄ  Ｎ）∈Ｑ｝か、ＢＺＮ，Ｑ＝｛ｘ∈ＺＮ*：ｘ２（ｍｏｄ  Ｎ）∈Ｑ｝によって置き換えられる場合、同様の結果が得られる。ここで、ＺＮ*は、Ｎを法として可逆である（すなわち、Ｎに対し公約数を持たない）全ての整数の集合ｘ∈［０，Ｎ／２］である。Ｑ＝［ｈ，ｈ′］であれば、Ｂ２Ｎ，Ｑは、Ｂ２Ｎ，ｈ，ｈ′と示され、ＢＺＮ，Ｑは、ＢＺＮ，ｈ，ｈ′と示される。
【０１２５】
いくつかの実施形態において、ｈ″＜Ｎのある区間［０，ｈ″］において、エンコードされたメッセージＨ（Ｍ）は、短いメッセージである。また、写像πをステップ６１０でプレーンテキストＭに適用してＭをｂに写像することで、エンコードステップ２１０（図６）は省略することができる。プレーンテキストＭは、［０，ｈ″］に含まれることがある。用語に関して、写像ステップ２１０が存在しても、プレーンテキストＭをある数ｂ∈Ｂに変換するステップ２１０、６１０の組み合わせを述べるのに「エンコード」という表現を用いることができる。
【０１２６】
復号化（図７）は、暗号化処理の逆となることがある。（図３のように）短い暗号文ｃは、ステップ３０４で受信者が受信し、ステップ３１０で復号化して中間メッセージｂ∈Ｂを復元する。復号化方式３１０では、ある所定長に等しい長さ（例えば、Ｎ−１以下の数の長さ、ここでＮはＲａｂｉｎ復号化の場合の法である）の暗号文や、より短い暗号文や、場合によってはより長い暗号文を復号化することができる。ステップ７１０で逆写像π−１を適用して、ｂをＨ（Ｍ）に写像する。次に、Ｈ（Ｍ）をデコードして（ステップ３２０）プレーンテキストＭを復元する。
【０１２７】
本発明のいくつかの実施形態において、短い署名が提供される。図８に、１つの署名方式の実施形態を示す。図４のように、ステップ４１０で、メッセージＭをＨ（Ｍ）にエンコードする。いくつかの実施形態において、メッセージＨ（Ｍ）は、上述の部分値域［ｈ，ｈ′］にある。ステップ４２０で、署名方式を適用してメッセージに署名し、中間署名ｂを得る。この署名方式（例えばモジュラ平方根計算）は、所定の長さ以下の長さや、場合によっては、より長い全てのメッセージＨ（Ｍ）に適応する。ステップ４１０、４２０は、先行技術におけるようなものであっても良いし、そうでなくてもよい。いくつかの実施形態は、ＯＡＥＰ＋エンコードのＲａｂｉｎ署名を用いる。しかしながら、中間署名ｂは、上述のタイプの集合Ｂにある。いくつかの実施形態において、これは、メッセージＭを、エンコードＨ（Ｍ）がＢに署名を有するメッセージの集合に限定することによって得られる。いくつかの実施形態において、エンコードされたメッセージＨ（Ｍ）は、短く（ある所定の長さよりも短い）、例えば、あるｈ″＜Ｎに関してＨ（Ｍ）∈［０，ｈ″］であり、署名方式４２０では、短いメッセージを集合Ｂに写像する。中間署名ｂは、長いビットストリングであってもよいことに注目されたい。
【０１２８】
ステップ８１０で、写像θを適用して中間署名ｂを、短い署名ｓに写像する。ステップ４３０で、署名ｓを受信者に送信する。
【０１２９】
署名検証を、図９に示す。ステップ５０４で、短い署名ｓは、受信者コンピュータシステム１１０で受信される。ステップ９１０で、逆写像θ−１を適用して、中間署名ｂを復元する。ステップ５１０、５２０で、検証を実行する。例えば、ステップ５１０で、中間署名を処理してＨ（Ｍ）を復元することができる。ステップ５２０で、図５のステップ５２０におけるように検証を実行することができる。ステップ５１０、５２０の方法は、ある所定長に等しい長さ（例えば数Ｎ−１の長さ、ここで、Ｎは、法である）のメッセージＨ（Ｍ）の署名や、より短いメッセージＨ（Ｍ）の署名や、場合によっては、より長いメッセージＨ（Ｍ）の署名を検証するのに適している。
【０１３０】
いくつかの実施形態において、集合Ｂは、全てのメッセージの集合よりも濃度が低いが、Ｂの個々のメッセージは、エンコードされたメッセージＨ（Ｍ）よりも長いことがある。このため、写像π−１とθは、一般的に圧縮と呼び、写像πとθ−１は、復元と呼ぶ。本発明は、実際の圧縮又は復元が起こる場合、すなわち、写像π−１又はθが各数をそれより短い数に写像するか、写像π又はθ−１が各数をそれより長い数に写像する実施形態に限定されない。
【０１３１】
いくつかの公開鍵暗号化及び署名の実施形態において、暗号文と署名のサイズは、通常のｌｏｇ２Ｎビットではなく、最大でも約２／３ｌｏｇ２Ｎビットである。同時に、圧縮及び署名方式のセキュリティは、かなり大きい（ｌｏｇ２Ｎ）ビットの数Ｎを因数分解することに基づく。
【０１３２】
いくつかの実施形態において、ｈ′−ｈが、約８＊Ｎ２／３以上である時、小さい定数ｃ１に関して、写像θは、Ｂ２Ｎ，ｈ，ｈ′内の数を長さｃ１＋ｌｏｇ２（ｈ′−ｈ）のビットストリングに写像する。いくつかの実施形態では、ｃ１≦３である。いくつかの実施形態において、写像πは長さ−ｃ２＋ｌｏｇ２（ｈ′−ｈ）のビットストリングを、Ｂ２Ｎ，ｈ，ｈ′内の数に写像する。ここで、ｃ２は、小さい定数である。いくつかの実施形態において、ｃ２＝ｌｏｇ２５≦３である。いくつかの公開鍵暗号化及び署名の実施形態において、両写像は、公開されている。すなわち、写像と、それらの逆は、秘密情報を必要とすることなく効率的に計算することができる。
【０１３３】
いくつかの実施形態において、帯域幅縮小サインクリプション方式を提供する。送信者は、送信者の公開鍵ＮＡと受信者の公開鍵ＮＢに関連して用いられる、例えば、θＡやθＢなどの、２つのバージョンのθ写像を使用する。ＮＡとＮＢは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、サインクリプションは、構造（ｃ１＋ｌｏｇ２（ｈ′−ｈ））ビット長である。このサインクリプションは、同時に、受信者が解読できるようにメッセージを暗号化し、メッセージに対する送信者の署名を含める。受信者は、送信者の公開鍵を用いて検証することができる。
【０１３４】
いくつかの実施形態において、帯域幅縮小集合署名方式を提供する。署名者｛Ｓ１，…，ＳＺ｝は、公開鍵｛Ｎ１，…，ＮＺ｝を有し、メッセージ｛Ｍ１，…，ＭＺ｝に順に署名する。これは、署名者Ｓｉが、Ｓｉ−１からｓｉ−１を受信した後にＭｉの署名ｓｉを生成することを意味する。鍵Ｎｉは、ほぼ同じビット長でもよいが、必然ではない。いくつかの実施形態において、各ｓｉ−１は、Ｂの要素の（θｉ−１によって）圧縮された表現であり、ここで、Ｂは、ｉに依存することもあればそうでないこともある。例えば、Ｂは、Ｂ２Ｎ，ｈ，ｈ′であることもある。ここで、Ｎ、ｈ及びｈ′は、ｉに依存することもあればそうでないこともあり、ｓｉは、基本的に［ｈ，ｈ′］の数のＮｉを法とする圧縮平方根として計算される。その数は、ｓｉ−１とＭｉに依存する。
【０１３５】
いくつかの実施形態において、帯域幅縮小リング署名方式を提供する。いくつかの実施形態において、Ｒｉｖｅｓｔ‐Ｓｈａｍｉｒ‐Ｔａｕｍａｎリング署名方式が、本発明の圧縮方式を、本発明の他の手法と組み合わせて用いて、上記リスト９の
【数３４】
0005412626.tif 000035
【０１３６】
の値を短くできるようにすることによって改良されている。
【０１３７】
本発明の他の特徴や利点について、以下に述べる。本発明は、添付の請求項によって定義される。
【図面の簡単な説明】
【０１３８】
【図１】両先行技術の暗号化方式と本発明のいくつかの実施形態と共に使用するのに適したシステムのブロック図を示す。
【図２】先行技術の暗号化方式のフローチャートを示す。
【図３】先行技術の復号化方式のフローチャートを示す。
【図４】先行技術の署名方式のフローチャートを示す。
【図５】先行技術の署名検証方式のフローチャートを示す。
【図６】本発明のいくつかの実施形態による暗号化方式のフローチャートを示す。
【図７】本発明のいくつかの実施形態による復号化方式のフローチャートを示す。
【図８】本発明のいくつかの実施形態による署名方式のフローチャートを示す。
【図９】本発明のいくつかの実施形態による署名検証方式のフローチャートを示す。
【図１０】Ｆａｒｅｙ被覆及びＦａｒｅｙ分割を示す。
【図１１】本発明のいくつかの実施形態で用いる圧縮及び復元方式のいくつかの特徴を説明するグラフを示す。
【図１２】本発明のいくつかの実施形態による復元方式のフローチャートを示す。
【図１３】本発明のいくつかの実施形態による圧縮方式のフローチャートを示す。
【図１４】本発明のいくつかの実施形態によるサインクリプション方式のフローチャートを示す。
【図１５】本発明のいくつかの実施形態によるサインクリプション検証方式のフローチャートを示す。
【発明を実施するための形態】
【０１３９】
１．前置き
後の説明では、いくつかの数学的表記を用いるが、その多くを便宜上ここに集める。｛０，１｝*を全てのビットストリングの集合を示すものとし、｛０，１｝ｎを長さｎの全てのビットストリングの集合を示すものとする。後者の表現は、また、ｎ以下の長さの全てのビットストリングの集合を示す。ストリング長が、ｎよりも小さい場合、該ストリングは、左側に０を付け加えることで長さｎにすることができる。通常、Ｈは、暗号ハッシュ関数及び／又はエンコードされたメッセージを示す。例えば、ＳＨＡ‐１やＭＤ５など、様々な暗号ハッシュ関数が、当技術で公知である（例えば、ＲＦＣ‐２１０４，Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ，Ｎｅｔｗｏｒｋｉｎｇ  Ｗｏｒｋｉｎｇ  Ｇｒｏｕｐ，Ｈ．Ｋｒａｗｃｚｙｋ  ｅｔ  ａｌ．，ＨＭＡＣ：Ｋｅｙｅｄ‐Ｈａｓｈｉｎｇ  ｆｏｒ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ，１９９７年２月、参照により本明細書に含む、を参照）。ハッシュ関数が耐衝突性であること、すなわち、Ｈ（ｍ１）＝Ｈ（ｍ２）となるようなｍ１≠ｍ２を見つけるのが計算上難しいことが望ましい。
【０１４０】
実数ｒに関して、
【数３５】
0005412626.tif 000036
【０１４１】
は、ｒの天井、すなわち、ｒ以上の最小の整数値を示す。同様に、
【数３６】
0005412626.tif 000037
【０１４２】
は、ｒの床、すなわち、ｒ以下の最大の整数値を示す。最後に
【数３７】
0005412626.tif 000038
【０１４３】
は、ｒに最も近い整数を示す。記号‖は、連結を示す。
【０１４４】
本明細書中、Ｎは、整数法を示す。有効なセキュリティのために、Ｎは、因数分解が計算上難しいものであるべきである。実際には、Ｎを２つの大きい素数ｐ及びｑ、例えば、各々５１２ビット、の積として生成することが多い。しかしながら、暗号文献に見られるように、ｄ＞１として、Ｎ＝ｐｄｑに設定すると、効率的利点があることが多い。本発明の方式では、Ｎは、任意の形式をとれる。しかしながら、後の説明では、便宜上、Ｎ＝ｐｑとする。
【０１４５】
「格子」は、基底ベクトルの集合の整数線形結合として生成することができる全てのベクトルの集合からなる。例えば、（ａ，ｂ）及び（ｃ，ｄ）が二次元空間において２つの基底ベクトルである場合、それらによって生成される格子は、ベクトル｛（ｋ１ａ＋ｋ２ｃ，ｋ１ｂ＋ｋ２ｄ）：ｋ１，ｋ２∈Ｚ｝の集合である。Ｚは、全ての整数の集合である。
【０１４６】
２．追加の前置き：Ｂ２Ｎ，ｈ，ｈ′内の数の分布
Ｎを法とする平方剰余が一様に分布していたならば、Ｂ２Ｎ，ｈ，ｈ′は、およそｈ′−ｈ個の数を含むと予想される。差し当たりＢ２Ｎ，ｈ，ｈ′が、ｈ′−ｈ個の数を含むとすれば、情報理論の観点から、
【数３８】
0005412626.tif 000039
【０１４７】
ビットを用いて、Ｂ２Ｎ，ｈ，ｈ′内の各数を一意に示すことは可能である。しかしながら、Ｂ２Ｎ，ｈ，ｈ′内の数は、ランダムに見えるように、区間［１，Ｎ／２］にわたって分散しており、従って、効率的に、つまり、計算の複雑性が小さい定数ｃに対し最大でＯ（（ｌｏｇＮ）ｃ）である方法を用いて、ある数の一意の表示を計算することができるかは少しも明らかではない。（文字ｃは、定数と暗号文の両方に用いるが、これら２つの使用は混同すべきでない）。
【０１４８】
Ｂ２Ｎ，ｈ，ｈ′の局所分布の解析
効率的に計算でき可逆であるＢ２Ｎ，ｈ，ｈ′内の数の簡潔な表示を作成するために、Ｂ２Ｎ，ｈ，ｈ′内の数がどのように［１，Ｎ／２］に分布しているかを理解するのが望ましい。この分布は、参照により本明細書に含まれる、Ｂ．Ｖａｌｌｅｅ著、Ｐｒｏｖａｂｌｙ  Ｆａｓｔ  Ｉｎｔｅｇｅｒ  Ｆａｃｔｏｒｉｎｇ  ｗｉｔｈ  Ｑｕａｓｉ‐Ｕｎｉｆｏｒｍ  Ｓｍａｌｌ  Ｑｕａｄｒａｔｉｃ  Ｒｅｓｉｄｕｅｓ（Ｐｒｏｃ．ｏｆ  ＳＴＯＣ  １９８９，９８‐１０６ページ）によって、因数分解問題（数Ｎの素因数を見つける問題）に関連して、−ｈ＝ｈ′＝４Ｎ２／３について研究されている。Ｖａｌｌｅｅは、−ｈ＝ｈ′＝４Ｎ２／３について、Ｂ２Ｎ，ｈ，ｈ′内の数の分布を解析した。彼女の観測を用いて、証明可能に低い計算の複雑性を有する（複雑性は、やはりまだ高くて、非常に大きい数（例えば、１０２４ビット）を因数分解することはできないが）因数分解方式が、Ｂ＝Ｂ２Ｎ，ｈ，ｈ′から「擬一様に」数を抜き出すサブルーチンを用いて、すなわち、ある定数ｃについて、所定の数が引き出される確率が、他の数が選択される確率のｃ倍以内であるようにして、開発された。
【０１４９】
Ｖａｌｌｅｅは（本発明によって利用されるような）圧縮方式を開発しておらず、確かに、Ｖａｌｌｅｅの因数分解方式の論考では、かかる圧縮方式は無意味であるようだが、ＶａｌｌｅｅのＢ２Ｎ，ｈ，ｈ′の分布についての観測は有用である。Ｖａｌｌｅｅの観測のいくつかを以下に列挙する。
【０１５０】
Ｆａｒｅｙ数列：
オーダーｋのＦａｒｅｙ数列Ｆｋは、ａ１＝０を除いて、１≦ａｉ≦ｂｉ≦ｋ及びｇｃｄ（ａｉ，ｂｉ）＝１である、分数
【数３９】
0005412626.tif 000040
【０１５１】
の昇列
【数４０】
0005412626.tif 000041
【０１５２】
である。“ｇｃｄ”の表現は、最大公約数を表す。
【０１５３】
Ｆａｒｅｙ数列の性質は、以下の定理で表される。
【０１５４】
定理１．
Ｆｋにおいて、
【数４１】
0005412626.tif 000042
【０１５５】
と
【数４２】
0005412626.tif 000043
【０１５６】
が連続していれば、ｂｉａｉ＋１−ａｉｂｉ＋１＝１である。
【０１５７】
Ｆａｒｅｙ数列に関する他の有用な定理は、以下のとおりである。
【０１５８】
定理２．
Ｆｋにおいて、
【数４３】
0005412626.tif 000044
【０１５９】
と
【数４４】
0005412626.tif 000045
【０１６０】
が連続していれば、ｂｉ＋ｂｉ＋１＞Ｋである。
【０１６１】
Ｆａｒｅｙ数列は、自然に、Ｆａｒｅｙ被覆の概念につながる。
【０１６２】
Ｆａｒｅｙ被覆：
区間［０，Ｎ／２］のオーダーｋのＦａｒｅｙ被覆は、開Ｆａｒｅｙ区間Ｉ（ａｉ，ｂｉ）の集合であり、ここでｉ＝０，１，２，…であり、各区間Ｉ（ａｉ，ｂｉ）は、中心
【数４５】
0005412626.tif 000046
【０１６３】
と、半径
【数４６】
0005412626.tif 000047
【０１６４】
とを有し、ここで、ａ１＝０を除いて、１≦ａｉ≦ｂｉ≦ｋ及びｇｃｄ（ａｉ，ｂｉ）＝１である。
【０１６５】
図１０Ａは、Ｆａｒｅｙ被覆を示している。
【０１６６】
上記定理１及び２を用いて、［０，Ｎ／２］内の全ての実数が少なくとも１つの、多くて２つのＦａｒｅｙ区間によって被覆されていることを容易に証明できる。
【０１６７】
後の論述は、また、（図１０Ｂに示す）Ｆａｒｅｙ分割を用いるが、Ｆａｒｅｙ被覆と密接な関係がある。
【０１６８】
Ｆａｒｅｙ分割：
区間［０，Ｎ／２］のオーダーｋのＦａｒｅｙ分割は、区間
【数４７】
0005412626.tif 000048
【０１６９】
の集合であり、ここで、ｉ＝０，１，２，…であり、ａ０＝ａ−１＝ｂ−１＝０を除いて、１≦ａｉ≦ｂｉ≦ｋ、ｇｃｄ（ａｉ，ｂｉ）＝１である。
【０１７０】
Ｆａｒｅｙ分割区間は、左側で閉じているが（端点を含む）、右側で閉じており左側で開いていると定義することもできる。（ここで、区間は交わらず、０を被覆しないように定義されるが、これは必然ではない。）
区間Ｊ（ａｉ，ｂｉ）は、Ｎ／２に隣接する小さい区間を除く［０，Ｎ／２］の全てを被覆する分割を形成し、図１０ＢではＪ（ａｆ，ｂｆ）として示し、ここで、ｆは、ａｉ，ｂｉに対する最大のｉ添数である。従って、ａｆ＝ｂｆ＝１である。ａｆ＋１＝ｂｆ＋１＝０と定義するならば、Ｊ（ａｆ，ｂｆ）は、一般式（８）により定義できる。
【０１７１】
再び定理１及び２を用いることによって、Ｉ（ａｉ，ｂｉ）がＪ（ａｉ，ｂｉ）を含むことを証明することができる。また、区間Ｉ（ａｉ，ｂｉ）は、区間Ｊ（ａｉ，ｂｉ）の２倍以内の幅である。
【０１７２】
Ｆａｒｅｙ数列は、Ｂ２Ｎ，ｈ，ｈ′内の整数の［０，Ｎ／２］内の分布に密接な関係がある。特に、Ｂの連続する要素間の空隙は、小さい分母ｂｉの有理数ａｉＮ／２ｂｉに近い大きな変分がある。しかしながら、ａｉＮ／２ｂｉを中心とするもっと広い値域を考えると、Ｂ要素の分布は「一様になる」、すなわち、該区間のＢ要素の数と、Ｂが一様に分布していた場合に予測される数との比率は、１に近づく。概略を言うと、固まりが無視できるようになるのに必要な区間幅は、ｂｉに反比例し、従って、上記で定義したＦａｒｅｙ区間とＢの要素の分布との関係である。
【０１７３】
Ｖａｌｌｅｅは、以下の定理を証明した。
【０１７４】
定理３．
−ｈ＝ｈ′＝４Ｎ２／３と、
【数４８】
0005412626.tif 000049
【０１７５】
に関し、部分集合Ｂ２Ｎ，ｈ，ｈ′とオーダーｋのＦａｒｅｙ被覆は、準独立である。
【０１７６】
準独立という用語は、以下のように定義される。部分集合ＸとＺＮ（ＺＮは、Ｎを法とする全ての整数の集合を示す）の被覆Ｙ＝｛Ｙｊ｝は、全てのｊについて、集合ＸとＹｊが、ある正の定数ｌ１とｌ２に対し（ｌ１，ｌ２）独立である、すなわち
【数４９】
0005412626.tif 000050
【０１７７】
であれば、準独立である。Ｐは、集合ＺＮについての一様確率測度である。ｈ′＝４Ｎ２／３であり、Ｆａｒｅｙオーダーｋ＝１／４Ｎ１／３であるＢ２Ｎ，ｈ，ｈ′に関し、Ｖａｌｌｅｅは、
【数５０】
0005412626.tif 000051
【０１７８】
と、ｌ２＝４が満たされることを証明する。
【０１７９】
この定理を証明するためのＶａｌｌｅｅの方法は、ある意味、建設的である。Ｂの要素がＦａｒｅｙ区間内で、すなわち「局所的に」どのように構成されているかを詳しく見ることによって、Ｖａｌｌｅｅは、区間のＢ要素の数について上限及び下限を与える、これらの要素の概略計数を提供することができる。この概略計数を用いて、Ｖａｌｌｅｅは、「擬一様に」Ｆａｒｅｙ区間に存在するＢから要素を選択する方法を提供する。形式上、一様確率Ｐと、ＺＮの部分集合Ｘ内の値を有する有限集合Ｕに対し定義される抜き出し方式Ｃは、全てのｘ∈Ｘに関し、
【数５１】
0005412626.tif 000052
【０１８０】
であれば、（ｌ１，ｌ２）一様（又は擬一様）であるといわれる。Ｂの要素が、擬一様にＦａｒｅｙ区間中に分布しているとすれば、これは直接「擬一様に」［１，Ｎ］内のＢから要素を選択する「大域的な」方式につながる。
【０１８１】
擬一様な分布で、Ｆａｒｅｙ区間Ｉ（ａｉ，ｂｉ）にあるＢ２Ｎ，ｈ，ｈ′内の数を選択したいものとする。
【数５２】
0005412626.tif 000053
【０１８２】
Ｖａｌｌｅｅは、ｈ′＝４Ｎ２／３としてＢ２Ｎ，ｈ，ｈ′∩Ｉ（ａｉ，ｂｉ）に存在する整数
【数５３】
0005412626.tif 000054
【０１８３】
を、これらの整数を２つの特定の放物線の間にある二次元の格子における点に関連付けることによって簡潔に特徴付けている。図１１において、区間｛ｕ：ｘ＝ｘ０＋ｕ∈Ｉ（ａｉ，ｂｉ）｝は、１１０４で示し、２つの放物線は、１１１０、１１２０で示す。
【０１８４】
ｘが、Ｂ２Ｎ，ｈ，ｈ′内にあるならば、
【数５４】
0005412626.tif 000055
【０１８５】
である。さて、Ｌ（ｘ０）をベクトル（１，２ｘ０）及び（０，Ｎ）によって生成する格子とする。すると、（ｕ，ｗ）∈Ｌ（ｘ０）及び、
【数５５】
0005412626.tif 000056
【０１８６】
となるようなｗが存在するとき、ｘ＝ｘ０＋ｕは、まさにＢ２Ｎ，ｈ，ｈ′に存在する。
【０１８７】
条件（１１）は、（ｕ，ｗ）が、式
【数５６】
0005412626.tif 000057
【０１８８】
（これは、図１１の放物線１１１０である）と、
【数５７】
0005412626.tif 000058
【０１８９】
（放物線１１２０）によって定義される放物線１１１０、１１２０の間にあることを意味している。
【０１９０】
ｘが、Ｉ（ａｉ，ｂｉ）にあるならば、
【数５８】
0005412626.tif 000059
【０１９１】
であり、ここで
【数５９】
0005412626.tif 000060
【０１９２】
であり、記号‖は、絶対値を示す。従って、Ｂ２Ｎ，ｈ，ｈ′とＩ（ａｉ，ｂｉ）の両方にある各整数ｘ＝ｘ０＋ｕは、
【数６０】
0005412626.tif 000061
【０１９３】
内の格子点に対応する。
【０１９４】
図１１において、Ｐ（ａｉ，ｂｉ）の点を十字形により１１２１で示し、残りの格子Ｌ（ｘ０）点を円により１１２２で示す。
【０１９５】
Ｌ（ｘ０）のどの格子点が放物線１１１０、１１２０の間にあるかを計算するのは、かなり複雑なタスクのように思えるかもしれない。幸い、Ｖａｌｌｅｅが述べるように、基底ベクトルがそれぞれ短く、一方の基底ベクトルは「準水平」で、他方は「準垂直」であるＬ（ｘ０）の格子基底を見つけることができる。基底は、（ｒ，ｓ）であり、
【数６１】
0005412626.tif 000062
【数６２】
0005412626.tif 000063
【０１９６】
である。
【０１９７】
ｂｉ≦ｋであり、ここで
【数６３】
0005412626.tif 000064
【０１９８】
であることを思い出されたい。
【０１９９】
Ｖａｌｌｅｅは、以下を証明している
定理４．
Ｐ（ａｉ，ｂｉ）の全ての点は、ある有理指数ｖ∈［０，ｈ′２／４ｂｉＮ＋２ｈ′ｂｉ／Ｎ］に関する縦座標ｗ０−ｖＮ／ｂｉで縦軸ｗと交差するｒに平行な線上にあり、ここで
【数６４】
0005412626.tif 000065
【０２００】
である。連続する指数ｖは、１だけ異なる。
【０２０１】
これらの線は、図１１において１１２４で示す。
【０２０２】
次に、Ｖａｌｌｅｅは、ｒに平行な準水平線１１２４をそれらの指数ｖによって数え、次に各線１１２４上のＰ（ａｉ，ｂｉ）の点の数を数えるか概算することによって、Ｐ（ａｉ，ｂｉ）の点を大まかに数える。
【０２０３】
特に、Ｖａｌｌｅｅは、２つの放物線の間の空間を「胸部」１１３０、「脚部」１１４０、「足部」１１５０に分割する４つの「特別」指数を定義している。２つの放物線の間の空間が、上端が連結された２つの「脚部」１１４０のように見える形をどのように形成することができ、上部１１３０が「胸部」であり、「足部」１１５０は、「脚部」がＦａｒｅｙ区間Ｉ（ａｉ，ｂｉ）の端に接触するところに形成されることが容易にわかる。胸部、脚部、足部の領域の境界は、ｒベクトルに平行な線１１６０によって定められる。特別指数は、以下のように定義される。
【０２０４】
定義１：
ｖ０は、定義域の第１（最小）指数である。
【０２０５】
脚部の第１指数であるｖ１は、４ｈｂｉ／Ｎ以上の最小指数である。
【０２０６】
脚部の最終指数であるｖ２は、ｈ′２／４ｂｉＮよりも小さい最大指数である。
【０２０７】
（足部１１５０の）ｖ３は、ｈ′２／（４ｂｉＮ）＋２ｈ′ｂｉ／Ｎよりも小さい最大指数である。
【０２０８】
ｂｉ≦ｋ＝Ｎ／ｈ′なので、胸部１１３０は、最大４つの線を含み、足部１１５０は、最大２つの線を含む。従って、Ｐ（ａｉ，ｂｉ）の点を数える際、いくつの点が胸部と足部にあるかの正確な計算をすぐに得ることができる。しかしながら、脚部は、非常に長いことがあり、（Ｎが無限になるにつれてオーダーＮ１／３で）Ｏ（Ｎ１／３）の線まで含むことがある。幸い、Ｖａｌｌｅｅは、以下の定理を証明できた。
【０２０９】
定理５（「脚部定理」）：
脚部の指数ｖの線１１２４上のＰ（ａｉ，ｂｉ）の点の数ｎ（ｖ）は、
【数６５】
0005412626.tif 000066
【０２１０】
を満たす。
【０２１１】
以下、値
【数６６】
0005412626.tif 000067
【０２１２】
は、Ｖａｌｌｅｅの下限と呼び、
【数６７】
0005412626.tif 000068
【０２１３】
は、Ｖａｌｌｅｅの上限と呼ぶ。
【０２１４】
ＶＬＢ及びＶＵＢ境界は、脚部のＰ（ａｉ，ｂｉ）の格子点の総数の上限下限を得るのに用いることができ、ａ≦ｂである全ての正の整数ａ及びｂに対し有効な以下の不等式を用いる。
【数６８】
0005412626.tif 000069
【数６９】
0005412626.tif 000070
【０２１５】
脚部定理を用いて、たとえ脚部１１４０が多数の線１１２４を有することがあっても、各線１１２４上で左から右へ点を数えることによって、Ｐ（ａｉ，ｂｉ）の格子点について概算できる。点は、最初に胸部、次に足部、その次に脚部で数えられる。胸部、足部、脚部の領域のそれぞれにおいて、点は、その領域の一番上の線１１２４で最初に数えられ、次にその下の線、というふうに数えられる。この概算を用いて、所定のＦａｒｅｙ区間に擬一様に存在するＢ２Ｎ，ｈ，ｈ′から数を抜き出すことができる。
【０２１６】
Ｖａｌｌｅｅの擬一様抜き出し方式
Ｖａｌｌｅｅは、以下の「大域的」抜き出し方式で上記結果を使用したが、−ｈ＝ｈ′＝４Ｎ２／３について、Ｂ２Ｎ，ｈ，ｈ′の数を擬一様に選択する。以下、ｎｃは、胸部１１３０の点の数を示し、ｎｆは、足部１１５０の点の数を示し、ｎｃ＋ｆ＝ｎｃ＋ｎｆ（胸部と足部の点の総数）であり、ｎｌは、脚部１１４０の点の数を示す。
【０２１７】
リスト１３：Ｖａｌｌｅｅの擬一様抜き出し方式
１．場所をランダムに選択する。任意の整数ｘ∈選択した一様分布の［１，Ｎ］を選ぶ。
【０２１８】
２．Ｆａｒｅｙ区間を決定する。連分数を用いて、ｘがＪ（ａｉ，ｂｉ）にある（ａｉ，ｂｉ）を計算し、ここでＪ（ａｉ，ｂｉ）は、オーダーｋ＝１／４Ｎ１／３の区間［０，Ｎ／２）のＦａｒｅｙ分割区間である。
【０２１９】
３．Ｐ（ａｉ，ｂｉ）の点の数を概算する。
【数７０】
0005412626.tif 000071
【０２２０】
を計算し、胸部と足部の点の数ｎｃ＋ｆを正確に数え、Ｖａｌｌｅｅの下限（１５）及び式（１７）を用いて脚部における点の数について概算ｎｌを得る。
【０２２１】
４．Ｐ（ａｉ，ｂｉ）から点を選ぶ。整数ｔ∈擬一様の［１，ｎｃ＋ｆ＋ｎｌ］をランダムに選択する。ｔ≦ｎｃ＋ｆであれば、胸部又は足部から適切な点を出力する。そうでなければ、各線がＶａｌｌｅｅの下限に接触していれば、式（１７）を用いて、どの準水平線１１２４が脚部の点数（ｔ−ｎｃ＋ｆ）を含んでいるかを決定し、一様分布のその線上のＰ（ａｉ，ｂｉ）の点をランダムに選択する。
【０２２２】
５．Ｐ（ａｉ，ｂｉ）から選択した点からｘ′を計算する。（ｕ，ｗ）を前ステップによって出力した格子点とする。ｘ′＝ｘ０＋ｕに設定する。ｘ′を出力する。
【０２２３】
リスト１３の終了。
【０２２４】
ｘ′∈Ｂ２Ｎ，ｈ，ｈ′であり、ｘ′は、ｘと同じＦａｒｅｙ区間にあることに注目されたい。Ｆａｒｅｙ区間は、幅が様々である。Ｉ（ａｉ，ｂｉ）が直径
【数７１】
0005412626.tif 000072
【０２２５】
を有し、１≦ｂｉ≦ｋであることを思い起こされたい。最初の２つのステップにおいて、広いＦａｒｅｙ区間が選択される可能性が高いが、広いＦａｒｅｙ区間は、より多くのＢ要素を含むので、選択したＦａｒｅｙ区間の特定のＢ要素は、そのＦａｒｅｙ区間が広ければ、選ばれる確率が低い。結局、これらの要因は「平衡」し、大域的な擬一様抜き出し方式を可能にする。
【０２２６】
参照により本明細書に含まれる「Ｊ．‐Ｓ．Ｃｏｒｏｎの論文、Ｓｅｃｕｒｉｔｙ  Ｐｒｏｏｆ  ｆｏｒ  Ｐａｒｔｉａｌ‐Ｄｏｍａｉｎ  Ｈａｓｈ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  （ｐｒｏｃ．ｏｆ  Ｃｒｙｐｔｏ  ２００２，ＬＮＣＳ  ２４４２，６１３‐６２６頁、Ｓｐｒｉｎｇｅｒ‐Ｖｅｒｌａｇ，２００２）」において、Ｃｏｒｏｎは、Ｖａｌｌｅｅの方式を拡張して、εを正の定数として、
【数７２】
0005412626.tif 000073
【０２２７】
について、Ｂ２Ｎ，ｈ，ｈ′の抜き出し方式を作り出した。該方式では、一様と統計的に区別が付かない分布、つまり、一様分布からの統計的距離が最大で
【数７３】
0005412626.tif 000074
【０２２８】
である分布の要素を抜き出す。このような改良により、Ｃｏｒｏｎは、「部分領域ハッシュ」署名方式のセキュリティを証明することができる。この方式では、署名は、基本的にＢ２Ｎ，ｈ，ｈ′内の数のモジュラ平方根である。しかしながら、Ｃｏｒｏｎの部分領域ハッシュ署名方式において、署名は短くない。署名は、（ｌｏｇ２Ｎ）ビットの数で表される。対照的に、本発明のいくつかの実施形態においては、可逆圧縮θ（図８、ステップ８１０）をＣｏｒｏｎ部分領域ハッシュ署名に適用して、帯域幅を縮小した部分領域ハッシュ署名を得る。
【０２２９】
Ｖａｌｌｅｅのように、Ｃｏｒｏｎは、２つの放物線１１１０、１１２０（図１１）の間にある格子点を考慮する。しかしながら、Ｃｏｒｏｎは、Ｉ（ａｉ，ｂｉ）ではなく局所領域Ｊ（ａｉ，ｂｉ）を考慮し、異なる準水平線を用いて２つの放物線の間の値域を分割する。Ｃｏｒｏｎは、Ｖａｌｌｅｅのように、ｖ０とｖ３を定義するが、ｖ１とｖ２は、Ｉ（ａｉ，ｂｉ）の端に接触する前にいずれの放物線とも交わらない（従って、Ｊ（ａｉ，ｂｉ）の端を通り過ぎる）最初と最後の線の指数である。ｖ１とｖ２の値は、
【数７４】
0005412626.tif 000075
【０２３０】
と、（ｈ′−ｈ）ｂｉ／Ｎに近い。ｖ３の値は、少し異なって定義され、
【数７５】
0005412626.tif 000076
【０２３１】
に近くなるのは、Ｃｏｒｏｎは、ｈ′がＮ／ｋに必ずしも等しくない場合を考慮しているからである。Ｃｏｒｏｎは、単にｖ１からｖ２までの指数を有する線上の格子点を抜き出すので、ｖ０からｖ１又はｖ２からｖ３までの指数を有する線上の点が選ばれる可能性はない。しかしながら、Ｃｏｒｏｎが考慮するパラメータ、すなわち、
【数７６】
0005412626.tif 000077
【０２３２】
と、
【数７７】
0005412626.tif 000078
【０２３３】
と、
【数７８】
0005412626.tif 000079
【０２３４】
について、除外された格子点の部分は、無視できるものであり、この抜き出し方式は、一様に非常に近い。εの値は、望ましくは、
【数７９】
0005412626.tif 000080
【０２３５】
が非常に小さくなるように選択する。
【０２３６】
３．本発明のいくつかの実施形態‐圧縮
さて、本発明に転じると、本発明のいくつかの実施形態では、Ｂ２Ｎ，ｈ，ｈ′内の数と、定数ｃがゼロに近いｎ＝ｃ１＋ｌｏｇ２（ｈ′−ｈ）として、｛０，１｝ｎのビットストリングとの間の写像を提供する、圧縮及び復元方式π，θ，π−１，θ−１を用いる。これらの写像は順列ではない。しかしながら、各写像又は、その逆の下の要素の像は小さい一定の基数を有するので、写像はここでは「準順列」と呼ぶ。
【０２３７】
形式上、集合Ｘ及びＹと定数（ｌ１，ｌ２，ｌ３，ｌ４）に関し、
全てのｘ∈Ｘについて、｛π（ｘ，ｒ）：ｒ∈Ｒ｝の基数が［ｌ１，ｌ２］にあり、
全てのｙ∈Ｙについて、｛ｘ：∃ｒ  ｗｉｔｈ  π（ｘ，ｒ）＝ｙ｝の基数が［ｌ３，ｌ４］にある場合、π：ＸｘＲ→Ｙを（ｌ１，ｌ２，ｌ３，ｌ４）の準順列と定義する（１９）。
【０２３８】
上記で、Ｒは、補助集合である。例えば、πをランダム化したい場合、ランダムビットのソースとして用いてもよい。Ｒの目的は、単に、πを、（たとえ単一のｘ∈Ｘに対し複数の出力が存在することがあっても）所定の入力に対し単一の出力である、実際の「写像」にすることである。Ｒは、空であることもある。実際の順列は、（ｌ，ｌ，ｌ，ｌ）の準順列であることに注意されたい。
【０２３９】
図６乃至９において、集合Ｒは、陰的である。Ｒは、ランダムビットのソースになることがある。
【０２４０】
以下、２つの準順列について説明する。１つは、発明者がおそらく暗号化により適していると考えたものであり、もう１つは、発明者がおそらく署名により適していると考えたものである。しかしながら、本発明は、暗号化又は署名に関連して一方の又は他方の準順列に限定されない。
【０２４１】
小さい非負定数ｃ１及びｃ２に対し、
【数８０】
0005412626.tif 000081
【０２４２】
を、暗号化により適していることがある準順列とし、
【数８１】
0005412626.tif 000082
【０２４３】
を、署名により適していることがある準順列とする。π及びθの両方は、以下に、より詳細に説明するように、効率的に計算可能であり、効率的に可逆である、すなわち、トラップドア情報なしでも、π（ｘ，ｒ）又はθ（ｘ，ｒ）からｘの可能性のある値を復元することは容易である。
【０２４４】
３．１  短いストリングをＢ要素に写像する（π準順列）
本発明のいくつかの実施形態による図６及び７の方式に関し、π及びπ−１を計算するための方法を次に説明する。基本的に、πは、短いビットストリングを、該ビットストリングがＦａｒｅｙ区間とそのＦａｒｅｙ区間内の「アドレス」を特定するものと解釈し、該ビットストリングをそのＦａｒｅｙ区間内のアドレスを有するＢ要素に写像することによって、Ｂ要素に写像する。短いビットストリングは、あるｈ″＜Ｎについて、ある区間［０，ｈ″］の数である。その逆であるπ−１は、基本的に、Ｂ要素のＦａｒｅｙ区間と、そのＦａｒｅｙ区間内のアドレスとを決定することによって計算され、Ｂ要素は、次に、その区間／アドレスの組み合わせを示すビットストリングに写像する。
【０２４５】
この方法は、以下の観測を用いる。Ｖａｌｌｅｅの定理３及び５と、不等式（１５）及び（１６）は、Ｆａｒｅｙオーダー
【数８２】
0005412626.tif 000083
【０２４６】
という条件で、また、定理５と式（１５）〜（１６）において、変数ｈ′が（ｈ′−ｈ）／２に置き換えられるという条件で、−ｈ＝ｈ′＝４Ｎ２／３だけでなく、全てのｈ，ｈ′に有効である。また、定理５は、置換なしでも依然有効である。
【０２４７】
図１２に、ビットストリングｘを、特定の狭いＮを法とする区間におけるモジュラ平方数を有する数ｘ′に写像するπ写像を示す。ステップ１２７０は、ビットストリングｘに対応するＦａｒｅｙ区間（以下にかなり詳細に論じる）を計算することを含む。ステップ１２８０は、該Ｆａｒｅｙ区間の各端のビットストリングを計算することを含む。ステップ１２９０は、Ｆａｒｅｙ区間について、ｘをＢ要素に対するｘ′に写像することを含み、該区間の計数は、最初と最後のビットストリングの間のｘの計数に対応する。
【０２４８】
復元及び圧縮関数は、以下の事実を利用する。「広い」Ｆａｒｅｙ区間のＢ要素に関し、該区間を特定するには少数のビットが必要であるが、該要素の該区間内の位置を特定するには多くのビットが必要である。全体としては、ビットの数は「平衡する」。π準順列の典型的な実施形態の詳細を、以下に述べる。πの定義（１９）に関して、その値を後に測定するあるパラメータｈ″について、Ｘ＝［０，ｈ″］である。｛０，１｝ｎのビットストリングは、上述の［０，２ｎ−１−１］の整数と解釈できることに注意されたい。
【０２４９】
以下のように仮定する。
【０２５０】
仮定１：ｈ，ｈ′を整数とする。いくつかの実施形態において、
【数８３】
0005412626.tif 000084
【０２５１】
である。Ｊ（ａｉ，ｂｉ）を、区間［０，Ｎ／２］に関するオーダー
【数８４】
0005412626.tif 000085
【０２５２】
のＦａｒｅｙ分割の区間とする。Ｉ（ａｉ，ｂｉ）を、区間［０，Ｎ／２］に関する同じオーダーｋのＦａｒｅｙ区間とする。Ｊ（ａｉ，ｂｉ）を、区間［０，Ｎ／２］の同じオーダーｋの、Ｆａｒｅｙ「拡張」分割区間、すなわち区間Ｊ（ａｆ，ｂｆ）を含むものとする。
【０２５３】
リスト１４‐π（ｘ，ｒ）の計算（図１２参照）：
１．ステップ１２７０（図１２）：
【数８５】
0005412626.tif 000086
【０２５４】
を計算して区間［０，ｈ″］を［０，Ｎ／２］に写像し、結果がＪ（ａｉ，ｂｉ）に含まれる（ａｉ，ｂｉ）を決定する。このステップもまた図１１に示される。
【０２５５】
２．ステップ１２８０：
【数８６】
0005412626.tif 000087
【０２５６】
が、Ｉ（ａｉ，ｂｉ）にある［０，ｈ″］の最小整数であるｘｌｅｆｔと、
【数８７】
0005412626.tif 000088
【０２５７】
がＩ（ａｉ，ｂｉ）にある［０，ｈ″］の最大整数であるｘｒｉｇｈｔを計算する。ステップ１２９０は、以下のステップ３乃至５に対応する。
【０２５８】
３．胸部と足部の格子点Ｐ（ａｉ，ｂｉ）の数である、ｎｃ＋ｆ＝ｎｃ＋ｎｆを計算する。脚部の点の数のＶＬＢ下限（１５）であるｎｌを計算する。（以下に説明するように、数ｈ″は、ｎｃ＋ｆ＋ｎｌ≧ｘｒｉｇｈｔ−ｘｌｅｆｔとなるように選択すべきである。）
４．Ｖａｌｌｅｅの計数や他の計数を用いて（以下の計算注記１を参照）、ｘ−ｘｌｅｆｔに対応する１つの格子点（ｕ，ｗ）（いくつかあることがある）を選択する。具体的には、
４Ａ．
【数８８】
0005412626.tif 000089
【０２５９】
内の整数を選ぶ。
【０２６０】
４Ｂ．ｃ≦ｎｃ＋ｎｆであれば、胸部又は足部に計数ｃを有する格子点（ｕ，ｗ）を選ぶ（すなわち、胸部と足部の点が一緒に数えられているとき）。
【０２６１】
４Ｃ．そうでなければ、ｖごとに、ｓｖを、指数が最大ｖである準水平線１１２４（図１１）上の脚部格子点の数の下限とする。値ｓｖはＶＬＢ値（１５）を用いて計算することができる。ＶＬＢ値を付加してｓｖ推定値を得ることができ、又は、不等式（１７）を用いて、右側の積分としてｓｖを計算することができる。ｓｖ−１＜ｃ−ｎｃ＋ｆ≦ｓｖとなるようにｖを計算する。ｎｖを、指数ｖの線１１２４上の格子点の数とし、ｎ′ｖをＶａｌｌｅｅの下限推定値（１５）とする。整数
【数８９】
0005412626.tif 000090
【０２６２】
を選択し、（ｕ，ｗ）を線上のＰ（ａｉ，ｂｉ）のｃ′番目の点に設定する。
【０２６３】
５．ｘ′＝ｘ０＋ｕに設定し、ここで
【数９０】
0005412626.tif 000091
【０２６４】
である。ｘ′を出力する。
【０２６５】
リスト１４の終了。
【０２６６】
計算注記１。
【０２６７】
リスト１４で用いられる値ｎｃ，ｎｆや、他の値を計算するのに多くの方法がある。１つの例は、以下のとおりである。各線１１２４は、形式βｒ＋αｓ
の点の集合であり、ここで、αは、固定整数であり、βは、全ての実数をとる。α＝０に関し、対応する線１１２４（図１１で１１２４．０と示す）は、原点（ｘ＝ｗ＝０）を通過し、縦線ｕ＝０との切片１２９４を見つけることができる。線ｕ＝０は、放物線１１１０、１１２０の対称軸である。定理４を用いて、対応する指数ｖ＝ｖ［０］が求められる。次に、他の全ての指数ｖは、１整数だけｖ［０］と異なるため見つけることができ、線ｕ＝０に対する線１１２４の切片１２９４は、それらのｗ値がＮ／ｂｉだけ線１１２４．０切片のｗ値と異なるため見つけることができる。特に、定義１の特別指数とそれに対応する切片１２９４を求めることができ、胸部と足部の全ての線１１２４についてｖ値とｗ切片値を見つけることができる。
【０２６８】
胸部及び足部における線１１２４ごとに、等式（２０）のための対応するα値を、その線の切片１２９４から求めることができ、次に、その切片１２９４のβ値を見つけることができる。このβ値をβｉｎと示す。格子Ｌ（ｘ０）点は、βの整数値に対応する。格子点は、例えば
【数９１】
0005412626.tif 000092
【０２６９】
、すなわちβｉｎに最も近い整数から始めて、その線上で横に移動することできる。各点の座標は、定義（１２）にはめ込んで、点がＰ（ａｉ，ｂｉ）に属するかどうかを決定することができ、このように、Ｐ（ａｉ，ｂｉ）の点は、ｎｃ又はｎｆの一部として数えることができる。線を右に移動し（β＞βｉｎ）、ある点と放物線１１２０の外側で遭遇した場合（すなわちｘ０２＋ｗ＋ｕ２＞ｈ′）、右方向の移動を止めることができる。同様に、線を左に移動し、点と放物線１１２０の外側で遭遇した場合、左方向の移動を止めることができる。Ｐ（ａｉ，ｂｉ）点は、また、他の順序で数えることもでき、例えば、各線１１２４の一番左の点から始めて、右に進んでもよい。一番左の点は、対応する等式（２０）と放物線１１１０、１１２０の等式から解析的に見つけることができる。これらの実施形態は限定的なものではない。
【０２７０】
リスト１４のステップ４Ｂで、ｃ≦ｎｃ＋ｎｆであれば、ｃ番目の点は、胸部と足部の線１１２４を数え、各線上の点を数えることによって見つけることができる。胸部と足部の線１１２４は、ある順序で横に移動することができ、例えば、胸部からｖ指数が増加する順で始めたり、その他の順序でもよい。各線１１２４上の点は、その線の対応する点
【数９２】
0005412626.tif 000093
【０２７１】
から始めて、又は他の順序で数えることができる。本発明は、特定の点の順序付けに限定されない。
【０２７２】
同様に、ステップ４Ｃで、脚部のある線１１２４に関してパラメータｎｖ，ｎ′ｖ，ｃ′を決定する時、その線上のＰ（ａｉ，ｂｉ）のｃ′番目の点は、その線の対応する点
【数９３】
0005412626.tif 000094
【０２７３】
から始めて、又は他の順序で、格子点を横に移動することによって見つけることができる。いくつかの実施形態において、ステップ４Ｂ、４Ｃの計数順序は、π写像の特徴であり、π−１を計算するとき（以下リスト１５で説明するように）と同じ順序である。他の実施形態において、所定のπ写像に関して、点の計数は、式（１９）のｒパラメータに対応するようにランダムである。さらに他の実施形態において、計数は、ランダムではないが、ｘに依存する（例えば、ｎｃ，ｎｆや、ｘに依存する他の値）。
【０２７４】
リスト１４において、計数がランダムであろうとなかろうと、出力ｘ′は、乱数ｃ，ｃ′の関数である。他の実施形態において、数ｃ，ｃ′は、確定的に選択される。例えば、ステップ４Ａ、４Ｃに示すそれぞれ対応する区間の第１の整数に選ぶことができる。或いは、ｃを単にｘ−ｘｌｅｆｔに選ぶことができ、ｘｒｉｇｈｔの計算を省略することができる。或いは、ｃをｘｒｉｇｈｔ‐ｘｌｅｆｔに選ぶことができる。同様に、ｃ′は、ｃ−ｎｃ＋ｆ−ｓｖ−１に選ぶことができる。その他のランダムな又はランダムでない選択も可能である。リスト１４の特定の方式は、以下に説明するように、ｃ，ｃ′が一様にランダムに選択されるならば、ランダムオラクルによる適応的選択メッセージ攻撃の下での対応する暗号化方式の証明できるセキュリティにより、有利である。
【０２７５】
計算注記１の終了。
【０２７６】
π（ｘ，ｒ）を計算する際、ｒを、確定的に又はランダムビットのソースとして用いることで、ｃ及びｃ′の値を選択する。Ｓｘ＝｛ｘ′∈Ｉ（ａｉ，ｂｉ）｜∃ｒ  ｗｉｔｈ  π（ｘ，ｒ）＝ｘ′｝とするならば、集合Ｓｘは、Ｉ（ａｉ，ｂｉ）の分割を形成し、これは、Ｉ（ａｉ，ｂｉ）の各Ｂ要素に選択される可能性があることを意味することに注目されたい。また、ｘとｒを一様に選択して、π（ｘ，ｒ）を出力する場合、擬一様にＢの整数を選択することに注目されたい。
【０２７７】
点の計数において、次に、胸部と足部のｎｃ＋ｎｆ＝ｎｃ＋ｆの点を、１からｎｃ＋ｎｆまである順序で数える。脚部の点は、多数の点が同じ数を共有することがあるという意味で「大まかに」数えられる。脚部の点は、Ｖａｌｌｅｅの下限を満たすかのように数え、特にＳｖを計算する。このＳｖの値は、個々の線についてのＶａｌｌｅｅの推定値である式（１７）において積分を計算することによって容易に計算することができる。脚部の準水平線１１２４は、Ｖａｌｌｅｅの下限推定値よりも多くの点を含むことが多い。その場合、計数において、かかる線上の隣接する点は、１つの数を共有することがある。
【０２７８】
図１３は、Ｂ要素ｘ′を［０，ｈ″］の数ｘに写像する逆写像π−１を示す。ステップ１３２０で、Ｆａｒｅｙ区間又はＦａｒｅｙ分割区間を求め、これは、Ｂ要素ｘ′に対応する。ステップ１３３０で、［０，ｈ″］のビットストリングを計算し、図１１の写像１２７０の逆である写像により、区間の各端に対応する。ステップ１３４０で、ｘ′を［０，ｈ″］のビットストリングｘに写像し、ステップ１３３０で得たビットストリング間の計数は、区間のｘ′の計数に対応する。
【０２７９】
以下のリスト１５では、（Ｆａｒｅｙ分割区間ではなく）Ｆａｒｅｙ区間を用いる時の詳細を説明する。ｘ′＝π（ｘ，ｒ）とすると、本発明の典型的な実施形態では、ｘの１つ又は２つの可能な値を復元する。（上記）仮定１が当てはまるものとする。
【０２８０】
リスト１５‐π−１（ｘ′，ｒ）の計算：
１．ステップ１３２０：ｘ′：Ｉ（ａｉ，ｂｉ）とおそらくＩ（ａｉ＋１，ｂｉ＋１）を含むＦａｒｅｙ区間を決定する。
【０２８１】
２．ステップ１３３０：
【数９４】
0005412626.tif 000095
【０２８２】
が、Ｉ（ａｉ，ｂｉ）にある［０，ｈ″］の最小の整数であるｘｌｅｆｔと、
【数９５】
0005412626.tif 000096
【０２８３】
が、Ｉ（ａｉ，ｂｉ）にある［０，ｈ″］の最大の整数であるｘｒｉｇｈｔとを計算する。ステップ１３４０は、以下のステップ３乃至７に対応する。
【０２８４】
３．Ｐ（ａｉ，ｂｉ）の胸部及び足部の格子点の数であるｎｃ＋ｆと、脚部の点の数の下限ＶＬＢ（１５）であるｎｌとを計算する。
【０２８５】
４．
【数９６】
0005412626.tif 000097
【０２８６】
とｕ＝ｘ′−ｘ０から、格子点（ｕ，ｗ）を復元する。具体的に、格子Ｌ（ｘ０）は、ベクトル（１，２ｘ０）及び（０，Ｎ）によって生成されるので、ある整数αに対して、各格子点（ｕ，ｗ）が等式ｗ＝２ｘ０ｕ＋αＮを満たさなければならないことは容易にわかる。‖ｈ′−ｈ‖＜Ｎ（仮定１に鑑み、大きいＮに対して当てはまらなければならない）と仮定すれば、所定のｕが放物線１１１０、１１２０の間にある格子点は１つだけある。この格子点は、放物線の間の領域を定める不等式（１１）を用いて計算することができる。例えば、α＝０（ｗ＝２ｘ０ｕ）から始めて、不等式（１１）が満たされるまでαを増加及び／又は減少することができる。
【０２８７】
５．Ｖａｌｌｅｅの下限計数又は他の計数（計算注記１を参照）を用いて、ｘ−ｘｌｅｆｔ、従ってｘの値を復元する。具体的に、
５Ａ．（ｕ，ｗ）が、胸部又は足部のｔ番目の点であれば、ｃ＝ｔに設定する。（胸部及び足部の点は、リスト１４におけるように一緒に数えられる。計算注記１を参照）。
【０２８８】
５Ｂ．そうでなければ、（ｕ，ｗ）を含む線１１２４の指数ｖを計算する。ｃ′の値を計算し、ここで、（ｕ，ｗ）は、線上のｃ′番目の点である。ｎｖを指数ｖの線上の格子点の数とし、ｎ′ｖをＶａｌｌｅｅの下限推定値ＶＬＢ（１５）とし、ｓｖ−１をｖよりも小さい指数の準水平線１１２４（図１１）上の脚部格子点の数の下限とする。値ｓｖ−１は、線１１２４ごとにＶＬＢ値（１５）を用いて計算することができる。これらの値を足してｓｖ−１推定値を得ることができ、又は、不等式（１７）を用いて、右側の積分としてｓｖ−１を計算することができる。
【数９７】
0005412626.tif 000098
【０２８９】
となるように、ｃの値を計算する。
【０２９０】
６．
【数９８】
0005412626.tif 000099
【０２９１】
となるように、ｘ−ｘｌｅｆｔの値を計算する。ｘ＝ｘｌｅｆｔ＋（ｘ−ｘｌｅｆｔ）を計算する。
【０２９２】
７．ｘを出力する。
【０２９３】
リスト１５の終了。
【０２９４】
上記の計算注記１を参照されたい。
【０２９５】
ｘ′がＩ（ａｉ，ｂｉ）とＩ（ａｉ＋１，ｂｉ＋１）の両方にある場合、ステップ２乃至６を繰り返して、Ｉ（ａｉ＋１，ｂｉ＋１）に対応するｘの値を得ることができる。このように、上記の方式では、ｘ′を含む１Ｆａｒｅｙ区間につき、ちょうど１つ、ｘの値を、２つまで出力する。従って、ｌ３＝１でありｌ４＝２である。エンコードされた値ｘ＝Ｈ（Ｍ）（図６、ステップ２１０）が、両出力ｘ＝π−１に当てはまらないある性質を確実に満たすようにすることによって、正確な値を選択することができる。例えば、エンコードｘ＝Ｈ（Ｍ）は、Ｈ（Ｍ）のいくつかのチェックサムを含むことがある。或いは、ステップ１３２０でどのＦａｒｅｙ区間を選ぶべきかの曖昧さを解決する何らかの方法があってもよい。
【０２９６】
少し変更した方法を用いて、π（ｘ，ｒ）が一意逆を確実に有するようにすることは難しくない。特に、ｘ′が確実にＪ（ａｉ，ｂｉ）内にあるようにすることで一意逆を実現することができ、それは、Ｐ（ａｉ，ｂｉ）についてのＶａｌｌｅｅの擬一様計数方法を、
【数９９】
0005412626.tif 000100
【０２９７】
の１つに適用することで確実にすることができる。この場合、ＰＪ（ａｉ，ｂｉ）は「一様でない」足部と脚部とを有するが、それでも、擬一様計数は、基本的に同じ方法を用いることで可能である。
【０２９８】
パラメータの設定：前述のように、暗号化方式には、π準順列がより適していることがある。準順列のパラメータ、特に、ｈ′−ｈの値とｈ″の値とを設定するために、暗号化方式とできるだけ両立するために準順列が持つべき性質について考慮することがある。望ましくは、πは、一意可逆であるかほぼそうであるべきである。上述のように、ｌ４＝２だが、Ｉ（ａｉ，ｂｉ）ではなく区間Ｊ（ａｉ，ｂｉ）を考慮することによって、ｌ４＝１を実現することができる。また、各Ｂ要素（おそらくそれらの無視できる一部は除く）が少なくとも１つの逆を有するようにしたい。その理由は、一様確率でｘを選択し、次にπ（ｘ，ｒ）を計算することからなるＢ要素抜き出し方式が「優れた」抜き出し方式であれば、暗号化方式のセキュリティが因数分解に関連する、セキュリティプルーフが通るということである。擬一様抜き出し方式を得るために、ｌ３は、少なくとも１であるべきである。
【０２９９】
ｌ１とｌ２の値は、π準順列の下で、ｘの像のサイズを制約する。各エンコードされたプレーンテキストは、Ｂ要素に写像可能であるべきなので、ｌ１は、望ましくは少なくとも１であるべきである。（しかしながら、これが当てはまらないようにパラメータを選択することは可能である）。ｌ２の値は、他のパラメータの値を考えると、できるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算を提示するが、具体的なパラメータを示している。
【０３００】
ｎｃ＋ｆ＋ｎｌ≧ｘｒｉｇｈｔ−ｘｌｅｆｔ、すなわち、Ｐ（ａｉ，ｂｉ）の点の数の下限が、Ｉ（ａｉ，ｂｉ）に対応付けられるビットストリングの数よりも大きくなるようにパラメータを選択することは、ｌ３が、望みどおり、少なくとも１になることを確実にする。
【数１００】
0005412626.tif 000101
【０３０１】
であることに注意されたい。ここで、後者の項は、ｈ′−ｈ＝Ｎ／２ｋであるので、Ｉ（ａｉ，ｂｉ）の直径である。これは、
【数１０１】
0005412626.tif 000102
【０３０２】
であることを意味する。さて、Ｖａｌｌｅｅが使用したパラメータについて考えてみよう。Ｖａｌｌｅｅは、−ｈ＝ｈ′＝４Ｎ２／３の場合を考慮したので、ｈ′−ｈ＝８Ｎ２／３である。このｈ′−ｈの値について、Ｖａｌｌｅｅは、
【数１０２】
0005412626.tif 000103
【０３０３】
の下限を証明した。従って、
【数１０３】
0005412626.tif 000104
【０３０４】
ならば、ｘｒｉｇｈｔ−ｘｌｅｆｔ−１＜ｎｃ＋ｆ＋ｎｌである。ｎｌ推定値が整数である限り、これは、望むとおり、ｘｒｉｇｈｔ−ｘｌｅｆｔ−１≦ｎｃ＋ｆ＋ｎｌであることを意味する。
【数１０４】
0005412626.tif 000105
【０３０５】
に設定することで、ｌ３とｌ１が少なくとも１であることを検証できる。
【０３０６】
他方、胸部と足部における点の数についてのＶａｌｌｅｅの上限は、ｌ２の値が上限を定められるのを可能にする。（ｎｌがまだ、脚部の点の数についての下限推定値ＶＬＢであることを思い起こされたい）。Ｖａｌｌｅｅの計算は、ｎｃ＋ｆ＋ｎｌが、
【数１０５】
0005412626.tif 000106
【０３０７】
によって上限が定められるのを可能にする。これにより、ｈ″の選択された値について、ｃの可能な値の数を８によって上限を定めることができ、ここで、ｃは、リスト１４のステップ４で選択した数である。また、リスト１４のステップ４で選択した数であるｃ′の、最大で
【数１０６】
0005412626.tif 000107
【０３０８】
（Ｖａｌｌｅｅの脚部定理を参照）の可能な値がある。従って、ｌ２は、最大８ｘ４＝３２である。このように、ｈ′−ｈ＝８Ｎ２／３と
【数１０７】
0005412626.tif 000108
【０３０９】
について、（１，３２，１，２）準順列を得る。
【０３１０】
暗号文は、［ｈ、ｈ′］にあり、プレーンテキストは、［１，ｈ″］（又は［０，ｈ″−１］）にあるので、ここで、
【数１０８】
0005412626.tif 000109
【０３１１】
であり、およそ
【数１０９】
0005412626.tif 000110
【０３１２】
ビット、すなわち、丸めを考慮すると最大で３ビットの暗号文拡張だけが見込める。性能に関して、π（ｘ，ｒ）又はπ−１（ｘ，ｒ）の計算には、Ｏ（ｌｏｇ２Ｎ）ビットの演算が必要なだけであり、暗号化及び復号化の複雑性に、ほとんど何も付加しない。
【０３１３】
ｈ′−ｈとｈ″の間の５の因数は、ｈ′−ｈ＝８Ｎ２／３に対するＶａｌｌｅｅの下限の「ゆるさ」の結果である。ｈ′−ｈのより大きい値、例えば、Ｃｏｒｏｎが考慮したもの等について、下限は、より厳密な概算となる。従って、ｈ′−ｈのより大きい値について、π準順列は、さらに小さい暗号文拡張を暗号化方式に与える。
【０３１４】
３．２  Ｂ要素を短いストリングに写像する（θ準順列）
θ準順列は、π準順列の逆に類似している。この場合も、圧縮及び復元方式は、ＶａｌｌｅｅのＦａｒｅｙ区間の分析によって与えられるＢ要素の分布について公知の情報を用いる。
【０３１５】
帯域幅縮小署名方式を用いる本発明の典型的な実施形態に関して、より詳細に説明するように、θ準順列は、例えば、Ｃｏｒｏｎによって安全性が証明されたものなど、通常のＲａｂｉｎ部分領域ハッシュ署名を損失なしに、すなわち、通常の署名を圧縮された署名から完全に復元できるように、圧縮できるようにする。この圧縮方式は、セキュリティの減少を必要としない。典型的な実施形態の詳細な説明を続ける。
【０３１６】
上記仮定１が当てはまるものとする。
【０３１７】
リスト１６‐Ｂのあるｘ′について［０，ｈ″］のｘ＝θ（ｘ′，ｒ）を計算する（図１３参照）：
１．ステップ１３２０：ｘ′がＪ（ａｉ，ｂｉ）にある（ａｉ，ｂｉ）を決定する。
【０３１８】
２．ステップ１３３０： 
【数１１０】
0005412626.tif 000111
【０３１９】
が、Ｊ（ａｉ，ｂｉ）にある［０，ｈ″］の最小の整数であるｘｌｅｆｔと、
【数１１１】
0005412626.tif 000112
【０３２０】
が、Ｊ（ａｉ，ｂｉ）にある［０，ｈ″］の最大の整数であるｘｒｉｇｈｔを計算する。ステップ１３４０は、以下のステップ３乃至５に対応する。
【０３２１】
３．Ｐ（ａｉ，ｂｉ）の胸部及び足部の格子点の数、ｎｃ＋ｆと、脚部の点の数についての上限ＶＵＢ（１６）、ｎｌとを計算する。（ｎｃ＋ｆ＋ｎｌ≦ｘｒｉｇｈｔ−ｘｌｅｆｔを望む。）
４．Ｖａｌｌｅｅの計数か他の計数（計算注記１参照）を用いて、ｘ′に対応付けられた格子点（ｕ，ｗ）に対応するｘｒｉｇｈｔ−ｘｌｅｆｔ（いくつかあることがある）の１つの整数を選択する。具体的には、
４Ａ．（ｕ，ｗ）が胸部又は足部のｔ番目の点であれば、ｃ＝ｔに設定する。
【０３２２】
４Ｂ．そうでなければ、ｓｖを、指数が最大でｖの準水平線１１２４（図１１）上の脚部格子点の数についての上限とする。値ｓｖは、線１１２４ごとにＶＵＢ値（１６）を用いて計算することができる。これらの値を足してｓｖ推定値を得ることができ、又は、不等式（１８）を用いて、右側の式としてｓｖを計算することができる。（ｕ，ｗ）を含む線の指数ｖを計算する。ｎｖを、指数ｖの線上の格子点の数とし、ｎ′ｖ＝ｓｖ−ｓｖ−１を、Ｖａｌｌｅｅの上限推定値ＶＵＢ（１６）とする。ｘ′が、線上のｔ番目の格子点であるとする。整数
【数１１２】
0005412626.tif 000113
【０３２３】
を選択する。
【０３２４】
５．整数
【数１１３】
0005412626.tif 000114
【０３２５】
を選択する。ｘ＝ｘｌｅｆｔ＋ｃ′に設定する。
【０３２６】
リスト１６の終了。
【０３２７】
計数についての考察を含む計算注記１は、π及びπ−１に当てはまるように、θ及びθ−１写像に当てはまる。
【０３２８】
θ（ｘ′，ｒ）を計算するのに、ｒを確定的に、又は、ランダムビットのソースとして用いて、ｃとｃ′の値を選択する。［０，ｈ″］においてｘ＝θ（ｘ′，ｒ）とすると、Ｂのｘ′の値を以下のように復元することができる。
【０３２９】
リスト１７‐θ−１（ｘ）を計算する（図１２）：
１．ステップ１２７０：
【数１１４】
0005412626.tif 000115
【０３３０】
が、Ｊ（ａｉ，ｂｉ）にある（ａｉ，ｂｉ）を決定する。
【０３３１】
２．ステップ１２８０： 
【数１１５】
0005412626.tif 000116
【０３３２】
が、Ｊ（ａｉ，ｂｉ）にある［０，ｈ″］の最小の整数であるｘｌｅｆｔと、
【数１１６】
0005412626.tif 000117
【０３３３】
が、Ｊ（ａｉ，ｂｉ）にある［０，ｈ″］の最大の整数であるｘｒｉｇｈｔを計算する。
【０３３４】
ステップ１２９０（以下のステップ３乃至５）。
【０３３５】
３．Ｐ（ａｉ，ｂｉ）の胸部及び足部の格子点の数、ｎｃ＋ｆと、脚部の点の数についての上限ＶＵＢ（１６）、ｎｌとを計算する。
【０３３６】
４．ｃ′＝ｘ−ｘｌｅｆｔを計算する。ｃ′とｎｃ＋ｆ＋ｎｌから、
【数１１７】
0005412626.tif 000118
【０３３７】
となるように値ｃを計算する。ｃ≦ｎｃ＋ｆであれば、（ｕ，ｗ）を胸部又は足部のｃ番目の点とする。そうでなければ、ｃ∈（ｎｃ＋ｆ＋ｓｖ−１，ｎｃ＋ｆ＋ｓｖ）となるように、指数ｖを計算し、ここで、ｓｖは、リスト１６、ステップ４Ｂにおけるように定義される。また、（リスト１６におけるように定義される）ｔの値を計算し、（ｕ，ｗ）を指数ｖの準水平線１１２４上のｔ番目の点とする。
【０３３８】
５．
【数１１８】
0005412626.tif 000119
【０３３９】
に設定する。
【０３４０】
リスト１７の終了。
【０３４１】
計数についての考察を含む計算注記１は、リスト１６に当てはまる。
【０３４２】
パラメータの設定。θ準順列は、おそらく署名方式により適しているので、ｈ′−ｈの値とｈ″の値を選択するのに、署名方式にできるだけ有用となるのに準順列が含むべき性質について考慮しなければならない。例えば、θは、一意可逆であるかほとんどそうであるべきである。しかしながら、図９のステップ５１０で、多数の候補から正確なＨ（Ｍ）値を認識したり、そうでなければ、ステップ５２０で、検証を認識するのが可能であれば、一意可逆は、必要ではない。一実施形態において、ｌ３とｌ４は、両方とも１に等しい。すなわち、各ビットストリングｘは、その逆としてちょうど１つのＢ要素ｘ′を有する。ｌ１が少なくとも１つであることは適切である。すなわち、各Ｂ要素は、その圧縮として少なくとも１つの短いビットストリングを有するべきである。前述のように、他のパラメータの値を考慮すると、ｌ２はできるだけ小さくするべきである。これらの考慮事項を念頭において、以下の計算は、具体的なパラメータを示している。
【０３４３】
ｎｃ＋ｆ＋ｎｌ≦ｘｒｉｇｈｔ−ｘｌｅｆｔとなるように、すなわち、Ｐ（ａｉ，ｂｉ）の点の数の上限が、Ｊ（ａｉ，ｂｉ）に対応付けられたビットストリングの数よりも小さくなるように、パラメータを選択することで、各Ｂ要素に一意に対応付けられる少なくとも１つのビットストリングが確実に存在することになる。
【数１１９】
0005412626.tif 000120
【０３４４】
であることに注目されたい。ここで、後者の項は、Ｉ（ａｉ，ｂｉ）の直径であり、少なくともＪ（ａｉ，ｂｉ）の直径である。このことは、
【数１２０】
0005412626.tif 000121
【０３４５】
であることを意味する。
【０３４６】
さて、Ｃｏｒｏｎが用いたパラメータについて考えてみる。Ｃｏｒｏｎは、
【数１２１】
0005412626.tif 000122
【０３４７】
の場合を考慮した。これらの値について、Ｃｏｒｏｎは、
【数１２２】
0005412626.tif 000123
【０３４８】
の上限を証明した。ここで、ｊｉは、Ｊ（ａｉ，ｂｉ）の整数の数である。従って、
【数１２３】
0005412626.tif 000124
【０３４９】
であれば、ｘｒｉｇｈｔ−ｘｌｅｆｔ＋１＞ｎｃ＋ｆ＋ｎｌである。ｎｌ推定値が整数である限り、望みどおり、ｘｒｉｇｈｔ−ｘｌｅｆｔ≧ｎｃ＋ｆ＋ｎｌとなる。従って、
【数１２４】
0005412626.tif 000125
【０３５０】
に設定してもよく、ここで、最大値は、全てのｉに取って代わる。
【０３５１】
他方、Ｃｏｒｏｎは、また、下限
【数１２５】
0005412626.tif 000126
【０３５２】
を証明する。これにより、ｃ′について可能な値の数の上限をおよそ
【数１２６】
0005412626.tif 000127
【０３５３】
に定めることができ、Ｎとεの標準値に対して最大で２である。また、ｃについて可能な値の数は、およそ
【数１２７】
0005412626.tif 000128
【０３５４】
によって上限を定められ、Ｃｏｒｏｎのパラメータに対し同じく最大で２である。従って、ｌ２は、最大で２・２＝４であり、（１，４，１，１）準順列を得る。しかしながら、Ｂ要素の無視できる部分だけは複数の像を有する。
【０３５５】
４．暗号化／復号化方式
本発明のπ変換を図６の方式において用いることで、暗号文のサイズの縮小を可能にすることによって、（上述の）Ｒａｂｉｎ‐ＯＡＥＰ＋等のＲａｂｉｎに基づく暗号化方式を改良することができる。
【０３５６】
以下、πＮ，ｈ，ｈ′という表現は、集合Ｂ２Ｎ，ｈ，ｈ′への写像πを示し、θＮ，ｈ，ｈ′は、集合Ｂ２Ｎ，ｈ，ｈ′からの写像θを示す。
【０３５７】
リスト１８‐暗号化（図６）：
１．ステップ２１０：メッセージＭのエンコードである、ｘ＝Ｈ（Ｍ）を計算する。
【０３５８】
２．ステップ６１０：ｘ′＝πＮ，ｈ，ｈ′（ｘ，ｒ）∈［０，Ｎ／２］を計算する。
【０３５９】
３．ステップ２２０：ｙ＝ｘ′２（ｍｏｄ  Ｎ）を計算する。ここで、文字ｙをｃの代わりに暗号文に用いて、本明細書におけるｃの他の使用との混同を避ける。
【０３６０】
４．ステップ２３０：ｙを暗号文として出力する。
【０３６１】
リスト１８の終了。
【０３６２】
リスト１９‐復号化（図７）：
１．ステップ３１０：ｘ′２≡ｙ（ｍｏｄ  Ｎ）となるように、各ｘ′∈［０，Ｎ／２］を計算する。図７において数ｘ′はｂと示す。［０，Ｎ／２］にはかかるｘ′が少なくとも１つ存在するのは、ｘ′２＝ｙ（ｍｏｄ  Ｎ）でありｘ′が［０，Ｎ／２］になければ、ｘ′はＮ−ｘ′に設定することができるからであり、この新しいｘ′値は［０，Ｎ／２］にあり、ｘ′２＝ｙ（ｍｏｄ  Ｎ）を満たす。
【０３６３】
２．ステップ３２０：
【数１２８】
0005412626.tif 000129
【０３６４】
を計算する。かかるｘ値は、いくつかあることがある。これらの値は、図７のＨ（Ｍ）に対応する。
【０３６５】
３．ステップ３３０：メッセージエンコードを取り消して、メッセージＭが正確にエンコードされているか確認する。
【０３６６】
４．Ｍが正確にエンコードされていない場合、ｘ′の別の値を試してみる。ｘ′の全ての値が試されているならば、復号化が失敗したことを示す。
【０３６７】
リスト１９の終了。
【０３６８】
リスト１４、１５、１８、１９による、π写像を含むＲａｂｉｎ暗号化方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でπ写像がないのと同じくらい安全であることを示すことができる。参照により本明細書に含まれる「Ｃｒａｉｇ  Ｇｅｎｔｒｙ著、Ｈｏｗ  ｔｏ  ｃｏｍｐｒｅｓｓ  Ｒａｂｉｎ  Ｃｉｐｈｅｒｔｅｘｔｓ  ａｎｄ  Ｓｉｇｎａｔｕｒｅｓ  （ａｎｄ  Ｍｏｒｅ），Ｐｒｏｃ．ｏｆ  Ｃｒｙｐｔｏ  ２００４，Ｍ．Ｆｒａｎｋｌｉｎ（Ｅｄ．），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ３１５２，ｐｐ．１７９−２００，Ｓｐｒｉｎｇｅｒ，２００４」を参照されたい。
【０３６９】
π準順列は、Ｎ，ｈ及びｈ′の特定の値に依存することに注意されたい。従って、ある意味、ｈ及びｈ′は、公開鍵の一部であり、送信者は、暗号化を実行するのにそれが必要である。ＲＳＡやＲａｂｉｎ暗号化と共に用いることができる当技術において公知の様々なエンコード方式は、本発明の帯域幅縮小暗号化方式においても用いることができる。以下、帯域幅縮小暗号化方式の詳細を示すが、上記リスト５及び６のＲａｂｉｎ‐ＯＡＥＰ＋の説明に類似している。上述のように、メッセージエンコードは、式（１）により上記定義したハッシュ関数を利用する。非帯域幅縮小Ｒａｂｉｎ‐ＯＡＥＰ＋（リスト５及び６）において、
【数１２９】
0005412626.tif 000130
【０３７０】
であったが、本発明の帯域幅縮小暗号化方式においては、式（２１）に示したＶａｌｌｅｅのパラメータに関するｈ″の値に従って、
【数１３０】
0005412626.tif 000131
【０３７１】
に設定するのが適切である。いくつかの実施形態において、Ｖａｌｌｅｅのパラメータにおけるように、ｈ′−ｈは、およそ８Ｎ２／３である。もちろん、ｎを大きくする、例えば、ｌｏｇ２Ｎにまですることができるが、エンコードしたプレーンテキストが、
【数１３１】
0005412626.tif 000132
【０３７２】
よりも大きくなければならない場合を除いて、それは必須ではない。
【０３７３】
メッセージＭ∈｛０，１｝ｍを暗号化するために、送信者は、以下の演算を実行する（図６参照）。
【０３７４】
リスト２０‐暗号化。
【０３７５】
図６のステップ２１０は、以下のステップ１乃至３に対応する。
【０３７６】
１．任意の
【数１３２】
0005412626.tif 000133
【０３７７】
を選択する。
【０３７８】
２．
【数１３３】
0005412626.tif 000134
【０３７９】
を設定する。
【０３８０】
３．ｎビットストリング、ｘ←ｓ‖ｔを設定する。
【０３８１】
４．ステップ６１０：ｘ′＝π（ｘ，ｒ）∈［０，Ｎ／２］を計算する。
【０３８２】
５．ステップ２２０：暗号文ｃ←ｘ′２（ｍｏｄ  Ｎ）を計算する。
【０３８３】
リスト２０の終了。
【０３８４】
ｘ′は、モジュラ平方数が非常に狭い値域（すなわち、［ｈ，ｈ′］）にある整数であるので、ｃの
【数１３４】
0005412626.tif 000135
【０３８５】
最下位ビットだけを実際に送信するだけでよく、暗号文を「短く」することに注目されたい。ｈ′−ｈ＝８Ｎ２／３に対し、暗号文は、およそ
【数１３５】
0005412626.tif 000136
【０３８６】
ビットである。
【０３８７】
復号化するために、受信者は、以下のステップを実行する（図７参照）。
【０３８８】
リスト２１−復号化
１．ステップ３１０：ｃのモジュラ平方根
【数１３６】
0005412626.tif 000137
【０３８９】
と
【数１３７】
0005412626.tif 000138
【０３９０】
とを計算する。
【数１３８】
0005412626.tif 000139
【０３９１】
の少なくとも１つと、
【数１３９】
0005412626.tif 000140
【０３９２】
の少なくとも１つは、［０，Ｎ／２］にある。一般性を失うことなく、
【数１４０】
0005412626.tif 000141
【０３９３】
は、［０，Ｎ／２］にあるものと仮定することができる。
【０３９４】
２．候補
【数１４１】
0005412626.tif 000142
【０３９５】
ごとに、
２Ａ．ステップ７１０：
【数１４２】
0005412626.tif 000143
【０３９６】
を計算する。
【０３９７】
２Ｂ．ステップ３２０：
【数１４３】
0005412626.tif 000144
【０３９８】
と、
【数１４４】
0005412626.tif 000145
【０３９９】
について、ｘｉをｓｉ‖ｔｉに構文解析し、次に、
【数１４５】
0005412626.tif 000146
【０４００】
と、
【数１４６】
0005412626.tif 000147
【０４０１】
について、ｓｉを
【数１４７】
0005412626.tif 000148
【０４０２】
に構文解析する。ｉごとに、
【数１４８】
0005412626.tif 000149
【０４０３】
と、
【数１４９】
0005412626.tif 000150
【０４０４】
とを計算し、
【数１５０】
0005412626.tif 000151
【０４０５】
かどうかテストする。条件が満たされる一意のｉが存在する場合、Ｍｉを正確なプレーンテキストとして出力し、そうでなければ、復号化の失敗を示す。
【０４０６】
リスト２１の終了。
【０４０７】
セキュリティのプルーフの概略を述べるのに、上記の帯域幅縮小暗号化方式を解読することは、法Ｎを因数分解するのと同じくらい難しいことを（例えば、「ランダムオラクルモデル」を用いて）証明できる。例えば、時間ｔＡでアドバンテージεＡで暗号化方式を解読するアルゴリズムＡが存在するものとし、ここで、アドバンテージは、Ａが選択した２つのプレーンテキスト、Ｍ０とＭ１、のどちらが特定の暗号文によって暗号化されているかを正確に推測できる確率（マイナス１／２）と定義する。次に、Ａとのインタラクションを通じて得た知識を用いることによって、Ｎを因数分解できる第２のアルゴリズムＢを構成することができる。例えば、以下の「ゲーム」を考えてみる。
【０４０８】
挑戦者は、因数分解する法ＮをＢに与える。Ｂは、Ｎをその公開鍵であると述べ、フェーズ１で、Ａが、Ａの選択した暗号文メッセージｃの復号化を要求することができるようにする。さて、Ｂは、秘密鍵を知らないので、Ｂは、実際に復号化できない。しかしながら、Ｂは、暗号ハッシュ関数Ｇ，Ｈ及びＨ′（１）の出力を制御する。これは、ランダムオラクルモデルである。ハッシュ関数は、「ゲーム」のエンティティが制御してもよいオラクルとみなされる。Ａは、Ａの選択したメッセージＭのハッシュ関数値をＢに問い合わせる。Ｂが同じメッセージＭについて、以前に、この問合せを受信していれば、Ｂは、以前と同じハッシュ関数値を返す。そうでなければ、Ｂは、ランダムにハッシュ関数値を生成する。Ａは、このハッシュ関数値を用いてＭを暗号文ｃに暗号化し、Ｂにｃを復号化するように要求する。
【０４０９】
Ｂがハッシュ関数を制御するので、また、Ａは（無視できる確率を除いて）ハッシュを問合せることなく有効にエンコードされた暗号文を作成することができないので、Ｂは、（例えば）ＡがＨ′に入力するＭの値など、Ａのハッシュ関数への入力Ｍを「見る」ことになる。この知識を用いて、Ｂは、圧倒的に高い確率でＡの復号化の問合せに正確に返答するこができる。フェーズ１の終わりに、Ａは、それについてテストされたいメッセージＭ０とＭ１を選択し、Ｂは、ランダムにあるビットｂ∈｛０，１｝を選択し、Ｍｂを暗号化する暗号文ｃ（「挑戦暗号文」）を返信する。Ｂは、ハッシュ関数の制御を用いて、この暗号文を巧妙に「間に合わせに作る」ので、ｃのモジュラ平方根
【数１５１】
0005412626.tif 000152
【０４１０】
がわかる。「フェーズ２」で、Ａは、挑戦暗号文以外の復号化すべき暗号文をさらに要求することができる。最終的に、推測ｂ′∈｛０，１｝を出力し、ｂ＝ｂ′であればゲームに勝利する。ハッシュの問合せをさらに行って、再びＢがこれらのハッシュ関数への入力を「見る」ことができるようしない限り、Ａは、せいぜいわずかなアドバンテージしか有さない。
【０４１１】
Ａが確かにｃのモジュラ平方根
【数１５２】
0005412626.tif 000153
【０４１２】
を計算すれば、
【数１５３】
0005412626.tif 000154
【０４１３】
である可能性があるので、
【数１５４】
0005412626.tif 000155
【０４１４】
は、Ｎの自明ではない因数を与える。確かに、ｘとｒを一様に計算し（ハッシュ関数はｘに対し一様出力を与えるものとする）、次に、ｘ′＝π（ｘ，ｒ）を計算することからなる抜き出し方式が擬一様抜き出し方式であれば、Ｂが、どのモジュラ平方根を知っているかをＡが推測する可能性は低いことを意味する。従って、Ａは、間違って推測することが多く、そのハッシュの問合せにより、Ｎの自明ではない因数を計算するのに必要な情報をＢに与える可能性が高い（擬一様抜き出し方式について、Ｖａｌｌｅｅの値を
【数１５５】
0005412626.tif 000156
【０４１５】
とすると、少なくとも
【数１５６】
0005412626.tif 000157
【０４１６】
の可能性）。
【０４１７】
５．署名方式
本発明のθ変換を用いて、署名を損失なしに圧縮できるようにすることによって、Ｃｏｒｏｎが安全であると証明した部分領域ハッシュ署名などの、Ｒａｂｉｎに基づく署名方式を改良することができる。基本的なアプローチは、以下のとおりである。
【０４１８】
リスト２２‐署名（図８も参照）：
１．図８のステップ４１０：メッセージＭのエンコード、ｙ∈［ｈ，ｈ′］を計算する。
【０４１９】
図８のステップ４２０は、以下のステップ２及び３に対応する。
【０４２０】
２．ｅｙがＮを法とする平方数となるように、ｅ∈｛−２、−１，１，２｝を計算し、ｅｙ（ｍｏｄ  Ｎ）を計算する。ｙは、Ｎを法とする平方根を持たないことがあるが、（Ｎが２つの素数の積とすると）−２*ｙ，−ｙ，ｙ，２*ｙのいずれかは、常にＮを法とする平方根を有するので、ｅで乗算がなされる。
【０４２１】
３．ｘ′２≡ｅｙ（ｍｏｄ  Ｎ）となるように、ｘ′∈［０，Ｎ／２］を計算する。「通常の」署名は、（ｘ′，ｅ）である。
【０４２２】
４．図８のステップ８１０：ｅが正であれば、ｘ＝θＮ，ｅｈ，ｅｈ′（ｘ′，ｒ）を計算し、ｅが負であれば、ｘ＝θＮ，ｅｈ′，ｅｈ（ｘ′，ｒ）を計算する。圧縮された署名は（ｘ，ｅ）である。
【０４２３】
リスト２２の終了。
【０４２４】
リスト２３-検証（図９参照）：
１．ステップ９１０（図９）：ｅが正であれば、
【数１５７】
0005412626.tif 000158
【０４２５】
を計算し、ｅが負であれば、
【数１５８】
0005412626.tif 000159
【０４２６】
を計算する。
【０４２７】
２．ステップ５１０：ｙ＝Ｈ（Ｍ）／ｅ（ｍｏｄ  Ｎ）を計算する。
【０４２８】
３．ステップ５２０：ｙ∈［ｈ，ｈ′］であり、メッセージＭのエンコードであるか確認する。
【０４２９】
リスト２３の終了。
【０４３０】
θ準順列は、Ｎ，ｈ，ｈ′及びｅの特定の値に依存することに注意されたい。従って、ある意味では、ｈとｈ′は、公開鍵の一部であり、検証者は、署名を検証するのにそれが必要である。ＲＳＡやＲａｂｉｎ署名と共に用いることができる当技術で公知の様々なエンコード方式は、本発明の帯域幅縮小署名方式においても用いることができ、その逆もまた同様である。ｅの値は、２ビットで表現することができる。ｅに様々な値を用いることができるが、ｅを小さくしておくことは適切である。
【０４３１】
リスト１６、１７、２２、２３による、θ写像を含むＲａｂｉｎ署名方式は、ランダムオラクルによる適応的選択メッセージ攻撃に関する存在偽造不可能モデルの下でθ写像がないのと同じくらい安全であることを示すことができる。上述のＣｒａｉｇ  Ｇｅｎｔｒｙ著の論文、Ｈｏｗ  ｔｏ  ｃｏｍｐｒｅｓｓ  Ｒａｂｉｎ  Ｃｉｐｈｅｒｔｅｘｔｓ  ａｎｄ  Ｓｉｇｎａｔｕｒｅｓ  （ａｎｄ  Ｍｏｒｅ）を参照されたい。
【０４３２】
以下、より詳細な帯域幅縮小署名方式を示すが、前述の全領域ハッシュ署名方式の説明と類似している（リスト７及び８参照）。メッセージ復元が可能な特定のエンコード方式を使用する。前述のように、上記式（１）により与えられる暗号ハッシュ関数を使用する。非帯域幅縮小署名方式（リスト７及び８）においては、
【数１５９】
0005412626.tif 000160
【０４３３】
であったが、帯域幅縮小署名方式には、Ｃｏｒｏｎのパラメータに従って、
【数１６０】
0005412626.tif 000161
【０４３４】
とするのが望ましい。この場合も、ｎを
【数１６１】
0005412626.tif 000162
【０４３５】
ビットよりも大きく設定することができるが、ある理由で、エンコードされたメッセージが
【数１６２】
0005412626.tif 000163
【０４３６】
ビットよりも長くなければならない場合を除いて、これは望ましくない。素数Ｐ≡３（ｍｏｄ  ８）及びｑ≡７（ｍｏｄ  ８）についてＮ＝ｐｑとなるようにＮを生成する際、署名者は、以下の演算を実行する。
【０４３７】
リスト２４‐署名(図８)：
図８のエンコードステップ４１０：
１．任意の
【数１６３】
0005412626.tif 000164
【０４３８】
を選択する。
【０４３９】
２．
【数１６４】
0005412626.tif 000165
【０４４０】
を設定する。
【０４４１】
３．ｎビット整数、ｙ←ｓ′‖ｓ″‖ｔを設定する。
【０４４２】
図８の署名ステップ４２０：
４．ｕｑ←ｙ（ｑ＋１）／４（ｍｏｄ  ｑ）を計算する。
【０４４３】
５．
【数１６５】
0005412626.tif 000166
【０４４４】
であれば、ｅｙ←１に、そうでなければ、ｅｙ←−１に設定する。
【０４４５】
６．ｕｐ←（ｅｙｙ）（ｐ＋１）／４（ｍｏｄ  ｐ）を計算する。
【０４４６】
７．
【数１６６】
0005412626.tif 000167
【０４４７】
であれば、ｆｙ←１に、そうでなければ、ｆｙ←２に設定する。
【０４４８】
８．ｖｑ←ｆｙ（３ｑ−５）／４ｕｑ（ｍｏｄ  ｑ）、及びｖｐ←ｆｙ（３ｑ−５）／４ｕｐ（ｍｏｄ  ｐ）を計算する。
【０４４９】
９．ｗ←ｖｑ＋ｑ（ｑｐ−２（ｖｐ−ｖｑ）ｍｏｄ  ｐ）を計算する。
【０４５０】
１０．２ｗ＜Ｎであれば、ｘ′←ｗに、そうでなければ、ｘ′←Ｎ−ｗに設定する。
【０４５１】
短い署名の生成（図８のステップ８１０）：
１１．ｅが正であれば、ｘ＝θＮ，ｅｈ，ｅｈ′（ｘ′，ｒ′）を計算し、ｅが負であれば、ｘ＝θＮ，ｅｈ′，ｅｈ（ｘ′，ｒ′）を計算する。
【０４５２】
１２．署名（ｅｙ，ｆｙ，ｒ，ｘ）を出力する。
【０４５３】
リスト２４の終了。
【０４５４】
この場合も、２（３ｑ−５）／４（ｍｏｄ  ｑ）、２（３ｐ−５）／４（ｍｏｄ  Ｐ）及びｑｐ−２（ｍｏｄ  ｐ）の値は事前に計算できるので、ステップ８及び９は、署名時間にほとんど何も付加しない。
【０４５５】
リスト２５‐検証（図９）：
１．ステップ９１０：ｅが正であれば、
【数１６７】
0005412626.tif 000168
【０４５６】
を計算し、ｅが負であれば
【数１６８】
0005412626.tif 000169
【０４５７】
を計算する。
【０４５８】
２．ステップ５１０、５２０：
【数１６９】
0005412626.tif 000170
【０４５９】
を計算し、ｙｔｍｐがｎビットであることを確認し、ｙｔｍｐを
【数１７０】
0005412626.tif 000171
【０４６０】
に構文解析し、
【数１７１】
0005412626.tif 000172
【０４６１】
を計算し、
【数１７２】
0005412626.tif 000173
【０４６２】
であることを確認する。
【０４６３】
リスト２５の終了。
【０４６４】
検証処理中にメッセージＭが復元されることに注意されたい。また、圧縮θ（リスト２４のステップ１１）は、「通常の」Ｒａｂｉｎ署名（ｅｙ，ｆｙ，ｘ′）が生成された後に、署名処理の終わりにやっと出てくることに注目されたい。
【０４６５】
セキュリティのプルーフは、Ｃｏｒｏｎが提供したような「通常の」部分領域ハッシュ署名方式に対するセキュリティのプルーフから容易に得られる。ある攻撃者Ａが、帯域幅縮小方式において偽造ができるならば、非帯域幅縮小方式に対する別の攻撃者Ｂは、単にθ−１をＡの偽造に適用することで、非帯域幅縮小方式において偽造することができることは明らかである。Ｂは、Ａの署名の問合せを挑戦者に中継し、次に挑戦者の応答に対し、それらをＡに中継する前にθを適用することによって、該署名の問合せに容易に応答するふりをすることができる。
【０４６６】
６．サインクリプション方式
本発明のいくつかの実施形態によるサインクリプション方式において、望ましくは、サインクリプションの送信が、送信者が署名と暗号文を別々に送信した場合よりも少ない帯域幅を消費するように、送信者は、同時に、自身の秘密鍵を用いてメッセージに署名し、受信者の公開鍵を用いてそれを暗号化する。受信者は、その秘密鍵でサインクリプションを復号化し、送信者の公開鍵を用いて送信者の署名を検証する。送信者の公開法をＮＡ又はＮ（Ａ）で示し、送信者のｈ，ｈ′パラメータをそれぞれｈＡ及びｈ′Ａで、又はｈ（Ａ）及びｈ′（Ａ）で示す。受信者の公開法をＮＢ又はＮ（Ｂ）で示し、受信者のｈ，ｈ′パラメータをそれぞれｈＢ及びｈ′Ｂで、又はｈ（Ｂ）及びｈ′（Ｂ）で示す。一実施形態は以下のとおりである（図６、８及び１４参照）。
【０４６７】
リスト２６‐サインクリプション（図１４）：
１．図１４のステップ４１０（エンコード）：メッセージＭのエンコード、ｙ∈［ｈＡ，ｈ′Ａ］を計算する。ステップ４２０（以下のステップ２、３）。
【０４６８】
２．ｅｙがＮＡを法とする平方数となるように、ｅ∈｛−２，−１，１，２｝を計算する。
【０４６９】
３．ｘ′２≡ｅｙ（ｍｏｄ  ＮＡ）となるように、ｘ′∈［０，ＮＡ／２］を計算する。
【０４７０】
４．ステップ８１０：ｅが正であれば、短い署名
【数１７３】
0005412626.tif 000174
【０４７１】
を計算し、ｅが負であれば、
【数１７４】
0005412626.tif 000175
【０４７２】
を計算する。
【０４７３】
５．ステップ１４１０：ｘ″∈［０，Ｎ／２］として、ｅが正であれば、
【数１７５】
0005412626.tif 000176
【０４７４】
を計算し、ｅが負であれば、
【数１７６】
0005412626.tif 000177
【０４７５】
を計算する。
【０４７６】
６．ステップ１４２０：ｃ＝ｘ″２（ｍｏｄ  ＮＢ）を計算する。サインクリプションは、ｅとｃ、又はｅとｃの省略形とからなる（ｃの省略形とは、ｃよりも少ないビットで表現することができ、それからｃを求めることができる数であり、例としてｃ−ｈや、ｃのある数の最下位ビットを含む）。
【０４７７】
リスト２６の終了。
【０４７８】
θ準順列は、Ｎ，ｅの特定の値と、ｈ及びｈ′の値に依存し、ユーザＡ及びＢによって異なることがあることに注意されたい。従って、いくつかの実施形態では、ｈとｈ′は、公開鍵の一部であり、受信者は、署名を検証し、メッセージを復号化するのにそれが必要である。異なる署名者は、ｈとｈ′に異なる値を用いることができるが、簡潔にするために同じであるのが望ましい。様々なエンコード方式が当技術において公知であり、１つの方式を以下に詳細に説明する。ｅの値は、２ビットで表現することができる。ｅに様々な値を用いることができるが、ｅを小さくしておくことが望ましい。「ｃの省略形」（例えば、
【数１７７】
0005412626.tif 000178
【０４７９】
ビットで表現することができる、ｃ−ｈ）を、ｈ及びｈ′と一緒に用いて、ｃの完全な値を復元することができるので、サインクリプションは「短い」。
【０４８０】
リスト２７‐アンサインクリプション（Ｕｎｓｉｇｎｃｒｙｐｔｉｏｎ）（図１５参照）：
１．ステップ１５１０（復号化）：ｘ″２≡ｃ（ｍｏｄ  ＮＢ）となるように、ｘ″∈［０，ＮＢ／２］の２つの値を計算する。
【０４８１】
２．ステップ１５２０：ｅが正であれば、
【数１７８】
0005412626.tif 000179
【０４８２】
を計算し、ｅが負であれば、
【数１７９】
0005412626.tif 000180
【０４８３】
を計算する。
【０４８４】
３．ステップ１５３０：ｅが正であれば、
【数１８０】
0005412626.tif 000181
【０４８５】
を計算し、ｅが負であれば、
【数１８１】
0005412626.tif 000182
【０４８６】
を計算する。
【０４８７】
４．ステップ１５４０：ｙ＝ｘ′２／ｅ（ｍｏｄ  ＮＡ）を計算する。
【０４８８】
５．ステップ１５５０：メッセージエンコードを取り消してＭを復元し、メッセージＭが正確にエンコードされているか確認する。Ｍが正確にエンコードされていなければ、ｘ″の他の値を試してみる。ｘ″の両方の値を試しているならば、復号化が失敗したことを示す。
【０４８９】
リスト２７の終了。
【０４９０】
アンサインクリプションにおいて、図１４のステップ８１０におけるθの計算でサインクリプター（ｓｉｇｎｃｒｙｐｔｅｒ）が用いるｒの特定の値を、アンサインクリプター（ｕｎｓｉｇｎｃｒｙｐｔｅｒ）は知らない。しかしながら、θ準順列にパラメータを望ましく選択するために、Ｂ要素の無視できる部分だけが複数の像を有するので、出力は一意になる可能性が高い（ｒから独立している）。しかし、必要ならば、サインクリプターは、どのｒの値を用いたかを示す少数の追加ビットを送信することができる。
【０４９１】
図１４のステップ４１０の典型的なエンコードは、以下のとおりである。ｍ，ｋ０，ｋ１をセキュリティパラメータとする。
【数１８２】
0005412626.tif 000183
【０４９２】
と
【数１８３】
0005412626.tif 000184
【０４９３】
の数量は、ごくわずかであるべきだが、必然ではない。ｎ＝ｍ＋ｋ０＋ｋ１とする。望ましくは、法ＮＡとＮＢは、ほぼ同じ数のビットを有し、帯域幅縮小署名方式におけるように、
【数１８４】
0005412626.tif 000185
【０４９４】
である。ＮＡとＮＢのサイズが異なるならば、
【数１８５】
0005412626.tif 000186
【０４９５】
となるように、ｎを設定することができる。この場合も、ｎをさらに大きく設定することはできるが、そうすることは最適ではない。以下の暗号ハッシュ関数を定義する。
【数１８６】
0005412626.tif 000187
【数１８７】
0005412626.tif 000188
【０４９６】
このＨ関数（メッセージエンコードの計算用の中間値）は、図１４のステップ４１０に示す、最終的なエンコードされたメッセージを表すＨ（Ｍ）関数と混同するべきではない。
【０４９７】
図１４のステップ４１０で、ｙを計算するために、ここで、ｙは、メッセージＭ∈｛０，１｝ｍのエンコードであるが、サインクリプターは、
１．任意の
【数１８８】
0005412626.tif 000189
【０４９８】
を選択する。
【０４９９】
２．ｔ＝Ｈ（ｒ‖Ｍ）及び
【数１８９】
0005412626.tif 000190
【０５００】
に設定する。
【０５０１】
３．ｙ＝ｓ‖ｔに設定する。
【０５０２】
ステップ１５５０で（図１５）、アンサインクリプターは、ｙをｓ及びｔに構文解析し、
【数１９０】
0005412626.tif 000191
【０５０３】
からｒとＭを復元し、ｔ＝Ｈ（ｒ‖Ｍ）であることを確認する。セキュリティプルーフは、基本的に、前述の、暗号化方式と署名方式のセキュリティプルーフを組み合わせたものである。さらに、帯域幅縮小署名方式に関連して上記に述べたモジュラ平方根の計算への数論的アプローチは、サインクリプション／アンサインクリプションと共に用いることができる。
【０５０４】
いくつかのサインクリプション実施形態において、署名と暗号化の順序を逆にする。すなわち、送信者は、まず、受信者の公開鍵を用いてメッセージを暗号化し、次に送信者の秘密鍵を用いてメッセージに署名する。受信者は、署名を検証し、暗号化されたメッセージを復元し、次にメッセージを復号化する。リスト２６、２７に類似した方法を、演算の順序を適切に変更して用いることができる。
【０５０５】
７．集合署名方式
本発明のいくつかの実施形態による集合署名方式において、それぞれ公開鍵法｛Ｎ１，…，ＮＺ｝を有する署名者の集合｛Ｓ１，…，ＳＺ｝は、それらの集合署名、すなわち、各ＳｉがＭｉに署名したことを検証するのに必要なビットストリングが「短く」、各署名者がそれぞれのメッセージに別々に署名した場合よりも少ない帯域幅を最適に消費するように、それぞれのメッセージ｛Ｍ１，…，ＭＺ｝に署名する。本発明のいくつかの実施形態において、メッセージは、順に署名され、これは、署名者Ｓｉが、Ｓｉ−１からｓｉ−１を受信した後に、Ｍｉについて署名ｓｉを生成することを意味する。いくつかの実施形態において、Ｎｉは、全てほぼ同じビット長を有する。Ｎｉのビット長に関する考慮事項は、本発明のサインクリプションの実施形態に関して前述したのと基本的に同じである。
【０５０６】
各ｓｉ−１は、
【数１９１】
0005412626.tif 000192
【０５０７】
の要素の、（
【数１９２】
0005412626.tif 000193
【０５０８】
により）圧縮した表示であり（図８のステップ８１０に注目）、ｓｉは、基本的に、［ｈ，ｈ′］の数のＮｉを法とする圧縮平方根として計算される（ステップ４２０、８１０）。その数は、ｓｉ−１とＭｉとに依存する。（以後、署名者は、それぞれ異なる値のｈ及びｈ′を用いることができるが、便宜上、このことは表記において示さない）。集合署名は、公開鍵｛Ｎ１，…，ＮＺ｝を用いて検証される。具体的に、このアプローチは、以下のとおりである。ｆを後述する関数とする。Ｎｉは、Ｎ（ｉ）とも示す。ｉ番目の署名者は、以下の演算を実行する。
【０５０９】
リスト２８‐集合署名（図８参照）：
０．ｓ０＝ｄに設定する。ここで、ｄは、所定の固定値である（任意の値）。
【０５１０】
１．ｉ＝１からｉ＝ｚについて、以下を行う。
【０５１１】
１Ａ．ステップ４１０：ｙｉ＝ｆ（ｓｉ−１，Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）∈［ｈ，ｈ′］を計算する。
【０５１２】
ステップ４２０（以下のステップ１Ｂ及び１Ｃ）：
１Ｂ．ｅｉｙｉがＮｉを法とする平方数となるように、ｅｉ＝ｅｉ（ｉ）∈｛−２，−１，１，２｝を計算する。Ｈ（Ｍ）＝ｅｉｙｉ(ｍｏｄ  Ｎｉ)を計算する。
【０５１３】
１Ｃ．ステップ４２０：
【数１９３】
0005412626.tif 000194
【０５１４】
となるように、
【数１９４】
0005412626.tif 000195
【０５１５】
を計算する。
【０５１６】
１Ｄ．ステップ８１０：ｅｉが正であれば、ｓｉ＝θＮ（ｉ），ｅ（ｉ）ｈ，，ｅ（ｉ）
ｈ′（ｓｉ’，ｒ）を計算し、ｅｉが負であれば、ｓｉ＝θＮ（ｉ），ｅ（ｉ）ｈ′，ｅ（
ｉ）ｈ（ｓｉ’，ｒ）を計算する。
【０５１７】
２．集合署名（ｓ１，ｅ１，・・・ｓｚ，ｅｚ）を出力する。
【０５１８】
リスト２８の終了。
【０５１９】
ｉ番目の署名者は、ｓｉを生成する前に、（ｉ−１）番目の署名者がそれ自身の署名を集合した後の結果である、ｓｉ−１の値を受信することに注目されたい。サインクリプション方式におけるように、署名者は、それぞれ、ｈとｈ′に異なる値を用いることができるが、簡潔にするためには同じであることが望ましい。関数ｆについては、本発明が利用する検証の概要を述べた後に説明する。
【０５２０】
リスト２９‐検証（図９参照）：
１．ｉ＝ｚからｉ＝１について、以下を行う。
【０５２１】
１Ａ．ステップ９１０：ｅｉが正であれば、ｓｉ′＝θ−１Ｎ（ｉ），ｅ（ｉ）ｈ，ｅ（ｉ）ｈ′（ｓｉ）を計算し、ｅｉが負であれば、ｓｉ′＝θ−１Ｎ（ｉ），ｅ（ｉ）ｈ′，ｅ（ｉ）ｈ（ｓｉ）を計算する。
【０５２２】
１Ｂ．ステップ５１０：
【数１９５】
0005412626.tif 000196
【０５２３】
を計算する。
【０５２４】
１Ｃ．ステップ５２０：ｙｉ＝ｆ（ｓｉ−１，Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）からｓｉ−１を計算する。
【０５２５】
２．ステップ５２０：ステップ１Ｂ‐２で計算したｓ０がｄに等しいことを確認する。
【０５２６】
リスト２９の終了。
【０５２７】
関数ｆは、集合署名処理において効率的に計算可能なだけでなく、検証処理においても効率的に可逆であるべきである。可逆であるとは、ｓｉ−１が、ｆ（ｓｉ−１，Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）と、Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１の値から導き出せるべきであるという意味においてである。かかる関数の候補の１つは、ｆ（ｓｉ−１，Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）＝ｓｉ−１・Ｈｉ（Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）である。ここで、“・”は、加算やＸＯＲなどの何らかの容易に可逆である２項演算である。
【０５２８】
この方式のセキュリティを証明するのに問題があることがある。１つの理由として、鍵とメッセージの固定集合（Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）に対する集合署名要素ｓｉ−１には、可能性のある値が多くあり、シミュレータ（すなわち、暗号化の項４の言語のアルゴリズムＢ）が、ｓｉに関するｓｉ−１の全ての可能性のある値についての攻撃者の署名の問合せに返答することができるように、シミュレータが、Ｈｉ（Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）の単一の値を「間に合わせに作る」ことはおそらく不可能であることがある。ここで、Ｈｉは、Ｎｉを法とする整数集合の値を有するあるハッシュ関数である。
【０５２９】
この問題に対処するために、ｆを計算する別のアプローチを用いることがあり、
【数１９６】
0005412626.tif 000197
【０５３０】
を計算し、ここで、Ｅは、対称暗号化方式であり、対称暗号鍵ｋｉは、あるハッシュ関数Ｈｉについて、ｋｉ＝Ｈｉ（Ｎｉ，Ｍｉ）（又は、必要なら、ｋｉ＝Ｈｉ（Ｎｉ，Ｍｉ，…，Ｎ１，Ｍ１）として計算する。ｆが可逆であることは容易にわかる。
【数１９７】
0005412626.tif 000198
【０５３１】
とＮｉ及びＭｉを与えられると、ｋｉ＝Ｈｉ（Ｎｉ，Ｍｉ）、次に、
【数１９８】
0005412626.tif 000199
【０５３２】
を計算することができる。ここで、
【数１９９】
0005412626.tif 000200
【０５３３】
は、鍵ｋｉの下の対称復号である。このセキュリティプルーフは、ランダム応答を返すオラクルのように、暗号ハッシュ関数がふるまうことを装うランダムオラクルモデルを用いるのではなく、ある対の鍵／メッセージについてランダム暗号文を返すオラクルのように暗号（対称暗号化方式）がふるまうことを装う理想暗号モデルを用いている。参照により本明細書に含まれる「Ｍ．Ｂｅｌｌａｒｅ、Ｄ．Ｐｏｉｎｔｃｈｅｖａｌ及びＰ．Ｒｏｇａｗａｙ著、“Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ｄｉｃｔｉｏｎａｒｙ  Ａｔｔａｃｋｓ”，ｉｎ  Ｐｒｏｃ．ｏｆ  Ｅｕｒｏｃｒｙｐｔ  ２０００，Ｂ．Ｐｒｅｎｅｅｌ（Ｅｄ．），Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １８０７，ｐｐ．１３９−１５５」を参照されたい。
【０５３４】
理想暗号モデルにより、シミュレータは、鍵やメッセージだけでなくｓｉ−１にも依存する問合せ応答を行うことができ、シミュレータは、その応答をより自由に「間に合わせに作る」ことができる。最適には、対称暗号化方式Ｅは、暗号文を拡張することなく、ｓｉ−１の長さ、すなわち、およそ（２／３＋ε）ｌｏｇ２Ｎｉビットのストリングを暗号化できるので、集合署名のサイズは、より多くの署名が集合されるにつれて著しく大きくなることはない。
【０５３５】
ｆを計算する上記方法はもちろん、θ圧縮関数を使用しない（すなわち、図８のステップ８１０を省略した）モジュラ２乗に基づく逐次集合署名方式を作成するのに用いることができる。
【０５３６】
８．リング署名方式
本発明のいくつかの実施形態の帯域幅縮小リング署名方式において、署名者Ｓｉは、Ｓｉがメンバーである署名者の集合｛Ｓ１，…，ＳＺ｝を選択して、検証者が、誰であるかは定められないけれども、｛Ｓ１，…，ＳＺ｝の少なくとも１人の署名者がメッセージに署名したことを検証者に確信させる、メッセージの「リング署名」を生成することができる。署名者Ｓｉは、従って、可能性のある署名者の「リング」内で限定された匿名性を有する。
【０５３７】
いくつかの実施形態において、署名者は、検証者がリング署名を検証するのに用いる公開法｛Ｎ１，…，ＮＺ｝を有する。リング署名は、集合的にＣｋ，ｖ｛ｙ１，…，ｙＺ｝を満たすｚのストリング｛ｘ１，…，ｘＺ｝を含み、ここで、
【数２００】
0005412626.tif 000201
【数２０１】
0005412626.tif 000202
【０５３８】
であり、ｖ及びｗは、所定のビットストリングであり、Ｃは、「結合関数」である。本発明のいくつかの実施形態の帯域幅縮小リング署名方式は、前述のθ準順列を用いることによって、また、法Ｎｉが異なるサイズを有することに対処するより帯域幅効率のよい方法を用いることによって、Ｒｉｖｅｓｔ‐Ｓｈａｍｉｒ‐Ｔａｕｍａｎ方式におけるよりも短いリング署名を実現している。
【０５３９】
Ｒｉｖｅｓｔ‐Ｓｈａｍｉｒ‐Ｔａｕｍａｎ方式（リスト１０、１１）において、
【数２０２】
0005412626.tif 000203
【０５４０】
について、（ｑｉ＋１）Ｎｉ≦２ｂであれば、ｙｉ＝ｑｉＮｉ＋ｇｉ（ｒｉ）を計算し、そうでなければ、
【数２０３】
0005412626.tif 000204
【０５４１】
を計算する。ここで、ｇｉは、関数
【数２０４】
0005412626.tif 000205
【０５４２】
を示し、ｂは、所定の定数である。ｂが十分に大きい限り、（ｑｉ＋１）Ｎｉ＞２ｂであるｙｉの割合は、無視できるものであるので、ｘ′ｉのｙｉへの写像は、Ｎｉを法とする２乗とほとんど区別できない振る舞いをする。残念ながら、ｂをこれほど大きいものに選ぶことは（全ての法の対数よりもはるかに大きい）、また、帯域幅効率が悪い。
【数２０５】
0005412626.tif 000206
【０５４３】
について、
【数２０６】
0005412626.tif 000207
【０５４４】
を計算するほうが帯域幅効率がよい。ここで、
【数２０７】
0005412626.tif 000208
【０５４５】
本発明のいくつかの実施形態において、θ準順列に関し、ｂが
【数２０８】
0005412626.tif 000209
【０５４６】
の約３分の２になるように、
【数２０９】
0005412626.tif 000210
【０５４７】
を用いて、さらによく行うことができる。従って、あるｘｉに対し、
【数２１０】
0005412626.tif 000211
【０５４８】
と
【数２１１】
0005412626.tif 000212
【０５４９】
とを計算することがある。結合関数は、やはり、
【数２１２】
0005412626.tif 000213
【０５５０】
となることができ、ここで、Ｅｋは、鍵ｋを用いる対称暗号化方式である。
【０５５１】
Ｓｉが「真の」署名者であるとすれば、本発明のいくつかの実施形態におけるリング署名は、以下のように生成される。
【０５５２】
リスト３０‐リング署名：
１．ｋ＝Ｈ（Ｍ）を計算する。ここで、Ｍは、署名するメッセージであり、Ｈは、ハッシュ関数である。
【０５５３】
２．任意のｖ∈｛０，１｝ｂを選択する。
【０５５４】
３．ｊ≠ｉごとに、
３Ａ．任意の
【数２１３】
0005412626.tif 000214
【０５５５】
を選択する。これは、Ｃ．Ｇｅｎｔｒｙの前述の論文において述べられているように、ランダムに一様に行うことができる。
【０５５６】
３Ｂ．ｙｊ＝ｇｊ（ｘ′ｊ）を計算する。
【０５５７】
４．
【数２１４】
0005412626.tif 000215
【０５５８】
となるように、ｙｉを計算する。
【０５５９】
５．Ｎｉについての秘密知識を用いて、
【数２１５】
0005412626.tif 000216
【０５６０】
となるように、
【数２１６】
0005412626.tif 000217
【０５６１】
を計算する。
【０５６２】
６．全てのｊについて、
【数２１７】
0005412626.tif 000218
【０５６３】
を計算する。リスト１６を参照（ｒ値はランダムなことがあり、異なるｊに対し異なることがある）。
【０５６４】
７．リング署名（ｘ１，…，ｘｚ，ｖ）を出力する。
【０５６５】
リスト３０の終了。
【０５６６】
前述のように（リスト１１）、リング署名者は、等式
【数２１８】
0005412626.tif 000219
【０５６７】
を用いて、ｙｊの値からｙｉを計算することができる（ｊ≠ｉである）。ｙｊのいくつかの値、実際に約４分の３は、モジュラ平方根を持たない。この場合、ｙｊがＮｊを法とする平方剰余となるまでステップ５を再び実行しなければならない。
【０５６８】
リスト３１‐リング署名の検証：
１．ｋ＝Ｈ（Ｍ）を計算する。
【０５６９】
２．全てのｊについて、
【数２１９】
0005412626.tif 000220
【０５７０】
を計算する。
【０５７１】
３．
【数２２０】
0005412626.tif 000221
【０５７２】
であることを確認する。
【０５７３】
リスト３１の終了。
【０５７４】
上述の他の方式におけるように、リスト３０のステップ６Ｂにおけるｒは余剰ビットのソースであり、準順列の呼出しごとにランダムに、又は、準順列の他の入力（例えば、ｘ′ｊ）に、確定的にしかし予測不可能に依存するように選ばれる。また、各署名者は、ｈとｈ′に異なる値を用いることができるが、各署名者のｈとｈ′の値は、リング署名の検証に必要である（従って、ある意味では、公開鍵の一部である）ので、いくつかの実施形態において、全ての署名者は、同じ値を用いる。
【０５７５】
９．他の方式と拡張
本発明のいくつかの実施形態の圧縮及び復元方式は、暗号化、署名、集合署名、及びリング署名以外の暗号のコンテキストで有益である。例えば、本発明の圧縮及び復元方式を利用する閾値暗号化及び復号化は、暗号文のサイズが小さければより効率的になることがある。また、他の署名方式（例えば、Ｆｉａｔ‐Ｓｈａｍｉｒのバージョン、特に、アイデンティティに基づくバージョン）や、他のアイデンティティに基づく暗号化方式（例えばＣｏｃｋの暗号化方式を利用するものなど）において、署名者は短い（アイデンティティに基づく）公開鍵や秘密鍵（後者はＢ要素）を持つことができる。さらに、モジュラ平方数を送信することに基づく識別方式は、本発明を適用することで同様に改良される。Ａ．Ｆｉａｔ及びＡ．Ｓｈａｍｉｒ著、“Ｈｏｗ  ｔｏ  Ｐｒｏｖｅ  Ｙｏｕｒｓｅｌｆ：Ｐｒａｃｔｉｃａｌ  Ｓｏｌｕｔｉｏｎｓ  ｔｏ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｐｒｏｂｌｅｍｓ”ｉｎ  Ｐｒｏｃ．ｏｆ  Ｃｒｙｐｔ  １９８６，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２６３，ｐｐ．１８６−１９４．Ｓｐｒｉｎｇｅｒ，１９８６と、Ｕ．Ｆｅｉｇｅ、Ａ．Ｆｉａｔ及びＡ．Ｓｈａｍｉｒ著、“Ｚｅｒｏ‐Ｋｎｏｗｌｅｄｇｅ  Ｐｒｏｏｆｓ  ｏｆ  Ｉｄｅｎｔｉｔｙ”ｉｎ  Ｊｏｕｒ．ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ（１），ｐｐ．７７‐９４（１９８８）と、Ｃ．Ｃｏｃｋｓ著、Ａｎ  Ｉｄｅｎｔｉｔｙ  Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ  Ｂａｓｅｄ  ｏｎ  Ｑｕａｄｒａｔｉｃ  Ｒｅｓｉｄｕｅｓ”ｉｎ  Ｐｒｏｃ．ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｃｏｄｉｎｇ  ２００１，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２２６０，Ｓｐｒｉｎｇｅｒ（２００１）と、Ａ．Ｍｅｎｅｚｅｓ、Ｐ．ｖａｎ  Ｏｏｒｓｃｈｏｔ及びＳｃｏｔｔ  Ｖａｎｓｔｏｎｅ著、Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，Ｃｈａｐｔｅｒ  １０，ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｍａｔｈ．ｕｗａｔｅｒｌｏｏ．ｃａ／ｈａｃ／で入手可能、を参照されたい。さらに、本発明の圧縮及び復元方式は、セキュリティがモジュラ平方根を計算することに基づく方式に対し、大域的な帯域幅効率を向上する。
【０５７６】
Ｆａｒｅｙの区間に基づく圧縮及び復元方式を用いずに帯域幅縮小方式を実現することもできる。以下、本発明のかかる２つの実施形態、暗号化方式及び署名方式、を説明する。両方とも、ある状況下では、圧縮及び復元に基づく本発明の実施形態よりもさらに大きい帯域幅縮小を享受するものである（しかし、証明可能なセキュリティを失う可能性など、他の望ましい性質を犠牲にするかもしれない）。
【０５７７】
Ｃｏｐｐｅｒｓｍｉｔｈの方式を通常のＲａｂｉｎ署名（リスト７、８）又は通常の低指数ＲＳＡ署名（リスト３及び４）に適用することによって、（おそらく）帯域幅を縮小した署名方式を得ることができる。Ｄ．Ｊ．Ｂｅｒｎｓｔｅｉｎ著、“Ｐｒｏｖｉｎｇ  Ｔｉｇｈｔ  Ｓｅｃｕｒｉｔｙ  ｆｏｒ  Ｓｔａｎｄａｒｄ  Ｒａｂｉｎ‐Ｗｉｌｌｉａｍｓ  Ｓｉｇｎａｔｕｒｅｓ”，ｈｔｔｐ：／／ｃｒ．ｙｐ．ｔｏ／ｄｊｂ．ｈｔｍｌで入手可能、と、Ｄ．Ｂｌｅｉｃｈｅｎｂａｃｈｅｒ著、“Ｃｏｍｐｒｅｓｓｅｄ  Ｒａｂｉｎ  Ｓｉｇｎａｔｕｒｅｓ”ｉｎ  Ｐｒｏｃ．ｏｆ  ＣＴ−ＲＳＡ  ２００４，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２９６４，ｐｐ．１２６−１２８．Ｓｐｒｉｎｇｅｒ，２００４と、Ｄ．Ｃｏｐｐｅｒｓｍｉｔｈ著、“Ｆｉｎｄｉｎｇ  ａ  Ｓｍａｌｌ  Ｒｏｏｔ  ｏｆ  ａ  Ｕｎｉｖａｒｉａｔｅ  Ｍｏｄｕｌａｒ  Ｅｑｕａｔｉｏｎ”ｉｎ  Ｐｒｏｃ．ｏｆ  Ｅｕｒｏｃｒｙｐｔ  １９９６，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐｐ．１５５‐１６５．Ｓｐｒｉｎｇｅｒ‐Ｖｅｒｌａｇ，１９９６、とを参照されたい。例えば、ｅを、Ｎを法とするＲａｂｉｎ又はＲＳＡ署名方式の公開指数とし、ｘを、リスト３又は７におけるように得られる通常の署名とする。Ｃｏｐｐｅｒｓｍｉｔｈの方式では、誰でも（Ｎについてのトラップドア情報を必要とすることなく）、（例えば）、ｘ２(ｍｏｄ  Ｎ)とｘの
【数２２１】
0005412626.tif 000222
【０５７８】
最上位ビットとから、ｘ∈［１，Ｎ］を復元することができる。従って、Ｒａｂｉｎ署名（ｅ＝２）について、図４の方法は以下のように変更することができる。
【０５７９】
リスト３２：
１．ステップ４１０：Ｈ（Ｍ）を計算する。Ｈは、全領域関数、すなわちその値域が［１，Ｎ］である関数（例えばリスト７を参照）であることもあれば、部分領域ハッシュ関数、すなわちその値域が［１，Ｎ］の真部分集合である関数であることもある。
【０５８０】
２．ステップ４２０：ｘ２＝Ｈ（Ｍ）（ｍｏｄ  Ｎ）となるように署名ｘ＝ｓ（Ｍ）を計算する。
【０５８１】
３．ステップ４３０：ｘの
【数２２２】
0005412626.tif 000223
【０５８２】
最上位ビットを送信する。また、Ｈ（Ｍ）かＨ（Ｍ）を復元するのに十分な何らかの情報を送信する。
【０５８３】
リスト３２の終了。
【０５８４】
しかしながら、Ｈ（Ｍ）を復元するのに十分な情報も送信しなければならないので、ｘの最上位ビットだけを送信することによって実現できる圧縮は、少し非現実的である。ステップ４３０で、Ｈ（Ｍ）自体を送信しなければならないならば、この署名方式は、明らかに望ましいメッセージ復元特性を有していない。
【０５８５】
Ｂ２Ｎ，ｈ，ｈ′内の数を見つけるための発見的方法を用いることによって、帯域幅縮小暗号化方式を得ることができる。ここで、ｈ′は
【数２２３】
0005412626.tif 000224
【０５８６】
と同じくらい小さいことがある。しかしながら、発見的抜き出し方式を用いた結果生じる暗号化方式は、証明可能なセキュリティを享受するものではない。発見的に、集合Ｓ＝Ｂ２Ｎ，ｈ，ｈ′により図１０のセキュリティプルーフモデルを用いるために、
【数２２４】
0005412626.tif 000225
【０５８７】
について、Ｂ２Ｎ，ｈ，ｈ′内の数を以下のように生成することができる。
【０５８８】
リスト３３：
１．任意の
【数２２５】
0005412626.tif 000226
【０５８９】
と
【数２２６】
0005412626.tif 000227
【０５９０】
を選択する。
【０５９１】
２．
【数２２７】
0005412626.tif 000228
【０５９２】
を計算する。
【０５９３】
３．ｘ＝ｘ′＋ｂを計算する。
【０５９４】
リスト３３の終了。
【数２２８】
0005412626.tif 000229
【０５９５】
について、
【数２２９】
0005412626.tif 000230
【０５９６】
であることを容易に示すことができる。これらの観測は、以下の暗号化方式につながる。
【０５９７】
リスト３４：
１．メッセージを（ａ，ｂ）にエンコードする。ここで、ａは、メッセージの最初の２εａｌｏｇ２Ｎビットであり、ｂは、残りのビットであり、２εａｌｏｇ２Ｎ，２εｂｌｏｇ２Ｎは、最も近い整数に切り下げている。
【０５９８】
２．リスト３３におけるようにｘを計算する。
【０５９９】
３．暗号文をｃ＝ｘ２（ｍｏｄ  Ｎ）に設定する。
【０６００】
リスト３４の終了。
【数２３０】
0005412626.tif 000231
【０６０１】
の適切なεａ，εｂについて、（ａ，ｂ）を、従ってメッセージを、以下のように復元することができる。
【０６０２】
リスト３５．
１．ｘをｃのモジュラ平方根として計算する。
【０６０３】
２．
【数２３１】
0005412626.tif 000232
【０６０４】
を計算する。
【０６０５】
リスト３５の終了。
【０６０６】
この方式の考えられる１つの不利点は、因数分解から証明可能な縮小を提供するのがおそらく難しいということである。
【０６０７】
多くの暗号化方式及び署名方式におけるように、プロトコルの計算複雑性を増すことによって、帯域幅のさらなる縮小‐小さい定数ｃについて約ｃ  ｌｏｇ  ｌｏｇ  Ｎビット（本明細書中、特に断りのない限り、対数は底２である）‐を実現することができる。例えば、単に最終ｃ  ｌｏｇ  ｌｏｇ  Ｎビットを送信しないことによって、暗号文のサイズをさらに減少することができる。デクリプター（ｄｅｃｒｙｐｔｅｒ）は単に、復号化方式を、必要ならば、
【数２３２】
0005412626.tif 000233
【０６０８】
回まで繰り返すことによって、それらの最終ビットを推測すればよい。同様に、エンクリプター（ｅｎｃｒｙｐｔｅｒ）は、一時的な暗号文が最終的に全て０である最終ｃ  ｌｏｇ  ｌｏｇ  Ｎビットを有するように、一時的暗号ごとに異なる乱数度を用いて、暗号化方式を期待される（ｌｏｇＮ）ｃ回行うことができ、その場合、それらのビットを送信する必要はない。署名及び検証に同様のシナリオが当てはまる。
【０６０９】
１０．システムと構成要素
帯域幅を縮小した暗号化、署名、サインクリプション、集合署名、及びリング署名方式と、圧縮及び復元方式とは、図１のコンピュータシステム１１０及びネットワーク１２０を使用して実現することができる。各システム１１０は、ネットワーク（図示せず）によって相互接続された多数のコンピュータシステムを含む分散システムであってもよいしそうでなくてもよい。各システム１１０は、本発明の方式を実行するための、例えば半導体、磁気、光、又は他の種類の記憶装置などの公知の又は考案したコンピュータ可読媒体（図示せず）に記憶したコンピュータ命令を実行するようにプログラム化した、１つ又は複数の処理装置（図示せず）を含むことがある。さらに、又はその代わりに、各システム１１０は、本発明の方式を実行するためのハードワイヤード回路を含むことがある。ネットワーク１２０はインターネット及び／又は無線通信ネットワークや、任意の種類の通信が送信される他の種類のネットワークであることがある。本発明の方式を実現するコンピュータ命令は、ケーブル、電波、又は他の手段で、物理的信号（例えば電磁信号）に組み込まれて、システム１１０へ又はシステム１１０から送信することができる。信号は、搬送波で変調してもしなくてもよい。
【０６１０】
コンピュータシステム１１０は、本発明の暗号化、署名、サインクリプション、集合署名、又はリング署名の実施形態において用いられる公開鍵に関連する、真正性や所有権や属性を証明するための公開鍵証明書を提供することができる、サーバ証明要素（「証明者」）として使用することがある。証明者は公開鍵を別のシステム１１０に送信することができる。また、証明者１１０は、権限保持者が使用するための公開鍵及び秘密鍵を生成し、それらを圧縮暗号化形式で別のシステム１１０に送信することによって権限保持者に提供することができる。非証明者システム１１０は、証明者システム１１０を通じて、又は直接に、暗号文や署名を互いに送信することができる。暗号文や署名はまた、電子媒体（例えばディスク）で非電子的に（例えば通常のメールによって）転送することができる。
【０６１１】
いくつかの実施形態において得られる付加的な特徴が、Ｃ．Ｇｅｎｔｒｙによる前述の論文、Ｈｏｗ  ｔｏ  Ｃｏｍｐｒｅｓｓ  Ｒａｂｉｎ  Ｃｉｐｈｅｒｔｅｘｔｓ  ａｎｄ  Ｓｉｇｎａｔｕｒｅｓ  （ａｎｄ  Ｍｏｒｅ）に述べられている。
【０６１２】
本発明は、上述の実施形態に限定されるものではない。例えば、上述の方法や、セキュリティプルーフは、集合ＢＮ，ｈ，ｈ′やＢＺＮ，ｈ，ｈ′に拡張することができる。ＢＮ，ｈ，ｈ′はＢ２Ｎ，ｈ，ｈ′からなり、Ｂ２Ｎ，ｈ，ｈ′，ＢＺＮ，ｈ，ｈ′内の数のＮを法とする負数は、１以外のＮに関する公約数を有する数を除くが、Ｎが２つの素数の積であれば、かかる数の集合は非常に小さいことに注意されたい。いくつかの実施形態は集合ＢＮ，Ｑ，Ｂ２Ｎ，Ｑ，ＢＺＮ，Ｑを用い、ここでＱは［ｈ，ｈ′］以外である。特に、Ｑは［ｈ，ｈ′），（ｈ，ｈ′］又は（ｈ，ｈ′）であることがある。また、Ｂ２Ｎ，Ｑはｘ＝０を含まないように、すなわち［ｘ∈［１，Ｎ）：ｘ２（ｍｏｄ  Ｎ）∈Ｑ｝と定義することができる。本発明はセキュリティプルーフが有効である方式に限定されない。上記で、ビットストリングｘ＝ｘ０ｘ１…ｘｎ−１について、それに対応する数がｘ０＋ｘ１＊２＋…＋ｘｎ−１＊２ｎ−１となるように、ビットストリングは数に対応付けられていたが、他の数値表現を用いることもできる。他の実施形態や変更例は、添付の請求項によって定義する本発明の範囲内にある。
【図１】
0005412626.tif 000234
【図２】
0005412626.tif 000235
【図３】
0005412626.tif 000236
【図４】
0005412626.tif 000237
【図５】
0005412626.tif 000238
【図６】
0005412626.tif 000239
【図７】
0005412626.tif 000240
【図８】
0005412626.tif 000241
【図９】
0005412626.tif 000242
【図１０】
0005412626.tif 000243
【図１１】
0005412626.tif 000244
【図１２】
0005412626.tif 000245
【図１３】
0005412626.tif 000246
【図１４】
0005412626.tif 000247
【図１５】
0005412626.tif 000248