(57)【特許請求の範囲】
【請求項１】
証明者をマイクロコントローラで構成し、検証者をより強力なマイクロコントローラまたはマイクロプロセッサで構成し、各アイデンティティは、秘密鍵ｓｉおよび公開鍵ｖｉを含み、公開される生成元は、αｑ≡１（ｍｏｄ  ｐ）であるようなαであり、ｑ｜ｐ−１であるような２つの素数ｐおよびｑを使用してｄｉ個のアイデンティティを認証する方法において、
前記証明者で、前記検証者に公開鍵ｖｉの順序付きリストを提供する第１ステップと、
前記証明者で、ｑ未満の非負数ｒを一様にランダムに選択する第２ステップと、
前記証明者で、前記検証者に数ｘ＝αｒ（ｍｏｄ  ｐ）を送る第３ステップと、
前記検証者で、２（ｔ＋ｌｏｇｄ）（ただし、ｌｏｇの底は２であり、数ｔは所定のセキュリティパラメータである）未満の非負数ｅを一様にランダムに選択する第４ステップと、
前記証明者で、前記検証者から前記数ｅを受け取る第５ステップと、
前記証明者で、数ｙ＝ｒ＋Σｉｓｉ＊ｅｉ（ｍｏｄ  ｑ）を生成する第６ステップと、
前記証明者で、前記検証者に前記数ｙを送る第７ステップと、
前記検証者で、前記数ｙに基づいて等式ｘ＝αｙ＊Πｉ（ｖｉ）ｅｉ（ｍｏｄ  ｐ）が真か否かを判断する第８ステップと、
前記検証者で、前記等式が真の場合にのみ、前記ｄｉ個のアイデンティティを有するものとして前記証明者を受理する第９ステップと
を含む方法。
【請求項２】
前記セキュリティパラメータは９５である請求項１に記載の方法。
【請求項３】
前記証明者で、前記第１ステップ、前記第３ステップおよび前記第７ステップにより行われる前記検証者へのデータ送信処理、および前記第５ステップにより行われる前記検証者からのデータ受信処理は、光を発光・検知する単一のＬＥＤにより行われる請求項１に記載の方法。
【請求項４】
前記証明者を構成する前記マイクロコントローラは、
前記データ送信処理を行う際に、前記ＬＥＤを順バイアスで駆動して発光させ、
前記データ受信処理を行う際に、前記ＬＥＤを逆バイアスで駆動して光を検知させる
請求項３に記載の方法。
【請求項５】
前記ＬＥＤは、限流抵抗器を介して前記証明者を構成する前記マイクロコントローラのピンに接続され、前記マイクロコントローラは、スイッチによって操作される請求項３に記載の方法。
【請求項６】
前記ＬＥＤは、認証している間はフラッシュライトとして動作する請求項３に記載の方法。
【請求項７】
前記証明者を構成する前記マイクロコントローラは、スマートカードのマイクロコントローラである請求項１に記載の方法。
【請求項８】
前記生成することは、高速フーリエ変換を用いる請求項１に記載の方法。
【請求項９】
前記第６ステップは、前記数ｙを生成するために、
前記証明者がアクセス可能なメモリに、各秘密鍵ｓｉ毎に、前記秘密鍵ｓｉと２１〜２１＋ｌｏｇｑまでの２のべき乗として表現される数ｎとの積のｑを法とする剰余のテーブルを記憶することと、
前記剰余のテーブル内の前記各秘密鍵ｓｉに対応する剰余を前記各秘密鍵ｓｉに加算することにより、特定の秘密鍵を特定の数ｎで乗算し、ｅのべき乗を求めることと
をさらに含む請求項１に記載の方法。
【請求項１０】
前記証明者がアクセス可能なメモリに、ｅと２１〜２１＋ｌｏｇｑまでの２のべき乗との積のｑを法とする各剰余を記憶することをさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には認証プロトコルに関し、詳細にはゼロ知識認証プロトコルに関する。
【背景技術】
【０００２】
認証
認証とは、証明者が検証者に対して自己を確信させるプロセスである。十分な説明がMenezes他著「Handbook of applied cryptography」CRC Press, 1997、およびSchneier著「Applied cryptography」Wiley, 1996により提供されている。
【０００３】
認証プロトコルの２つの主な目的は、完全性および健全性である。完全性は、証明者が認証を常に完了することができることを意味する。健全性は、詐称者が認証を完了してしまう確率がごくわずかであることを意味する。
【０００４】
様々な等級の不正および対応するレベルのセキュリティがある。従来のセキュリティの枠組みでは、詐称者は、証明者に対して複数の攻撃を行うことができると想定される（Feige他著「Zero Knowledge proofs of identity」Journal of Cryptology, Vol. 1, pp.77-94, 1988）。
【０００５】
認証プロトコルの代表的な要件は、プロトコルが受動的攻撃下で、敵対する証明者が証明者−検証者の対話の写しにアクセスすることができる偽装から安全であることである。より高い要件は、プロトコルが能動攻撃から安全であることである。ここで、敵対する証明者は、偽装を試みる前に何度も証明者と不正検証者の役割を能動的に演じ得る。
【０００６】
また、同時攻撃に対して安全であることも望ましい。こういった攻撃では、敵対する証明者は、偽装に先立って不正検証者の役を演じる。鍵となる区別は、詐称者は、複数の正直な証明者と同時に対話することである。
【０００７】
また、認証プロセスがいずれの秘密情報、たとえば、証明者のアイデンティティを明らかにしないことも望ましい。これは、ゼロ知識認証として知られている。ゼロ知識の概念の明快かつ非数学的な紹介が、Quisquater他著「How to explain zero knowledge protocols to your children」Advances in Cryptology-CRYPTO '89, LNCS 435, pp. 628-631, 1989に提供されている。
【０００８】
ゼロ知識認証プロトコルを使用する場合、証明者は、秘密自体を明らかにすることなく、秘密の知識を所有していることを検証者に納得させる。これは、証明者が認証のために検証者に秘密を明らかにしなければならない従来のパスワードプロトコルと異なる。
【０００９】
認証プロトコルは、プロトコルが首尾良く完了した瞬間にのみ保証を提供することを念頭に置くことが非常に重要である。したがって、認証プロセスがある形の進行中のセキュリティサービスと結びついていることを保証することが重要である。あるレベルでは、すべての認証プロトコルは、証明者の認証が成功した直後に割り込んでくる敵に対して脆弱である。
【００１０】
ゼロ知識プロトコルは、証明者が秘密を保有すること以外の情報をまったく明らかにすることなく、証明者が秘密についての知識を実証できるようにする（Goldwasser他著「The knowledge complexity of interactive proof-systems」Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pp. 291-304, 1985、および１９９１年２月１９日にSchnorrに発行された米国特許第４，９９５，０８５号「Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system」）。
【００１１】
対話式プロトコルは、秘密を常に抽出することができるアルゴリズムが存在する場合に知識の認証であると言える。プロトコルは、秘密を明らかにしない場合は、ゼロ知識と言える。利点として、ゼロ知識プロトコルは、繰り返しの使用による劣化を受けず、偽装時のすべての攻撃に耐える。
【００１２】
プロトコルは、正直な検証者と対話するときにゼロ知識である場合、正直検証者ゼロ知識であると言える。正直検証者ゼロ知識プロトコルは、不正直な検証者が秘密を抽出することができる可能性があるため、一般のゼロ知識プロトコルよりも弱いセキュリティ保証を有する。
【００１３】
認証プロトコルの価値の究極の指標は、偽装攻撃に対するそのセキュリティにある。同時攻撃下での偽装に対して安全なプロトコルは、ただ単に正直検証者ゼロ知識の場合であっても「安全」であると考えられる。
【００１４】
生体認証技法を含む認証プロトコルについての詳細および完全な考察は、Davies他著「Security for computer networks」Wiley, 1989、およびFord著「Computer communications security: principles, standard protocols and techniques」Prentice Hall, 1994を参照のこと。ソルト処理の概念を含むパスワードベースの方式は、Morris他著「Password security: a case history」Communications of the ACM, Vol. 22, pp. 594-597, 1979に説明されており、また、Needham他著「Using encryption for authentication in large networks of computers」Communications of the ACM, Vol. 21, pp. 993-999, 1978も参照願いたい。
【００１５】
Feige他は、ゼロ知識の概念を知識の認証および証明の応用に適合させた。これ以後、ゼロ知識の様々な態様についての研究が、紛れもなく爆発的に増加している。Schneier「Applied cryptography」Wiley, 1996を参照願いたい。
【００１６】
従来のゼロ知識プロトコルでは、証明者と検証者との間で相当量のデータを相互交換する必要がある。プロトコルの処理もまた、相当なコンピュータ資源をとる。したがって、ゼロ証明知識プロトコルは、相当な通信帯域幅およびメモリと、比較的高度なマイクロプロセッサとを有する高複雑性システムにおいてのみ実行が可能である。このようなシステムは比較的高価であり、構築、操作、および保守が複雑である。
【００１７】
しかし、資源が厳しく制限された低複雑性ハンドヘルド装置の数は、ますます増大している。こういった装置の多くは、マイクロプロセッサの代わりにマイクロコントローラを使用する。マイクロプロセッサを有用にするには、マイクロプロセッサをＲＡＭ、ディスク、キーボード、および他のＩ／Ｏ周辺機器に取り付けなければならない。オペレーティングシステムおよびアプリケーションプログラムをインストールする必要がある。マイクロプロセッサチップは、単独では用をなさない。
【００１８】
マイクロコントローラは、そうではなく、そのままで使用することができる。マイクロコントローラは、通常、オンチップメモリを有し、大量生産されるコントローラの場合、ソフトウェアは、工場でインストール済みである。利点として、マイクロコントローラは、製造が安価であるとともに、操作が単純である。価格が低いため本質的に使い捨てにできることから、保守はない。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
したがって、マイクロコントローラを使用して動作可能な単純な低帯域幅ゼロ知識プロトコルを提供することが望ましい。
【課題を解決するための手段】
【００２０】
本発明は、高速かつ安全であることを立証できるSchnorrのゼロ知識認証の一般化を提供する。本発明は、様々な特権クラスを使用してアイデンティティの順序付きリストを効率的にまとめて検証することができる。本発明は、次数ｄの多項式を使用してｄ個のアイデンティティの順序付きリストを表す。プロトコルは、正直検証者ゼロ知識である。さらに、プロトコルは、同時攻撃下の偽装に対して安全である。
【００２１】
低複雑性認証装置では、マイクロコントローラがＬＥＤを動作させて、認証情報を搬送する光通信チャネルを提供する光の送信および検出の両方を行う。
【００２２】
利点として、装置は、スマートカードと異なり、物理的な接触を必要としないため、摩耗がない。さらに、装置は、スマートカードのように、不正変更の影響を受けやすい、外部電源を必要としない。
【００２３】
ＲＦシステムと異なり、光学装置は指向性があり、かつ短距離であるため、認証環境が制御される。また、鍵として使用される単一の装置が、偶然近くにあった誤った錠を意図せずに開けてしまう恐れなく、複数の錠を開けることができる。
【００２４】
ＬＥＤの可視性質により、普通のユーザインタフェースが提供される。すなわち、ユーザは、ＬＥＤが発光しているか否か、すなわちバッテリがなくなっているか否かを容易に判断することができる。さらに、装置は、使用中にフラッシュライトのような照明を提供して、さらなる物理的なセキュリティを提供することができる。
【００２５】
好ましい装置は、光通信を使用するが、プロトコルは、スマートカード、ハンドヘルド装置、およびマイクロプロセッサを含め、他の任意の演算装置と併せて使用することも可能である。
【発明の効果】
【００２６】
本発明は、ハンドヘルド光学トランシーバおよびスマートカード等、低複雑性携帯装置と併せて使用することが可能な低複雑性ゼロ知識認証プロトコルを提供する。プロトコルは、能動的な同時攻撃下での偽装に対して安全である。本発明のプロトコルは、正直検証者ゼロ知識であり、一般ゼロ知識プロトコルに拡張することが可能である。
【発明を実施するための最良の形態】
【００２７】
本発明は、Schnorrのゼロ知識認証プロトコルの一般化を用いる。付録を参照願いたい。Schnorr方式の単純な一般化は、ｄ個の認証巡を直列に構成することにより、ｄ個の秘密鍵、すなわちアイデンティティを認証する。証明者は、ｄ個のコミットメントを送信し、検証者は、各アイデンティティに１つずつ、ｄ個のチャレンジを返送する。この方式は、Schnorr方式のコストのｄ倍の通信および通信コストを有する。
【００２８】
対照的に、本発明による認証プロトコルは、１個のコミットメントを送信し、検証者は、すべてのアイデンティティに対して並列に１個のチャレンジを返送する。証明者の返信は、Schnorrによる１次多項式から、本発明による、ｄ個の秘密アイデンティティから形成されるｄ次多項式に一般化される。
【００２９】
図１は、本発明による認証プロトコルの基本的なステップを示す。
【００３０】
本発明によるプロトコルが使用するパラメータは以下である。２つの素数ｐおよびｑは、ｑ｜ｐ−１のようなものである。位数ｑのＺｐにおける原始根は、α≠１のようなα、すなわちαｑ≡１（ｍｏｄ  ｐ）のようなものである、すなわちαはＧｑの生成元である。言い換えれば、αｑ（ｍｏｄ  ｐ）によって生成される値は、最終的に、１〜Ｇｑの範囲のすべての整数値を生成する。数ｐ、ｑ、およびαは、公開される。
【００３１】
ｄｉ個の秘密アイデンティティ１０３がある。各アイデンティティｄｉは、秘密鍵ｓｉおよび公開鍵ｖｉからなる。秘密鍵ｓｉは、ｑ未満の非負整数であり、一様にランダムに選択される。公開鍵は、ｖｉ＝α−ｓｉ（ｍｏｄ  ｐ）である。証明者１０１のみが公開鍵を知っている。
【００３２】
開始
証明者１０１は、証明者が対応するｄ個の秘密鍵を所有していると主張するｄ個の公開鍵ｖの順序付きリストを検証者１０２に送ることにより、プロトコルを開始する（１１０）。検証者は、他の手段で公開鍵１１１を得てもよいことに留意されたい。最終的な結果は、検証者が順序付きのｄ個の公開鍵を所有するということである。
【００３３】
証明者によるコミットメント
証明者は、ｑ未満の非負数ｒを一様にランダムに選択する。証明者は、ｘ＝αｒ（ｍｏｄ  ｐ）１２１を検証者に送る（１２０）。
【００３４】
検証者からのチャレンジ
検証者は、２（ｔ＋ｌｏｇｄ）未満の非負数ｅを一様にランダムに選択する。ここで、ｌｏｇの底は２である。数ｔは、セキュリティパラメータであり、たとえば９５である。検証者は、ｅ１３１を証明者に送る（１３０）。
【００３５】
証明者からのレスポンス
証明者は、ｉ＝１，・・・，ｄについて、ｙ＝ｒ＋Σｉｓｉ＊ｅｉ（ｍｏｄ  ｑ）を生成する（１０４）。証明者は、ｙ１４１を検証者に送信する（１４０）。
【００３６】
検証
検証者は、ｘ＝αｙ＊Πｉ（ｖｉ）ｅｉ（ｍｏｄ  ｐ）であるか否かを判断し（１０５）、等式が真の場合にのみ証明者の主張を受理する（１５０）。
【００３７】
完全性
正直な証明者が、確率１をもって検証者に対してアイデンティティを証明することができることは明らかである。
【００３８】
健全性およびゼロ知識
不正な証明者は、前もって正確なチャレンジｅを推測し、コミットメントｘ＝αｒ＊Πｉ（ｖｉ）ｆｉ（ｍｏｄ  ｐ）を送ることによってだますことができる。ここで、ｆは、式ｒ＋Σｉｓｉ＊ｆｉ＝ｒ＋Σｉｓｉ＊ｅｉ（ｍｏｄ  ｑ）の多くてもｄ個の根の１つである。ここで、レスポンスは、ｙ＝ｒであるものが選択される。しかし、この攻撃が成功する確率は、多くても２−ｔである。この確率は、一般に当てはまらない離散対数の計算が容易にならない限り増大し得ない。
【００３９】
対応するSchnorrの定理を拡張して、以下述べるように、本発明のプロトコルが知識の証明であることを示す。無視できない成功確率を有する不正な証明者が存在する場合、この不正な証明者を繰り返しシミュレートすることにより、同じコミットメントを有する複数の成功した写しを明らかにすることが可能である。次に、こういった写しを使用して、ｄ個のアイデンティティすべてを計算することができるため、プロトコルは、知識の証明であることが実証される。
【００４０】
証明の基本的な概念は、同じコミットメントｒを有するｄ＋１枚の写しが生成される場合、各公開鍵の離散対数は、しかるべきVan der Monde行列を反転させることによって求めることができることである。Golub他著「Matrix Computations」Johns Hopkins University Press, 1993を参照のこと。
【００４１】
証明の説明には以下の表記を用いる。不正な証明者Ｐ’は、値ｐ、ｑ、およびα、ならびにｄ個の公開鍵ｖｉを有する任意の確率的チューリングマシンである。Ｐ’のランダムストリングはＲＰで表し、成功ビットＳ（ＲＰ，ｅ）は、Ｐ’がＲＰ、ｅに成功した場合にのみ真（１）であり、その他の場合は偽（０）である。
【００４２】
成功率Ｓは、Ｓ（ＲＰ，ｅ）にわたる平均であり、ここで、ＲＰおよびｅは一様にランダムに選択される。ＴをＰ’の実行時間とする。時間を成功対ＲＰおよびｅの平均実行時間を２倍したものに制限すると、成功率が最大で２分の１に低減するため、Ｔは、ＲＰおよびｅから独立しているものと仮定する。
【００４３】
定理１
Ｐ’の成功率Ｓが２−ｔ＋１よりも高い場合、Ｐ’に対するブラックボックスアクセスが与えられると、ｄ個の秘密鍵ｓｉ＝ｌｏｇαｖｉを計算する確率的チューリングマシンまたはプロセスＰＬが存在する。
【００４４】
証明
プロセスＰＬは、以下のように実行される。
【００４５】
ステップ１において、プロセスは、ランダムにストリングＲＰを選択し、ランダムプローブｅ、たとえばｅ１を使用してＰ’をシミュレートする。Ｐ’が失敗した場合、新しいＲＰを使用してステップ１を繰り返す。その他の場合、ステップ２に進む。
【００４６】
ステップ２において、プロセスは、ＲＰを固定保持し、Ｐ’が成功する総計でｄ＋１個のｅ：ｅ１、ｅ２、・・・，ｅ（ｄ＋１）を見つけようと試みて、最大で（８ｕ）（ｄ＋１）＊ｌｏｇ（ｄ＋１）ランダムｅをプローブする。ここで、ｕはステップ１のパス数である。プロセスは、ｄ＋１個のｅを見つけようとするこの試みに失敗した場合、ステップ１に戻る。
【００４７】
この試みに成功した場合、プロセスは、ｙ＝ｒ＋Σｉｓｉ＊ｅｉの形のｄ＋１個の式を解いて、ｄ個の未知数ｓ１〜ｓｄを計算する。値ｒは、（ｄ＋１）番目の未知数である。これらｄ＋１個の式を解くことは、対応するVan der Monde行列を反転させることに等しい。
【００４８】
ＰＬの実行時間を解析するために、いくつかの追加の定義および２つの付加的な結果が必要である。Ｓ（ＲＰ）をＳ（ＲＰ，ｅ）が１であるｅの小数部と定義する。ＲＰを、Ｓ（ＲＰ）が少なくともＳ／２の場合に「良好」と定義する。＃ＲＰがすべてのＲＰの集合のサイズを表すとし、＃ｅがすべてのｅの集合のサイズを表すとする。＃ｅ＝２（ｔ＋ｌｏｇｄ）であることに留意する。
【００４９】
補助定理：少なくとも１／２の確率で、ＰＬは、ステップ１において良好なＲＰを選択する。
【００５０】
証明：一様にランダムに選択される、すべてのＲＰにわたるＳ（ＲＰ）の平均は、Ｓである。ここで、ΣＲＰＳ（ＲＰ）＝＃ＲＰ＊Ｓである。しかし、Ｓ（ＲＰ）の非良好なＲＰの総和は、Σｎｏｔ−ｇｏｏｄ ＲＰＳ（ＲＰ）≦＃ＲＰ＊Ｓ／２であるため、当然の結果として、Ｓ（ＲＰ）の良好なＲＰの総和は、Σｇｏｏｄ ＲＰＳ（ＲＰ）≧＃ＲＰ＊Ｓ／２である。言い換えれば、Ｓ（ＲＰ，ｅ）が１であり、かつＲＰが良好であるＲＰ、ｅの集合は、Ｓ（ＲＰ，ｅ）が１である集合全体の少なくとも半分である。したがって、ＲＰは、少なくとも１／２の確率で良好である。
【００５１】
補助定理：（クーポンコレクター補助定理）：少なくとも１／２の確率で、良好なＲＰに関して、ＰＬは、最大で（４／Ｓ）（ｄ＋１）＊ｌｏｇ（ｄ＋１）個のランダムプローブを使用して、Ｐ’が成功する総計でｄ＋１個のｅ：ｅ１，ｅ２，・・・，ｅ（ｄ＋１）を見つけることに成功する。
【００５２】
証明：良好なＲＰを固定する。ＲＰが良好であるため、Ｓ（ＲＰ，ｅ）が１であるようにＳ／２よりも多くのｅがなければならない、すなわち２−ｔ＊２（ｔ＋ｌｏｇｄ）＝ｄよりも多くの成功ｅがなければならないことを観察する。ｋ≧Ｓ／２＊２（ｔ＋ｌｏｇｄ）≧ｄ＋１個の成功ｅ、すなわちＳ（ＲＰ，ｅ）が１であるｅ、があるとする。次に、ｄ＋１個の別個の成功ｅを見つけるために予期されるプローブの数は、２（ｔ＋ｌｏｇｄ）（１／ｋ＋１／（ｋ−１）＋・・・＋１／（ｋ−ｄ））である。ｋ≧Ｓ／２＊２（ｔ＋ｌｏｇｄ）であるため、予期されるプローブの数は、多くても（２ｋ／Ｓ）（１／ｋ＋１／（ｋ−１）＋・・・＋１／（ｋ））であり、これは多くても（２／Ｓ）（ｄ＋１）ｌｎ（ｄ＋１）である。したがって、少なくとも１／２の確率で、ＰＬは、予期される数の多くても２倍のプローブを使用して成功する。
【００５３】
ステップ１において、予期されるプローブの数は１／Ｓであり、ｕの予想は１／Ｓであり、少なくとも１／２の確率で、ｕ≧（１／２）（１／Ｓ）である。ＲＰは、確率１／２で良好である。したがって、少なくとも１／４の確率で、ｕ≧（１／２）（１／Ｓ）であり、かつＲＰが良好であり、ＰＬは、ステップ２において、少なくとも１／２の確率で成功する。各プローブにはＯ（Ｔ）個のステップが採用されるため、当然の結果として、少なくとも１／８の確率で、ＰＬがＯ（ｄｌｏｇｄ＊Ｔ／Ｓ）個のステップで成功する。
【００５４】
したがって、予想時間は（（１／８）＋（７／８）（１／８）＋（７／８）（７／８）（１／８）＋・・・）＊Ｏ（ｄｌｏｇｄ＊Ｔ／Ｓ）＝Ｏ（ｄｌｏｇｄ＊Ｔ／Ｓ）個のステップにより束縛される。
【００５５】
正直な検証者の場合、同じ分布を有する写しを生成することがあり得る。したがって、プロトコルは、正直検証者ゼロ知識である。しかし、不正直な検証者がコミットメントに依存するチャレンジを選択し得ることにより、同じ分布を有する写しを生成することが困難になるため、一般的な場合ではゼロ知識ではない。しかし、非公式に、情報が露呈されない理由は、コミットメントおよびレスポンスである数ｘおよびｙが本質的にランダムであるためである。
【００５６】
同時攻撃下の偽装に対するセキュリティ
本発明のプロトコルは、同時攻撃下での偽装に対して安全である。上に述べたように、認証プロトコルの究極の最終目標は、偽装に対してセキュリティを確立することである。
【００５７】
同時攻撃では、偽造試行に先立って、不正な証明者が不正な検証者の役を演じ、同時に複数の正直な証明者と対話し得る。
【００５８】
証明は、離散指数が、根本となる群において、さらにｄ個多くの反転下で安全であるという仮定に基づく。非公式に、仮定は、不正敵対者に離散対数オラクルへのアクセスが与えられた場合、敵対者が、チャレンジポイントよりも厳密にｄ個少ないクエリを離散対数オラクルに対して使用して、ランダムに選択された集まりの中のすべてのチャレンジポイントの離散対数を計算することは、計算的に実行不可能であることを述べている。
【００５９】
ｄが１であり、かつチャレンジポイントの集まりがサイズ１を有する場合、この仮定は、離散指数関数の普通の一方向性である。この仮定は、認証方式のセキュリティを、数論問題の困難性に下げる利点を有する。ｄ＞１の場合、仮定は、Bellare他著「GQ and Schnorr identification schemes: proofs of security against impersonation under active and concurrent attacks」Advances in Cryptology-CRYPTO '02, 2002に説明される対応する仮定により含意されるため、この対応する仮定よりも強くない。
【００６０】
定理の証明を説明する前に、以下の表記を策定する。ＤＬＰＧが離散対数パラメータ発生器を表すものとする。これは、パラメータｋがｑおよびαの対を出力する場合、ｐｏｌｙ（ｋ）時間ランダム化アルゴリズムである。但し、ｑは、ｑ｜ｐ−１であるような素数であり、αは、Ｇｑの生成元であり、ｐは、ｋビット長である。証明は、特定の発生器を必要としない。プロトコルのセキュリティの証明は、ＤＬＰＧについての仮定に基づく。
【００６１】
ｄｍｄｌ敵対者は、入力ｑおよびαを取得し、２つのオラクル（呼び出されると、その都度Ｇｑにおけるランダム要素を返すチャレンジオラクル、およびＧｑ中の要素Ｙが与えられる場合、ｌｏｇαＹを返す離散対数オラクル）にアクセスすることができるランダム化多項式時間アルゴリズムである。ゲームは、ＤＬＰＧを実行し、それからｄｍｄｌ敵対者をその出力に対して実行することである。ｄｍｄｌ敵対者は、厳密にｄ個少ないポイントに対して離散対数オラクルを照会しながら、チャレンジオラクルによって生成されるすべてのポイントの離散対数を見つけることに成功した場合勝利する。
【００６２】
ａｄｖ−ｄｍｄｌ（ｋ）がｄｍｄｌ敵対者の成功する確率を表すものとする。ｉｍｐｃａが、最初に不正検証者の役を演じ、その後不正証明者の役を演じる前に、いくつかの正直な証明者クローンと同時に対話する敵対者を表すものとする。ａｄｖ−ｉｍｐｃａ（ｋ）が、ｉｍｐｃａが偽装に成功する確率を表すものとする。
【００６３】
定理２
ＤＬＰＧに関連するプロトコルを攻撃している敵対者ｉｍｐｃａがいる場合、あらゆるｋについて、Ａｄｖ−ｉｍｐｃａ（ｋ）＜＝２−ｔ＋（ａｄｖ−ｄｍｄｌ（ｋ））１／（ｄ＋１）であるようなｄｍｄｌ敵対者が存在する。
【００６４】
証明
ｉｍｐｃａ敵対者と対話し、得た知識を用いて、離散対数オラクルから得るよりもｄ個多いチャレンジポイントの離散対数を計算するｄｍｄｌ敵対者を構築することが可能である。
【００６５】
まず、ｄｍｄｌ敵対者は、チャレンジオラクルをｄ回照会し、ｄ個のランダムグループ要素ｖｉ＝α−ｓｉを得る。次に、ｄｍｄｌ敵対者は、不正検証者モードにおいてｉｍｐｃａ敵対者を実行し、各証明者に対応して、チャレンジオラクルを照会することによってコミットメントｘｉを返し、また、チャレンジｅｉに対応して、離散対数オラクルからクエリｘｉ＊Πｊ（ｖｉ）（−ｅｉｊ）、ｊ＝１〜ｄにレスポンスを返すことにより、レスポンスｙｉを返す。
【００６６】
次に、ｄｍｄｌ敵対者は、不正証明者モードにおいてｉｍｐｃａ敵対者をｄ＋１回実行する。いずれか２つのチャレンジが同じである場合、ｄｍｄｌ敵対者は失敗する。不正証明者のコミットメントは、不正検証者として知識を得る都度開始されるため、同じままである。任意のランダム性をこの知識の中に組み込むこともできる。
【００６７】
ｘ＝αｒをコミットメントとし、ｗｉを別個のチャレンジｃｉに対応するレスポンスとする。不正証明者が一度でも失敗した場合、ｄｍｄｌ敵対者は失敗する。不正証明者がｄ＋１回のそれぞれに成功する場合、ｄｍｄｌ敵対者は、ｗｉ＝ｒ＋Σｊｓｊ＊ｃｉｊの形のｄ＋１個の式を有し、ｄ＋１個の未知数ｒおよびｄｃｉがある。これら式から形成されたVan der Monde行列を反転することにより、式を解いてｓｉを得ることができる。次に、ｄｍｄｌ敵対者は、チャレンジオラクルの行われたクエリｘｉに対応して、ｙｉ−Σｊｓｊ＊ｅｉｊを返す。
【００６８】
不正ｉｍｐｃａ証明者がｄ＋１回成功する場合、ｄｍｄｌが、離散対数オラクルに対して厳密にｄ個少ないクエリを使用して成功するかを検証することが可能である。２つのイベントの確率は、ここで関連する。付加的な結果が、Bellare他により得られた結果に等しい一般化である。
【００６９】
一般化リセット補助定理：潜在的に不正な証明者を含む任意の証明者を考える。ＡおよびＢを、証明者のランダムコインＲＰの空間にわたる確率変数とする。Ａが、ｅにわたってとられる、検証者が受理する確率を表すものとする。Ｂが、検証者がリセットされ、ｄ＋１回実行されたときに、異なるｅがその都度生成され、その都度検証者が受理する、ｅにわたってとられる確率を表すものとする。ａｃｃ＝Ｅ（Ａ）かつｒｅｓ＝Ｅ（Ｂ）とする。すると、ａｃｃ≦２−ｔ＋ｒｅｓ１／ｄ＋１である。
【００７０】
証明：１／ｃ＝２ｔ＋ｌｏｇｄをチャレンジ集合のサイズ、すなわち＃ｅとする。Ｂ≧Ａ（Ａ−ｃ）（Ａ−２ｃ）・・・（Ａ−ｄｃ）であることが容易に分かる。これは、Ｂ≧（Ａ−ｄｃ）（ｄ＋１）であることを含意し、これはＥ（Ａ）≦ｄｃ＋Ｅ（Ｂ）１／（ｄ＋１）またはＥ（Ａ）≦２−ｔ＋Ｅ（Ｂ）１／ｄ＋１をもたらす。
【００７１】
ここで、ａｄｖ−ｉｍｐｃａ（ｋ）＝Ｅ（ａｃｃ）であることを観察する。ここで、ｖｉの選択および不正検証者として得た知識に対する予想がとられる。同様に、ａｄｖ−ｄｍｄｌ（ｋ）＝Ｅ（ｒｅｓ）である。リセット補助定理を適用すると、
ａｄｖ−ｉｍｐｃａ（ｋ）＝Ｅ（ａｃｃ）
≦Ｅ（２−ｔ＋（ｒｅｓ）１／（ｄ＋１））
＝２−ｔ＋Ｅ（（ｒｅｓ）１／（ｄ＋１））
≦２−ｔ＋（Ｅ（ｒｅｓ））１／（ｄ＋１）、（Jensenの不等式による）
＝２−ｔ＋（ａｄｖ−ｄｍｄｌ）１／（ｄ＋１）
である。
【００７２】
以下の結論は、定理２の直接の帰結である。
【００７３】
結論
ＤＬＰＧが、ａｄｖ−ｄｍｄｌが無視できるようなものであり、かつｔ＝ω（ｌｏｇｋ）である場合、ＤＬＰＧに関連するプロトコルは、同時攻撃に対して安全である。ｔがｋにおける超対数であるという仮定が、そのままでは検証者のチャレンジを推測することによって方式が破れ得るため必要である。
【００７４】
複数のアイデンティティを用いる認証
認証プロトコルは、認証およびアクセス制御システムの構成要素を成す。アクセス制御システムの典型的な構造は、資源および関連するアイデンティティのアクセス制御行列を含む。アイデンティティの認証の成功により、関連する資源へのアクセスが可能になる。
【００７５】
アクセス制御には２つの主なタイプがある。一方のタイプでは、証明者が、特定の資源セットへのアクセスを許可する証明書を有する。他方のタイプでは、検証者が、特定のアイデンティティに対して許可されている資源に関する情報を所有する。
【００７６】
実際の用途では、証明者は、証明書の交換に携わる手段を常に所有している訳ではなく、検証者は、独立している場合が多いため、検証者に許可を受けているアイデンティティおよび対応する特権についてのリストを提供する必要がある。
【００７７】
理論上、資源の各部分集合に対して一意のアイデンティティを生成し、可能なすべてのアイデンティティに対応するアクセス制御行列を検証者に提供することができる。しかしこれは、ｎ個の資源に対して可能な資源部分集合が２ｎ個あるため、記憶に関して非常に高価となる。
【００７８】
しかし、本プロトコルが１巡で最大ｄ個のアイデンティティの順序付きリストを認証可能であることを利用することが可能である。そうすると、最大でｍ個のアイデンティティ、すなわち公開／秘密鍵の対をサポート可能な検証者のメモリがある場合、１＋ｍ＋ｍ２＋・・・ｍｄ＝（ｍｄ＋１−１）／（ｍ−１）個の可能な資源集合を生成することができる。
【００７９】
したがって、２ｎ個の別個のアイデンティティに対する空間が不十分な場合であっても、処理とメモリのトレードオフにより、適正なｄ＝Ｏ（ｎ／ｌｏｇｍ）を選択することによって同じ効果を実現することが可能である。
【００８０】
効率
ｄ個のアイデンティティの順序付きリストの場合、本発明による認証プロトコルＯ（ｌｏｇｄ）は、１個のアイデンティティに対してSchnorr方式よりも多数のビットを有する。しかし、Schnorr方式では１つのみの剰余乗算を使用して行うが、本発明による認証プロトコルはｄ個の剰余乗算を必要とする。
【００８１】
実施態様
ＬＥＤ
発光ダイオード（ＬＥＤ）は、ユビキタスインタフェースである。それぞれの種々の用途には、数値表示、フラッシュライト、車両のブレーキ灯、交通信号、および偏在する機器のインジケータが挙げられる。
【００８２】
ＬＥＤは、一般に発光器として使用されるため、ＬＥＤが基本的にはフォトダイオードであり、したがって光検出器としても動作可能なことは忘れられている場合が多い。ＬＥＤは、光検出に最適化されていないが、光の検出に非常に有効であり得る。
【００８３】
固体状態の光の放出と検出との間の相互交換可能性について、Forrest W. Mims著「Siliconnections: Coming of age in the electronic era」McGraw Hill, 1986および「LED circuits and projects」Sams and Co, 1993に述べられているが、以後大半は忘れられてしまっている。
【００８４】
ＬＥＤを使用して光を交互に放出し検出するインタフェース回路が、２００１年４月１９日にDiets他により出願された米国特許出願第１０／１２６，７６１号にDietz他により記載されている。ＬＥＤおよび単純なマイクロコントローラの２つのデジタルＩ／Ｏピンの他に回路が必要とするのは、たった１つの限流抵抗器だけである。順バイアスの場合、ＬＥＤは光を発し、逆バイアスの場合、ＬＥＤは光を検出する。
【００８５】
ＬＥＤベースのデータ通信の意味は、マイクロコントローラにＬＥＤを２つの異なるモードで動作させるのは本質的にソフトウェアであるため、大きな意義を有する。この技法を用いて、マイクロプロセッサに接続された任意のＬＥＤを、比較的低帯域幅であるが、双方向データポートとして動作させることができる。マイクロプロセッサも同様に、その処理能力に制約される。
【００８６】
ハードウェア
低帯域幅ゼロ知識認証プロトコルは、図２に示すように比較的単純な装置２００を使用して実施することができる。
【００８７】
認証装置２００は、マイクロコントローラ２１０、たとえば、Ｍｉｃｒｏｃｈｉｐ  ＰＩＣ１６ＬＦ６２８を備える。マイクロコントローラの第１のＩ／Ｏピン２０１は、ＬＥＤ２２０の入力に接続され、第２のＩ／Ｏピン２０２は、抵抗器２３０に接続され、そして、抵抗器２３０は、ＬＥＤの出力に接続される。第３のＩ／Ｏピン２０３に接続された押しボタンスイッチ２４０が、小型３ボルトリチウムコイン型電池２５０で装置を動作させる。図示されている他の構成要素は、すべて従来通り動作する。動作中、装置は、Dietz他が述べているように光２６０を放出・検知して、本明細書に記載の認証プロトコルに対応するデータを送受信する。
【００８８】
ＰＩＣは、８ビット命令を使用し、５ＭＩＰＳで動作し、１６ＫＢの書き込み可能メモリを有する。装置２００の大量生産版のコストは、ＬＥＤキーチェインフラッシュライトのコストにすぎないであろう。実際に、本発明による装置は、フラッシュライトとしても使用することが可能である。
【００８９】
装置のデータ速度は比較的遅いため、低帯域幅認証プロトコルは、この装置にうってつけである。通信範囲は、数ｃｍである。意図は、証明者がこの装置を動かすことにある。検証者は、おそらくより強力なマイクロコントローラまたはマイクロプロセッサを使用した同様の装置を使用する。
【００９０】
代表的な用途では、証明者は、検証者により制御されるセキュリティ保護された設備（家、銀行）または機器（ＡＴＭ、車、コンピュータ）へのアクセスを得たい人物である。
【００９１】
セキュリティ
セキュリティパラメータｔ（上記参照）は、９５に設定される。これは、一般に適正なセキュリティであると考えられる。Schnorrを参照願いたい。アイデンティティの数ｄは、ｔ＋ｌｏｇｄ＝１００となるように３２に設定される。
【００９２】
素数ｑは、離散対数を見つけるプロセスにＯ（ｑ１／２）個の「赤ちゃんステップ／巨大ステップ」が存在するため、少なくとも２００ビット長を有する。Schnorrを参照願いたい。一般数体ふるい法の存在と併せて、素数ｐは、約１５００ビットを有する。LaMacchia他著「Computation of discrete logarithms in prime fields」Designs, Codes and Cryptography, Vol. 1, pp. 46-62, 1991を参照願いたい。
【００９３】
証明者
利点として、本発明によるプロトコルは、比較的小量のメモリを使用して動作することができる。小型サイズのメモリは、データ、たとえば鍵、パラメータ、およびテーブルと、ソフトウェア実施プロトコルとを両方とも記憶する。これは、小型サイズの装置ならびにこれもまた本発明を使用することが可能なスマートカードにとって一般的である。スマートカードを使用する場合、データは、光学的ではなく電気的に通信され、物理的なインタフェースを必要とする。
【００９４】
証明者によって行われる主な演算は、剰余乗算である。この乗算は、Ｏ（ｎｌｏｇｎ）ビット演算を採用する、CooleyおよびTukeyの既知の高速フーリエ変換によって実施することができる。Strang G.著「Linear algebra and its applications」Harcourt Brace, 1988を参照願いたい。しかし、この方式は、漸近的に有効であるが、比較的高い複雑性を有する。
【００９５】
したがって、好ましい実施の形態は、予め計算されたテーブルを使用して、手順の複雑性ならびに計算時間を実質的に低減する。各秘密鍵ｓ毎に、メモリは、２１〜２１＋ｌｏｇｑまでの２のべき乗と秘密鍵との積のｑを法とする剰余の、予め計算されたテーブルを記憶する。
【００９６】
秘密鍵を任意所与の数で乗算するため、２のべき乗に対応する剰余は、その数が加算された２進表現で提示される。２１＋ｌｏｇｑのｑを法とする剰余により、ｌｏｇｑビットを有する数を常に有するように、加算を行う際のオーバーフローを低減することができる。
【００９７】
検証者からチャレンジｅ１３１を受け取ったことに応答して、ｅと２１〜２１＋ｌｏｇｑまでの２のべき乗との積のｑを法とする剰余を記憶した同様のテーブルが構築される。このテーブルは、ｅのべき乗を求めるために使用され、秘密鍵の予め計算されたテーブルを使用してｙ＝ｒ＋Σｉｓｉ＊ｅｉ（ｍｏｄ  ｑ）を計算する。この改良により、装置は、各種パラメータのサイズに応じて認証を数秒足らずで完了することができる。
【００９８】
スマートカード
本発明は、財布サイズのスマートカードと併せて使用することも可能である。スマートカードは、かなり多くの用途に使用することが可能である。従来、スマートカードは、通常、電子マネーおよびクレジットの支払いおよび受け取りに使用されている。スマートカードは、公衆電話から電話をかける、文書にサインする、銀行口座にアクセスする、または建物に入場する際にも使用することができる。通常、スマートカードは、不正開放防止となっている。Guillou他著「The smart card: a standardized security device dedicated to public cryptography」Contemporary Cryptology: The Science of Information Integrity, IEEE, pp. 561-613, 1992を参照願いたい。
【００９９】
スマートカードは、通常、公開鍵方式の実行に必要なパラメータを記憶するメモリ（ＲＡＭまたはＰＲＯＭ）を備えた単一のマイクロコントローラからなる。多くのスマートカードシステムは、やりとりに磁気ストライプおよびカードリーダを採用している。スマートカードは、通常、たとえばカードリーダからのように、外部電源に頼る。これにより、障害が起きた電源を有する悪条件の環境に対してスマートカードを不正開放防止にすることが難しくなる。こういったマイクロコントローラは、本発明によるプロトコルを実施するようにプログラムすることができる。
【０１００】
本発明について好ましい実施の形態の例により説明したが、本発明の精神および範囲内で他の様々な適合および変更を行い得ることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内にあるこのような変形および変更をすべて包含することにある。
【０１０１】
付録
Schnorrの認証方式
【０１０２】
プロトコル
Schnorrの認証方式は、離散対数の困難性に基づくものである。２つの素数ｐおよびｑは、ｑ｜ｐ−１のようなものである。位数ｑのＺｐにおける原始根は、α≠１であるようなα、すなわちαｑ≡１（ｍｏｄ  ｐ）のようなものである。素数ｐ、ｑ、およびαは公開される。
【０１０３】
秘密鍵またはアイデンティティは、秘密鍵ｓおよび公開鍵ｖからなる。秘密鍵ｓは、一様にランダムに選択されるｑ未満の非負整数である。公開鍵は、ｖ＝α−ｓ（ｍｏｄ  ｐ）である。
【０１０４】
大半のゼロ知識認証方式のように、Schnorrプロトコルの心臓部は、以下の主なステップを有する。
【０１０５】
開始
証明者が、対応する秘密鍵を所有すると主張する公開鍵を送ることにより、プロトコルを開始する。
【０１０６】
証明者によるコミットメント
証明者が、一様にランダムにｑ未満の非負数ｒを選択する。証明者は、ｘ＝αｒ（ｍｏｄ  ｐ）を検証者に送る。
【０１０７】
検証者からのチャレンジ
検証者は、一様にランダムに選択される２ｔ未満の非負数ｅを選択する。数ｔは、プロトコルの健全性を特徴付けるセキュリティパラメータである。検証者は、ｅを証明者に送る。
【０１０８】
証明者からのレスポンス
証明者は、ｙ＝ｒ＋ｓ＊ｅ（ｍｏｄ  ｑ）を計算する。証明者は、ｙを検証者に送る。検証者は、ｘ＝αｙ＊ｖｅ（ｍｏｄ  ｐ）であるかをチェックし、等式が真の場合にのみ証明者の主張を受理する。
【０１０９】
完全性
正直な検証者がこのプロトコルに携わり、確率１をもってアイデンティティを検証者に対して証明することができることは明らかである。
【０１１０】
健全性
不正な証明者は、前もって正確なチャレンジｅを推測し、コミットメントｘ＝αｒｖｅ（ｍｏｄ  ｐ）を送信することによってだますことができる。ここで、レスポンスは、ｙ＝ｒであるものが選択される。しかし、この攻撃が成功する確率は、２−ｔである。成功率は、離散対数の計算が容易にならない限り増大し得ない。
【０１１１】
ゼロ知識
このプロトコルは、同じコミットメントｒを有する２つの写しを生成することができることから知識の証明であり、離散対数（ｌｏｇαｖ＝（ｙ−ｙ’）／（ｅ−ｅ’）（ｍｏｄ  ｑ））の計算は容易である。無視できない成功確率を有する不正な証明者が存在する場合、この不正な証明者を繰り返しシミュレートすることにより、同じコミットメントを有する２つの写しを明らかにすることが可能であるため、プロトコルは、知識の証明であることが実証される。
【０１１２】
明らかに、正直な検証者の場合、同じ分布を有する写しを生成することが可能であり、したがって、プロトコルは、正直検証者ゼロ知識である。しかし、このプロトコルは、不正直な検証者がコミットメントに依存するチャレンジを選択し得ることから、一般的な場合ではゼロ知識ではない。これにより、同じ分布を有する写しの生成が困難になる。しかし、非公式に、情報が露呈されない理由は、数ｘおよびｙが本質的にランダムであるためである。
【図面の簡単な説明】
【０１１３】
【図１】本発明によるゼロ証明認証プロトコルの図である。
【図２】図１のプロトコルを使用する装置の概略図である。
【図１】
0004651996.tif 000002
【図２】
0004651996.tif 000003