(57)【要約】【課題】無線タグデータの認証を行うために利用できる軽量の認証プロトコルによる認証システムを提供する。【解決手段】秘密鍵情報を記憶する秘密鍵記憶部と、チャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部と、乱数ビットを発生させる乱数ビット発生器と、秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部と、前記制御部により制御されて乱数ビットに基づいて二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部を備える。【選択図】図３
2008205675.tif 000002
【特許請求の範囲】
【請求項１】
認証プロトコルにより無線タグデータの認証を行うための認証システムであって、
秘密鍵情報を記憶する秘密鍵記憶部と、
チャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部と、
乱数ビットを発生させる乱数ビット発生器と、
秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部と、
前記制御部により制御されて乱数ビットに基づいて、ビット欠落、ビット挿入、ビット反転を伴う二元通信路の役割を模倣した処理を実行してレスポンスデータを出力する出力処理部と
を備えることを特徴とする認証システム。
【請求項２】
認証プロトコルにより無線タグデータの認証を行うための認証システムであって、
２つの秘密鍵情報を記憶する秘密鍵記憶部と、
チャレンジデータおよび２つの秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部と、
ランダムビットを発生させる乱数ビット発生器と、
秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部と、
前記制御部により制御されて乱数ビットに基づいて、ビット欠落、ビット挿入、ビット反転を伴う通信路の役割を模倣した処理を実行してレスポンスデータを出力する出力処理部と
を備えることを特徴とする認証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、認証プロトコルにより無線タグデータの認証を行うための認証システムに関するものであり、更に詳細には、無線タグ（ＲＦＩＤ）等電力や計算資源が制限された機器に適したチャレンジ・レスポンス通信に基づく情報の挿入、喪失、反転を伴う二元通信路のモデルを利用した新しい軽量の認証プロトコルによる認証システムに関するものである。
【背景技術】
【０００２】
非常に制限された実装条件のもとでの応用における、軽量の認証プロトコルの設計は、研究者の間でも解決困難な問題として広く認識されている。そのような実装環境の問題をもつ例として、無線タグとして利用されるＲＦＩＤ（ｒａｄｉｏ−ｆｒｅｑｕｅｎｃｙ  ｉｄｅｎｔｉｆｉｃａｉｏｎ）における認証の問題がある。ＲＦＩＤシステムにおける認証法については、近年、非特許文献９および非特許文献１０といった論文が発表されている。
【０００３】
一方、非特許文献６においては、これらの論文で使用されている手法の安全性、具体的には、非特許文献９で見積もられている安全性の余裕度（ｍａｒｇｉｎ）は、主張されているものよりも低いことが指摘されている。非特許文献６では、非特許文献6で提案された認証法がその不正困難性の根拠としているＬＰＮ（Ｌｅａｒｎｉｎｇ  Ｐａｒｉｔｙ  ｗｉｔｈ  Ｎｏｉｓｅ）問題を効率的に解く新しいアルゴリズムが提案され、その性能が評価されている。
【０００４】
このアルゴリズムは、近年提案された「高速相関攻撃（ｆａｓｔ  ｃｏｒｒｅｌａｔｉｏｎ  ａｔｔａｃｋ）」の改良版に基づいて構成されており、同様に「破棄（ｄｅｃｉｍａｔｉｏｎ）」、「一次結合（ｌｉｎｅａｒ  ｃｏｍｂｉｎｉｎｇ）」、「仮説（ｈｙｐｏｔｈｅｓｉｚｉｎｇ）」、「最小距離復号法（ｍｉｎｉｍｕｍ  ｄｉｓｔａｎｃｅ  ｄｅｃｏｄｉｎｇ）」といった概念を採用している。高速相関攻撃とは異なり、ＬＰＮ問題においては、その性質上、全く前処理を行うことが許されないという性質がある。
【０００５】
そこで提案されたアルゴリズムは、先にＢｌｕｍ，Ｋａｌａｉ，Ｗａｓｓｅｒｍａｎによって提案され、これまで最強の攻撃と言われていたＢＫＷアルゴリズムよりも強力な攻撃法である。実際のところ、ＢＫＷアルゴリズムは、提案されたアルゴリズムの特殊な場合であることが示されている。ただし、ＢＫＷアルゴリズムでは、非特許文献６で提案されているパラメータの最適化がなされていない。
【０００６】
非特許文献６では、ＲＦＩＤ認証プロトコルとして、ＨｏｐｐｅｒとＢｌｕｍにより提案されたＨＢプロトコルと、その改良版であるＨＢ＋プロトコル（非特許文献９を参照）について、受動的攻撃（すなわち攻撃者がシステムに働きかけない、例えば、盗聴や正規の通信のみで得た情報を用いた攻撃）を仮定した環境における詳細な安全性評価を行っている。
【０００７】
非特許文献６では、提案アルゴリズムを用い、ＨＢプロトコルの安全性が再評価されている。そこでは、提案時に報告された安全性の余裕度は、良く見積もられ過ぎていることが明らかにされた。
【０００８】
その他の認証システムに関係する技術として、次に例示している非特許文献１〜２０が参照できる。
【非特許文献１】E.R. Berlekamp,R.J. McEliece, and H.C.A. van Tilborg, "On the Inherent Intractability of  Certain Coding Problems", IEEE Trans.Info. Theory, vol. 24, pp. 384-386, 1978.
【非特許文献２】A. Blum, A.Kalai and H. Wasserman, "Noise-Tolerant Learning, the Parity Problem, andthe Statistical Query Model", Journal of the ACM, vol. 50, no. 4, pp.506-519, July 2003.
【非特許文献３】P. Chose, A.Joux and M. Mitton, "Fast Correlation Attacks: An Algorithmic Point ofView", EUROCRYPT2002, Lecture Notes in Computer Science, vol. 2332, pp.209-221, 2002.
【非特許文献４】E. Drinea and M.Mitzenmacher, "On Lower Bounds for the Capacity of DeletionChannels", IEEE Trans. Inform. Theory, vol. 52, pp. 4648-4657, Oct. 2006.
【非特許文献５】M.P.C.Fossorier, M.J. Mihaljevic and H. Imai, "A Unified Analysis for the FastCorrelation Attack", 2005 IEEE Int. Symp. Inform. Theory - ISIT'2005, Adelaide, Australia,Sept. 2005, Proceedings, pp. 2012-2015 (ISBN 0-7803-9151-9).
【非特許文献６】M.P.C.Fossorier, M.J. Mihaljevic, H. Imai, Y. Cui and K. Matsuura, "An Algorithmfor Solving the LPN Problem and its Application to Security Evaluation of theHB Protocols for RFID Authentication", INDOCRYPT2006, Lecture Notes inComputer Science, vol. 4329, pp. 48-62, 2006.
【非特許文献７】H. Gilbert, M.Robshaw and H. Sibert, "An Active Attack against HB+ - a Provably SecureLightweight Authentication Protocol", IACR, Cryptology ePrint Archive,Report 2005/237, July 2005. Available at http://eprint.iacr.org/2005/237.
【非特許文献８】N. Hopper and M.Blum, "Secure Human Identification Protocols", ASIACRYPT 2001,Lecture Notes in Computer Science, vol. 2248, pp. 52-66, 2001.
【非特許文献９】A. Juels and S.Weis, "Authenticating Pervasive Devices with Human Protocols",CRYPTO2005, Lecture Notes in Computer Science, vol. 3621, pp. 293-308, 2005.Updated version available at:http://www.rsasecurity.com/rsalabs/staff/bios/ajuels/publications/pdfs/lpn.pdf.
【非特許文献１０】J. Katz andJ.S. Shin, "Parallel and Concurrent Security of the HB and HB+Protocols", EU-ROCRYPT2006, Lecture Notes in Computer Science, vol. 4004, pp.73-87, 2006.
【非特許文献１１】M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "A General Formulation ofAlgebraic and Fast Correlation Attacks Based on Dedicated SampleDecimation", AAECC2006, Lecture Notes in Computer Science, vol. 3857, pp.203-214, 2006.
【非特許文献１２】M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "Cryptanalysis of KeystreamGenerator by Decimated Sample Based Algebraic and Fast CorrelationAttacks", INDOCRYPT2005, Lecture Notes in Computer Science, vol. 3797, pp.155-168, Dec. 2005.
【非特許文献１３】M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "A low-complexity andhigh-performance algorithm for the fast correlation attack", FSE2000,Lecture Notes in Computer Science, vol. 1978, pp. 196-212, 2001.
【非特許文献１４】[14] M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "Fast Correlation AttackAlgorithm with List Decoding and an Application", FSE2001, Lecture Notesin Computer Science, vol. 2355, pp. 196-210, 2002.
【非特許文献１５】[15] M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "Key management with minimizedsecret storage employing an erasure channel approach", IEEE CommunicationsLetters, vol. 9, pp. 741-743, Aug. 2005.
【非特許文献１６】[16] M.Mitzenmacher and E. Drinea, "A Simple Lower Bound for the Capacity of the DeletionChannel", IEEE Trans. Inform. Theory, vol. 52, pp. 4657-4660, Oct. 2006.
【非特許文献１７】D. Wagner,"A Generalized Birthday Problem," CRYPTO '02, Lecture Notes inComputer Science, vol. 2442, pp. 288-304, 2002.
【非特許文献１８】M.J.Mihaljevic, M.P.C. Fossorier and H. Imai, "Key management with minimizedsecret storage employing an erasure channel approach", IEEE CommunicationsLetters, vol. 9, pp. 741-743, Aug. 2005.
【非特許文献１９】E. Drinea andM. Mitzenmacher, "On Lower Bounds for the Capacity of DeletionChannels", IEEE Trans. Inform. Theory, vol. 52, pp. 4648-4657, Oct. 2006.
【非特許文献２０】M. Mitzenmacherand E. Drinea, "A Simple Lower Bound for the Capacity of the DeletionChannel", IEEE Trans. Inform. Theory, vol. 52,
【発明の開示】
【発明が解決しようとする課題】
【０００９】
［ＲＦＩＤシステムと認証における問題点］
ＲＦＩＤシステムは、全体として非常に複雑なものとなる場合が多いが、一般的に商用で用いられる場合は、大きくまとめると以下のような３つのサブシステムから構成される。
（１）ＲＦサブシステム；これは、個々のＲＦＩＤを識別する部分と無線通信を用いた、それに関係する処理を担当する部分からなる。
（２）エンタープライズサブシステム；これはＲＦサブシステムから取得したデータを、サポートしている商用サービスで役立てるために、保持、処理、分析を行うシステムである。システム用に作成されたソフトウェアを動作させるコンピュータを含んでいる。
（３）相互エンタープライズサブシステム；情報を地理的あるいは組織的な境界を超えて共有する必要があるとき、エンタープライズサブシステムに接続されるシステムである。
【００１０】
各ＲＦＩＤシステムにはＲＦサブシステムがあり、ほぼ全てのＲＦＩＤシステムには、エンタープライズサブシステムがある。無線を用いたＲＦＩＤ識別を可能とするため、ＲＦサブシステムは次の２つの部分から構成されている。
【００１１】
（ａ）ＲＦＩＤタグ（中継器と呼ばれることもある）は、非常に小さな電子機器であり、物体に貼られたり埋め込まれたりする。各ＲＦＩＤタグは、固有の識別番号（ＩＤ）を持っており、必要な場合には付加的な情報を記憶するためのメモリや環境センサー、セキュリティ機能等、他の機能を持っていることもある。
（ｂ）ＲＦＩＤ問い合わせ器（しばしばリーダと呼ばれる）は、各ＲＦＩＤタグが何に付けられているのかを検知したり、ＲＦＩＤタグが付けられている物と関係するデータを関連付けるために、ＲＦＩＤタグと無線通信を行う。
【００１２】
ＲＦＩＤタグとＲＦＩＤリーダは双方向無線通信を行う。それぞれにアンテナを持ち、無線信号の変調復調機能を有する。ＲＦＩＤタグの主要なセキュリティ問題の一つは、ＲＦＩＤタグがＲＦＩＤリーダに認証してもらうという機能を実現する認証プロトコルである。ＲＦＩＤタグは、多くのシナリオにおいて、非常に制限された容量（データ処理能力および記憶容量）しか持たず、したがって、軽量の認証プロトコルしか対応できないようなシステム部品である。
【００１３】
［ＲＦＩＤ認証のためのＨＢプロトコル］
ＨｏｐｐｅｒとＢｌｕｍによる先駆的な研究に続いて発表された非特許文献９では、２つの共有された鍵を用いた認証プロトコルが提案され、分析されている。それらは非常に小さな計算コストしか要求しないため、ＲＦＩＤタグのような低価格な機器でも適用可能となっている。ＨＢプロトコルと呼ばれる最初のプロトコルでは、受動的な（盗聴のみを行う）攻撃者に対して安全性が証明されている。
【００１４】
一方、二番目に提案された（ＨＢ＋プロトコルと呼ばれる）プロトコルでは、能動的な攻撃者を考慮に入れた、より強いクラスの安全性が証明されている。これらの二つのプロトコルの安全性は、雑音存在下におけるパリティ値の同定“ｌｅｒｎｉｎｇ  ｐａｒｉｔｙ  ｗｉｔｈ  ｎｏｉｓｅ”（ＬＰＮ）問題が困難であるという仮定に基づいている（例えば、非特許文献２参照）。
【００１５】
非特許文献９では、ＨＢプロトコルとＨＢ＋プロトコルが平行に、あるいは並列に実行された場合の安全性が証明されている。ＨＢプロトコルが基礎にしている理論的な枠組みは、次のとおりである。
【００１６】
具体例で説明する。認証対象のタグ「Ａｌｉｃｅ」と計算デバイス（リーダ）「Ｃ」がｋビットの秘密情報ｘを共有しているとする。そして、「Ａｌｉｃｅ」が「Ｃ」に対して自分を認証させようとしている場面（認証プロトコル）を考える。このとき、「Ｃ」は、ランダムにチャレンジデータａ∈｛０，１｝ｋを選び、それを「Ａｌｉｃｅ」に送る。「Ａｌｉｃｅ」は、内積（ａ・ｘ）を計算し、その結果を「Ｃ」に返す。「Ｃ」は内積（ａ・ｘ）を計算し、「Ａｌｉｃｅ」のパリティビットが正しければ、この１ラウンドの認証が成功したと判断して受理する。ある１ラウンドにおいて、「Ａｌｉｃｅ」に成りすまそうとする秘密情報ｘを知らないユーザが、正しい内積（ａ・ｘ）の値を推測する確率は１／２である。この１ラウンド認証をｒ回繰り返すことにより、「Ａｌｉｃｅ」はこの単純なパリティの推測の全てに成功する確率を２−ｒに減らすことができる。
【００１７】
しかし、盗聴を行っているユーザが、「Ａｌｉｃｅ」と「Ｃ」の間で行われたＯ（ｋ）の数の正しいチャレンジ・レスポンスの値の組を得ることができると、盗聴者はガウスの消去法を用いることで、すぐに秘密情報ｘの値を計算することができる。受動的な攻撃を行う盗聴者が秘密情報ｘを計算することを防ぐため、「Ａｌｉｃｅ」はレスポンス値に雑音を入れるようにする。「Ａｌｉｃｅ」は、わざとｐ∈（０，１／２）の範囲内の定数確率で誤ったレスポンスを送る。このとき「Ｃ」は、「Ａｌｉｃｅ」のＩＤを、誤り回数がｐｒより小さかったときに認証する。
【００１８】
盗聴者、すなわち受動的な攻撃者が、複数に実行されたＨＢプロトコルのｑラウンドを盗聴し、成りすましを試みた場合を考える。各チャレンジデータａは行列Ａのある行の値であるとする。同様に、レスポンスの集合をベクトルｚとみなす。
【００１９】
チャレンジデータａの集合Ａが与えられたとき、攻撃者が行う自然な攻撃として、秘密情報であるベクトルｘを計算することが考えられる。言い換えれば、攻撃者は、ＨＢプロトコルにおけるチャレンジデータａの集合Ａが与えられたとき、雑音を少量含むレスポンスデータの集合ｚを計算するのに使用された秘密情報ｘを計算しようとするかもしれないということである。
【００２０】
このような場合における攻撃者の目標は、ここで分析している主要な問題と同じものとなる。この問題は、雑音を伴う状況においてパリティを推定する問題、ＬＰＮ問題（ｔｈｅ  ｌｅｒｎｉｎｇ  ｐａｒｉｔｙ  ｉｎ  ｔｈｅ  ｐｒｅｓｅｎｃｅ  ｏｆ  ｎｏｉｓｅ），として知られている。非特許文献９では、ＨＢ、ＨＢ＋プロトコル両方において、受動的な攻撃者に対する安全性は、ＬＰＮ問題を解く難しさに依存していることが示されている。
【００２１】
一方、非特許文献７では、ＨＢ＋プロトコルに対する中間者攻撃（ｍａｎ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅ  ａｔｔａｃｋ）が報告されている。しかしながら、非特許文献９および非特許文献１０で与えられた次の議論は、そのような攻撃法の影響が限定的なものであることを示している。
【００２２】
非特許文献１０（の７６ページ）によれば、非特許文献７の攻撃が成功してプロトコルを弱体化できるとしても、それがより弱い攻撃モデルにおけるＨＢ／ＨＢ＋プロトコルの安全性を議論する必要がないことを意味するわけではない。効率性と安全性の間にはトレードオフがあり、本発明者らの研究成果によると、ＨＢ／ＨＢ＋プロトコルにもこのトレードオフが存在することが言える。
【００２３】
さらに、非特許文献９の付録Ａにおいては、認証が数多く失敗した場合に直ちに警告するような検知機能を備えたシステムにおいて、非特許文献７の中間者攻撃が適用できないことが述べられている。さらに言えば、特に、ＲＦＩＤシステムのような短距離通信を行う場合には、中間者攻撃が非常に難しいという事実がある。したがって、本発明による認証システムにおいては、後述するように、ＨＢ／ＨＢ＋プロトコルに対するＬＰＮ問題と受動的な攻撃のみに注目している。
【００２４】
［二元対称通信路を使用したＨＢプロトコルのモデル］
二元対称通信路を使用したＨＢ／ＨＢ＋プロトコルのモデルは、それぞれ図１および図２のように与えられる。図１は、ＨＢプロトコルの１つのラウンド処理のモデル化を説明する図であり、図２は、ＨＢ＋プロトコルの１つのラウンド処理のモデル化を説明する図である。図１において、１０は秘密鍵情報を記憶する秘密鍵記憶部、１１はチャレンジデータと秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部、１２は乱数ビットを発生させる乱数ビット発生器、１３は二元対称通信路によるビット反転通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部である。また、図２において、２０は２つの秘密鍵情報を記憶する秘密鍵記憶部、２１はチャレンジデータと２つの秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部、２２は乱数ビットを発生させる乱数ビット発生器であり、２３は二元対称通信路によるビット反転通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部である。
【００２５】
図１に示すチャレンジ・レスポンス通信のＨＢプロトコルによるシステムについて、概略の動作を説明する。チャレンジデータが内積データ生成部１１に入力されると、内積データ生成部１１が、秘密鍵記憶部１０に記憶している秘密鍵情報を読み出し、チャレンジデータと秘密鍵情報の内積演算によるパリティチェックのためのデータを生成し、出力処理部１３に供給する。出力処理部１３では、内積データ生成部１１からのデータと、乱数ビット発生器１２からの乱数ビットにより、二元対称通信路におけるビット反転の役割を果たす処理を実行してレスポンスデータを出力する。このようなチャレンジ・レスポンス通信の１つのラウンドの処理を行い、認証プロトコルを実行する。
【００２６】
図２に示すチャレンジ・レスポンス通信のＨＢ＋プロトコルによるシステムについても同様に動作する。概略の動作を説明すると、チャレンジデータが内積データ生成部２１に入力されると、内積データ生成部２１が、秘密鍵記憶部２０に記憶している２つの秘密鍵情報を読み出し、チャレンジデータと２つの秘密鍵情報の内積演算によるパリティチェックのためのデータを生成し、出力処理部２３に供給する。出力処理部２３では、内積データ生成部２１からのデータと、乱数ビット発生器２２からの乱数ビットにより、二元対称通信路におけるビット反転の役割を果たす処理を実行してレスポンスデータを出力する。
【００２７】
［ＨＢプロトコルおよびＲＦＩＤ認証用ＨＢプロトコルの安全性再評価］
ＨＢプロトコルの安全性は、ＬＰＮ問題を解く困難性“ｌｅａｒｎｉｎｇ  ｐａｒｉｔｙ  ｗｉｔｈ  ｎｏｉｓｅ”に依存している（非特許文献９および非特許文献１０の例を参照）。
ＬＰＮ問題を形式的に定義するために、次のような記法を導入する：
（１）ｘ＝［ｘｉ］ｋｉ＝１は、ｋ次元の二元ベクトルを表す。
（２）Ｇ＝［ｇｉ］ｎｉ＝１は、ｋ×ｎ二元行列を表し、各ｇｉ＝［ｇｉ（ｊ）］ｋｊ＝１は、ｋ次元の二元列ベクトルを表す。
（３）ｙ＝［ｙｉ］ｎｉ＝１，ｚ＝［ｚｉ］ｎｉ＝１は、ｎ次元二元ベクトルを表す。
（４）各ｉ＝１，２，…，ｎに対して、ｅｉを二元確率変数Ｅｉの実現値、Ｐｒ（Ｅｉ＝１）＝ｐかつＰｒ（Ｅｉ＝０）＝１−ｐとし、全ての確率変数Ｅｉは互いに独立であるとする。
【００２８】
ベクトルＧとベクトルｘに対して、ベクトルｙとベクトルｚは次のように計算される：ｙ＝ｘ・Ｇ，ｚｉ＝ｙｉ(＋)ｅｉ，ｉ＝１，２，３，…，ｎ．したがって、この説明に関係しているＬＰＮ問題は、次のように形式的に定義される。すなわち、ＬＰＮ問題とは「Ｇ，ｚ，ｐが与えられたとき、秘密情報ｘを復元する問題」である。
【００２９】
ＨＢプロトコルの安全性評価に関する問題は、次の２つの処理にまとめられる。
（１）プロトコルが実行されている間に交換されたチャレンジとレスポンスを記憶することによる解読のためのサンプル収集と、関係するＬＰＮ問題を定義する行列Ｇとベクトルｚを作成すること。すなわち、各チャレンジデータは、行列Ｇの列ベクトルｇｉとして記録され、さらに、それぞれに対応するレスポンスデータはベクトルｚの要素ｚｉとして記録される。
（２）得られたデータによりＬＰＮ問題を解くこと。
【００３０】
非特許文献６においては、そこで提案され解析されたＬＰＮ問題を解く新しいアルゴリズムと、そのアルゴリズムのＨＢプロトコルが提案された際に主張している安全性余裕度への影響分析が報告されている。このアルゴリズムは、近年提案された高速相関攻撃の改良版をもとにしており、「破棄（ｄｅｃｉｍａｔｉｏｎ）」、「一次結合（ｌｉｎｅａｒ  ｃｏｍｂｉｎｉｎｇ）」、「仮説（ｈｙｐｏｔｈｅｓｉｚｉｎｇ）」、「最小距離復号法（ｍｉｎｉｍｕｍ  ｄｉｓｔａｎｃｅ  ｄｅｃｏｄｉｎｇ）」といった概念を採用している。しかしながら、一般の高速相関攻撃とは異なり、ＬＰＮ問題においてはその性質上、全く前処理を行うことが許されないという性質がある。この提案されたアルゴリズムは、Ｂｌｕｍ，Ｋａｌａｉ，Ｗａｓｓｅｒｍａｎによって提案され、これまで最強の攻撃と言われていたＢＫＷアルゴリズムよりも強力な攻撃法である。実際のところ、ＢＫＷアルゴリズムは、この提案されたアルゴリズムの特殊な場合であること（ただし、ＢＫＷアルゴリズムでは、パラメータの最適化がされていない）が示されている。
【００３１】
本発明は、このような従来の問題点を解決するためになされたものであり、本発明の目的は、例えば、無線タグデータの認証を行うために利用できる軽量の認証プロトコルによる認証システムを提供することであり、本発明の他の目的は、無線タグ（ＲＦＩＤ）等電力や計算資源が制限された機器に適したチャレンジ・レスポンス通信に基づく情報の挿入、喪失、反転を伴う二元通信路のモデルを利用した新しい軽量の認証プロトコルによる認証システムを提供することにある。
【課題を解決するための手段】
【００３２】
上記のような目的を達成するため、本発明による軽量の認証プロトコルによる認証システムは、基本的には、二元対称通信路モデルを用いたチャレンジ・レスポンス通信による軽量の認証プロトコルを設計する際の問題点を解決する方法を提供する。本発明の認証システムにおいては、特に、軽量の認証プロトコルについて、その設計法の包括的な理論的枠組みを構築する。この枠組みを利用することにより、これまでに提案されてきた同種のプロトコルと比較し、実装の複雑度においては同等程度で実現でき、安全性においてはより高い安全性を満たす軽量の認証プロトコルによる認証システムを提供するものとなっている。
【００３３】
具体的には、本発明による認証システムは、第１の態様として、秘密鍵情報を記憶する秘密鍵記憶部と、チャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部と、乱数ビットを発生させる乱数ビット発生器と、秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部と、前記制御部により制御されて乱数ビットに基づいて二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部とを備えることを特徴とする。
【００３４】
また、本発明による認証システムは、第２の形態として、２つの秘密鍵情報を記憶する秘密鍵記憶部と、チャレンジデータおよび２つの秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部と、乱数ビットを発生させる乱数ビット発生器と、秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部と、前記制御部により制御されて乱数ビットに基づいて二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部とを備えることを特徴とする。
【発明の効果】
【００３５】
本発明の認証システムによれば、二元通信路モデルを用いた確率的チャレンジ・レスポンス手法を用いた認証プロトコルについて、その包括的な枠組みが提供されて、確率的な振舞の性質を二元対称通信路を含む、より一般的な雑音を伴う通信路モデルを利用してモデル化された認証プロトコルにより無線タグの認証を行うための認証システムが構成される。このモデルは、これまでに提案されてきた手法とは異なり、認証システムが、確率的な振舞の性質を乱数ビットに基づいて二元通信路モデルにおいて情報の消失、挿入、反転を起こすような雑音を伴う通信路モデルを使用してモデル化しており、これまでに提案されてきた同種のプロトコルと比較し、実装の複雑度においては同等程度で実現でき、安全性においてはより高い安全性を満たす軽量の認証プロトコルによる認証システムとなっている。
【発明を実施するための最良の形態】
【００３６】
［軽量の認証プロトコルの基本的な概念］
先に考察されたＨＢプロトコルの安全性の問題は、次のようにまとめられる。
（１）二元対称通信路の雑音に対応するＨＢプロトコルの確率的次数の問題；および
（２）ＬＰＮ問題を解く困難性に対応するＨＢプロトコルのセキュリティの問題：
【００３７】
したがって、ＨＢプロトコルと同様の制限のある実装条件で実行される本発明による軽量の認証プロトコルを構築する上での主要な概念は、次のようなものである。
（ａ）確率的なチャレンジ・レスポンス通信で、より複雑なモデルを使用する。
（ｂ）新たなプロトコルの安全性をＬＰＮ問題より複雑な問題に帰着させる。
（ｃ）ビットの消失、挿入、反転を伴う二元通信路を使用した軽量認証プロトコルのモデルのシステムである。
【００３８】
新種の認証プロトコルのための新しい枠組みは、ビットの消失、挿入、反転を伴う二元通信路の理論的枠組みに基づいている。この新しい軽量の認証プロトコルのモデルは次のような重要な特徴を持っている。
（１）同じ実装コストでより高い安全性を提供する。
（２）これまで報告されてきた二元対称通信路の枠組みを使った手法とは異なった、別の手法を利用している。
（３）次のような役割を果たす制御論理の処理を行う制御部の使用を基礎にしている。
（３ａ）秘密鍵およびラウンドの最初のチャレンジデータが出力処理を制御する。
（３ｂ）内積データが計算されるかどうかを決定する。内積データはｑ＜１の確率で計算される。このことは、全内積データの複雑度評価を低減させることを意味する。
【００３９】
本発明により提供される軽量の認証プロトコルとしては、次の二つのプロトコルが提案される。
（４）プロトコル１：受動的およびある種の能動的攻撃に対して安全な認証プロトコルである。
（５）プロトコル２：受動的および一般的な能動的攻撃に対して安全な認証プロトコルである。ただし、中間者攻撃は考慮しない。プロトコル１に比べると多少実装複雑度は上がる。
【００４０】
プロトコル１およびプロトコル２の２つの認証プロトコルによるモデルの認証システムの構成が、それぞれ図３および図４に示される。また、図５および図６には、それぞれプロトコル１およびプロトコル２による制御部の構成を示している。
【００４１】
図３は、本発明による認証システムにおける受動的攻撃に基づく安全性を提供するプロトコル１の１つのラウンド処理のモデルを説明する図である。図３において、３０は秘密鍵情報を記憶する秘密鍵記憶部、３１はチャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する内積データ生成部、３２は乱数ビットを発生させる乱数ビット発生器、３３は制御部により制御されて乱数ビットに基づいて二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部、３４は秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部である。
【００４２】
ここで、認証システムにおける受動的攻撃に基づく安全性を提供するプロトコル１の１つのラウンド処理は、次のように行われる。秘密鍵記憶部３０は認証プロトコルにより認証を行うための秘密鍵情報を記憶しており、チャレンジデータが内積データ生成部３１に与えられると、内積データ生成部３１が、チャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する。乱数ビット発生器３２は、乱数ビットを発生させて、出力処理部３３に供給する。制御部３４は、秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う。出力処理部３３は、制御部３４により制御されて、乱数ビット発生器３２からの乱数ビットに基づいて、二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する。
【００４３】
プロトコル１による制御部３４の構成は、図５に示すように、キースストリーム発生器９１および制御論理部９２から構成されている。キーストリーム発生器９１は、ラウンド処理をトリガするためのチャレンジデータが入力されると、秘密鍵情報に基づいて疑似乱数ビット列を生成し、制御論理部９２に供給する。制御論理部９２では、疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う。
【００４４】
図４は、本発明による認証システムにおける能動的攻撃に基づく安全性を提供するプロトコル２の１つのラウンド処理のモデルを説明する図である。図４のシステムで使用される秘密鍵ｘと秘密鍵ｙの情報は、２つの秘密鍵情報を表す二元ベクトルである。図４において、４０は２つの秘密鍵情報を記憶する秘密鍵記憶部、４１は２つの秘密鍵情報の内積によるパリティチェックのためのデータを生成する内積データ生成部であり、４２は乱数ビットを発生させる乱数ビット発生器、４３は制御部により制御されて乱数ビットに基づく二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する出力処理部、４４秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う制御部である。
【００４５】
ここで、認証システムにおける能動的攻撃に基づく安全性を提供するプロトコル２の１つのラウンド処理は、次のように処理が行われる。秘密鍵記憶部４０は２つの秘密鍵情報を記憶しており、チャレンジデータが内積データ生成部４１に与えられると、内積データ生成部４１が、チャレンジデータおよび秘密鍵情報の内積演算によるパリティチェックのためのデータを生成する。乱数ビット発生器４２は乱数ビットを発生させており、発生された乱数ビット列を出力処理部４３および内積データ生成部に供給する。制御部４４は、秘密鍵情報に基づくキーストリームにより生成された疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う。出力処理部４３では、制御部４４により制御されて乱数ビットに基づいて二元通信路によるビット欠落、ビット挿入、ビット反転の通信路の役割を果たす処理を実行してレスポンスデータを出力する。
【００４６】
プロトコル２による制御部４４の構成は、図６に示すように、キースストリーム発生器１０１および制御論理部１０２から構成されている。キーストリーム発生器１０１は、ラウンド処理をトリガするためのチャレンジデータが入力されると、秘密鍵情報に基づいて疑似乱数ビット列を生成し、制御論理部１０２に供給する。制御論理部１０２では、疑似乱数ビット列に基づいてビット反転の制御、乱数ビット挿入の制御、内積データ評価の制御の各制御処理を行う。ここでのキーストリーム発生器１０１には、目隠し因子ｂが乱数ビット発生器２２から供給されて、疑似乱数ビット列の生成について更にランダム化される。
【００４７】
［認証プロトコルとラウンド処理の説明］
認証処理は、複数のラウンドのチャレンジ・レスポンスプロトコルに基づいて処理を実行する。各ラウンドは、次のような二種類のどちらかのラウンドから構成されている。
（１）プロトコルの有効なラウンド（認証それ自体と安全性に関連がある）。
（２）プロトコルのダミーラウンド（安全性を拡張するものである）。
【００４８】
Ｎ，Ｌ，η，およびΔが適当な値を取るパラメータであるとした場合に、本発明の認証システムで提供される認証プロトコルの枠組みは次のようになる。
（１）各プロトコルは、リーダに対してタグのＮ（＝ＮＥ＋ＮＤ）ラウンドの認証処理を行う。ここでＮＥは有効なラウンド数、ＮＤはダミーのラウンド数を表す。
（２）各ラウンドは１回のチャレンジ・レスポンス通信から構成される。かく乱するための要素を含むチャンレンジデータは、Ｌ次元の二元ベクトルであり、レスポンスデータは１ビットの情報である。
（３）リーダ側において、各ラウンドの結果は、受け取ったレスポンスデータのビットと自身で計算した正当なレスポンスデータの値に基づき、「ラウンド受理」あるいは「ラウンド拒否」のどちらかとなる。
（４）与えられたプロトコルパラメータηに対し、もし、ラウンド拒否の総数がＮＥ＋Δ＜＜Ｎ／２より少なかった場合、プロトコルは正当な認証が行われたと判断する。もし、正当な認証であると判断した場合、ＲＦＩＤリーダは正当なＲＦＩＤタグと通信していると判断する。
【００４９】
ＲＦＩＤリーダが正当なＲＦＩＤタグと通信している場合には、それらの間で共通の秘密鍵が共有されていること、ＲＦＩＤリーダはどのラウンドが有効で、どのラウンドがダミーであるかがわかっていること、を意味することに注目すべきである。
【００５０】
本発明によるプロトコル１の有効なラウンドとダミーのラウンドは、それぞれ図７および図８に例示されている。図７は、プロトコル１の有効ラウンドの間のメッセージ交換を説明する図であり、図８は、プロトコル１のダミーラウンドの間のメッセージ交換を説明する図である。
【００５１】
また、本発明によるプロトコル２の有効なラウンドとダミーのラウンドは、それぞれ図９および図１０に例示されている。図９は、プロトコル２の有効ラウンドの間のメッセージ交換を説明する図であり、図１０は、プロトコル２のダミーラウンドの間のメッセージ交換を説明する図である。
【００５２】
［本発明の認証プロトコルとＨＢプロトコルが基礎としている概念の比較］
従来の手法と新たに提供される本発明による認証プロトコルにおける手法が基礎としているアイデアを比較し、次のように同じ部分と異なる部分にまとめられる。
（１）同じ部分
（１ａ）認証のために、チャレンジ・レスポンスの通信を通じ、複数のパリティチェックを使用する。
（１ｂ）攻撃者にパリティチェックの入手手段を、雑音を伴う通信路からのみに強制する。
（２）異なる部分
（２ａ）新たなアプローチでは、従来のものとは異なる雑音を伴う通信路を使用することを強制する。
（２ｂ）既存の手法と提案手法の安全性根拠を比較すると次のようなことが言える。従来の認証プロトコルでは、確率ｐ（典型的にはｐ＜０．２５）をとる二元対称通信路を通して見たパリティチェックでＬＰＮ問題を解く困難性に安全性根拠を置いていることを意味する。
（２ｃ）本発明による認証プロトコルでは、ビットの消失、挿入、反転を伴う二元通信路を通して見たパリティチェックで、より複雑な系列を比較する問題の困難性を安全性の根拠にしていることを意味する。
【００５３】
［安全性評価における注意］
本発明の認証プロトコルの安全性は、ビットの消失、挿入、反転を伴う二元通信路における、復号複雑度であるとみなせる。正当なタグのみが正しい有効ラウンドのビット列とダミーラウンドのビット列を生成することができる、ということは、正当なリーダにとっては、正当なタグとの通信の認証処理が、二元対称通信路における復号問題という簡単な問題になるということを意味する。
【００５４】
一方、攻撃者による秘密鍵情報の復元は、ビットの消失、挿入、反転といった激しい雑音を伴う通信路における復号問題に対応する。上記の問題については、それを説明している図１１が参照できる。図１１に示されるように、認証プロトコルにおける通信データの中に認証に用いられるパリティチェックのためのデータがランダムに挿入されている。
【００５５】
なお、提案認証プロトコルの安全性評価に関する議論は、非特許文献１８、非特許文献１９、非特許文献２０に詳細に記載されており、これらが参照できる。
【００５６】
ＢＫＷアルゴリズムに対するものと同じ入力を、本発明により提供されるアルゴリズムの同じ例として仮定し、提供されるアルゴリズムで得られる利得は、追加されたパラメータの最適化と、そのより洗練された構造に依っている。その特長の要因は、次のようにまとめられる。
（ａ）サンプルの収集時におけるパリティチェックの選択（破棄）。その処理では、適当なパリティチェックデータのみが使用される。それによって、計算複雑度を下げることができる。
（ｂ）仮説検定の適切なバランス化と与えられた仮説のもとでの復号複雑度。
【００５７】
ＬＰＮ問題を解くための非特許文献６で提案されたアルゴリズムは、ＢＫＷアルゴリズムに帰着できる。すなわち、ＢＫＷアルゴリズムは、この提供されるアルゴリズムのある特別な場合を表している。したがって、提供されるアルゴリズムは、少なくともＢＫＷアルゴリズムと同様に動作して、多くの場面では（与えられた入力にしたがって変化する柔軟な構造に基づいた最適化の可能性がある結果として）より効率的に動作する。
【００５８】
暗号解読のためのサンプル収集に関しては、次のような問題点に注意すべきである。
（ａ）同じ秘密鍵に関係する各認証セッションと、したがって、得られる全てのチャレンジ・レスポンスの組は、その秘密鍵を得るために用いることができる。
（ｂ）行列Ｇのｒ列ベクトルを与え、ベクトルｚのｒ要素に対応する、独立したｒ回の相互認証チャレンジ・レスポンスの各認証セッション、s回の認証セッションから得られた組を収集することで、ｋ×ｎの行列Ｇとｎ次元ベクトルｚを得ることができる。ここでｎ＝ｓ・ｒである。
【００５９】
したがって、同じ秘密鍵を用いる異なる認証セッションから情報を収集することで、多数の暗号解読に必要なサンプルを得ることができる。それらは秘密鍵を算出するための洗練された処理に適したデータである。
【００６０】
［ＢＫＷアルゴリズムと非特許文献６で提案されたアルゴリズムに基づいたＨＢプロトコルの安全性評価］
非特許文献６にしたがい、ここでは、ＨＢおよびＨＢ＋プロトコルの受動的な攻撃に対する安全性の再評価を与えるため、非特許文献６で提案されたＬＰＮ問題を解くアルゴリズムを用いて安全性を再評価する。その結果、これまでの安全性余裕度は良く見積もられすぎていることがわかった。
【００６１】
ここでの安全性評価では、受動的攻撃のみが行われると仮定する。非特許文献９で採用されているような安全性評価手法にならい、秘密鍵の１ビットを解読するために必要な計算量を用いて安全性の余裕度を測定する。
【００６２】
簡単な例を説明すると、まず、最初に、ｋ＝３２，ｐ＝０．２５というパラメータをとるＨＢプロトコルの安全性を考慮する。そして、ｎ＝２２４のサイズのサンプルを収集することができると仮定する。非特許文献９で示唆されているように、ａ＝２，ｂ＝１６のパラメータをとる場合のＢＫＷアルゴリズムを用いた場合のプロトコルの安全性余裕度は次のようになる。
【００６３】
非特許文献６の提案３および提案４に基づいて、ＢＫＷアルゴリズムの時間複雑度（計算時間）の期待値はｋａ３（１−２ｐ）−２ａ２ｂ＝３２・２３・２４・２１６に比例するので、安全性の余裕度（秘密鍵の１ビットを解読する平均的複雑度）は２２３となる。
【００６４】
本発明により提供されるアルゴリズムに対し、非特許文献６の表１に基づいて、ｗ＝２，ｂ０＝１６，ｂＨ＝５を選ぶと、秘密鍵の１ビットを解読する平均複雑度は、２・２１１／１６＝２８となる。この結果、この簡単な例により、本発明により提供されるアルゴリズムは時間複雑度を、ＢＫＷアルゴリズムのほぼ３乗根にまで減少させることができる。
【００６５】
ｋ＝２２４，ｎ＝２８０，ｐ＝０．２５である場合のＨＢプロトコルの安全性評価において、ａ＝４，ｂ＝５６をとるＢＫＷアルゴリズムを考慮し(非特許文献９参照)、一方、非特許文献６の表３に基づき、ｗ＝６，ｂ０＝５８，ｂＨ＝５６をとる提案アルゴリズムを考える。このときそれぞれの安全性余裕度は２８０，２６１となる。また、この場合も顕著な利点が本発明により提案されるアルゴリズムでは得られている。安全性評価に関するこれらの結果は、つぎの表１にまとめられている。
【表１】
2008205675.tif 000003
表１は、受動的攻撃に対するＨＢプロトコルの安全余裕度を示している。この場合に、使用される鍵はｋビットからなり、使用されるノイズは、ＢＫＷおよび非特許文献６のアルゴリズムに基づいてＰ＝０．２５に対応している。
【００６６】
非特許文献６の表３で考慮されている特別な場合に関して、全パラメータの適切な最適化を行うことで、本発明により提供されるアルゴリズムではＢＫＷアルゴリズムに対して（ｌｏｇ２ｗ＋１）３（１−２ｐ）−ｗ倍を超える利得を得ることができる。例えば、ｋ＝３２およびｋ＝２２４に対し、それぞれ値２５と値２１４となる。一方、対応する利得は、２１５および２１９となる。
【００６７】
ＨＢおよびＨＢ＋プロトコル両方の安全性は、安全性の根拠としてＬＰＮ問題の困難性を使用しているので、非特許文献６で提案されたその問題を解くアルゴリズムが、それらの安全性評価に用いられた。同じ暗号解読のシナリオを仮定した場合、このアルゴリズムは秘密鍵をＢＫＷアルゴリズムより少ない計算複雑度で解読できることが示された。したがって、非特許文献９の付録Ｄで報告されている安全性余裕度は良く見積もられすぎていることが明らかとなった。
【００６８】
本発明の軽量認証プロトコルによる認証システムにおいては、非特許文献９で提案されたプロトコルと同等の低い複雑度（計算量、記憶量、電力量等）で、非特許文献６で指摘された脆弱性を持たない認証プロトコルが構成されている。
【００６９】
本発明においては、二元系列上の確率的チャレンジ・レスポンス手法を用いて、ある種の軽量認証プロトコル設計の一般的な手法により構成される軽量認証プロトコルによる認証システムが提供される。
【００７０】
これまでに提案されてきた手法による二元対称通信路として知られている雑音通信路モデルを利用して確率的な振舞をモデル化していたのとは対照的に、本発明の軽量の認証プロトコルによる認証システムでは、確率的な振舞の性質を、二元系列において情報の消失、挿入、反転を起こすような雑音を伴う通信路モデルを使用してモデル化する。この新たな手法を使うことで、認証プロトコルにこれまでとは異なる構造を与えることができる。
【００７１】
これまで提案されてきた手法と最も異なる点は次の二つである。
（１）本発明による認証プロトコルでは専用の制御部を付加している。この制御部の制御処理により、二元系列において情報の消失、挿入、反転を起こすような雑音を伴う通信路モデルを使用してモデル化している。
（２）本発明による認証プロトコルの各ラウンドには二つの選択肢がある。これは、有効なラウンドと、擬似乱数的な方法で発生させられるダミーのラウンドである。
【００７２】
有効ラウンドとダミーラウンドの擬似乱数的な選択を行うことで、次の二つの利点が得られる。
（１）レスポンス評価の平均的な複雑度を削減することができる。
（２）プロトコルの安全性を高められる。適切な制御部を使用すると仮定すれば、提案する認証プロトコルは、ＨＢプロトコルに対して、次のような利点があることを示せる。
（２ａ）実装における複雑度は同等程度である。
（２ｂ）認証という意味でより高い安全性を達成できる。
（２ｃ）より短い秘密鍵の使用で良い。
【００７３】
特に、次の点を強調したい。ＨＢプロトコルの安全性は、ＬＰＮ（Ｌｅａｒｎｉｎｇ  Ｐａｒｉｔｙ  ｗｉｔｈ  Ｎｏｉｓｅ）問題を解くことの困難性に依拠しているが、最近これまで提案されていた攻撃よりも強力な攻撃アルゴリズムが提案されている（非特許文献６）。その攻撃法を用いた場合、ＨＢプロトコルの安全性の余裕度は、これまで報告されていたものよりも低いことが示されている。一方で、本発明によって提供される認証プロトコルは、非特許文献６で最近報告されたようなＨＢプロトコルの脆弱性を持っていない。これは、本発明により提供される認証プロトコルの安全性がＬＰＮ問題の困難性に依拠していないからである。
【図面の簡単な説明】
【００７４】
【図１】ＨＢプロトコルの１つのラウンド処理のモデル化を説明する図である。
【図２】ＨＢ＋プロトコルの１つのラウンド処理のモデル化を説明する図である。
【図３】本発明による認証システムにおける受動的攻撃に基づく安全性を提供するプロトコル１の１つのラウンド処理のモデル化を説明する図である。
【図４】本発明による認証システムにおける能動的攻撃に基づく安全性を提供するプロトコル２の１つのラウンド処理のモデル化を説明する図である。
【図５】プロトコル１の制御部を説明する図である。
【図６】プロトコル２の制御部を説明する図である。
【図７】プロトコル１の有効ラウンドの間のメッセージ交換を説明する図である。
【図８】プロトコル１のダミーラウンドの間のメッセージ交換を説明する図である。
【図９】プロトコル２の有効ラウンドの間のメッセージ交換を説明する図である。
【図１０】プロトコル２のダミーラウンドの間のメッセージ交換を説明する図である。
【図１１】レスポンスのシーケンスを説明する図である。
【符号の説明】
【００７５】
１０  秘密鍵記憶部、
１１  内積データ生成部、
１２  乱数ビット発生器、
１３  出力処理部、
２０  秘密鍵記憶部、
２１  内積データ生成部、
２２  乱数ビット発生器、
２３  出力処理部、
３０  秘密鍵記憶部、
３１  内積データ生成部、
３２  乱数ビット発生器、
３３  出力処理部、
３４  制御部、
４０  秘密鍵記憶部、
４１  内積データ生成部、
４２  乱数ビット発生器、
４３  出力処理部、
４４  制御部、
９１  キーストリーム発生器、
９２  制御論理部
１０１  キーストリーム発生器、
１０２  制御論理部
【図１】
2008205675.tif 000004
【図２】
2008205675.tif 000005
【図３】
2008205675.tif 000006
【図４】
2008205675.tif 000007
【図５】
2008205675.tif 000008
【図６】
2008205675.tif 000009
【図７】
2008205675.tif 000010
【図８】
2008205675.tif 000011
【図９】
2008205675.tif 000012
【図１０】
2008205675.tif 000013
【図１１】
2008205675.tif 000014