(57)【特許請求の範囲】
【請求項１】
ワードＲを含むストリーミングデータにおける消失訂正装置であり、
（ａ）下記に示す消失値置換処理；
Ｒ（０）：消失値を"０"にセット
Ｒ（１）：消失値を"１"にセット
を実行することにより、受信ワードＲに基づく一対の置換データセット、Ｒ（０）およびＲ（１）を生成する消失値置換手段と、
（ｂ）受信ワードＲの各位置の非消失値を格納するメモリと、
（ｃ）前記置換データセットＲ（０）およびＲ（１）に基づいて、一対の符号語としてのコードワードＣ（０）およびＣ（１）を、下記の対応： 
Ｒ（０）に基づいてコードワードＣ（０）
Ｒ（１）に基づいてコードワードＣ（１）
に従って取得するためのルックアップテーブルと、
（ｄ）２つのハミング距離として、
Ｄ０＝Ｃ（０）からＲまでの距離、
Ｄ１＝Ｃ（１）からＲまでの距離、
を算出し、２つの算出距離を比較する演算処理手段と、
（ｅ）前記演算処理の結果に基づいて、Ｒにより近い距離を持つ１つのコードワードＣを選択するセレクタと、
を有することを特徴とするストリーミングデータにおける消失訂正装置。
【請求項２】
消失訂正装置において、ワードＲを含むストリーミングデータにおける消失訂正処理を実行する消失訂正方法であり、
（ａ）消失値置換手段において、下記に示す消失値置換処理；
Ｒ（０）：消失値を"０"にセット
Ｒ（１）：消失値を"１"にセット
を実行することにより、受信ワードＲに基づく一対の置換データセット、Ｒ（０）およびＲ（１）を生成し、
（ｂ）制御手段の制御の下、メモリに受信ワードＲの各位置の非消失値を格納し、
（ｃ）制御手段の制御の下、前記置換データセットＲ（０）およびＲ（１）に基づいて、一対の符号語としてのコードワードＣ（０）およびＣ（１）をルックアップテーブルを適用して、下記の対応： 
Ｒ（０）に基づいてコードワードＣ（０）
Ｒ（１）に基づいてコードワードＣ（１）
に従って取得し、
（ｄ）演算処理手段において、２つのハミング距離、
Ｄ０＝Ｃ（０）からＲまでの距離、
Ｄ１＝Ｃ（１）からＲまでの距離、
を算出し、
（ｅ）演算処理手段において、前記２つの算出距離Ｄ０およびＤ１を比較し、
（ｆ）セレクタにおいて、前記比較処理の結果に基づいて、Ｒにより近い距離を持つ１つのコードワードＣを選択する、
上記各処理を有することを特徴とするストリーミングデータにおける消失訂正方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ストリーミングデータにおける消失訂正および限定受信方法および装置、並びに、データ通信装置に関し、さらに詳細には、ルックアップテーブルを適用して効率的に消失訂正処理および暗号化、復号化処理を実行する方法および装置に関する。
【０００２】
【従来の技術】
昨今、例えば、ビデオストリーミングデータ等の情報についてのリアルタイム転送処理等、ストリーミング処理に関する研究が盛んとなり興味深いトピックとなってきている。例えば、リアルタイムデータ転送システムを開示している論文として、「Wu, Y.T. Hou, W. Zhu, Y.Q. Zhang and J.M. Peha,"Streaming Video over the Internet: Approaches and Directions," IEEE Trans. Circ.and Syst. for Video Tech., vol. 11, no. 3, pp. 282-300, March 2001」がある。
【０００３】
本発明は、ストリーミングメディア転送のための信頼性の低い公衆パケット・スイッチ・ネットワークを考慮したシステムである。信頼性の低い公衆パケット・スイッチ・ネットワークについては、「V. Paxson, "End-to-end Internet packet dynamics", IEEE/ACM Transactions on Networking, vol. 7,pp. 277-292, 1999」を参照されたい。
【０００４】
本システムに係わる重要な２つの論点は、ロストパケットの回復、および配信メディアコンテンツのセキュリティである。
【０００５】
ロストパケットの回復処理は、消失（ｅｒａｓｕｒｅ）訂正処理によって実行される。消失（ｅｒａｓｕｒｅ）は、パケットの紛失（ｌｏｓｔ）時、あるいは時間内の到着が実行されない場合に宣言されるものである。本発明においては、処理遅延および煩雑な復号処理をできるだけ低減し、一方、十分なパフォーマンスを達成する消失訂正処理スキームを提供する。
【０００６】
公衆ネットワークを介した情報ストリーミング転送に関するセキュリティ上の主要な目標には以下に示すものがある。文献「"E.T. Lin, G.W. Cook, P.Salama and E.J. Delp, "An overview of Security Issues in Streaming Video", Int. Conf. on Information Tech.: Coding and Computing, Proc., pp. 345-248, 2001"」は、セキュリティ問題を開示している。限定受信、認証処理、複製制御、コンテンツ追跡等である。セキュリティに関して言えば、本発明は、限定受信に的を絞ったものである。限定受信システムは、いわば、プロバイダとユーザ間のストリーミング情報アクセスにおける一連のルールを規定するアクセスモデルを定義し、かつ有効化するものである。
【０００７】
暗号処理は、限定受信システムにおいてよく適用される。すなわち、管理者によって承認された者のみが必要な復号鍵を利用可能とする構成である。暗号処理に関しては、例えば、「J.L. Massey, "An introduction to contemporary cryptology", Proceedings of the IEEE, vol. 76, pp. 534-549, May 1988」または、「 A. Menezes, P.C. van Oorschot and S.A. Vanstone, Handbook of Applied Cryptography. Boca Raton: CRC Press, 1997」を参照されたい。
【０００８】
本発明においては、公衆パケットスイッチ・ネットワークを介するメディア転送における高速消失訂正処理および限定受信処理に関する技術を提案する。この両技術の共通点は、パケット指向（例えばパケット・バイ・パケット・プロセス）であること、および、ルックアップテーブル（ＬＵＴ）を適用した処理であることである。
【０００９】
ここで提案する消失訂正技術は、短いバイナリ線形ブロックコードの適用に基づく技術である。すでに良好な短いバイナリ線形ブロックコードが知られており、短いバイナリ線形ブロックコードは、良好な消失訂正機能を有する。一例として、データ長７ビットのバイナリ・ハミングコードが適用可能である。ここで提案する限定受信技術は、あるストリーミング・アプリケーションに最適である新規な暗号処理スキームに基づいている。
【００１０】
【発明が解決しようとする課題】
本発明の１つの目的は、パケットロス回復における新規なバイナリ消失訂正アルゴリズムを提供し、かつ新規なストリーム暗号に基づくパケット指向限定受信技術を提供することである。消失訂正処理においては、２つの硬判定復号ルックアップテーブル、及び、２つの硬判定デコーダ出力値のハミング距離算出、比較および選択処理を実行する簡易ロジックを伴った、短いバイナリ線形ブロックコードが適用される。提案アルゴリズムは、高速かつ遅延の少ない処理が可能であり、低信頼性のネットワークを介したストリーミング・メディア・アプリケーションに対する適性を保有するのである。
【００１１】
ここで提案するストリーム暗号は、ルックアップテーブル処理のみに基づくものであり、処理は、耐タンパＲＯＭ内において実行される。本発明の技術は、非常に高速な技術であり、リアルタイム・アプリケーションに最適である。また、その暗号処理学的な安全性は、代数問題における解取得の困難性に基づくものである。
【００１２】
【課題を解決するための手段】
本発明の第１の側面は、
ワードＲを含むストリーミングデータにおける消失訂正装置であり、
（ａ）下記に示す消失値置換処理；
Ｒ（０）：消失値を"０"にセット
Ｒ（１）：消失値を"１"にセット
を実行することにより、受信ワードＲに基づく一対の置換データセット、Ｒ（０）およびＲ（１）を生成する消失値置換手段と、
（ｂ）受信ワードＲの各位置の非消失値を格納するメモリと、
（ｃ）前記置換データセットＲ（０）およびＲ（１）に基づいて、一対の符号語としてのコードワードＣ（０）およびＣ（１）を、下記の対応： 
Ｒ（０）に基づいてコードワードＣ（０）
Ｒ（１）に基づいてコードワードＣ（１）
に従って取得するためのルックアップテーブルと、
（ｄ）２つのハミング距離として、
Ｄ０＝Ｃ（０）からＲまでの距離、
Ｄ１＝Ｃ（１）からＲまでの距離、
を算出し、２つの算出距離を比較する演算処理手段と、
（ｅ）前記演算処理の結果に基づいて、Ｒにより近い距離を持つ１つのコードワードＣを選択するセレクタと、
を有することを特徴とするストリーミングデータにおける消失訂正装置にある。
【００１３】
本発明のさらなる側面は、
消失訂正装置において、ワードＲを含むストリーミングデータにおける消失訂正処理を実行する消失訂正方法であり、
（ａ）消失値置換手段において、下記に示す消失値置換処理；
Ｒ（０）：消失値を"０"にセット
Ｒ（１）：消失値を"１"にセット
を実行することにより、受信ワードＲに基づく一対の置換データセット、Ｒ（０）およびＲ（１）を生成し、
（ｂ）制御手段の制御の下、メモリに受信ワードＲの各位置の非消失値を格納し、
（ｃ）制御手段の制御の下、前記置換データセットＲ（０）およびＲ（１）に基づいて、一対の符号語としてのコードワードＣ（０）およびＣ（１）をルックアップテーブルを適用して、下記の対応： 
Ｒ（０）に基づいてコードワードＣ（０）
Ｒ（１）に基づいてコードワードＣ（１）
に従って取得し、
（ｄ）演算処理手段において、２つのハミング距離、
Ｄ０＝Ｃ（０）からＲまでの距離、
Ｄ１＝Ｃ（１）からＲまでの距離、
を算出し、
（ｅ）演算処理手段において、前記２つの算出距離Ｄ０およびＤ１を比較し、
（ｆ）セレクタにおいて、前記比較処理の結果に基づいて、Ｒにより近い距離を持つ１つのコードワードＣを選択する、
上記各処理を有することを特徴とするストリーミングデータにおける消失訂正方法にある。
【００３１】
【発明の実施の形態】
本明細書は、以下に示す構成からなる。セクションＡでは、前提となるシステム全般について説明する。セクションＢでは、提案する高速消失訂正方法および装置について説明する。また、提案するアルゴリズムの詳細、すなわち、短いバイナリ線形ブロックコードを適用し、ＬＵＴを基本として適用した硬判定デコード処理についての説明を行なう。エンコード、デコード構成については長さ７ビットのバイナリ・ハミングコードの適用例を示す。
【００３２】
セクションＣでは、新規な鍵ストリームに基づく限定受信処理方法および装置について説明する。最後に、セクションＤでは、本発明の結論について説明する。
【００３３】
［セクションＡ］
ストリーミングシステム
本明細書では、ストリーミング・メディア転送用の低信頼性の公衆パケットスイッチネットワークを考慮している。
【００３４】
論点は、以下の２つの機能を持つ単純化されたストリーミングシステムに絞られる。
（ａ）例えば消失訂正の如きパケットロスに対する回復処理
（ｂ）パケットコンテンツに対する限定受信
【００３５】
限定受信処理、および消失訂正処理は、それぞれ独立に実行され、パケット毎の処理、すなわちパケット−バイーパケット・ベースで実行される。ここで適用する限定受信技術は、暗号化／復号化処理を基本として用いる。消失訂正処理は、パケットグループに対してビット単位で実行される。図１は、本発明の提案に係るストリーミングシステムのブロック図である。
【００３６】
図１は、データ送信側構成と、データ受信側構成とを含むデータ通信装置を示している。データ送信側では、データは暗号処理手段１１１によって暗号化され、消失対応バイナリエンコーダ１１２によってエンコード処理が実行される。
【００３７】
暗号化されエンコードされたデータは、パケット出力手段（図示せず）において形成されたパケットにカプセル化される。例えばＴＣＰ、ＵＤＰ、あるいは他のプロトコルに従ったパケットを含むＩＰパケットである。データパケットは、例えばインターネット、Ｍボーン（マルチキャスト  バックボーン）、無線ＬＡＮ等のデータネットワーク上に送出される。
【００３８】
データ受信側では、受信データが、まず、パケット解析手段（図示せず）においてパケット単位、すなわちパケットーバイーパケット・ベースで解析され、消失対応バイナリデコーダ１２２によってデコードされ、さらに復号処理手段１２１によって復号される。
【００３９】
図１におけるデータ送信側では、データは、まず、暗号処理手段１１１において暗号化され、暗号化データは、消失対応バイナリエンコーダ１１２においてエンコードされる。なお、この暗号処理手段１１１、および消失対応バイナリエンコーダ１１２において実行される処理順は変更、すなわち手順を入れ替えることが可能である。さらに、データ受信側における消失対応バイナリデコーダ１２２、および復号処理手段１２１において実行される処理順についても変更、すなわち手順を入れ替えることが可能である。
【００４０】
［セクションＢ］
パケットロスト・エラーに対応するエラー訂正技術
【００４１】
昨今、様々な文献において、マルチキャスト・ネットワークにおけるエラー訂正コード・アプリケーションに対するアプローチが提案されている。まず、１つのアプローチとして、マルチキャスト・プロトコルおよびエラー制御符号化（ＥＣＣ）の統合的適用がある。これは、「L.Rizzo in "Effective Erasure Codes for Reliable Computer Communication Protocols, "Computer Comm. Review, 1997"」において提案されている。
【００４２】
ＥＣＣ手法は、デジタルファウンティン（Digital Fountain）、あるいはマイクロソフト（Microsoft）においても、それぞれ「J.W. Byers, M. Luby, M. Mitzenmacher and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data," Proc. SIGCOMM'98, Vancouver, Canada, 1998」や、「 J. Gemmell, E. Schooler and J. Gray, "Fcast Scalable Multicast File Distribution: Caching and Parameter Optimizations," Microsoft Research Tec. Report, MSR-TR-99-14, June 22, 1999」においてそれぞれ論じられている。
【００４３】
一方、適応ＥＣＣベースプロトコルについては、「P.J.M. Havinga, "Energy Efficiency of Error Correction on Wireless Systems," Proc. WCNC'99, vol. 2, pp. 616 -620, 1999」において論じられている。ＥＣＣに結合されたフィードバック情報（ＡＲＱ）を利用するハイブリッドなアプローチが、「J. Nonnenmacher, E.W. Biersack and D. Towsley, "Parity-Based Loss Recovery for Reliable Multicast Transmission,"  IEEE/ACM Trans. Networking, vol. 6, no. 4, pp. 349-361, Aug. 1998」において提案されている。すべてのＥＣＣベースのマルチキャスト・スキームにおいて、ＥＣＣは、消失の保護（ｐｒｏｔｅｃｔｉｏｎ）構成を提供するものとして利用されている。
【００４４】
消失（ｅｒａｓｕｒｅ）は、パケットが消失（ｌｏｓｔ）した際、あるいは時間内に到着しない場合に宣言される。ＥＣＣは、アプリケーションがスケールアップすることを可能にし、それによって多くのユーザがネットワークあるいはサーバリソースへのオーバーロードをすることなく利用可能である。
【００４５】
これまでのすべてのＥＣＣスキーム（消失コード）は、以下に示す３タイプのコードのいずれかを適用している。
（ｉ）リードソロモンコード（Reed-Solomon codes）、これは、例えば「Effective Erasure Codes for Reliable Computer Communication Protocols, "Computer Comm. Review, 1997 by L.Rizzo" and " J. Nonnenmacher, E.W. Biersack and D. Towsley, "Parity-Based Loss Recovery for Reliable Multicast Transmission," IEEE/ACM Trans. Networking, vol. 6, no. 4, pp. 349-361, Aug. 1998」において論じられている。
【００４６】
（ｉｉ）トルネードコード（Tornado codes）、これは例えば、「J.W. Byers, M. Luby, M. Mitzenmacher and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data」において論じられている。
【００４７】
（ｉｉｉ）イーブンオッド（EVENODD）、これは例えば、「P.J.M. Havinga, "Energy Efficiency of Error Correction on Wireless Systems," Proc. WCNC'99, vol. 2, pp. 616 -620, 1999」において論じられている。
【００４８】
本特許明細書においては、消失訂正処理に短いバイナリ線形ブロックコードの適用を提案する。すでに良好な短いバイナリ線形ブロックコードが知られており、短いバイナリ線形ブロックコードは、良好な消失訂正機能を有する。
【００４９】
一例として、データ長７ビットのバイナリ・ハミングコードが適用可能である。本コードの消失訂正能力は、コード長に対応して正規化され、２８．３％に等しい。これは、他の複雑なアプローチに比較しても十分対抗し得るものである。しかし、ここで提案するスキームの複雑性は、単に小さなＬＵＴと対応するロジックを持つだけに過ぎない。
【００５０】
消失保護は、処理遅延およびデコード処理の煩雑さを可能な限り低減するように実行され、一方、十分なパフォーマンスを達成するように実行される。
【００５１】
［パケットのバイナリコーディング］
一般的な概念で説明するために、パケット構成を長さＮpacketバイトである構成を仮定する。長さｎ、ｋ次元の組織符号化を伴ったバイナリ線形ブロックコードＣを適用する。
【００５２】
すなわち、図２に示すように、ｋビットの情報ビットと、後続のｎ−ｋビットの冗長ビットによりｎビットのコードワードが構成される。パケットのエンコード処理について以下説明する。
【００５３】
まず、ｋ個のパケットが、１単位を８×Ｎpacketとしたアレイに格納される。バイナリエンコード処理が縦列単位に実行され、ｎパケットが生成される。結果として生成されたｎパケットが、バイトフォーマット形態に再構築されネットワーク上に出力される。図２は上述の処理を説明した図である。
【００５４】
高速エンコード処理は、ＬＵＴを用いて実行される。ｋビットの情報ビットがＬＵＴに対するアドレスとして適用され、対応するｎビット長のコードワードが選択抽出される。パケットエンコード処理時間は、バイナリコードの適用する次元数：ｋに比例する。従って、短いブロックにより、エンコード処理時間を削減可能となる。
【００５５】
［高速消失訂正アルゴリズム］
バイナリコードによる消失訂正処理は、消失位置の全シンボルを０および１にセットしたデータ（Ｒ（０），Ｒ（１）と記す）の生成、さらに２つの硬判定デコード処理により実行される。これらのデコード処理による出力コードワード（Ｃ（０），Ｃ（１）と記す）は、受信ワードＲ（受信パケット）とのハミング距離についての比較処理が実行される。
【００５６】
ハミング距離の演算においては、非消失位置のみが考慮される。受信ワードＲに最も近いコードワードＣの情報ビットが訂正情報として出力される。本発明の好適な実施例に従った基本的な消失訂正アルゴリズムを図３に示す。
【００５７】
図１に示す消失対応バイナリデコーダ１２２は図３に示すプロセスを実行する。ステップＳ１０１において、受信データパケットに基づいて、入力データの抽出が実行される。入力データは、受信ワード：Ｒ、消失の数、さらに消失位置データを含む。ステップＳ１０２において、消失置換処理が実行される。この処理は、下記に示す処理となる。
Ｒ（０）消失値を０にセット
Ｒ（１）消失値を１にセット
【００５８】
ステップＳ１０３において、受信ワードＲの非消失位置の値をメモリに記憶する。
【００５９】
ステップＳ１０４において、ルックアップテーブルを適用したデコード処理を実行する。デコード処理は、以下に示す処理として実行する。
Ｒ（０）に基づくコードワードＣ（０）生成
Ｒ（１）に基づくコードワードＣ（１）生成
【００６０】
ステップＳ１０５において、ハミング距離演算プロセスを実行する。この演算プロセスは、下記に示すハミング距離の算出処理を実行するものである。
Ｄ０＝Ｃ（０）からＲまでの距離
Ｄ１＝Ｃ（１）からＲまでの距離
【００６１】
ステップＳ１０６は、比較および選択処理ステップである。このステップでは、上述の２つのハミング距離Ｄ０およびＤ１の比較処理が実行され、この比較処理に基づいてＲにより近い距離を持つ１つのコードワードＣが選択される。
【００６２】
上述の処理手順に従えば、ルックアップテーブル（ＬＵＴ）を用いた高速デコード処理が実現される。長さｎのバイナリ線形ブロックコードに対して、各エントリがｋビットの２nエントリを持つテーブルが構成される。このテーブルはコードのスタンダート配列にすぎないものである。Ｎビット受信ワードＣ（ｊ）｛ｊ＝１，２｝がＬＵＴに対するアドレスとして使用され、対応するｋビットがデコードビットを構成する。
【００６３】
デコード用ＬＵＴは、デコード用ＬＵＴと連結することができる。その結果、ここで提案する消失訂正アルゴリズムによって必要とされているｋビットのデコード情報ビットがエンコード用ＬＵＴにおいてコードワードを生成するエントリとして利用される。
【００６４】
［ハミングコードを適用した高速消失訂正処理］
図４にエンコーダおよびデコーダの構成図を示す。図４（ａ）に示すエンコーダは、図１における消失対応バイナリエンコーダ１１２に対応する。図４（ｂ）のデコーダは、図１における消失対応バイナリデコーダ１２２に対応する。
【００６５】
ここで提案する手法の具体例として、長さ７ビット、次元４、最小距離３のハミングコードを想定する。これは、受信ワードに含まれるあらゆる２つのランダム消失を訂正可能なコードである。エンコードおよびデコード用のＬＵＴのサイズは、１６×７＝１１２ビットおよび１２８×４＝５１２ビットである。従って、ＬＵＴに必要な全体の記憶領域は、６２４ビットとなる。
【００６６】
図４に示すように、本発明の最適な実施例に従ったエンコーダは、ハミング（７，４）エンコーダ２１１、消失発生チャネル２１２を有する。４ビットの情報ビットは、エンコーダに入力され、ハミングエンコード処理が実行される。３ビットの冗長ビットがこのエンコード処理において付加され、エンコーダは７ビットのコードワードを出力する。
【００６７】
デコーダに対する入力データは、受信ワードＲ、消失の数Ｎｅ、消失位置データｅ１，ｅ２を含む。デコーダは、消失値置換手段２２１、非消失（７−Ｎｅ個に対応する位置の値）を記憶するためのメモリ２２２、Ｒ（受信ワード）の最初の４ビットを記憶するためのメモリ、遅延手段２２４、２つのルックアップテーブル２２６，２２７を持つルックアップテーブル２２５、ハミング距離の算出および比較処理を実行する演算手段２２８、さらに、セレクタ２２９を有する。
【００６８】
ハミング距離演算は、アキュムレータ（累算器）、および排他的論理和ゲートにより実行され、６ビット（＝ｎ−１）の最大待ち時間を持つ。受信ワードに対するデコード・コードワードの比較および最近接デコード・コードワードの選択処理は、加算器およびマルチプレクサーによって実現される。デコード処理による出力は、４ビットの情報ビットからなるベクトルとなる。
【００６９】
消失値置換手段２２１は、消失の置換処理を実行する。すなわち、Ｒ（０）が消失値を０にセット（Ｅ＝０）、Ｒ（１）が消失値を１にセット（Ｅ＝１）する各処理である。メモリ２２２は、Ｒ，消失数Ｎｅ，消失の位置データｅ１，ｅ２を受信するとともに、受信ワードＲの非消失位置の値を格納する。
【００７０】
デコード処理は、ルックアップテーブル２２５を適用して実行される。このデコード処理は、以下に示す通りである。すなわち、デコード用ＬＵＴ２２６の適用により、Ｒ（０）からコードワードＣ（０）を抽出、デコード用ＬＵＴ２２７の適用により、Ｒ（１）からコードワードＣ（１）を抽出する。
【００７１】
演算手段２２８は、以下に示す２つのハミング距離を算出する。
Ｄ０＝Ｃ（０）からＲの距離
Ｄ１＝Ｃ（１）からＲの距離
【００７２】
演算手段２２８は、上記２つのハミング距離Ｄ０およびＤ１の比較処理を実行する。この比較処理に基づいて、Ｒにより近い１つのコードワードＣが選択され、演算手段２２８は、選択したビットデータをセレクタに出力する。セレクタ２２９は、消失数Ｎｅに基づいて、演算手段２２８および遅延手段２２４から入力される４ビットデータの選択処理を実行する。
【００７３】
上述したように、デコード処理は、ＬＵＴに基づいて実行されるので、高速のデコード処理が実現される。
【００７４】
図５は、バイナリハミング（７，４）コードに対応するデコード用ＬＵＴの例を示す図である。図５は、単一エラー訂正のみに適用するためのＬＵＴの例である。テーブルには１２８のエントリがあり、これは、受信する７ビット長のバイナリベクトルの数に対応している。基本的に、全ゼロの組合わせ、７つの位置における１つまたは２つの消失に対応する、すなわち１＋７＋２１＝２９の可能性について検討することが必要となる。各組み合わせにおいて、他の全ての位置については自由に選択可能である。すなわち、（１）消失ゼロの場合、テーブルに１２８個のベクトル候補が存在することになる。（１）消失１の場合（７パターン）、テーブルに６４個のベクトル候補が存在することになる。（３）消失２の場合（２１パターン）、テーブルには３２個のベクトル候補が存在することになる。従って、受信ベクトルの全パターン数は、１２８＋７×６４＋２１×３２＝１２８＋４４８＋６７２＝１，２４８の入力ベクトルとなる。
【００７５】
様々な入力ベクトル、消失の数、消失位置について、図４に示す回路はシミュレートされ、その結果としてのメッセージ（４ビット）がＬＵＴに記録されている。この結果として、ＬＵＴのサイズが１２８×４ビットとして設定されている。入力ビット（１５ビット）数がテーブルコンテンツに対するアドレス用ビット（１１ビット）よりも大きい場合は、アドレス算出処理ブロックをＬＵＴの前段に付け加えて４出力ビットグループを選択することができる。
【００７６】
図６（ｂ）は、デコーダシステムの別の実施例を示すものである。このデコーダは単一ＬＵＴである。このデコーダはアドレス算出手段２３１、消失対応デコード用ルックアップテーブル２３２を有する。
【００７７】
アドレス算出手段２３１は、受信ワードＲ、消失数Ｎｅ、消失位置データｅ１，ｅ２を入力し、消失対応デコード処理用ルックアップテーブル２３２に対して１１ビットのアドレスデータを出力する。このルックアップテーブル２３２を適用して、入力アドレスデータに基づいて４ビットデータが出力される。この４ビットデータは、上述のハミング距離算出および比較処理によって算出されるデータに対応する。
【００７８】
［パケットロス回復処理］
消失訂正処理は、パケットレベルで実行される。最終的には、ロストパケットの回復がゴールとなる。所定の十分な数のパケット数Ｎrecの受信パケットがあったとき、これらのパケットに関係づけられたすべての８×Ｎpacketの受信ワードについて、消失パターンは同一となることを意味する。ここで、Ｎrec＝ｎ−ｓ＝ｎ−ｄ＋１であり、ｎは、コード長を示し、ｓ＝ｄ−１は、コードによる消失訂正能力を示すことになる。このことは、デコード処理の大きな効率化を示している。
【００７９】
消失の置換処理は、８×Ｎpacketの全受信ワードに対して１回のみ実行すればよい。さらに並列処理も可能である。また、消失置換処理、距離算出および比較処理、さらにコードワード選択処理は無記憶構成においても実現可能である。従って、これらの一連の処理は、消失位置および非消失位置の受信ビットを入力とする単一のデコード用ＬＵＴを適用した処理として統合することも可能である。この全ＬＵＴ適用デコード処理は、消失訂正アルゴリズムの実行における処理遅延を最小に低減する可能性を持つものである。
【００８０】
［セクションＣ］
パケット指向限定受信技術
ストリーミング情報に対する限定受信を効果的に実行するよく知られた手法として暗号化された形態での配信方法がある。この目的のために、暗号処理手段に対する入力メッセージは全ストリーム情報としたり、あるいは、部分毎の処理とする方法がある。
【００８１】
パケット紛失に対する耐性を保持するためには、パケット指向暗号処理が採用される。この場合、パケットロスは、他のパケットの復号処理に対して影響を与えない。以下、このセクションでは、本提案に係る新規なストリーム暗号をべースとしたパケット指向型限定受信技術について説明する。
【００８２】
本発明の好適な実施例に係るストリーム暗号の形成は、以下に示す基本的アイディアに基づくものである。
（ａ）ＬＵＴのみに基づく処理
（ｂ）耐タンパＲＯＭに基づく処理
【００８３】
この考え方による利点は以下に示すものがある。
（ｉ）鍵ストリームの主要コンポーネント、鍵ストリーム生成手段は、秘密鍵そのものであると考えられる。
（ｉｉ）鍵ストリーム生成手段は、物理的に保護されたプラグイン／プラグアウト・システムコンポーネントとして考えられる。
【００８４】
これは、（マスター）秘密鍵が１度のみ入力され、セッション鍵が公のランダムデータに基づいて算出されるストリーム暗号の形成を可能とする。従って、秘密鍵配信に係る切実な問題は存在し得ない。
【００８５】
［ルックアップテーブル・コンセプトに基づくパケット指向ストリーム暗号］
このセクションでは、前述の基本的アイディアに基づくストリーム暗号形成の特徴的な構成について説明する。ここで提案するストリーム暗号は、パケット指向であり、パケットロスに対して耐性を持つ。
【００８６】
図７に示す標準的なストリーム暗号を想定する。図７（ａ）に示す暗号処理手段５１１は、図１の暗号処理手段１１１に対応する。図７（ｂ）に示す復号処理手段５２１は、図１の復号処理手段１２１に対応する。
【００８７】
暗号処理の施されるパケット本体は、最大２０４８バイト長であるものと想定する。鍵ストリーム・シーケンスが暗号処理手段５１１に入力されると、平文テキストおよび鍵ストリーム・バイナリ・シーケンスデータに対して、ビット・バイ・ビットのＸＯＲ処理が実行される。また、一方、復号処理では、復号処理手段５２１において、暗号文テキストと、鍵ストリーム・バイナリ・シーケンスデータに対して、ビット・バイ・ビットのＸＯＲ処理が実行される。
【００８８】
本発明の好適な実施例に係る鍵ストリーム生成手段５１２，５２２は、鍵ストリーム列を生成する。図８に示すように、鍵ストリーム生成手段５１２，５２２は、耐タンパＲＯＭ５３０内に構成されることが好ましい。
【００８９】
［鍵ストリーム生成手段構成］
ここで提案する鍵ストリーム生成手段は、ブロック構成として想定すると、以下のコンポーネントからなる。
（ａ）入力値非線形マッピング処理：｛０，１｝8→｛０，１｝8を実行するための、各々が２8バイトからなる入力値置換処理用の１６の異なるルックアップテーブルＩＳ（Ｉｎｐｕｔ  Ｓｕｂｓｔｉｔｕｔｅ）１−ＩＳ１６と、
（ｂ）１６の異なるバイト（ｂｙｔｅｓ）ｓ１−ｓ１６、
（ｃ）ラテンスクェア非線形マッピング処理：｛０，１｝16→｛０，１｝8を実行するための各々が２16バイトからなる１６の異なるルックアップテーブルＬＳ（Ｌａｔｉｎ  Ｓｑｕａｒｅ）１−ＬＳ１６と、
（ｄ）各々が２15バイトからなり、１６の異なるランダムシーケンスを格納した１６の異なるレジスタＲ１−Ｒ１６と、
（ｅ）出力値非線形マッピング処理：｛０，１｝8→｛０，１｝8を実行するための、各々が２8バイトからなる出力値置換処理用の１６の異なるルックアップテーブルＯＳ（Ｏｕｔｐｕｔ  Ｓｕｂｓｔｉｔｕｔｅ）１−ＯＳ１６と、
【００９０】
上述の鍵ストリーム・コンポーネントの全てのコンテンツは、秘密鍵によって決定される。すなわち、秘密鍵の長さは１６（２8＋１＋２16＋２15＋２8）バイトである。秘密鍵はたった１度のみ配送され、耐タンパＲＯＭ内に格納されるので、このような長いデータ長を持つ秘密鍵が許容される。実際には、ユーザ自身は、秘密鍵自体を知る必要がない。
【００９１】
各鍵ストリーム・シーケンスは、ランダムデータおよび秘密鍵に基づいて生成される。ランダムデータは秘密でない１２８ビットデータである。ランダムデータは、例えばパケットデータ本体の暗号処理のなされていない最初の１６バイト部分に付加する構成が想定可能である。
【００９２】
ランダムデータは、データヘッダ一に付加することができる。例えばＴＣＰヘッダＵＤＰヘッダ等である。データ送信側のパケット出力手段は、上述の秘密としないランダムデータを持つヘッダを有するパケットを生成して出力する。その他のデータ部分は、前述の最初の１６バイトおよび秘密鍵に基づく暗号化処理が施される
【００９３】
一方、データ受信側においては、データ受信側に備えられたバケット解析手段が、受信パケットから秘密状態にないランダムデータを抽出する。以下、ランダムデータバイトをａ１，ａ２，…，ａ１６と記載する。
【００９４】
［鍵ストリーム生成手段初期化処理］
鍵ストリーム生成手段の初期化処理は以下のステップを含む処理である。
（ａ）初期化処理フェーズＩ（図９参照）
アドレスａ１−ａ１６に基づいて、入力値置換処理用テーブルＩＳ（Ｉｎｐｕｔ  Ｓｕｂｓｔｉｔｕｔｅ）１−ＩＳ１６から、それぞれの出力値の読み出し、図９に示すように、ラテンスクェア・テーブルＬＳ（Ｌａｔｉｎ  Ｓｑｕａｒｅ）１−ＬＳ１６から出力値を読み出す。
【００９５】
（ｂ）初期化処理フェーズＩＩ（図１０参照）
以下の処理を１６サイクル繰り返す。
図１０に示すスキームに従って、前サイクルのＬＳ１−ＬＳ１６の出力値を現サイクルのＬＳ１−ＬＳ１６の入力として設し、
図１０に示す構成に従って、テーブルＬＳ１−ＬＳ１６から出力を読み出す。
【００９６】
ＬＳ１−ＬＳ１６の各々はラテンスクェア・ルックアップテーブルであり、ｎ×ｎ次元のスクェア・マトリクス（正方行列）である。各エレメントは、以下に示す態様に従った０，１，２，〜ｎ−１からなる数値配列を持つ。各行は、０，１，２，〜ｎ−１の入れ替え配列を有し、各列も、０，１，２，〜ｎ−１の入れ替え配列を有する。ｎ＝１６の設定の場合、例えばＬＳは図１１に示す構成を持つ。
【００９７】
［鍵ストリーム・シーケンス生成処理］
上述の初期化処理後に実行される、各々が１６バイトブロックからなる暗号化／復号化用鍵ストリーム・シーケンスの生成処理は以下のステップを有する。
【００９８】
１．下記サイクルを１６回繰り返す。
各レジスタＲ１−Ｒ１６（図１２参照）から新規バイトの読み出し、
図１２に示す構成に従って、前サイクルのＬＳ１−ＬＳ１６の出力値を現サイクルのＬＳ１−ＬＳ１６の入力として設定し、ＬＳ１−ＬＳ１６からの新出力値を読み出す。
２．図１２に示す構成に従って、ＯＳ（Ｏｕｔｐｕｔ  Ｓｕｂｓｔｉｔｕｔｅ）１−ＯＳ１６の出力に基づいて、１６の出力バイトを生成する。
【００９９】
［鍵ストリーム生成手段の主要特徴］
ここで提案する鍵ストリーム生成手段の処理実行時の複雑性は、以下に説明する通りである。
（ａ）鍵ストリーム生成手段の初期化処理には、２８８のＬＵＴ処理が必要とされる。
（ｂ）各鍵ストリームシーケンスバイトの生成時には、１７回のＬＵＴ処理のみが必要となる。
【０１００】
従って、ここでの提案に係るアルゴリズムは、高速処理可能であり、リアルタイムアプリケーションに適合したものであると言える。
【０１０１】
鍵ストリーム生成手段における暗号セキュリティ評価は重要であり、この話題を説明したものとして、例えば下記に示す文献がある。
【０１０２】
M.J.Mihaljevic and H. Imai, "Cryptanalysis of TOYO- CRYPT-HS1 stream cipher", IEICE Transactions on Fundamentals, vol. E85-A, pp. 66-73, Jan. 2002.
M.J. Mihaljevic, M.P.C. Fossorier and H. Imai, "Fast correlation attack algorithm with the list decoding and an application", Fast Software Encryption Workshop - FSE2001, Yokohama, Japan, April 2001, Pre-proceedings, pp. 208-222 (also Lecture Notes in Computer Science}, in print).
【０１０３】
M.J. Mihaljevic, M.~P.~C. Fossorier and H. Imai, "A low-complexity and high-performance algorithm for the fast correlation attack", Fast Software Encryption 2000,  Lecture Notes in Computer Science, vol. 1978, pp. 196-212, 2001.
M.J. Mihaljevic, M.~P.~C. Fossorier and H. Imai, "On decoding techniques for cryptanalysis of certain encryption algorithms", IEICE Trans. Fundamentals, vol. E84-A, pp. 919-930, April 2001.
【０１０４】
M.J. Mihaljevic and J. Golic, "A method for convergence analysis of iterative probabilistic decoding",  IEEE Transactions on Information Theory, vol. 46, pp. 2206-2211, Sept. 2000.
"New European Schemes for Signatures, Integrity and Encryption (NESSIE) Project",
【０１０５】
なお、提案に係る鍵ストリーム生成手段における暗号の安全性は、本明細書においてはスコープ外であり、以下に説明することを重要点として指摘するにとどめる。
【０１０６】
提案に係る鍵ストリーム生成手段における暗号の安全性は、生成手段構成に対応する非線形方程式の解を得る困難性に基づくものであり、実際上、２128の異なる鍵ストリーム・シーケンスを生成することになる。
【０１０７】
［セクションＤ］
結論
以上、特定の実施例に基づいて、本発明を説明してきたが、本発明は、実施例に限定されるものではない。当業者が該実施例の修正や代用を成し得ることは自明である。本発明の要旨、すなわち、特許請求の範囲の欄の記載を逸脱しない範囲で実施例の修正や代用は成し得るものである。
【０１０８】
【発明の効果】
上述したように、本発明に従えば、低信頼度の公衆パケットスイッチ・ネットワークにおけるストリーミング・メディアに対応したパケットロス回復および限定受信を実行するための新規な遅延の少ないまた簡易な構成を持つパケット指向型技術が提供される。
【０１０９】
さらに、本発明は、低信頼度のネットワークでのストリーミング・メディア配信におけるパケットロス回復処理としての新規アプローチである高速バイナリ消失訂正技術を提供する。提案に係る消失訂正アルゴリズムは、高速で遅延の少ないものである。具体例の提示として、（７，４）バイナリ・ハミングコードを適用したパケットの高速バイナリ消失訂正手法具体例を示した。
【０１１０】
なお、他の短いバイナリ線形ブロックコードも同様に適用可能である。ただ１つの制限は、暗号化あるいは復号化処理用ＬＵＴのサイズに適合することのみである。例えば、他のバイナリコードの候補としては、バイナリ（８，４）拡張ハミングコードや、バイナリ（２４，１２）拡張ゴーレイ（Ｇｏｌａｙ）コードが含まれる。小さなＬＵＴの適用は、デコード処理の高速化を実現し、処理遅延を低減させるものである。
【０１１１】
本発明に従えば、公衆ネットワーク上におけるストリーミング・メディア・アプリケーションに適用するための新規な鍵ストリームを適用したパケット指向限定受信技術が提供される。その構成は、ＬＵＴを適用した処理のみに基づくものであり、この処理は耐タンパＲＯＭ内での処理として実行される。このコンセプトに基づく利点は以下に示す通りである。
【０１１２】
（ｉ）鍵ストリームの主要コンポーネント、および鍵ストリーム生成手段構成自体が秘密鍵として認識される。
（ｉｉ）鍵ストリーム生成手段がプラグイン／プラグアウト・システムコンポーネントとして認識される。
【０１１３】
この開発された限定受信技術は高速であり、その暗号学的な安全性は、鍵ストリーム生成手段構成に対応する非線形方程式の解を得る困難性に基づくものであり、実際上、２128の異なる鍵ストリーム・シーケンスを生成することになる。
【図面の簡単な説明】
【図１】ストリーミングメディア・アプリケーションに適用するセキュアな信頼性の高いシステム構成図である。
【図２】パケットのバイナリ・エンコード処理を説明する図である。
【図３】高速バイナリ消失訂正アルゴリズムを示すフローチャートである。
【図４】（７，４）ハミングコードを適用したエンコードおよび消失訂正処理を実行するシステム構成図である。
【図５】ルックアップテーブルのコンテンツ例である。
【図６】（７，４）ハミングコードを適用したエンコードおよび消失訂正処理を実行するシステム構成図である。
【図７】鍵ストリーム生成手段構成を示す図である。
【図８】耐タンパＲＯＭ内に構成した鍵ストリーム生成手段構成を示す図である。
【図９】鍵ストリーム生成手段における初期化処理フェーズについて説明する図である。
【図１０】鍵ストリーム生成手段における初期化処理フェーズについて説明する図である。
【図１１】鍵ストリーム生成手段におけるラテンスクウェアテーブル構成について説明する図である。
【図１２】鍵ストリーム生成手段における鍵ストリーム生成フェーズについて説明する図である。
【符号の説明】
１１１  暗号処理手段
１１２  消失対応バイナリエンコーダ
１２１  復号処理手段
１２２  消失対応バイナリデコーダ
２１１  ハミングエンコーダ
２１２  消失発生チャネル
２２１  消失置換手段
２２２  メモリ
２２３  メモリ
２２４  遅延手段
２２５  ルックアップテーブル
２２６，２２７  デコード処理用ＬＵＴ
２２８  演算手段
２２９  セレクタ
２３１  アドレス算出手段
２３２  消失対応デコード用ルックアップテーブル
５１１  暗号処理手段
５１２  鍵ストリーム生成手段
５２１  復号処理手段
５２２  鍵ストリーム生成手段
５３０  耐タンパＲＯＭ
【図１】
0003918578.tif 000002
【図２】
0003918578.tif 000003
【図３】
0003918578.tif 000004
【図４】
0003918578.tif 000005
【図５】
0003918578.tif 000006
【図６】
0003918578.tif 000007
【図７】
0003918578.tif 000008
【図８】
0003918578.tif 000009
【図９】
0003918578.tif 000010
【図１０】
0003918578.tif 000011
【図１１】
0003918578.tif 000012
【図１２】
0003918578.tif 000013