(57)【特許請求の範囲】
【請求項１】
『認証されるべき』第１主体（Ａ）を、『認証されている』第２主体（Ｂ）が認証システムを使用して認証するための認証方法であって、
前記認証システムが、前記認証されるべき主体（Ａ）のための送信手段と受領手段と計算手段とを具備しており、さらに、前記認証されている主体（Ｂ）のための受領手段と選択手段と計算手段と送信手段と測定手段と検証手段とを具備しており、
−前記認証されるべき主体（Ａ）が、前記認証されている主体（Ｂ）に対して、ビット数でカウントされるあるサイズを有した少なくとも１つの情報ｃを前記送信手段によって送信し、
−前記認証されている主体（Ｂ）が、前記情報ｃを前記受領手段によって受領し、『質問』と称される数ｅを前記選択手段によってランダムに選択し、該質問ｅを、前記認証されるべき主体（Ａ）に対して前記送信手段によって送信し、
−前記認証されるべき主体（Ａ）が、前記質問ｅを前記受領手段によって受領し、該質問ｅを使用して前記計算手段によって計算操作を行うとともに該計算操作の結果から応答ｙを構成し、該応答ｙを、前記認証されている主体（Ｂ）に対して前記送信手段によって送信し、
−前記認証されている主体（Ｂ）が、前記応答ｙを前記受領手段によって受領し、該応答ｙを使用して前記計算手段によって計算操作を行い、計算操作が、先に受領した前記情報ｃとなるかをチェックするという場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、前記認証に関して、１−２−ｋという安全度レベルが得られ、
この場合、前記認証されている主体（Ｂ）が、前記認証されるべき主体（Ａ）に対して前記送信手段によって送信を行った瞬間から、前記認証されるべき主体（Ａ）から応答を前記受領手段によって受領した瞬間までの、時間Δｔを前記測定手段が測定し、該測定時間Δｔが、所定時間Δｔｍａｘ よりも短いことを前記検証手段が検証し、
前記認証されるべき主体（Ａ）に関する前記計算手段が、前記所定時間（Δｔｍａｘ ）内において２Ｐ という計算能力を有していることにより、前記認証されるべき主体（Ａ）によって使用された前記情報のサイズが、少なくとも（ｋ＋Ｐ）ビットに等しいことを特徴とする認証方法。
【請求項２】
請求項１記載の認証方法において、
前記認証されるべき主体（Ａ）が、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって情報を計算しておくことを特徴とする認証方法。
【請求項３】
請求項１または２記載の認証方法において、
前記数Ｐが１６に等しく、前記数ｋが３２に等しく、
そのため、予備情報のサイズまたは情報のサイズが、少なくとも４８ビットに等しいことを特徴とする認証方法。
【請求項４】
請求項１記載の認証方法において、
前記認証されている主体（Ｂ）によって提起される前記質問ｅが、ｋよりも大きなビット数を有していることを特徴とする認証方法。
【請求項５】
請求項４記載の認証方法において、
前記数ｋが３２であるときには、前記認証されている主体（Ｂ）によって提起される前記質問ｅが、約６４に等しいビット数を有していることを特徴とする認証方法。
【請求項６】
請求項１記載の認証方法において、
前記認証されている主体（Ｂ）が、予備操作において数ｗをランダムに選択して、前記認証されるべき主体（Ａ）に対して前記数ｗを送信し、
前記認証されるべき主体（Ａ）は、前記数ｗを使用して、情報ｃを構成し、
前記認証されている主体（Ｂ）によって提起される前記質問ｅが、ｋに等しいビット数を有し、
前記時間（Δｔ）が、前記認証されている主体（Ｂ）が前記認証されるべき主体（Ａ）に対して前記数ｗの送信を行った瞬間から、前記認証されている主体（Ｂ）が前記認証されるべき主体（Ａ）から応答ｙを受領した瞬間までにわたって、測定されることを特徴とする認証方法。
【請求項７】
請求項６記載の認証方法において、
前記認証されている主体（Ｂ）から前記認証されるべき主体（Ａ）に対して既に提示されている前記数ｗが３２ビットを有し、
前記情報のサイズが、４８ビット以上であり、
前記認証されている主体（Ｂ）によって提起される前記質問ｅのビット数が、３２ビットであることを特徴とする認証方法。
【請求項８】
請求項１〜７のいずれかに記載の認証方法において、
前記認証されるべき主体（Ａ）が、前記情報内にメッセージ（Ｍ）を導入し、
該メッセージ（Ｍ）に対して認証が付与されることを特徴とする認証方法。
【請求項９】
『証明者』をなす第１主体（Ａ）と『認証者』をなす第２主体（Ｂ）との間で認証システムを使用して実施されるメッセージ署名方法であって、
前記認証システムが、前記認証されるべき主体（Ａ）のための送信手段と受領手段と計算手段とを具備しており、さらに、前記認証されている主体（Ｂ）のための受領手段と選択手段と計算手段と送信手段と測定手段と検証手段とを具備しており、
−前記証明者をなす主体（Ａ）が、署名すべきメッセージの関数として数ｅを前記計算手段によって計算し、ｅの関数としての応答と称される数ｙを前記計算手段によって計算し、さらに、前記認証されている主体（Ｂ）に対して前記応答を前記送信手段によって送信し、
−前記認証されている主体（Ｂ）が、前記応答ｙを前記受領手段によって受領し、該応答ｙを使用して前記計算手段によって計算操作を行い、計算操作が、先に受領した前記数ｅとなるかをチェックするという場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、前記署名に関して、１−２−ｋという安全度レベルが得られ、
この場合、
−所定時間（Δｔｍａｘ ）内における前記証明者をなす主体（Ａ）に関する前記計算手段の計算能力が２Ｐ である場合に、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの数ｅを、前記証明者をなす主体（Ａ）が前記計算手段によって計算し、
−予備計算において、前記認証されている主体（Ｂ）が、ランダムに数ｗを前記選択手段によって選択して、この数ｗを前記証明者をなす主体（Ａ）に対して前記送信手段によって送出し、前記証明者をなす主体（Ａ）に関する前記計算手段は、この数ｗを使用して数ｅを構成し、
−前記認証されている主体（Ｂ）が、前記証明者をなす主体（Ａ）に対して前記数ｗを送信を行った瞬間から、前記証明者をなす主体（Ａ）から応答ｙを受領した瞬間までの、時間Δｔを、前記測定手段が測定し、該測定時間Δｔが、所定時間Δｔｍａｘ よりも短いことを前記検証手段によって検証することを特徴とするメッセージ署名方法。
【請求項１０】
請求項９記載のメッセージ署名方法において、
前記証明者をなす主体（Ａ）が、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって数ｅを計算しておくことを特徴とするメッセージ署名方法。
【請求項１１】
請求項９または１０記載のメッセージ署名方法において、
前記数Ｐが１６に等しく、前記数ｋが３２に等しく、
そのため、予備情報のサイズまたは数ｅのサイズが、少なくとも４８ビットに等しいことを特徴とするメッセージ署名方法。
【請求項１２】
『認証されるべき』第１主体（Ａ）を、『認証されている』第２主体（Ｂ）が認証するためのシステムであって、
前記システムが、前記認証されるべき主体（Ａ）のための送信手段と受領手段と計算手段とを具備しており、さらに、前記認証されている主体（Ｂ）のための受領手段と選択手段と計算手段と送信手段と測定手段と検証手段とを具備しており、
−前記認証されるべき主体（Ａ）が、前記認証されている主体（Ｂ）に対して、ビット数でもってサイズがカウントされる少なくとも１つの情報ｃを前記送信手段によって送信し、
−前記認証されている主体（Ｂ）が、前記情報ｃを前記受領手段によって受領し、『質問』と称される数ｅを前記選択手段によってランダムに選択し、該質問ｅを、前記認証されるべき主体（Ａ）に対して前記送信手段によって送信し、
−前記認証されるべき主体（Ａ）が、前記質問ｅを前記受領手段によって受領し、該質問ｅを使用して前記計算手段によって計算操作を行い、該計算操作の結果から応答ｙを構成し、該応答ｙを、前記認証されている主体（Ｂ）に対して前記送信手段によって送信し、
−前記認証されている主体（Ｂ）が、前記応答ｙを前記受領手段によって受領し、該応答ｙを使用して前記計算手段によって計算操作を行い、計算操作が、先に受領した前記情報ｃとなるかをチェックする場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、前記認証に関して、１−２−ｋという安全度レベルが得られ、
この場合、前記認証されている主体（Ｂ）が、前記認証されるべき主体（Ａ）に対して送信を行った瞬間から、前記認証されるべき主体（Ａ）から応答を受領した瞬間までの、時間Δｔを前記測定手段によって測定し、該測定時間Δｔが、所定時間Δｔｍａｘ よりも短いことを前記検証手段によって検証し、
前記認証されるべき主体（Ａ）が、前記所定時間（Δｔｍａｘ ）内において２Ｐ という計算能力を有していることにより、前記認証されるべき主体（Ａ）によって使用された前記情報のサイズが、少なくとも（ｋ＋Ｐ）ビットに等しいことを特徴とするシステム。
【請求項１３】
請求項１２記載のシステムにおいて、
前記認証されるべき主体（Ａ）が、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって情報を前記計算手段によって計算することを特徴とするシステム。
【請求項１４】
請求項１２または１３記載のシステムにおいて、
前記数Ｐが１６に等しく、前記数ｋが３２に等しく、
そのため、予備情報のサイズまたは情報のサイズが、少なくとも４８ビットに等しいことを特徴とするシステム。
【請求項１５】
請求項１２記載のシステムにおいて、
前記認証されている主体（Ｂ）によって提起される前記質問ｅが、ｋよりも大きなビット数を有していることを特徴とするシステム。
【請求項１６】
請求項１５記載のシステムにおいて、
前記数ｋが３２であるときには、前記認証されている主体（Ｂ）によって提起される前記質問ｅが、約６４に等しいビット数を有していることを特徴とするシステム。
【請求項１７】
請求項１２記載のシステムにおいて、
前記認証されている主体（Ｂ）が、予備操作において数ｗをランダムに前記選択手段によって選択し、前記認証されるべき主体（Ａ）に対して前記数ｗを前記送信手段によって送信し、
前記認証されるべき主体（Ａ）は、前記数ｗを使用して、情報ｃを構成し、
前記認証されている主体（Ｂ）によって提起される前記質問ｅが、ｋに等しいビット数を有し、
前記認証されている主体（Ｂ）が、前記認証されている主体（Ｂ）が前記認証されるべき主体（Ａ）に対して前記数ｗの送信を行った瞬間から、前記認証されている主体（Ｂ）が前記認証されるべき主体（Ａ）から応答ｙを受領した瞬間までの、前記時間（Δｔ）を前記測定手段によって測定することを特徴とするシステム。
【請求項１８】
請求項１７記載のシステムにおいて、
前記認証されている主体（Ｂ）から前記認証されるべき主体（Ａ）に対して既に提示されている前記数ｗが３２ビットを有し、
前記情報のサイズが、４８ビット以上であり、
前記認証されている主体（Ｂ）によって提起される前記質問ｅのビット数が、３２ビットであることを特徴とするシステム。
【請求項１９】
請求項１２記載のシステムにおいて、
前記認証されるべき主体（Ａ）が、前記情報内にメッセージ（Ｍ）を導入し、
該メッセージ（Ｍ）に対して認証が付与されることを特徴とするシステム。
【請求項２０】
『証明者』をなす第１主体（Ａ）と『認証者』をなす第２主体（Ｂ）との間で実施されるシステムであって、
前記システムが、前記認証されるべき主体（Ａ）のための送信手段と受領手段と計算手段とを具備しており、さらに、前記認証されている主体（Ｂ）のための受領手段と選択手段と計算手段と送信手段と測定手段と検証手段とを具備しており、
−前記証明者をなす主体（Ａ）が、署名すべきメッセージの関数として数ｅを前記計算手段によって計算し、応答と称される数ｙを前記計算手段によって計算し、さらに、前記『認証者』をなす主体（Ｂ）に対して前記応答を前記送信手段によって送信し、
−前記『認証者』をなす主体（Ｂ）が、前記応答ｙを前記受領手段によって受領し、該応答ｙを使用して前記計算手段によって計算操作を行い、計算操作が、先に受領した前記数ｅとなるかをチェックする場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、前記署名に関して、１−２−ｋという安全度レベルが得られ、
この場合、
−所定時間（Δｔｍａｘ ）内における前記証明者をなす主体（Ａ）の計算能力が２Ｐ である場合に、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの数ｅを、前記証明者をなす主体（Ａ）が、前記計算手段によって計算し、
−予備計算において、前記『認証者』をなす主体（Ｂ）が、ランダムに数ｗを前記選択手段によって選択し、この数ｗを前記証明者をなす主体（Ａ）に対して前記送信手段によって送出し、前記証明者をなす主体（Ａ）は、この数ｗを使用して数ｅを構成し、
−前記『認証者』をなす主体（Ｂ）が、前記証明者をなす主体（Ａ）に対して前記数ｗを送信を行った瞬間から、前記証明者をなす主体（Ａ）から応答ｙを受領した瞬間までの、時間Δｔを前記測定手段によって測定し、該測定時間Δｔが、所定時間Δｔｍａｘ よりも短いことを前記検証手段によって検証することを特徴とするシステム。
【請求項２１】
請求項２０記載のシステムにおいて、
前記証明者をなす主体（Ａ）が、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって数ｅを前記計算手段によって計算することを特徴とするシステム。
【請求項２２】
請求項２０または２１記載のシステムにおいて、
前記数Ｐが１６に等しく、前記数ｋが３２に等しく、
そのため、予備情報のサイズまたは数ｅのサイズが、少なくとも４８ビットに等しいことを特徴とするシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、小さなサイズの情報内容を使用したメッセージの認証および署名、ならびに、そのためのシステムに関するものである。
【０００２】
本発明は、識別すなわち主体認証の技術分野に関するものであり、また、暗号技術を使用したメッセージの認証およびデジタルメッセージ署名の分野に関するものである。
【０００３】
より詳細には、本発明は、一般キー暗号として公知の暗号に関するものである。この分野においては、認証されるべき主体は、個人的キーと、関連する一般のキーと、を有している。認証を行うためには、認証主体は、一般キーが必要であるだけである。
【０００４】
さらに詳細に説明すれば、本発明は、ゼロ知識として公知の認証方法に関するものである。これは、証明されているように科学世界が完全に正当であるものとして理解するという仮定に従って、認証されるべき主体の個人的キーを明らかにしないようなプロトコルに従って認証が行われることを意味している。
【０００５】
本発明は、主体やメッセージや署名メッセージを認識する必要があるようなすべてのシステムにおいて、特に、伝送されるおよび／または格納されるビット数が重要パラメータを構成するようなシステムにおいて、応用することができる。これは、特に、暗号計算を促進するための数学的コプロセッサ（多くの場合、暗号コプロセッサと称される）を備えていないような、標準的なまたは安価なマイクロ回路の場合である。
【０００６】
本発明の典型的な応用は、コストの理由のためにあるいは技術的な理由のために（例えば、非接触インターフェースの利用）あるいは双方の理由のために暗号コプロセッサを排除しつつも非常に高レベルの安全性が要求されるような、電子口座への応用である。
【０００７】
他の可能な応用は、電子口座よりもずっと安価であるような、次世代のテレホンカードである。
【０００８】
【従来の技術】
多くのゼロ知識認識プロトコルが公知である。それらの中でも、以下の４つのプロトコルを引用する。
【０００９】
１）Fiat-Shamir プロトコル。原典は、A. Fiat and A. Shamir,“Howe to
prove yourself: Practical solutions to identification and signature
problems”, published in Advances in Cryptology; Proceedings of Crypto
'86, Lecture Notes in Computer Science, vol. 263, Springer-Verlag,
Berlin, 1987, pp. 186-194 である。
【００１０】
２）Guillou-Quisquater プロトコル。原典は、L.C. Guillou and J.J.
Quisquater,“A practical zero-knowledge protocol fitted to security
microprocessors minimizing both transmission and memory”, published inAdvances in Cryptology: Proceedings of Eurocrypto '88, Lecture Notes in Computer Science, vol. 330, Springer-Verlag, Berlin, 1988, pp. 123-128 である。
【００１１】
３）Schnorr プロトコル。原典は、C.P. Schnorr,“Efficient identification and signatures for smart cards”, published in Advances in Cryptology: Proceedings of Crypto '89, Lecture Notes in Computer Science, vol. 435,Springer-Verlag, Berlin, 1987, pp. 239-252 である。
【００１２】
４）Girault プロトコル。原典は、仏国特許出願公開明細書第２ ７１６ ０５８号。
【００１３】
一般に、多くのゼロ知識認証プロトコルは、４ステージでもって行われる。簡単化のために、Ｂと称される認証主体が、Ａと称される、認証されるべき主体に関して特徴的なすべての一般パラメータを既に知っているものと仮定する。換言すれば、Ａの認識や一般キー等を既に知っているものと仮定する。
【００１４】
［第１ステージ］
Ａは、Ｂに対して、Ａによってランダムに選択されたパラメータｘ、または、パラメータｘの擬似ランダム関数ｈ、のいずれかからなる少なくとも１つの情報ｃを与える。必要であれば、認証されるべきまたは署名されるべきメッセージを与える。ここで、ｃ＝ｈ（ｘ，［Ｍ］）である（記号［Ｍ］は、Ｍが付加的なものであることを表している）。
【００１５】
［第２ステージ］
Ｂは、『質問』と称されるパラメータｅをランダムに選択し、Ａに対して送信する。
【００１６】
［第３ステージ］
Ａは、Ｂに対して、質問ｅと情報ｃとＡの一般キーｖとに一致した応答ｙを与える。
【００１７】
［第４ステージ］
Ｂは、要素ｙ，ｅ，ｖからｘを計算する、すなわち、ｘ＝φ（ｙ，ｅ，ｖ）を計算する。そして、ｃ＝ｈ（φ（ｙ，ｅ，ｖ），［Ｍ］）をチェックする。
【００１８】
ある種のプロトコルにおいては、１つか２つの付加的なＡとＢとの間の交換が存在する。メッセージ署名に関しては、２つの初期交換が除去され、パラメータｅが、ｃと同じであるように選択される。引き続いて、ｃ，ｅ（ｃに等しい），ｙだけが計算される。
【００１９】
Ｂによって選択し得る質問の数ｕは、詐称者（すなわち、Ａであるふりをして不正な試みを行おうとする主体Ｃ）の成功確率が依存するプロトコルの安全度レベルに直接的に関連している。ｐと称される安全度レベルは、関係式ｐ＝１−２-kを満たすパラメータｋによって特徴づけられる。換言すれば、詐称者は、うまく詐称を行うには２k において唯一の機会しか有していない。プロトコルが困難な数学的課題をベースとしておりかつ情報が十分な長さを有している場合には、ｕの長さは、ｋビットに等しくなければならないことがわかっている。換言すれば、質問は、組｛０，…，２k −１｝（リミッタを含む）から選択されなければならない。
【００２０】
従来技術においては、ｋは、３２ビットに等しい。このため、詐称が成功する確率は、４０億分の１しかない。認識の失敗が例えば実行といったような非常にダメージのある結果を有する場合には、長さは、数ビットへと低減することができる。
【００２１】
上記のいずれのプロトコルにおいても、例えば上述のような高要求応用における基本バージョンにおいて実施することができない。なぜなら、必要とされる計算操作を、暗号コプロセッサを備えていないＩＣカードでは実行することができないからである。
【００２２】
Fiat氏およびShamir氏によって導入された第１の最適化は、２つの主体間にわたって交換されるビット数に関するものである。この最適化においては、情報の計算操作においてハッシュ（hash）関数を使用する。最適化自身は、認証主体によって行われる計算操作の数を低減させない。というのは、最適化によって計算されるべき情報が継続するからである。
【００２３】
計算操作の数を低減するために、予備計算モードと称される特別の計算を使用しなければならない。予備計算においては、情報の計算操作内に含まれている、予備情報と称されるパラメータを前もって計算する。情報は、また、大容量の起算能力を有したサーバーによって計算し、その後、認証されるべき主体のＩＣカード内に格納することもできる。電子的処理が実際に行われたときには、ＩＣカードは、基本計算操作を実行したに過ぎない。この操作手順は、上述の仏国特許出願公開明細書第２ ７１６ ０５８号に開示されている。各予備情報は、１つの処理のためだけに使用される。すべての予備情報がＩＣカードによって使用され尽くしたときには、新たな情報を計算して、それらをＩＣカード内に格納する必要がある（再充電操作）。
【００２４】
安価なＩＣカードのデータメモリがめったに８キロバイトを超えることがないことにより、予備情報だけを格納するのに１キロバイト以上を使用することは、困難である。したがって、２つの再充電間における処理の最大数を実行するためには、予備情報のサイズを低減する必要がある。
【００２５】
これらすべての認証方法においては、計算操作能力とは、実施手段が実用的な時間内で実行し得る計算操作の最大数であると定義することができる。計算操作が２進法であることにより、計算能力は、例えば２N といったように２の累乗で表現することができる。ここで、Ｎは、整数である。数は、大いなる正確さでもって決定されるのではなく、数個のユニット内に対して決定される。例えば、ここでの整数Ｎが、約８０の程度である場合には、換言すれば、能力が２80である手段の場合には、実用的な時間内において、最大約２80回の操作をを行うことができる。
【００２６】
上述の仏国特許出願公開明細書第２ ７１６ ０５８号に開示されている方法における基本バージョンにおいては、予備情報のサイズまたは情報自体のサイズは、約２Ｎビットであり、Ｎは、約８０である。したがって、予備情報のサイズは、約１６０ビットである（上記文献においてＮが６４であれば、１２８ビットとなる）。したがって、５０個の情報を、１キロバイトメモリ内に格納することができる。これは、比較的小さなものである。
【００２７】
他の仏国特許出願公開明細書第２ ７５２ １２２号においては、伝送または格納すべきビット数を低減させる認証方法が開示されている。予備情報または情報のサイズは、Ｎビット付近にまで低減することができる。すなわち、Ｎ＝８０であれば、約８８にまで低減することができる。このことは、１キロバイトのメモリ内に９０個以上の予備情報を格納することを可能とすると共に、プロトコルが実行されたときに伝送されるビット数を１８％にまで低減することを可能とする。
【００２８】
【発明が解決しようとする課題】
うまくないことに、この利点は、多くの応用において不十分なままである。特に電子口座への応用において不十分なままである。多くの処理は、例えば大衆移動やパーキングメータや局所的遠隔通信等においては、非常に少量でしかなく、使用者は、他の考慮によって制限されることなくクレジットが終わるまで処理を行うことができる。この観点から、最小でも１５０〜２００回の処理が、再充電することなく必要であるように思われる。公知の方法では、これを行うことができない。
【００２９】
本発明の目的は、予備情報のサイズを正確にさらに低減することであり、付加的には、情報自身のサイズを正確にさらに低減することである。本発明においては、ビット数は、約４８にまで低減することができ、これにより、１キロバイトメモリ内に１７０個の予備情報を格納することができる。ある種の応用においては、サイズを、さらに小さくすることができ、例えば、３２ビットにまで低減することができて、２５６個の予備情報を格納することができる。
【００３０】
したがって、本発明は、例えば電子口座や次世代テレホンカードといったような応用に関して、安価なＩＣカードにおいてメッセージのまたはメッセージの署名の識別すなわち認証のアルゴリズムを迅速に実行することができる。
【００３１】
【課題を解決するための手段】
本発明は、以下の知見をベースとしている。低減された計算手段を使用して詐称者が短時間で計算操作を行おうとしたときには、計算容量が大幅に低減する（典型的には、２80ではなくて２16）。
【００３２】
上記知見に基づき、本発明は、認証されている主体に対して、認証されるべき主体が応答するのに要する時間Δｔを測定すること、さらに、そのような応答時間を最大値Δmax へと制限すること、を提案する。
【００３３】
Δｔmax という時間内においては、実施手段は、２P （上記議論による）に等しい計算能力を有している。２P という数は、計算操作を行う時間が制限されていることにより、２N という数よりは、明らかに小さい。したがって、本発明は、予備情報のサイズまたは情報のサイズとして、ｋ＋Ｐ以上であり、かつ、ｋ＋Ｎよりは小さい数を提案する。典型的には、Ｐは、１６とすることができ、この場合、ｋ＝３２であれば、予備情報のサイズまたは情報のサイズは、３２＋１６、すなわち、４８ビットとなり、（上記２つの特許文献における１２８ビットや８８ビットよりも）少し小さくなる。
【００３４】
したがって、２つの選択肢が可能である。
【００３５】
−第１選択肢においては、従来技術におけるサイズがｋビットであった質問ｅが拡張され、典型的には、６４ビットというサイズとされる。
【００３６】
−第２選択肢においては、プロトコルに対して予備交換が付加される。その際、Ｂは、Ａに対して、ランダム数ｗ（典型的には、３２ビット）を送信する。数ｗは、情報ｃ：ｃ＝ｈ（α，ｗ，［Ｍ］）を計算するために使用される付加的なパラメータを構成する。測定されるべき時間Δｔは、予備交換の送信とパラメータｅおよびｙの受領との間の時間である。提示された質問ｅは、ｋビットというサイズを維持する。
【００３７】
第２選択肢は、メッセージの署名に関して使用しなければならない。第２選択肢の利点は、質問ｅのサイズが、減らないことである。しかしながら、ある種のプロトコルにおいては（特に、Fiat-Shamir や Guillou-Quisquater）、 応答ｙの計算時間が、ｅの長さに大いに依存し、一方、情報ｃの計算時間は、ｗの長さにほとんど依存しない。したがって、これらプロトコルにおいては、第２選択肢は、プロトコルを実行するのに要する時間を大幅に増加させることなく、情報のサイズを低減させる。さらに、第２選択肢だけが、メッセージの署名に関して利用可能である。なぜなら。厳格に言えば、もはや質問が存在しないからである。
【００３８】
本発明のプロトコルの安全度レベル、すなわち、詐称者の最小検出確率は、公知のプロトコルと同じである（１−２-k）。一方、予備情報または情報の長さは、ほぼ４分割されている。等価な安全度レベルは、以下によって証明される。つまり、Ｃを、Ａを装った詐称者とする（あるいは、Ａから発せられたメッセージＭを装ったメッセージとする）。明らかに、Ｃは、Ａの個人的キーを知らない。Ｃは、推測による詐欺、リアルタイム詐欺（実行時に行われる）、および、後での詐欺（実行後に行われる）という３つの主要な戦略を実施するくらいのことしかできない。これら戦略は、組み合わせることができる。
【００３９】
ａ）推測による詐欺
−第１選択肢
Ｃは、ランダムに選択することによって質問ｅの値を推測し、応答ｙをランダムに選択し、ｃ＝ｈ（φ（ｖ，ｅ，ｙ），［Ｍ］）を計算し、その後、そのｃの値でもって実行を開始する。Ｃは、推測したｅの値が正しかった場合にしか成功しない。よって、確率は、２-64である。
【００４０】
−第２選択肢
Ｃは、ランダムに選択することによって質問ｅの値を推測し、応答ｙをランダムに選択し、ｃ＝ｈ（φ（ｖ，ｅ，ｙ），ｗ，［Ｍ］）を計算する。これは、ｗが既知となってしか可能ではない。すなわち、実行時にしか可能ではない。Ｃは、その後、そのｃの値でもって実行を開始する。Ｃは、推測したｅの値が正しかった場合にしか成功しない。よって、確率は、２-64である。
【００４１】
ｂ）リアルタイム詐欺
ｃの値がランダムに送信され、ｅの値が受領されたときには、Ｃは、ｃ＝ｈ（φ（ｖ，ｅ，ｙ），［Ｍ］）という検証式を満たすようなｙの値を徹底的に探そうとする。Ｃは、最大で２P 回の試みを行うことができること、および、ｃとして可能な値の数が２k+P 個であることにより、成功確率は、１／２k である。
【００４２】
ｃ）後での詐欺
−第１選択肢
Ｃは、ｙおよびｅの様々な値をベースとして大量のｃの値を計算する。Ｃが最大で２N 回計算できることにより、各ｃのそれぞれ可能な値に対して、ｙおよびｅの２N-P-k 個の適合値が存在する。Ｃは、ランダムにある１つの値を選択し、ｙおよびｅの適合値を格納する。そして、プロトコルを開始する。ｅの可能な値として２N-P 個が存在することにより、Ｃが、Ｂから受領した値を格納する確率は、１／２k である。
【００４３】
−第２選択肢
計算操作は、基本的には、第１選択肢の場合と同じである、それは、２つのランダム数ｗおよびｅの合計サイズが、第２選択肢におけるｅのサイズと同じであるからである。
【００４４】
より詳細には、本発明の目的は、『認証されるべき』第１主体（Ａ）を、『認証されている』第２主体（Ｂ）が認証するための認証方法であって、
−認証されるべき主体（Ａ）が、認証されている主体（Ｂ）に対して、ビット数でカウントされるあるサイズを有した少なくとも１つの情報ｃを送信し、
−認証されている主体（Ｂ）が、情報ｃを受領し、『質問』と称される数ｅをランダムに選択し、この質問ｅを、認証されるべき主体（Ａ）に対して送信し、
−認証されるべき主体（Ａ）が、質問ｅを受領し、質問ｅを使用して計算操作を行い、計算操作の結果から応答ｙを構成し、応答ｙを、認証されている主体（Ｂ）に対して送信し、
−認証されている主体（Ｂ）が、応答ｙを受領し、応答ｙを使用して計算操作を行い、計算操作が、先に受領した前記情報ｃとなるかをチェックするという場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、認証に関して、１−２-kという安全度レベルが得られ、
この場合、認証されている主体（Ｂ）が、認証されるべき主体（Ａ）に対して送信を行った瞬間から、認証されるべき主体（Ａ）から応答を受領した瞬間までの、時間Δｔを測定し、測定時間Δｔが、所定時間Δｔmax よりも短いことを検証し、
認証されるべき主体（Ａ）が、所定時間（Δｔmax ）内において２P という計算能力を有していることにより、認証されるべき主体（Ａ）によって使用された前記情報のサイズが、少なくとも（ｋ＋Ｐ）ビットに等しいことを特徴とする認証方法である。
【００４５】
この場合、サイズは、（ｋ＋Ｐ）ビットに等しくても、あるいは、これよりも大きくても良いことは、理解されるであろう。
【００４６】
ある特定の実施モードにおいては、認証されるべき主体（Ａ）は、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって情報を計算しておく。しかしながら、認証されるべき主体は、数をランダムに選択し、その数から計算することによって、情報を計算することができる。
【００４７】
他の実施形態においては、認証されている主体（Ｂ）が、予備操作において数ｗをランダムに選択して、認証されるべき主体（Ａ）に対して数ｗを送信し、認証されるべき主体（Ａ）は、数ｗを使用して、情報ｃを構成し、認証されている主体（Ｂ）によって提起される質問ｅが、ｋに等しいビット数を有し、時間が、認証されている主体（Ｂ）が認証されるべき主体（Ａ）に対して数ｗの送信を行った瞬間から、認証されている主体（Ｂ）が認証されるべき主体（Ａ）から応答ｙを受領した瞬間までにわたって、測定される。
【００４８】
本発明の他の目的は、『証明者』をなす第１主体（Ａ）と『認証者』をなす第２主体（Ｂ）との間で実施されるメッセージ署名方法であって、
−証明者をなす主体（Ａ）が、署名すべきメッセージに応じて数ｅを計算し、ｅの関数としての応答と称される数ｙを計算し、さらに、認証されている主体（Ｂ）に対して応答を送信し、
−認証されている主体（Ｂ）が、応答ｙを受領し、応答ｙを使用して計算操作を行い、計算操作が、先に受領した数ｅとなるかをチェックするという場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、署名に関して、１−２-kという安全度レベルが得られ、
この場合、
−所定時間（Δｔmax ）内における証明者をなす主体（Ａ）の計算能力が２P である場合に、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの数ｅを、証明者をなす主体（Ａ）が計算し、
−予備計算において、認証されている主体（Ｂ）が、ランダムに数ｗを選択して、この数ｗを証明者をなす主体（Ａ）に対して送出し、証明者をなす主体（Ａ）は、この数ｗを使用して数ｅを構成し、
−認証されている主体（Ｂ）が、証明者をなす主体（Ａ）に対して数ｗを送信を行った瞬間から、証明者をなす主体（Ａ）から応答ｙを受領した瞬間までの、時間Δｔを測定し、測定時間Δｔが、所定時間Δｔmax よりも短いことを検証することを特徴とするメッセージ署名方法である。
【００４９】
この場合においても、証明者をなす主体（Ａ）は、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって数ｅを計算しておく。
【００５０】
本発明は、また、『認証されるべき』第１主体（Ａ）を、『認証されている』第２主体（Ｂ）が認証するためのシステムに関するものであって、
−認証されるべき主体（Ａ）が、認証されている主体（Ｂ）に対して、ビット数でもってサイズがカウントされる少なくとも１つの情報ｃを送信するための手段を有し、
−認証されている主体（Ｂ）が、前記情報ｃを受領するための手段と、『質問』と称される数ｅをランダムに選択するための手段と、質問ｅを、認証されるべき主体（Ａ）に対して送信するための手段と、を有し、
−認証されるべき主体（Ａ）が、質問ｅを受領するための手段と、質問ｅを使用して計算操作を行い、計算操作の結果から応答ｙを構成するための手段と、応答ｙを、認証されている主体（Ｂ）に対して送信するための手段と、を有し、
−認証されている主体（Ｂ）が、応答ｙを受領するための手段と、応答ｙを使用して計算操作を行うための手段と、計算操作が、先に受領した情報ｃとなるかをチェックするための手段と、を有する場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、認証に関して、１−２-kという安全度レベルが得られ、
この場合、認証されている主体（Ｂ）が、認証されるべき主体（Ａ）に対して送信を行った瞬間から、認証されるべき主体（Ａ）から応答を受領した瞬間までの、時間Δｔを測定するための手段と、測定時間Δｔが、所定時間Δｔmax よりも短いことを検証するための手段と、を有し、
認証されるべき主体（Ａ）が、所定時間（Δｔmax ）内において２P という計算能力を有していることにより、認証されるべき主体（Ａ）によって使用された情報のサイズが、少なくとも（ｋ＋Ｐ）ビットに等しいことを特徴とするシステムに関するものである。
【００５１】
ある実施形態においては、認証されるべき主体（Ａ）は、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの予備情報に基づいて前もって情報を計算するための手段を有している。
【００５２】
数Ｐが１６に等しく、数ｋが３２に等しく、そのため、予備情報のサイズまたは数ｅのサイズが、少なくとも４８ビットに等しい。
【００５３】
認証されている主体（Ｂ）によって提起される質問ｅは、ｋよりも大きなビット数を有することができる。
【００５４】
認証されている主体は、予備操作において数ｗをランダムに選択するための手段と、認証されるべき主体（Ａ）に対して前記数ｗを送信するための手段と、を有し、認証されるべき主体（Ａ）は、数ｗを使用して、情報ｃを構成するための手段を有し、認証されている主体（Ｂ）によって提起される質問ｅが、ｋに等しいビット数を有し、認証されている主体（Ｂ）が認証されるべき主体（Ａ）に対して数ｗの送信を行った瞬間から、認証されている主体（Ｂ）が認証されるべき主体（Ａ）から応答ｙを受領した瞬間までの、時間（Δｔ）を測定するための手段を、認証されている主体（Ｂ）が有している。
【００５５】
本発明の他の目的は、『証明者』をなす第１主体（Ａ）と『認証者』をなす第２主体（Ｂ）との間で実施されるシステムであって、
−証明者をなす主体（Ａ）が、署名すべきメッセージの関数として数ｅを計算するための手段と、応答と称される数ｙを計算するための手段と、さらに、認証されている主体（Ｂ）に対して応答を送信するための手段と、を有し、
−認証されている主体（Ｂ）が、応答ｙを受領するための手段と、応答ｙを使用して計算操作を行うための手段と、計算操作が、先に受領した数ｅとなるかをチェックするための手段と、を有する場合において、
ｋが、要求される安全度レベルに応じて決定された整数である場合には、前記署名に関して、１−２-kという安全度レベルが得られ、
この場合、
−所定時間（Δｔmax ）内における証明者をなす主体（Ａ）の計算能力が２P である場合に、少なくとも（ｋ＋Ｐ）ビットに等しいサイズの数ｅを、証明者をなす主体（Ａ）が、計算するための手段を有し、
−予備計算において、認証されている主体（Ｂ）が、ランダムに数ｗを選択するための手段と、この数ｗを証明者をなす主体（Ａ）に対して送出するための手段と、を有し、証明者をなす主体（Ａ）は、この数ｗを使用して数ｅを構成するための手段を有し、
−認証されている主体（Ｂ）が、証明者をなす主体（Ａ）に対して数ｗを送信を行った瞬間から、証明者をなす主体（Ａ）から応答ｙを受領した瞬間までの、時間Δｔを測定するための手段と、測定時間Δｔが、所定時間Δｔmax よりも短いことを検証するための手段と、を有していることを特徴とするシステムである。
【００５６】
証明者をなす主体（Ａ）は、少なくとも（ｋ＋Ｐ）ビット以上のサイズの予備情報に基づいて前もって数ｅを計算するための手段を有している。
【００５７】
数Ｐが１６に等しく、数ｋが３２に等しく、そのため、予備情報のサイズまたは数ｅのサイズは、少なくとも４８ビットに等しい。
【００５８】
【発明の実施の形態】
以下の説明においては、本発明を、上記仏国特許出願公開明細書第２ ７１６ ０５８号に開示されているような、特に第３ステージの操作において、モジュール乗算を除去する技術に適用することを仮定する。したがって、予備計算モードが使用されたときにＩＣカード内でこのタイプの操作を行う必要がない。自明なように、この例は、本発明の範囲を制限するものではなく、本発明は、モジュール乗算プロトコルにおいても使用することができる。
【００５９】
上記応用におけるプロトコルは、離散対数の計算の困難さをベースとしている。一般的パラメータ、すなわち、すべての使用者によって共有されるパラメータは、以下のようなものである。
−大きな複合数ｎ，
−整数α（ベース），
−４つのパラメータｔ，ｋ，ｕ，ｚ、ここで、ｋは、安全度パラメータである。
【００６０】
ｎの推奨長さは、少なくとも５１２ビットである。しかしながら、７６８ビット以上が好ましい。典型的な安全度パラメータｋは、３２である。パラメータｕは、可能な質問数である。したがって、ｕ＝２k である。ｔの長さの典型的な値は、１６０ビットである。ｚの長さの典型的な値は、６４ビットである。
【００６１】
使用者の個人的キーは、ｔよりも小さな整数ｓである。一般的キーは、ｖ＝α-s（ｎの剰余）である。
【００６２】
先の出願において開示された基本的認証プロトコルは、次のようなものである。
１．Ａが、｛０  …  ｔｕｚ−１｝の中からランダムに整数ｒを選択し、ｘ＝α（ｎの剰余）を計算し、Ｂに対してｃを送信する。
２．Ｂが、｛０  …  ２k −１｝の中からランダムに要素ｅを選択し、Ａに対してｅを送信する。
３．Ａが、ｙ＝ｒ＝ｓｅを計算し、Ｂに対してｙを送信する。
４．Ｂが、ｘ＝αyｙe（ｎの剰余）をチェックする。
【００６３】
ｓを知らないはずである詐称者が、整数ｙと要素ｅとを選択し第４ステージにおいてｘを計算することによって、２-kという確率で認証者をだますことができることに注意されたい。証明されているように、離散的対数という課題が困難であるにしても、確率を大幅に改良することはできず、そのため、安全度レベルは、１−２-kである。
【００６４】
Fiat氏およびShamir氏によって提案されているように、伝送されるビット数を低減するために、ｈを擬似ランダム関数として、ｃ＝ｈ（ｘ）を、情報として使用することができる。この場合、第４ステージにおける検証式は、ｃ＝ｈ（αy ｖe（ｎの剰余））となる。
【００６５】
さらに、メッセージＭを認証する必要がある場合には、Ｍは、情報ｃ＝ｈ（ｘ，Ｍ）という計算中に含有されている。
【００６６】
安全度レベルを１−２k に維持するためには、他のすべてのパラメータを不変としたときに、ｃの長さが少なくとも１６０ビットである必要がある。
【００６７】
上記特許文献を残余として引用することにより、本発明によるプロトコルは、第１選択肢を使用するバージョンによって説明することができる。Ｎ＝８０であり、Ｐ＝１６であり、予備情報の長さおよび情報の長さが、共に、最小値にまですなわち４８ビットにまで低減されている。この低減は、ｅの長さを６４ビットに増やすことによって補償される。さらに、第４ステージにおいて、Ｂは、Ａが使用した時間をチェックする。したがって、改良されたプロトコルの安全度レベルは、１−２-kのままである。本発明による方法における各ステージは以下の通りである。
１．Ａが、｛０  …  ｔｕｚ−１｝の中からランダムに整数ｒを選択し、ｘ＝αr （ｎの剰余）を計算し、そして可能であれば、｛０  …  ２48−１｝に属するｃ’＝ｆ（ｘ）を計算し、｛０  …  ２48−１｝に属するｃ＝ｈ（ｘ，ｗ，［Ｍ］）またはｃ＝ｈ（ｘ’，ｗ，［Ｍ］）を計算し、Ｂに対してｃを送信する。
２．Ｂが、｛０  …  ２64−１｝の中からランダムに要素ｅを選択し、Ａに対してｅを送信する。
３．Ａが、ｙ＝ｒ＋ｓｅを計算し、Ｂに対してｙを送信する。
４．Ｂが、ｃ＝ｈ（αyｖe（ｎの剰余），［Ｍ］）またはｃ＝ｈ（ｆ（αyｖe（ｎの剰余），［Ｍ］）をチェックし、第２ステージにおける送信から第３ステージにおける受領までの時間が１〜２秒間よりも短いことをチェックする。
【００６８】
本発明は、このタイプの基本的プロトコルに対して特に好適である。なぜなら、主要な一般的パラメータを変化させないからである。すなわち、ｎや、αや、使用者の個人的キーや一般的キー等の他の個人的パラメータを変化させないからである。他方、ｅの拡張を示唆する。というのは、ｕが２54に等しく、もはや第２選択肢が採用されないからである。
【００６９】
さらに重要なことに、本発明は、また、予備計算モードにおいて、特に有効である。なぜなら、予備情報のサイズが、４８ビットに低減されているからである。それでもなお、予備情報だけでなく、ｒの適合値までもが、前もって格納されていなければならないことは、明らかである。しかしながら、上述の仏国特許出願公開明細書第２ ７１６ ０５８号に開示されているように、Ａの安全デバイス内に含有されている擬似ランダム発生器を使用して数を発生させることによって、これを避けることができる。
【００７０】
第２選択肢が選択された場合には、本発明による方法においては、第０ステージと称される付加的な準備ステージを行う。本発明による方法は以下のようなものとなる。
０．Ｂが、｛０  …  ２32−１｝の中からランダム数ｗを選択し、Ａに対してｗを送信する。
１．Ａが、｛０  …  ｔｕｚ−１｝の中からランダムに整数ｒを選択し、ｘ＝αr （ｎの剰余）を計算し、そして可能であれば、｛０  …  ２48−１｝に属するｘ’＝ｆ（ｘ）を計算し、｛０  …  ２48−１｝に属するｃ＝ｈ（ｘ，ｗ，［Ｍ］）またはｃ＝ｈ（ｘ’，ｗ，［Ｍ］）を計算し、Ｂに対してｃを送信する。
２．Ｂが、｛０  …  ２32−１｝の中からランダムに要素ｅを選択し、Ａに対してｅを送信する。
３．Ａが、ｙ＝ｒ＋ｓｅを計算し、Ｂに対してｙを送信する。
４．Ｂが、ｃ＝ｈ（αyｖe（ｎの剰余），ｗ，［Ｍ］）またはｃ＝ｈ（ｆ（αyｖe（ｎの剰余），ｗ，［Ｍ］）をチェックし、第０ステージにおける送信から第３ステージにおける受領までの時間が１〜数秒間よりも短いことをチェックする。
【００７１】
最後に、署名プロトコルは、以下のようなものである。
０．Ｂが、｛０  …  ２64−１｝の中からランダム数ｗを選択し、Ａに対してｗを送信する。
１．Ａが、｛０  …  ｔｕｚ−１｝の中からランダムに整数ｒを選択し、ｘ＝αr （ｎの剰余）を計算し、そして可能であれば、｛０  …  ２48−１｝に属するｘ’＝ｆ（ｘ）を計算する。
２．Ａが、｛０  …  ２48−１｝に属するｅ＝ｈ（ｘ，ｗ，［Ｍ］）を計算する。
３．Ａが、ｙ＝ｒ＋ｓｅを計算し、Ｂに対して（ｅ，ｙ）を送信する。
４．Ｂが、ｅ＝ｈ（αyｖe（ｎの剰余），ｗ，［Ｍ］）をチェックし、第０ステージにおける送信から第３ステージにおける受領までの時間が１〜数秒間よりも短いことをチェックする。