(57)【特許請求の範囲】
【請求項１】
秘密鍵及び公開鍵を使用する暗号化技術に基づいて照合器により少なくとも一の証明器を認証する方法であり、上記認証は知識なし型プロトコルにより実現され、ここで、上記公開鍵は条件付き線形方程式を使用して確定され、
ａ）上記証明器と上記照合器の対話を可能にさせ、その座標が一定の集合Ｘから選択される次数ｎの少なくとも一のベクトルＳからなる秘密鍵と、その係数が０乃至ｄ−１の整数値からランダムに選択され、ｄは数値ｃの平方に近い素数である次数ｍ×ｎの行列Ｍと、ｇが集合Ｘと整数の集合（１，２，．．．ｄ−１）の部分群Ｇにより定まる関数であり、ｘがｇ（ｘ）とＸの要素ｋ（ｘ）の積として一意に表わされるようにＧの要素ｇ（ｘ）をベクトルＰの各座標ｘに関連させるＰ＝ｇ（Ｍ（Ｓ））のような少なくとも一のベクトルＰとからなる公開鍵を確定するステップと；
ｂ）上記証明器は、上記照合器により生成される１以上のランダムな数値を受け、次いで、Ｓ、Ｍ、及び上記ランダムな数値の関数であるパラメータに暗号化ハッシュ関数を適用することにより得られるコミットメントを上記照合器に戻すステップと；
ｃ）上記照合器により選択された上記ランダムな数値に依存して、上記照合器は、上記受けられた値と上記公開鍵とを使用して上記コミットメントが正しいかどうかを検査するステップと、
よりなることを特徴とする方法。
【請求項２】
上記証明器と上記照合器の対話が確立され、ランダムな要素が選択された後に：
ａ）上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わす〕で表わされるハッシュ関数Ｈにより生成される上記コミットメントｈ１及びｈ２を計算し、上記照合器に送出し、
ｂ）上記照合器は０乃至ｄ−１から数値“ａ”をランダムに選択し、上記証明器に送出し、
ｃ）上記証明器は：
Ｙ＝（ａＳ＋Ｕ）．ｐ
Ｚ＝（ａＴ−Ｖ）．ｑ
〔式中、Ｔはベクトルｋ（Ｍ（Ｓ））である〕
で表わされるベクトルを計算し、上記照合器に送出し、
ｄ）上記照合器はビット“ｂ”（＝０又は１）をランダムに選択し、上記証明器に送出し、
ｅ）上記証明器は：
ｂ＝０の場合に、応答ｒはｐ及びｑの値からなり；
ｂ＝１の場合に、ｒはベクトルＵ’＝Ｓ．ｐ及びＶ’＝Ｔ．ｑからなる；により定められる応答ｒを戻し、
ｆ）上記照合器は上記応答ｒを受け：
ｂ＝０の場合に、上記受けられた要素（ｐ，ｑ）から（Ｙ’）．ｐ＝Ｙ及び（Ｚ’）．ｑ＝ＺであるようなベクトルＹ’及びＺ’を計算し、次いで、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，Ｍ（Ｙ’）−Ｐ* Ｚ’）
である必要のあるベクトルＭ（Ｙ’）−Ｐ* Ｚ’を計算し；
ｂ＝１の場合に、上記受けられた要素から上記応答が正しい場合に：
ｈ２＝Ｈ（Ｙ−ａＵ’，ａＶ’−Ｚ）
である必要のあるベクトルＹ−ａＵ’及びａＶ’−Ｚを計算し、ベクトルＵ’及びＶ’がＸの要素だけを含むかどうかを検査する；
段階を有する請求項１記載の方法。
【請求項３】
上記証明器と上記照合器の対話が確立され、ランダムな要素が選択された後に：
ａ）上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（（Ｕ＋Ｓ）．ｐ，（Ｖ−Ｔ）．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わし、Ｔは、上記証明器によりＳの関数として計算し得るか、又は、上記証明器のメモリの物理的にアクセス不可能の部分に格納し得るベクトルｋ（Ｍ（Ｓ））を表わす〕
で表わされるハッシュ関数Ｈにより生成される上記コミットメントｈ１、ｈ２及びｈ３を計算し、上記照合器に送出し、
ｂ）上記照合器は０＜ｂ＜４であるような数値“ｂ”をランダムに選択し、上記証明器に送出し、
ｃ）上記証明器は：
ｂ＝１の場合に、ｒはｐ、ｑ、Ｕ及びＶの値からなり；
ｂ＝２の場合に、ｒはｐ、ｑ、及びベクトルＵ’＝（Ｕ＋Ｓ）とＶ’＝（Ｖ−Ｔ）からなり；
ｂ＝３の場合に、ｒはベクトルＵ．ｐ、Ｖ．ｑ、Ｕ”＝（Ｕ＋Ｓ）．ｐ及びＶ”＝（Ｖ−Ｔ）．ｑからなる；
により定められる応答ｒを戻し、
ｄ）上記照合器は上記応答ｒを受け：
ｂ＝１の場合に、上記受けられた要素（ｐ，ｑ，Ｕ及びＶ）から、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
である必要のあるＭＵ＋Ｐ* Ｖ、Ｕ．ｐ、及びＶ．ｑの値を計算し；
ｂ＝２の場合に、上記受けられた要素（ｐ，ｑと、ベクトルＵ’及びＶ’
）から、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ’＋Ｐ* Ｖ’）
ｈ３＝Ｈ（Ｕ’．ｐ，Ｖ’．ｑ）
である必要のあるＭＵ’＋Ｐ* Ｖ’、Ｕ’．ｐ、及びＶ’．ｑの値を計算し；
ｂ＝３の場合に、以下の式：
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（Ｕ”，Ｖ”）
が真であるかどうかを照合し、２つのベクトルＵ”−Ｕ．ｐ及びＶ”−Ｖ．ｑを計算し、Ｘの要素だけから構成されるかどうかを検査する；
段階を有する請求項１記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、少なくとも一の確認装置を照合装置によって認証し、認証には条件付き線形方程式（ＣＬＥ）の問題に基づく知識なし型プロトコルを利用する新規の方法に関する。
【０００２】
【従来の技術】
ＣＬＥ問題とは、素数ｄを法としたある数の線形方程式を満たし、その上、特定の集合Ｘの要素である値を見つけることである。
本発明は、特に、所謂「プロテクトされた」又は「秘密」通信に適用し、ここで、２台の装置、即ち、確認装置（従来は証明器(prover)と呼ばれる）と照合装置（従来は照合器(verifier)と呼ばれる）は、その機密性が不確実であるチャネル間のデータを交換する。かかる状況では、相互認識の手段を有すること、換言すれば、利用者がデータ又はサービスにアクセスする前に照合器に利用者の身元を認識させることが不可避である。上記のようなプロテクトされた通信を必要とする状況は多数ある。その好例は、金融取引を伝える銀行のコンピュータ、自動銀行券払出し機、有料テレビジョンデコーダ、及び公衆電話機である。
【０００３】
上記の応用に対し通常使用される認証システムは、秘密鍵の暗号化方法に基づいている。従来では、上記の方法が最も簡単に利用可能な技術である。この場合、一般的に、コンピュータ化したカードである証明器、カード読み取り器のような照合器、デコーダ又は公衆電話機は、同一の秘密鍵を共有する。確認は対称アルゴリズム又は一方向に機能する関数によって行われる。
【０００４】
【発明が解決しようとする課題】
上記の方法の欠点は、２台の装置（証明器と照合器）が相互に協働し、かつ、秘密的である必要のあることである。例えば、偽造者は、秘密鍵が通信線の両端で証明器と照合器の両方に存在するので、その内部動作を理解し高性能の装置を製造するため照合装置を手に入れ分析する。
【０００５】
従来の方法の欠点を解決するのに使用される周知の方法において、現時点では知識なし型プロトコルが最高の機密性のレベルを提供していることは周知である。かかる知識なし型プロトコルは、照合器での取扱の回数に制限の無い場合、及び、この照合器自体を完全に分析する場合でさえ、この装置を再製するのには十分ではない点に機能的な特徴がある。知識なし型の証明は、特に、フィアット他による米国特許第４  ７４８  ６６８号明細書、及び、シャミル他による米国特許Ａ第４  ９３２  ０５６号明細書に説明されている。後者の特許には、置換されたカーネル問題に基づき「ＰＫＰ」という名前で周知の認証システムが説明されている。
【０００６】
本発明はシンドロームデコーディング(syndrome decoding) の問題に基づく新規の認証システムを開発した。この問題は、ＣＲＹＰＴＯ９３学術講演会（「コンピュータサイエンスの講義ノート」に刊行予定の予稿集）で発表されたジャキューズ  スターンの「シンドロームデコーディングに基づく新規の確認システム」という論文に記載されている。上記の種々の方法の欠点は、証明器と照合器の間の情報交換がかなり遅い点である。その上、上記の方法に利用される公開又は秘密鍵は、一般的に、非常に膨大な数のビットを使用して符号化され、かなりの処理能力とメモリ容量とを必要とする。
【０００７】
従って、本発明の目的は、照合器による証明器の高速の確認と、適当な大きさの公開及び秘密鍵の使用とを可能にさせる新規の認証方法を提供し、上記の欠点を解決することである。
【０００８】
【課題を解決するための手段】
本発明の方法は、秘密及び公開鍵を使用する暗号化技術に基づく照合器によって少なくとも一の証明器を認証し、認証は知識なし型プロトコルを用いて実現され、ここで、公開鍵は条件付き線形方程式で確定する。
【０００９】
本発明の方法は：
−  証明器と照合器の対話を可能にさせ、その座標が特定の集合Ｘから選択される次数ｎの少なくとも一のベクトルＳからなる秘密鍵と、その係数が０乃至ｄ−１の整数値からランダムに選択され、ｄは数値ｃの平方に近い素数である次数ｍ×ｎの行列Ｍと、ｇは集合Ｘと整数の集合（１，２，．．．ｄ−１）の部分群Ｇにより定まる関数であり、ｘがｇ（ｘ）とＸの要素ｋ（ｘ）の積として一意に表わされるようにＧの要素ｇ（ｘ）をベクトルＰの各座標ｘに関連させるＰ＝ｇ（Ｍ（Ｓ））のような少なくとも一のベクトルＰとからなる公開鍵を確定し、
−  上記証明器は上記照合器により生成される１以上のランダムな数値を受け、次いで、暗号化ハッシュ関数をＳ、Ｍ及び上記ランダムな数値の関数であるパラメータに適用することにより得られるコミットメントを上記照合器に戻し、
−  上記照合器により選択された上記ランダムな数値に依存して、上記照合器は、上記受けられた値と上記公開鍵とを使用して、上記コミットメントが正しいかどうかを検査し、
−  必要とされる機密性のレベルに依存して上記動作を数回繰り返す段階からなる。
【００１０】
認証システムにおいて、全ての利用者に共通であるランダムに構成されたｍ×ｎの行列Ｍが使用される。各利用者は、その座標が特定の集合Ｘから選択されるｎビット語の秘密鍵Ｓを受ける。かかる集合Ｘはｃ個の要素からなり、１乃至ｄ−１の全ての整数はＧの要素とＸの要素の積として一意的に表わされる。上記の例の場合、システムはＰ＝ｇ（Ｍ（Ｓ））となるような公開鍵Ｐを計算する。
【００１１】
その上、確認処理は主としてコミットメントの技術的概念に基づいている。Ｕが２進の要素の系列である場合に、Ｕに対するコミットメントは所定の暗号化ハッシュ関数により生成されるＵの写像である。上記コミットメントは一方向の関数として使用され、換言すれば、それが構築された元の系列を公表することにより解読される。ハッシュ関数自体は、例えば、Ｒ．リベストによりＣＲＹＰＴＯ９０会議（ＣＲＹＰＴＯ  ９０  予稿集、「コンピュータサイエンスの講義ノート」集のページ３０３−３１１）で説明された「ＭＤ４」法を使用して得ることができる。「ＭＤ５」という呼ばれる上記方法の変形、又は、アメリカ標準規格ＳＨＡ（機密性ハッシュ標準規格、連邦情報処理標準規格公報、１９９２年１０月３０日）を使用することも可能である。最後に、ハッシュ関数の代わりに、ハッシュすべきメッセージが鍵、及び／又は、符号化すべき平文の役割を果たすＤＥＳ（データ暗号化標準規格）のような暗号化アルゴリズムを使用することも可能である。しかし、上記ハッシュは、圧縮されたハッシュの結果が好ましくは１２８ビットであるように繰り返されることが好ましい。
【００１２】
上記証明器は更に２進のベクトルを置換するために使用されるランダムな順列の発生器を使用する。上記発生器はディジタル化された白色雑音源、例えば、所謂「エルボー(elbow) 」ゾーンにおける逆向きに極性化されたダイオードから作ること、或いは、ギュンターによる米国特許第４  ８１７  １４７号明細書、又は、アラゴンによる米国特許第４  ６４９  ４１９号明細書に記載されるソフトウェア的手法を使用して実現することが可能である。
【００１３】
本発明の認証処理の一実施例によれば、全ての処理に共通の第１の段階において、証明器はその身元証明、及び／又は、その署名された公開鍵を照合器に提示し：
−  ０乃至ｄ−１の整数からなる次数が夫々ｍ及びｎの２つのベクトルＵ及びＶと、夫々にｍ及びｎ個の要素の２つの順列ｐ及びｑとをランダムに選択した後に、上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（（Ｕ＋Ｓ）．ｐ，（Ｖ−Ｔ）．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わし、Ｔは、上記証明器によりＳの関数として計算し得るか、又は、上記証明器のメモリの物理的にアクセス不可能の部分に格納し得るベクトルｋ（Ｍ（Ｓ））を表わす〕
で表わされるハッシュ関数Ｈにより生成される上記コミットメントｈ１、ｈ２及びｈ３を計算し、上記照合器に送出し；
−  上記照合器は０＜ｂ＜４であるような数値“ｂ”をランダムに選択し、上記証明器に送出し；
−  上記証明器は：
ｂ＝１の場合に、ｒはｐ、ｑ、Ｕ及びＶの値からなり；
ｂ＝２の場合に、ｒはｐ、ｑ、及びベクトルＵ’＝（Ｕ＋Ｓ）とＶ’＝（Ｖ−Ｔ）からなり；
ｂ＝３の場合に、ｒはベクトルＵ．ｐ、Ｖ．ｑ、Ｕ”＝（Ｕ＋Ｓ）．ｐ及びＶ”＝（Ｖ−Ｔ）．ｑからなる；
により定められる応答ｒを戻し；
−  上記照合器は上記応答ｒを受け：
ｂ＝１の場合に、上記受けられた要素（ｐ，ｑ，Ｕ及びＶ）から、上記応
答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
である必要のあるＭＵ＋Ｐ* Ｖ、Ｕ．ｐ、及びＶ．ｑの値を計算し；
ｂ＝２の場合に、上記受けられた要素（ｐ，ｑと、ベクトルＵ’及びＶ’）から、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ’＋Ｐ* Ｖ’）
ｈ３＝Ｈ（Ｕ’．ｐ，Ｖ’．ｑ）
である必要のあるＭＵ’＋Ｐ* Ｖ’、Ｕ’．ｐ、及びＶ’．ｑの値を計算し；
ｂ＝３の場合に、以下の式：
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（Ｕ”，Ｖ”）
が真であるかどうかを照合し、２つのベクトルＵ”−Ｕ．ｐ及びＶ”−Ｖ．ｑを計算し、Ｘの要素だけから構成されるかどうかを検査する。
【００１４】
本発明の認証処理の他の好ましい実施例において、全ての処理に共通の第１の段階において、証明器はその身元証明及び／又はその署名された公開鍵を照合器に提示し：
−  ０乃至ｄ−１の整数からなる次数が夫々にｍ及びｎの２つのベクトルＵ及びＶと、夫々にｍ及びｎ個の要素の２つの順列ｐ及びｑとをランダムに選択した後に、上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わす〕
で表わされるハッシュ関数Ｈにより生成される上記コミットメントｈ１及びｈ２を計算し、上記照合器に送出し、
−  上記照合器は０乃至ｄ−１から数値“ａ”をランダムに選択し、上記証明器に送出し、
−  上記証明器は：
Ｙ＝（ａＳ＋Ｕ）．ｐ
Ｚ＝（ａＴ−Ｖ）．ｑ
〔式中、Ｔは、上記証明器によりＳの関数として計算し得るか、又は、上記証明器のメモリの物理的にアクセス不可能の部分に格納し得るベクトルｋ（Ｍ（Ｓ））である〕
で表わされるベクトルを計算し、上記照合器に送出し、
−  上記総合器はビット“ｂ”（＝０又は１）をランダムに選択し、上記証明器に送出し、
−  上記証明器は：
ｂ＝０の場合に、応答ｒは値ｐ及びｑからなり；
ｂ＝１の場合に、ｒはベクトルＵ’＝Ｓ．ｐ及びＶ’＝Ｔ．ｑからなる；により定められる応答ｒを戻し、
−  上記照合器は上記応答ｒを受け：
ｂ＝０の場合に、上記受けられた要素（ｐ，ｑ）から（Ｙ’）．ｐ＝Ｙ及び（Ｚ’）．ｑ＝ＺであるようなベクトルＹ’及びＺ’を計算し、次いで、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，Ｍ（Ｙ’）−Ｐ* Ｚ’）
である必要のあるベクトルＭ（Ｙ’）−Ｐ* Ｚ’を計算し；
ｂ＝１の場合に、上記応答が正しい場合に：
ｈ２＝Ｈ（Ｙ−ａＵ’，ａＶ’−Ｚ）
である必要のあるベクトルＹ−ａＵ’及びａＶ’−Ｚを計算し、ベクトルＵ’及びＶ’がＸの要素だけを含むかどうかを検査する。
【００１５】
【実施例】
本発明の他の特徴及び利点は、添付図面を参照して、その例に限定されることのない以下の２つの好ましい実施例の説明により明らかになる。
本発明は知識なし型プロトコルを使用する新規な認証システムに係る。かかる例において、処理の機密性は条件付き線形方程式（ＣＬＥ）の問題に基づいている。ＣＬＥ問題は素数ｄを法として所定の数の線形方程式を充足し、かつ、所定の集合Ｘの要素であるｎ個の値を見つけることからなる。変数の数が多い場合に、この問題は、周知の計算手段を用いて解くことが極めて困難である。ここに説明するシステムは、事実上、ｎ＋ｍ個の変数を有するｍ個の方程式の例に対応し、現在のコンピュータの能力を遙に上回る例である。
【００１６】
本発明による認証システムを実現するために、認証者は、その次数がｍ×ｎ、好ましくは、ｍ＝ｎである行列Ｍを選択し公開する。この行列は０乃至ｄ−１の整数からランダムに選択された係数からなり、ここで、ｄは一般的に数値ｃの平方に近い素数である。好ましくは、ｄ＝２５７、即ち、ｄは（１６×１６）＋１に一致する。さらに、認証者は、その座標が集合Ｘからランダムに選択される次数ｎのベクトルＳの集合を選択する。集合Ｘは、ｄを法として数値の順次の巾乗の系列から形成される乗法群として周知の集合Ｇの関数として定められ、上記集合は集合Ｇの要素の数がｃであるように選択される。上記の例において、同様に、ｃ個の要素から形成される集合Ｘが存在し、１乃至ｄ−１の全ての整数は集合Ｇの要素と、集合Ｘの要素の積として一意に定められる。従って、１乃至ｄ−１の整数の一意的な分解に含まれるＧの要素をｇ（Ｕ）で表わし、対応するＸの要素をｋ（Ｕ）で表わす。Ｕが１乃至ｄ−１の整数からなるベクトルである場合に、ｇ（Ｕ）はＧによるＵの座標の写像から構成される。ｋ（Ｕ）も同様に定められる。
【００１７】
上記の方法で定められる秘密鍵は種々の証明器に配付される。その上、ベクトルＰ＝ｇ（Ｍ（Ｓ））により構成される全ての公開鍵は公開される。本発明の構成において、かかる公開鍵は少数のバイトを使用して符号化され、同様に、秘密鍵はＧ及びＸの要素のテーブルを使用して符号化される。かくして、ｄ＝２５７かつｍ＝ｎ＝２０である場合に、１０バイトの鍵が得られ、この点で本発明の処理は他の周知の知識なし型プロトコルよりも優れている。
【００１８】
以下に本発明による認証システムに特有の２つの実施例を説明する。
第１の実施例を認証を行うために証明器と照合器との間で使用される通信プロトコルを概略的に示す図１を参照して説明する。例えば、コンピュータ化したカード、或いは、電子的鍵の形をなし得る証明器は、物理的にアクセス不可能であることが必要である。例えば、コンピュータ化したカードの場合に、その内部メモリは読めないことが必要である。一方、照合器の動作する環境に条件は課されない。その上、証明器は、次数ｎのベクトルＳ及び次数ｍ×ｎの行列Ｍである秘密鍵Ｓをその不揮発性メモリに含み、一方、照合器は、ベクトルＰ、又は、署名された鍵Ｐが認可された認証者により生成されたかどうかを照合するのに充分なデータにより構成される全ての公開鍵をその不揮発性メモリに含む。証明器が照合器との通信を望む場合に、２台の装置は以下のプロトコルを実施する：
−  最初に、証明器はその身元証明及び／又はその署名された公開鍵を照合器に提示し；照合器は上記身元証明がＰに一致するかどうかを照合し；
−  次いで、０乃至ｄ−１の整数からなる次数が夫々にｍ及びｎ、好ましくはｍ＝ｎである２つのベクトルＵ及びＶと、夫々にｍ及びｎ個の要素の２つの順列ｐ及びｑとをランダムに選択する。上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（（Ｕ＋Ｓ）．ｐ，（Ｖ−Ｔ）．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わし、Ｔはベクトルｋ（Ｍ（Ｓ））を表わす〕
で表わされるコミットメントを計算し、上記照合器に送出し；
−  上記照合器は０＜ｂ＜４であるようなランダムな数値“ｂ”を選択し、上記証明器に送出し；
−  上記証明器は：
ｂ＝１の場合に、ｒはｐ、ｑ、Ｕ及びＶの値からなり；
ｂ＝２の場合に、ｒはｐ、ｑ、及びベクトルＵ’＝（Ｕ＋Ｓ）とＶ’＝（Ｖ−Ｔ）とからなり；
ｂ＝３の場合に、ｒはベクトルＵ．ｐ、Ｖ．ｑ、Ｕ”＝（Ｕ＋Ｓ）．ｐ及びＶ”＝（Ｖ−Ｔ）．ｑからなる；
により定められる応答ｒを上記照合器に送出し；
−  上記照合器は上記応答ｒを受け：
ｂ＝１の場合に、上記受けられた要素（ｐ，ｑ，Ｕ及びＶ）から、上記応
答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
である必要のあるＭＵ＋Ｐ* Ｖ、Ｕ．ｐ、及びＶ．ｑの値を計算し；
ｂ＝２の場合に、上記受けられた要素（ｐ，ｑと、ベクトルＵ’及びＶ’）から、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ’＋Ｐ* Ｖ’）
ｈ３＝Ｈ（Ｕ’．ｐ，Ｖ’．ｑ）
である必要のあるＭＵ’＋Ｐ* Ｖ’、Ｕ’．ｐ、及びＶ’．ｑの値を計算し；
ｂ＝３の場合に、以下の式：
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
ｈ３＝Ｈ（Ｕ”，Ｖ”）
が真であるかどうかを照合し、２つのベクトルＵ”−Ｕ．ｐ及びＶ”−Ｖ．ｑを計算し、Ｘの要素だけから構成されるかどうかを検査する。
【００１９】
上記のテストの全てが成功である場合に、照合器は認証プロトコルが首尾よく終了したと見なし、取扱を可能な状態にするためプロテクトされているシステムの入出力インタフェースに制御信号を送出し；不成功である場合には、証明器は拒否される。
【００２０】
照合器は、より高いレベルの機密性が必要とされる場合に、上記の段階をｔ回に亘り繰り返す。
上記の動作は図１に概略的に示され、同図において左側は証明器により行われる動作を示し、右側は照合器により行われる操作を示す。
【００２１】
以下に図２を参照して本発明の認証システムの他の実施例を説明する。
第２の実施例は第１の実施例よりも多くの計算を必要とするが、プロテクトされたシステムの不法進入の可能性は急激に減少する。第２の実施例は、図１と同様に表わされた図２に概略的に示される以下の段階を含む：
−  最初に、第１の実施例と同様に、証明器はその身元証明及び／又はその署名された公開鍵を照合器に提示する。
を照合し；
−  次いで、０乃至ｄ−１の整数からなる夫々に次数がｍ及びｎ（ｍはｎに一致してもよい）の２つのベクトルＵ及びＶと、夫々にｍ及びｎ個の要素の２つのランダムな順列ｐ及びｑとをランダムに選択する。上記証明器は：
ｈ１＝Ｈ（ｐ，ｑ，ＭＵ＋Ｐ* Ｖ）
ｈ２＝Ｈ（Ｕ．ｐ，Ｖ．ｑ）
〔式中、Ｐ* Ｖは、ｄを法としてベクトルＰ及びＱの成分の項と項の積を表わし、Ｈは暗号化ハッシュ関数を表わす〕
で表わされるコミットメントを計算し、上記照合器に送出する。
−  上記照合器は０乃至ｄ−１からランダムの数値“ａ”を選択し、上記証明器に送出する。
−  上記証明器は：
Ｙ＝（ａＳ＋Ｕ）．ｐ
Ｚ＝（ａＴ−Ｖ）．ｑ
〔式中、Ｔは、上記証明器によりＳの関数として計算し得るか、又は、上記装置のメモリの物理的にアクセス不可能の部分に格納し得るベクトルｋ（Ｍ（Ｓ））である〕
で表わされるベクトルを計算し、上記照合器に送出する。
−  上記総合器はビット“ｂ”（＝０又は１）をランダムに選択し、上記証明器に送出し；
−  上記証明器は：
ｂ＝０の場合に、ｒはｐ及びｑの値からなり；
ｂ＝１の場合に、ｒはベクトルＵ’＝Ｓ．ｐ及びＶ’＝Ｔ．ｑからなる；により定められる応答ｒを戻す。
−  上記照合器は上記応答ｒを受け：
ｂ＝０の場合に、上記受けられた要素（ｐ，ｑ）から（Ｙ’）．ｐ＝Ｙ及び（Ｚ’）．ｑ＝ＺであるようなベクトルＹ’及びＺ’を計算し、次いで、上記応答が正しい場合に：
ｈ１＝Ｈ（ｐ，ｑ，Ｍ（Ｙ’）−Ｐ* Ｚ’）
である必要のあるベクトルＭ（Ｙ’）−Ｐ* Ｚ’を計算し；
ｂ＝１の場合に、上記応答が正しい場合に：
ｈ２＝Ｈ（Ｙ−ａＵ’，ａＶ’−Ｚ）
である必要のあるベクトルＹ−ａＵ’及びａＶ’−Ｚを計算し、ベクトルＵ’及びＶ’がＸの要素だけを含むかどうかを検査する。
【００２２】
ｂに関するテストが成功である場合に、照合器は認証プロトコルが首尾よく終了したと見なし、取扱を可能な状態にするためプロテクトされているシステムの入出力インタフェースに制御信号を送出し；不成功である場合には、証明器は拒否される。
【００２３】
機密性のレベルを高めるために、証明器及び照合器は、上記の段階をｔ回に亘り繰り返してもよく、この例の場合に、認証プロトコルは、全ての回のテストが成功である場合にのみ成功であると見なされる。好ましくは、ｔは０＜ｔ＜６０であるように選択される。上記の第１及び第２の実施例に対し、ｔ＝３５及びｔ＝２０の値夫々は、多数の応用において充分な機密性のレベルを与える。
【００２４】
上記の本発明の２つの実施例はその例に限定されることはなく：本発明の範囲を逸脱することなく多数の方法で変形することが可能である。
【図面の簡単な説明】
【図１】本発明の認証方法の第１の実施例の説明図である。
【図２】本発明の認証方法の第２の実施例の説明図である。
【符号の説明】
なし
【図１】
0003966912.tif 000002
【図２】
0003966912.tif 000003