(57)【要約】【課題】被圧縮データ列から圧縮データ列を生成するデータ圧縮方法に関し、データ圧縮の秘匿性を向上する。【解決手段】被圧縮データ列の先頭に、スクランブル値を付与し（１４）、動的可変長符号化を使用して、データ圧縮する（１６）。ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできる。即ち、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、処理時間の短縮に有効である。【選択図】図７
2005217842.tif 000002
【特許請求の範囲】
【請求項１】
被圧縮データ列から圧縮データ列を生成するデータ圧縮方法において、
入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するステップと、
前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するステップとを有する
ことを特徴とするデータ圧縮方法。
【請求項２】
前記圧縮されたデータ列の先頭部分を取得するステップと、
前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取る又は前記鍵で暗号化するステップと、
前記排他的論理和又は暗号化で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップとを更に有する
ことを特徴とする請求項１のデータ圧縮方法。
【請求項３】
請求項１で生成された圧縮データ列を復元するデータ復元方法であって、
前記圧縮データ列を前記動的可変長符号化により展開するステップと、
前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有する
ことを特徴とするデータ復元方法。
【請求項４】
請求項２で生成された圧縮データ列を復元するデータ復元方法であって、
前記圧縮されたデータ列の先頭部分を取得するステップと、
前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取る又は復号化するステップと、
前記排他的論理和又は復号化で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップと、
前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するステップと、
前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有する
ことを特徴とするデータ復元方法。
【請求項５】
被圧縮データ列から圧縮データ列を生成するデータ圧縮プログラムであって、
入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するプログラムデータと、
前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するプログラムデータとを有する
ことを特徴とするデータ圧縮プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的にデータを格納又は通信するためのデータ圧縮方法、データ復元方法及びそのプログラムに関し、特に、データの秘匿性を向上したデータ圧縮方法、データ復元方法及びそのプログラムに関する。
【背景技術】
【０００２】
近年、文字コード、画像データ等の様々な種類のデータがコンピュータで扱われるようになるのに伴い、取り扱われるデータ量も増大している。電子的にデータを格納又は通信するには、データを圧縮して、格納又は通信することが、有効である。
【０００３】
一方、インターネットおよび携帯端末の普及に伴い、データを格納、通信するときのセキュリティに対する意識が高くなってきている。このため、暗号化技術が有効である。暗号化は、大きく分けて、ストリーム暗号とブロック暗号とがあるが、実装がシンプルなブロック暗号の方が主流になっている。
【０００４】
ブロック暗号は、データを予め定めたビットサイズに分割して、分割したブロック毎に暗号化を行う機構になっている。このため、全く中身の同じ２つの異なるブロックからそれぞれ生成される暗号データが全く同じになり、使い方に注意しないと秘匿性が下がる。
【０００５】
この秘匿性を高めるため、従来の技術では、図２７に示すように、連鎖的に前のブロックを用いて次のブロックをランダマイズするCBC (Cipher Block Chaining) モードが提案されている（例えば、非特許文献１、２）。
【０００６】
即ち、図２７に示すように、CBC暗号では、先頭ブロックをランダマイズするための初期値（初期化ベクトル）を用意し、ブロック化された平文の先頭ブロックを、XOR演算等でランダマイズした後、暗号化し、暗号化ブロックを作成する。
【０００７】
この暗号化ブロックと、次の平文ブロックを、XOR演算等でランダマイズした後、暗号化し、次の暗号化ブロックを作成する。以下、同様にして、平文ブロックを暗号化する。
【０００８】
又、CBC復元では、暗号化と同一の初期値（初期化ブロック）を用意し、先頭の暗号化ブロックを、復号化した後、XOR演算等でランダム化を解除し、元の平文ブロックを得る。
【０００９】
この先頭の暗号化ブロックと、次の暗号化ブロックの復号化したものを、XOR演算等でランダム化を解除し、次の平文ブロック２を得る。以下、同様にして、暗号化ブロックを復号化する。
【００１０】
このように、暗号化だけでは、解読され易いため、データをランダマイズし、ランダマイズした後のデータを暗号化することにより、秘匿性を向上させている。
【非特許文献１】「暗号技術入門」（著者  結城  浩、ソフトバンクパブリッシング社発行）
【非特許文献２】「Practical Cryptography」（著者  Bruce Schneier, Niels Ferguson, John Wiley & Sons Inc発行）
【００１１】
一方、データを圧縮後に、圧縮データにダミーデータを付加して、ダミーデータを付加した圧縮データ全体を暗号化する方法も提案されている（例えば、特許文献３、４）。
【特許文献３】特開平１０−１２１７５３号公報
【特許文献４】ＷＯ  ００／５２６８４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
前者の従来の方法は、連鎖的に前のブロックを用いて、次のブロックをランダマイズすることにより、暗号化の秘匿性を向上する方法であるが、先頭ブロックをランダマイズするための初期値を必要とし、生成側と復元側とで初期値を共有しなければならないという問題がある。
【００１３】
又、暗号化処理だけでも高負荷のため、更に、ランダマイズの処理が嵩み、処理時間がかかるという問題も生じる。
【００１４】
後者の従来技術では、基本的に、前者の従来技術のランダム化初期値を圧縮済みのデータに対し、付与する方法であるため、同様の問題が生じる。
【００１５】
従って、本発明の目的は、生成側と復元側とで、初期値を共有しなくても、暗号化の秘匿性を維持するためのデータ圧縮方法、データ復元方法及びそのプログラムを提供することにある。
【００１６】
又、本発明の他の目的は、暗号化の秘匿性を維持しつつ、暗号化の処理時間を短縮するためのデータ圧縮方法、データ復元方法及びそのプログラムを提供することにある。
【００１７】
更に、本発明の他の目的は、暗号化強度を増加しても、処理時間を短縮するためのデータ圧縮方法、データ復元方法及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１８】
この目的の達成のため、本発明のデータ圧縮方法は、入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するステップと、前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するステップとを有する。
【００１９】
又、本発明のデータ復元方法は、前記圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有する。
【００２０】
又、本発明のデータ圧縮プログラムは、入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するプログラムデータと、前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するプログラムデータとを有する。
【００２１】
更に、本発明のデータ圧縮方法は、好ましくは、前記被圧縮データ列又は前記先頭にスクランブル値を付与された被圧縮データ列のデータサイズを取得するステップと、前記取得したデータサイズを、前記先頭にスクランブル値を付与された被圧縮データ列に付与するステップを更に有する。
【００２２】
更に、本発明のデータ復元方法は、好ましくは、前記圧縮データ列から前記データサイズを除去するステップと、前記データサイズを除去された圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去するステップと、前記展開されたデータ列又は前記圧縮データ列のデータサイズを求めるステップと、前記除去したデータサイズと前記求めたデータサイズとを比較するステップと、前記比較結果に応じて、前記スクランブル値を除去した展開データを出力するステップとを有する。
【００２３】
更に、本発明のデータ圧縮方法は、好ましくは、前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップとを更に有する。
【００２４】
更に、本発明のデータ復元方法は、好ましくは、前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有する。
【００２５】
更に、本発明のデータ圧縮方法は、好ましくは、前記圧縮されたデータ列の先頭部分又は全部を取得するステップと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵を用いて暗号化するステップと、前記暗号化で求めたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるステップとを更に有する。
【００２６】
更に、本発明のデータ復元方法は、好ましくは、前記圧縮されたデータ列の先頭部分又は全部を取得するステップと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵で解読するステップと、前記解読されたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるステップと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有する。
【００２７】
更に、本発明のデータ圧縮方法は、好ましくは、前記先頭部分が置き換えられた圧縮データ列の前記先頭部分と前記鍵との排他的論理和を取り、元の圧縮されたデータ列に変換するステップと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の他の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるステップとを更に有する。
【００２８】
更に、本発明のデータ圧縮方法は、好ましくは、前記先頭部分が置き換えられた圧縮データ列の前記先頭部分を前記鍵で解読して、元の圧縮されたデータ列に変換するステップと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分を、所定のビット長の他の鍵で暗号化するステップと、前記暗号化で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるステップとを更に有する。
【００２９】
更に、本発明のデータ圧縮方法は、好ましくは、前記圧縮ステップは、圧縮のための符号表に従い、前記圧縮データを生成するステップと、前記圧縮したデータ列に従って、前記符号表を更新するステップとからなる。
【００３０】
更に、本発明のデータ圧縮方法は、好ましくは、前記符号表がスプレイ木構成である。
【００３１】
更に、本発明のデータ復元方法は、好ましくは、前記展開ステップは、展開のための符号表に従い、前記展開データを生成するステップと、前記展開したデータ列に従って、前記符号表を更新するステップとからなる。
【００３２】
更に、本発明のデータ復元方法は、好ましくは、前記符号表がスプレイ木構成である。
【発明の効果】
【００３３】
本発明では、被圧縮データ列の先頭に、スクランブル値を付与し、動的可変長符号化を使用して、データ圧縮するため、ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできる。即ち、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、処理時間の短縮に有効である。
【発明を実施するための最良の形態】
【００３４】
以下、本発明の実施の形態を、第１の実施の形態、圧縮方法の詳細、第２の実施の形態、第３の実施の形態、第４の実施の形態、他の実施の形態の順で説明するが、本発明は、この実施の形態に限られない。
【００３５】
［第１の実施の形態］
図１は、本発明のデータ圧縮方法の第１の実施の形態のブロック図、図２は、本発明のデータ復元方法の第１の実施の形態のブロック図、図３は、図１のデータ圧縮動作の説明図、図４乃至図６は、本発明に使用される圧縮方法の説明図である。
【００３６】
図１及び図２は、データ圧縮／復元方法の機能ブロックを示し、ハードウェア又はプログラムで実現する。図１に示すように、生成側（圧縮側）は、データ入力部１０、乱数発生部１２、乱数付与部１４、圧縮部１６、データ出力部１８を有する。
【００３７】
データ入力部１０からの対象データの先頭に、乱数発生部１２で発生した乱数を、乱数付与部１４で、付与する。そして、乱数を含めて対象データを、圧縮部１６で圧縮し、データ出力部１８から出力する。
【００３８】
図３に示すように、対象（入力）データの先頭に、予め定めたビット長または指定された任意のビット長のスクランブル値（例えば、乱数）を付与し、付与したスクランブル値を含めた対象データを圧縮しながら、圧縮済みのデータに応じて圧縮符号表を更新する（以下、スクランブル値を付与して圧縮した圧縮データをスクランブル圧縮データと呼ぶ）。
【００３９】
このことにより、先頭寄りのデータの影響を受けて、後方データの圧縮符号が変更される。このように、ランダム性の高いデータを生成する圧縮を用いることにより、対象データをランダマイズできる。
【００４０】
一方、復元側は、図２に示すように、データ入力部２０と、圧縮データ展開部２２と、乱数除去部２４と、データ出力部２６とを有する。データ入力部２０から入力された圧縮データを、展開部２２で展開し、乱数除去部２４で、先頭の乱数を除去して、出力部２６から出力する。これらの乱数は、予め定めたビット長、または外部から指示されたビット長とする。
【００４１】
上述の実施の形態では、乱数を生成して付与しているが、対象データの先頭に付与する値は、どういう値であってもよく、恣意的でない値が望ましい。簡易的に切り分けが可能となる。
【００４２】
このように、データ圧縮により、ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできる。即ち、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、処理時間の短縮に有効である。
【００４３】
前述の圧縮方法について、説明する。図４は、本発明に好適なロスレス圧縮方法の説明図である。ロスレス圧縮方法は、元のデータが完全に復元できるロスレス(情報の損失なない)の圧縮方法である。
【００４４】
ロスレス圧縮としては、（ａ）辞書型のユニバーサル圧縮法、（ｂ）統計型の適応符号化圧縮法，が良く使われている。以降では，情報理論の表記法を踏襲し，入力するデータの１ワードを「文字」，データ列を「文字列」と呼ぶことにする。
【００４５】
（ａ）の圧縮法は，過去に出現した文字列を辞書に持っていて、一度現れた文字列を、辞書の位置や辞書登録番号で表す方式である。（ｂ）の圧縮法は、過去に出現した文字列の出現確率に応じて、出易い文字程、短い符号を割り当てて符号化する方法である。これらの方法は、一般に図４に示すように、２つのステージで構成して、高圧縮を得る。
【００４６】
即ち、「モデル化」のステージ１０００では、「同じ文字が繰り返す長さ」や，「過去に同じ文字列が出てきた位置，その長さ」の組や，「予め文字種をグループ分けした場合の直前文字のグループ番号」や，規則性が捉えられない文字等を、中間データとして出力する。
【００４７】
「可変長符号化」のステージ２０００では、入力される中間データの文字に対して、出易いもの程、短い符号語を割り当てる。中間データは、１文字が固定長で、規則性が残っており、可変長符号化段で冗長性を省くことになる。従って、可変長符号化のやり方が、圧縮データにランダム性を与える鍵となる。
【００４８】
この可変長符号化を説明する。図５は、静的符号化方法の説明図、図６は、本発明に好適な動的符号化方法の説明図である。可変長符号化の主な方法には、図５に示す静的符号化方法と、図６に示す動的符号化方法とがある。
【００４９】
図５に示すように、静的符号化方法は、圧縮するデータまたは，圧縮するデータのサンプルを入力して，現れる文字の出現確率を求め，出易い文字程，短いbit数を割り当てた符号語を並べた符号表２０１０を作る。そして，データを入力し，符号表２０１０に従って，各文字を符号語で置換え，圧縮符号化する。
【００５０】
復元する場合は，圧縮と同じ符号表２０１０を用いて、復号化する。このため，復元側に、圧縮側（送信側）と同じ符号表２０１０を送る必要がある。また，サンプルデータから作った符号表２０１０を用いる場合は，データの種類ごとに符号表を備える必要がある。代表的な静的符号化法としては、Huffman符号化、Shanon-fano符号化がある。
【００５１】
一方、動的符号化方法は、図６に示すように、圧縮するデータを入力し、上記のような符号表２０２０を動的に作りながら、即ち、参照と更新を繰り返し、作った符号表２０２０で逐次、圧縮符号化する。現在の文字の符号化には、過去に入力した文字から出現確率を求めて、割り当てた符号表２０２０が用いられる。
【００５２】
又、復元する場合は，圧縮した場合と同様に，逐次 復元した文字から符号表２０４０を動的に作りながら，復号する。復元側では，圧縮側と同じ符号表２０４０を圧縮データから再構成できるので，符号表２０２０を送る必要はない。代表的な動的符号化法として、動的Huffman符号化方法が、最適な方法であり、Splay符号化法は、符号表の作成が簡単かつ高速な方法である。
【００５３】
次に、解読が困難な圧縮法の観点から、静的符号化法と動的符号化法を検討する。まず，圧縮データの暗号としての解読のし難さを考えると、圧縮データは、可変長符号で構成されるので、１文字ごとの区切り位置や符号長が分からなければ解読ができない。
【００５４】
しかし、静的符号化の場合は、圧縮データ全体で同一の符号表を使い、符号語が固定しているので、解読が比較的容易になる。また、符号表が入手された場合には、解読すべき探索回数は大幅に減って、解けてしまう。
【００５５】
これに対して、動的符号化の場合は、符号表を作りながら、符号化するので、図３で示したように、符号語が固定していない。動的符号化では、圧縮データの最初の部分は、符号表が初期状態に近いので、解読され易いが、最初の部分を隠蔽すれば，途中から復元することは、非常に困難になる。
【００５６】
このため、本発明では、最初の部分を隠蔽するため、スクランブルデータを対象データの先頭に付与し、動的符号化によるロスレス圧縮方法を用いることで、従来のCBCモードように、前のデータで次のデータを暗号化する機能を圧縮自体に付与するものである。これにより、データ圧縮により、ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできる。即ち、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、処理時間の短縮に有効である。
【００５７】
［圧縮方法の詳細］
次に、本発明の実施の形態に適用される動的符号化法の動的Huffman符号化とSplay符号化を、具体的に説明する。
【００５８】
図７は、図１のデータ圧縮方法の第１の実施の形態のブロック図、図８は、図２のデータ復元方法の第１の実施の形態のブロック図、図９乃至図１２は、図７のデータ圧縮動作の説明図。
【００５９】
図７及び図８は、データ圧縮／復元方法の機能ブロックを示し、ハードウェア又はプログラムで実現し、それぞれ、動的Huffman符号化を適用した圧縮部１６、展開部２２の詳細を示す。図７に示すように、生成側（圧縮側）は、データ入力部１０、乱数発生部１２、乱数付与部１４、圧縮部１６、データ出力部１８を有する。
【００６０】
圧縮部１６は、圧縮データ生成部３０と、圧縮符号表更新部３２と、圧縮符号表保持部３４とを有する。この例でも、データ入力部１０からの対象データの先頭に、乱数発生部１２で発生した乱数を、乱数付与部１４で、付与する。そして、乱数を含めて対象データを、後述する圧縮部１６で圧縮し、データ出力部１８から出力する。
【００６１】
一方、復元側は、図８に示すように、データ入力部２０と、圧縮データ展開部２２と、乱数除去部２４と、データ出力部２６とを有する。圧縮データ展開部２２は、展開データ作成部３６と、圧縮符号表更新部３８と、圧縮符号表保持部４０とを有する。
【００６２】
この例でも、データ入力部２０から入力された圧縮データを、後述する動的Huffman符号化を用いた展開部２２で展開し、乱数除去部２４で、先頭の乱数を除去して、出力部２６から出力する。これらの乱数は、予め定めたビット長、または外部から指示されたビット長とする。
【００６３】
次に、図７及び図８で適用した動的Huffman符号化方法を、図９乃至図１２を使用して、説明する。動的Huffman符号化法は、入力データ中の各文字の出現頻度を計数しながら、符号化し、文字の計数値が、大きく変化した時点で、符号表を作り直して、符号化する方法である。以下では，この方法を DH (dynamic Huffman) 符号と略す。DH符号は，1980年前半から使われるようになった。FGKアルゴリズムと，その改良版の Vアルゴリズムが提案されている。
【００６４】
図９乃至図１２により、具体的に説明する。先ず、データ列 "aa bbb cccc ddddd eeeeee fffffff gggggggg"を入力したとき、符号語を作成しながら、FGKアルゴリズムでDH符号化する例を説明する。図９乃至図１２において、丸内の「Ｘ」は、出現回数ｘの内部節点、四角内の「ｙ」は、出現回数ｙの葉の節点を示す。
【００６５】
符号化手順は、最初に，符号の木は、葉が１つだけの番号「０」の節点だけからなる。番号「０」の節点は、未使用の全ての文字を代表する節点である。尚、図９乃至図１２では、番号は、丸及び四角の左上に記載してある。
【００６６】
次に、文字が入力されるごとに、その文字にいたる経路上の全ての節点の計数値（図の丸内の数値）がインクリメントされ，兄弟の性質（Sibling property）を保つように符号の木が再構成される。兄弟の性質とは，１つの節点に繋がる２つの枝の計数値が、同じ値か、１つしか違わない値を持つことである。
【００６７】
兄弟の性質を保持すれば，Huffman符号になることが証明されている。例えば、図９は、“aa bb"の符号化後の符号の木を示し、「１１」が、次の”ｂ”の符号語となる。
【００６８】
計数値をインクリメントすると、兄弟の性質が崩れるときは、置換によって木の形を更新し，兄弟の性質を維持する。この置換は、例えば、図９で，文字”b”が入力されたとき，そのまま計数値をインクリメントすると、兄弟の性質が崩れるが，図１０に示すように、文字”b”の葉を文字”a”の葉と置き換えてから、インクリメントすることで，兄弟の性質が保たれる。
【００６９】
例えば、図１０では、３番目の文字”ｂ”を符号化後の木を示し、「１０１」が、次のスペースの符号語となる。符号の木の形は変わらず、頻度の計数値だけが更新される。又、「１１１」が、最初の”ｃ”の符号語となる。
【００７０】
更に、新たな文字kを入力したときは，文字kを番号「０」の葉の符号語で符号化するとともに，文字kが出たことを指定する情報を符号化する。これと同時に，番号「０」の葉を，新たな番号「０」と文字kの葉に分割する。
【００７１】
例えば、図１１は、最初の文字”ｃ”を符号化した後の符号の木を示す。そして、前述のデータ列の全ての入力終了後の符号の木の構成を、図１２に示す。
【００７２】
このように、図９から図１２のように、符号表（符号の木）を更新しながら、逐次文字を符号化する。例えば、図９では、文字”ａ”は、符号語「０」であるが、図１２では、「１０００１」となる。
【００７３】
次に、Splay符号化法を説明する。図１３は、図１のデータ圧縮方法の第２の実施の形態のブロック図、図１４は、図２のデータ復元方法の第２の実施の形態のブロック図、図１５乃至図１６は、図１３のデータ圧縮動作の説明図。
【００７４】
図１３及び図１４は、データ圧縮／復元方法の機能ブロックを示し、ハードウェア又はプログラムで実現し、それぞれ、Splay符号化を適用した圧縮部１６、展開部２２の詳細を示す。図１３に示すように、生成側（圧縮側）は、データ入力部１０、乱数発生部１２、乱数付与部１４、圧縮部１６、データ出力部１８を有する。
【００７５】
圧縮部１６は、圧縮データ生成部５０と、スプレイ木更新部５２と、スプレイ木保持部５４とを有する。この例でも、データ入力部１０からの対象データの先頭に、乱数発生部１２で発生した乱数を、乱数付与部１４で、付与する。そして、乱数を含めて対象データを、後述するスプレイ符号化による圧縮部１６で圧縮し、データ出力部１８から出力する。
【００７６】
一方、復元側は、図１４に示すように、データ入力部２０と、圧縮データ展開部２２と、乱数除去部２４と、データ出力部２６とを有する。圧縮データ展開部２２は、展開データ生成部５６と、スプレイ木更新部５８と、スプレイ木保持部６０とを有する。
【００７７】
この例でも、データ入力部２０から入力された圧縮データを、後述するスプレイ符号化を用いた展開部２２で展開し、乱数除去部２４で、先頭の乱数を除去して、出力部２６から出力する。これらの乱数は、予め定めたビット長、または外部から指示されたビット長とする。
【００７８】
次に、図１３及び図１４で適用したSplay符号化方法を、図１５乃至図１６を使用して、説明する。Splay符号は、符号の木において、ルートからアクセスされた葉までのパスの長さが1/2になるように，符号木を動的に組替えて，符号表を入力データに適応させるものである。動的Huffman符号のように，文字の出現数を計数する操作はなく，シンプルで高速に動作する。
【００７９】
元々，Splay  treeは、自己均衡する２進探索木(self-balancing binary search tree) の一つとして考案された。図１５及び図１６において、符号の木は，２進木(binary tree)で表される。２進木は、枝が２つで，左右の枝が「０」と「１」の1bitに対応する。２進木の葉が、各文字が対応付けられ，葉から根（ルート）までのパスの「0」，「１」が符号語に対応することになる。
【００８０】
符号木を組替えるSplay操作は，図１５に示すように、アクセスされた節点を、右のsubtreeに組替える。即ち、線形リストの先頭移動法(Move-To-Front) の操作を２進木で行ったものである。図１５は、Splay符号の符号更新の基本操作を示し、Ａがアクセスされた場合の更新操作を示す。
【００８１】
図１６のSplay符号の符号更新の例に示すように、「ｃ」がアクセスされた場合には、出現文字の符号長を1/2に縮めるように毎回，符号木を更新する。従って、文字「ｃ」のアクセス（参照）により、符号語（Ａ：００，Ｂ：０１０，Ｃ：０１１１，Ｅ：１）は、符号語（Ａ：００，Ｂ：１１０，Ｃ：１０，Ｄ：１１１，Ｅ：０１）に更新される。
【００８２】
この解読困難な動的符号化について、更に、動的Huffman符号化と Splay符号化の解読のし難さについて説明する。
【００８３】
動的Huffman符号化は，符号語が動的に変化するが，入力データの統計的性質が一様な場合は，入力データが長くなれば，符号語が一定のパターンに収束する。同様に解読され易い。一方、Splay符号化は，符号語の動的均衡を用いており，収束しない。従って解読され難い。
【００８４】
例えば、Waikato大学 S. A. Irvine氏が、博士論文(1997.3.13), "Compression and Cryptology" で各種圧縮法の暗号強度を定式化している。以下，この文献のHuffman符号とSplay符号の暗号強度に関する記述を解説する。
【００８５】
Huffman符号は安全ではないが，Splay符号は十分な強度を持つとしている。Splay符号化の暗号としての強度は，解読に要する総当り法の回数(全数探索)で表せる。
【００８６】
Splay符号の取りえる符号語数は，アルファベット・サイズ(文字種)をnとしたとき，  (2n - 2) ! / (n - 1) !バイト単位に符号化するので，n = 256のとき  3.97 x 10656，ｎ > 14ならば，暗号鍵56bitのDES (Data Encryption Standard)の探索すべき初期状態数を越えると述べている。
【００８７】
数量的には次のように考えられる。1年= 1.3 x 106秒とし、100nsで１回で探索できるとして、1万台並列に１年間，動かして，1017回しか探索できない。従って，Splay符号の圧縮データを途中から総当り法で解読することは，事実上，不可能である。
【００８８】
又、圧縮処理は１バイト単位に行なうため，アルファベット・サイズを任意に増やすのは、実装上困難である。その代わりに，図４のモデル化のステージ１０００で，直前文字の属するグループごとに別々な符号表を割り当て（「文脈を付ける」と言う）れば，アルファベット・サイズを増やしたのと等価になり，総当り回数を飛躍的増大させることができる。例えば文脈が、128通りならば，アルファベット・サイズは 等価的に256x128でn = 32Kとなり、総当り法では解読不可能となる。
【００８９】
尚、文脈をつける方法は、D. W. Jones氏の論文”Application of Splay Tree To Data Compression"(Communications of the ACM, Vol.31, No.8 Aug, 1988)で述べられている。
【００９０】
［第２の実施の形態］
図１７は、本発明のデータ圧縮方法の第２の実施の形態のブロック図、図１８は、本発明のデータ復元方法の第２の実施の形態のブロック図である。
【００９１】
図１７及び図１８も、データ圧縮／復元方法の機能ブロックを示し、ハードウェア又はプログラムで実現する。図１７に示すように、生成側（圧縮側）は、データ入力部１０、乱数発生部１２、乱数付与部１４、圧縮部１６、データ出力部１８を有する。更に、データ入力部１０の入力データ（ファイル）のサイズ値を取得するデータサイズ値取得部７０と、取得したデータサイズ値を、圧縮部１６で圧縮されたデータに付与し、データ出力部１８に渡すデータサイズ値付与部７２とを有する。
【００９２】
この動作を説明すると、データ入力部１０からの対象データの先頭に、乱数発生部１２で発生した乱数を、乱数付与部１４で、付与する。そして、乱数を含めて対象データを、圧縮部１６で圧縮する。一方、データサイズ値取得部７０は、入力部１０の入力データ（ファイル）のサイズ値を取得し、データサイズ値付与部７２は、取得したデータサイズ値を、圧縮部１６で圧縮されたデータの先頭又は最後に付与し、データ出力部１８に渡す。データサイズ値付与された圧縮データは、データ出力部１８から出力される。
【００９３】
この例でも、図３に示したように、対象（入力）データの先頭に、予め定めたビット長または指定された任意のビット長のスクランブル値（例えば、乱数）を付与し、付与したスクランブル値を含めた対象データを圧縮しながら、圧縮済みのデータに応じて圧縮符号表を更新する（以下、スクランブル値を付与して圧縮した圧縮データをスクランブル圧縮データと呼ぶ）。
【００９４】
このことにより、先頭寄りのデータの影響を受けて、後方データの圧縮符号が変更される。このように、ランダム性の高いデータを生成する圧縮を用いることにより、対象データをランダマイズできる。
【００９５】
一方、復元側は、図１８に示すように、データ入力部２０と、圧縮データ展開部２２と、乱数除去部２４と、データ出力部２６とを有する。更に、入力データからデータサイズ値を除去するデータサイズ値除去部７４と、除去されたデータサイズ値を保持するデータサイズ値保持部７６と、展開後のデータから乱数が除去されたデータのデータサイズ値を計算するデータサイズ値取得部７８と、データサイズ値保持部７６のデータサイズ値と、データサイズ値取得部７８のデータサイズ値を比較し、データ出力部２６を制御するデータサイズ値比較部８０とを有する。
【００９６】
この動作を説明すると、データ入力部２０から入力された圧縮データからデータサイズ値を除去し、データサイズ値保持部７６に保持し、データサイズ値が除去された圧縮データを、展開部２２で展開し、乱数除去部２４で、先頭の乱数を除去して、出力部２６に渡す。
【００９７】
取得部７８は、展開後のデータから乱数が除去されたデータのデータサイズ値を計算し、データサイズ値比較部８０は、データサイズ値保持部７６のデータサイズ値と、データサイズ値取得部７８のデータサイズ値を比較し、データ出力部２６を制御する。
【００９８】
このように、生成側で、データサイズ値を付与し、復元側で、入力データからデータサイズ値を除去してから展開する。展開後、データ先頭部の乱数を除去し、元の被圧縮データのデータサイズ値を取得する。最初に除去したデータサイズ値と取得したデータサイズ値が同じになるか比較をし、同じ場合、復元データを出力する。
【００９９】
このように、データサイズ値を確認することにより、改竄検出を行うことができる。勿論、データ圧縮により、ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできる。即ち、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、処理時間の短縮に有効である。
【０１００】
［第３の実施の形態］
次に、ブロック暗号化の前に、第１の実施の形態の圧縮方法を適用した実施の形態を説明する。図１９は、本発明のデータ圧縮方法の第３の実施の形態のブロック図、図２０は、本発明のデータ復元方法の第３の実施の形態のブロック図である。
【０１０１】
図１９及び図２０は、データ圧縮／復元方法の機能ブロックを示し、ハードウェア又はプログラムで実現し、それぞれ、動的符号化を適用した圧縮部１６、展開部２２を使用している。図１９に示すように、生成側（圧縮側）は、データ入力部１０、乱数発生部、乱数付与部１４、圧縮部１６、データ出力部１８を有する。
【０１０２】
圧縮部１６は、圧縮データ生成部３０と、圧縮符号表更新部３２と、圧縮符号表保持部３４とを有する。更に、圧縮データ生成部３０と、データ出力部１８との間に、圧縮データに対し、暗号処理を行う暗号化部８２を設ける。
【０１０３】
この例でも、データ入力部１０からの対象データの先頭に、乱数発生部１２で発生した乱数を、乱数付与部１４で、付与する。そして、乱数を含めて対象データを、前述した圧縮部１６で圧縮した後、暗号化部８２で暗号化し、データ出力部１８から出力する。
【０１０４】
一方、復元側は、図２０に示すように、データ入力部２０と、圧縮データ展開部２２と、乱数除去部２４と、データ出力部２６とを有する。圧縮データ展開部２２は、展開データ作成部３６と、圧縮符号表更新部３８と、圧縮符号表保持部４０とを有する。更に、データ入力部２０と展開データ作成部３６との間に、暗号解読部８４を設ける。
【０１０５】
この例でも、データ入力部２０から入力された暗号化圧縮データを、暗号解読部８４で解読後、動的符号化を用いた展開部２２で展開し、乱数除去部２４で、先頭の乱数を除去して、出力部２６から出力する。
【０１０６】
このように、暗号化を併用することにより、より暗号強度の強い圧縮データが得られる。即ち、対象データを圧縮しながら、圧縮済みのデータに応じて圧縮符号表を更新する（以下、スクランブル値を付与して圧縮した圧縮データをスクランブル圧縮データと呼ぶ）。このことにより、先頭寄りのデータの影響を受けて後方データの圧縮符号が変更される。その後、ブロック暗号を用いることで、全く中身の同じデータからも異なる暗号データを生成することができる。
【０１０７】
又、復元の際には、暗号解読後、通常の初期状態の圧縮符号表で復元し、復元後予め定めたビット長または指定されたビット長の先頭部分を除去する。
【０１０８】
この暗号化処理を軽減する方法として、図２１、図２２に示す方法が有効である。即ち、更に処理を軽減する方法として、スクランブル圧縮データの先頭と、別途鍵として取得したビット列と排他的論理和を取ることによって、スクランブル圧縮データの先頭部分を単純に展開できないようにし、ランダマイズ処理により、暗号処理自体をなくすことができる。
【０１０９】
具体的には、図２１は、図１９の圧縮構成において、暗号化部８２を、データバッファ８６、先頭取得部８８、鍵取得部９０、排他的論理和演算部９２で構成した例であり、図２２は、図２０の構成において、暗号解読部８４を、データバッファ部９２、先頭取得部９４、鍵取得部９６、排他的論理演算部９８で構成した例である。
【０１１０】
図２１に示すように、データバッファ８６から先頭取得部８８で、スクランブル圧縮データの先頭ブロックを取り出し、この先頭ブロックと、鍵取得部９０で、別途鍵として取得したビット列とを、排他的論理和演算部９２で排他的論理和を取る。データ出力部１８で、排他的論理和演算結果を、データバッファ部８６からの先頭ブロック以外のスクランブル圧縮データの先頭に付加して、出力する。
【０１１１】
一方、図２２に示すように、先頭取得部９４が、データバッファ部９２から入力データの先頭ブロックを取得し、この先頭ブロックと、鍵取得部９６で、別途鍵として取得したビット列とを、排他的論理和演算部９８で排他的論理和を取る。圧縮データ展開部２２は、排他的論理和演算結果を、データバッファ部９２からの先頭ブロック以外のスクランブル圧縮データの先頭に付加したものを、展開する。
【０１１２】
そして、乱数除去部２４で、展開されたデータの先頭ブロック（乱数）を除去し、データ出力部２６から出力する。このように、スクランブル圧縮データの先頭部分は、この鍵を用いないと復元することができず、それに続く圧縮データも復元することができない。
【０１１３】
この実施の形態では、スクランブル圧縮データが、連鎖的にデータを圧縮するため、スクランブル圧縮データの先頭ブロックのみをランダマイズすることは、全体をランダマイズ化したと同等の効果があり、しかも処理が簡単で、処理速度が向上できる。又、複雑な暗号化処理の代わりに、ランダマイズ処理を行うため、より処理が簡単で、処理速度を向上して、秘匿性を高めることができる。
【０１１４】
図２３及び図２４は、スクランブル圧縮データの先頭を、既存の暗号方法で暗号化する実施の形態を示す。具体的には、図２３は、図１９の圧縮構成において、暗号化部８２を、データバッファ８６、先頭取得部８８、鍵取得部９０、暗号部１００で構成した例であり、図２４は、図２０の構成において、暗号解読部８４を、データバッファ部９２、先頭取得部９４、鍵取得部９６、暗号解読部１０２で構成した例である。
【０１１５】
図２３に示すように、データバッファ８６から先頭取得部８８で、スクランブル圧縮データの先頭ブロックを取り出し、この先頭ブロックを、鍵取得部９０で、別途鍵として取得したビット列で、暗号化する。データ出力部１８で、暗号化結果を、データバッファ部８６からの先頭ブロック以外のスクランブル圧縮データの先頭に付加して、出力する。
【０１１６】
一方、図２４に示すように、先頭取得部９４が、データバッファ部９２から入力データの先頭ブロックを取得し、暗号解読部１０２で、この先頭ブロックを、鍵取得部９６で、別途鍵として取得したビット列で、解読する。圧縮データ展開部２２は、解読結果を、データバッファ部９２からの先頭ブロック以外のスクランブル圧縮データの先頭に付加したものを、展開する。
【０１１７】
そして、乱数除去部２４で、展開されたデータの先頭ブロック（乱数）を除去し、データ出力部２６から出力する。この暗号には、ブロック暗号でもストリーム暗号でも、公開鍵暗号を用いてもよい。例えば、トリプルDESが好適である。
【０１１８】
スクランブル圧縮データの先頭部分は、データ生成の時に使用した鍵と暗号方法に対応する解読方法を用いないと復元することができず、それに続く圧縮データも復元することができない。
【０１１９】
また、スクランブル圧縮を用いることにより単純に圧縮した場合と比べ、全く同じドキュメントをスクランブル圧縮且つ暗号化した場合でも、暗号をかけていない後部のデータ列を異なるビット列とすることができ、秘匿性がより向上する。
【０１２０】
この実施の形態でも、スクランブル圧縮データが、連鎖的にデータを圧縮するため、スクランブル圧縮データの先頭ブロックのみを暗号化することは、全体を暗号化したと同等の効果があり、しかも処理が簡単で、処理速度が向上できる。又、複雑な暗号化処理を一部に施すだけで良いため、より処理が簡単で、処理速度を向上して、秘匿性を高めることができる。
【０１２１】
［第４の実施の形態］
次に、図２１で示したスクランブル圧縮データの先頭にかけた鍵を、かけなおす実施の形態を説明する。例えば、図２１で鍵をかけたスクランブル圧縮データを、ユーザーに提供し、ユーザーが自己の鍵で、スクランブル圧縮データに鍵をかける用途がある。
【０１２２】
図２５は、図２１の圧縮処理により、スクランブルデータの先頭にかけた鍵をかけなおす第４の実施の形態の機能ブロック図である。
【０１２３】
図２５に示すように、入力部１０からバッファ部８６への入力データは、図２１の処理により、スクランブル圧縮データの先頭を第１の鍵で論理和演算したスクランブル圧縮データである。
【０１２４】
先頭取得部８８は、データバッファ部８６から、鍵と排他的論理和を取ったスクランブル圧縮データの先頭部を取得し、鍵１取得部１０４からの元の鍵で、排他的論理和演算部９２で、排他的論理和を取り、元のスクランブル圧縮データに戻す。
【０１２５】
更に戻したスクランブル圧縮データの先頭部を、鍵２取得部１０６からの別の鍵で、排他的論理和演算部９２で排他的論理和を取り、データ出力部１８で、残りの後部の圧縮データと合わせて出力する。
【０１２６】
この例では、データバッファ８６に、全てのデータを保有するようになっているが、データの先頭部のみ取得し、元のデータに上書きしてもよい。
【０１２７】
図２６は、同様に、スクランブル圧縮データの先頭の暗号をかけなおす第４の実施の形態の機能ブロック図である。図２６に示すように、入力部１０からバッファ部８６への入力データは、図２３の処理により、スクランブル圧縮データの先頭を第１の鍵で暗号化したスクランブル圧縮データである。
【０１２８】
先頭取得部８８は、データバッファ部８６から、鍵で暗号化したスクランブル圧縮データの先頭部を取得し、鍵１取得部１０４からの元の鍵で、暗号解読部１０８で、解読し、元のスクランブル圧縮データに戻す。
【０１２９】
更に戻したスクランブル圧縮データの先頭部を、鍵２取得部１０６からの別の鍵で、暗号部１１０で暗号化し、データ出力部１８で、残りの後部の圧縮データと合わせて出力する。
【０１３０】
この例でも、データバッファ８６に、全てのデータを保有するようになっているが、データの先頭部のみ取得し、元のデータに上書きしてもよい。
【０１３１】
このように、暗号化したデータの先頭部を取得し、生成側で使用した鍵と暗号方法に対応する鍵と解読方法を用いて、元のスクランブル圧縮データに戻し、更に戻した圧縮データの先頭部を別の鍵と暗号方法で暗号化し，残りの後部の圧縮データと合わせて出力する。
【０１３２】
このため、ファイル装置等に格納したスクランブル圧縮データを、その先頭ブロックのみを、他の鍵で、ランダマイズ又は暗号化すれば、スクランブル圧縮データ全体を、別の鍵で、ランダマイズ又は暗号化でき、容易に、別のスクランブル圧縮データが得られる。
【０１３３】
［他の実施の形態］
前述の実施の形態では、データ圧縮法として、動的Huffman符号化とSplay符号化で説明したが、他の動的可変長符号化方法を適用できる。同様に、実施の形態の各機能ブロックは、プログラムでも、ハードウェアでも実現できる。
【０１３４】
又、使用用途も、ファイルの格納、取り出しの他に、送信、受信にも適用でき、対象データも文字列の他に、画像データにも適用できる。更に、第２の実施の形態で、被圧縮データ列のデータサイズを取得しているが、前述した先頭にスクランブル値を付与された被圧縮データ列のデータサイズを取得しても良い。
【０１３５】
以上、本発明を実施の形態により説明したが、本発明の趣旨の範囲内において、本発明は、種々の変形が可能であり、本発明の範囲からこれらを排除するものではない。
【０１３６】
（付記１）被圧縮データ列から圧縮データ列を生成するデータ圧縮方法において、入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するステップと、前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するステップとを有することを特徴とするデータ圧縮方法。
【０１３７】
（付記２）前記被圧縮データ列又は前記先頭にスクランブル値を付与された被圧縮データ列のデータサイズを取得するステップと、前記取得したデータサイズを、前記先頭にスクランブル値を付与された被圧縮データ列に付与するステップを更に有することを特徴とする付記１のデータ圧縮方法。
【０１３８】
（付記３）前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップとを更に有することを特徴とする付記１のデータ圧縮方法。
【０１３９】
（付記４）前記圧縮されたデータ列の先頭部分又は全部を取得するステップと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵を用いて暗号化するステップと、前記暗号化で求めたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるステップとを更に有することを特徴とする付記１のデータ圧縮方法。
【０１４０】
（付記５）前記先頭部分が置き換えられた圧縮データ列の前記先頭部分と前記鍵との排他的論理和を取り、元の圧縮されたデータ列に変換するステップと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の他の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるステップとを更に有することを特徴とする付記３のデータ圧縮方法。
【０１４１】
（付記６）前記先頭部分が置き換えられた圧縮データ列の前記先頭部分を前記鍵で解読して、元の圧縮されたデータ列に変換するステップと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分を、所定のビット長の他の鍵で暗号化するステップと、前記暗号化で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるステップとを更に有することを特徴とする付記４のデータ圧縮方法。
【０１４２】
（付記７）前記圧縮ステップは、圧縮のための符号表に従い、前記圧縮データを生成するステップと、前記圧縮したデータ列に従って、前記符号表を更新するステップとからなることを特徴とする付記１のデータ圧縮方法。
【０１４３】
（付記８）前記符号表がスプレイ木構成であること特徴とする付記７のデータ圧縮方法。
【０１４４】
（付記９）付記１で生成された圧縮データ列を復元するデータ復元方法であって、前記圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有することを特徴とするデータ復元方法。
【０１４５】
（付記１０）付記２で生成された圧縮データ列を復元するデータ復元方法であって、前記圧縮データ列から前記データサイズを除去するステップと、前記データサイズを除去された圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去するステップと、前記展開されたデータ列又は前記圧縮データ列のデータサイズを求めるステップと、前記除去したデータサイズと前記求めたデータサイズとを比較するステップと、前記比較結果に応じて、前記スクランブル値を除去した展開データを出力するステップとを有することを特徴とするデータ復元方法。
【０１４６】
（付記１１）付記３で生成された圧縮データ列を復元するデータ復元方法であって、前記圧縮されたデータ列の先頭部分を取得するステップと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るステップと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるステップと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有することを特徴とするデータ復元方法。
【０１４７】
（付記１２）付記４で生成された圧縮データ列を復元するデータ復元方法であって、前記圧縮されたデータ列の先頭部分又は全部を取得するステップと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵で解読するステップと、前記解読されたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるステップと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するステップと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するステップとを有することを特徴とするデータ復元方法。
【０１４８】
（付記１３）前記展開ステップは、展開のための符号表に従い、前記展開データを生成するステップと、前記展開したデータ列に従って、前記符号表を更新するステップとからなることを特徴とする付記９のデータ復元方法。
【０１４９】
（付記１４）前記符号表がスプレイ木構成であること特徴とする付記１４のデータ復元方法。
【０１５０】
（付記１５）被圧縮データ列から圧縮データ列を生成するデータ圧縮プログラムであって、入力された被圧縮データ列の先頭に、所定のビット長のスクランブル値を付与するプログラムデータと、前記先頭にスクランブル値を付与された被圧縮データ列を、動的可変長符号化法により圧縮するプログラムデータとを有することを特徴とするデータ圧縮プログラム。
【０１５１】
（付記１６）前記被圧縮データ列又は前記先頭にスクランブル値を付与された被圧縮データ列のデータサイズを取得するプログラムデータと、前記取得したデータサイズを、前記先頭にスクランブル値を付与された被圧縮データ列に付与するプログラムデータを更に有することを特徴とする付記１５のデータ圧縮プログラム。
【０１５２】
（付記１７）前記圧縮されたデータ列の先頭部分を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るプログラムデータと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるプログラムデータとを更に有することを特徴とする付記１５のデータ圧縮プログラム。
【０１５３】
（付記１８）前記圧縮されたデータ列の先頭部分又は全部を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵を用いて暗号化するプログラムデータと、前記暗号化で求めたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるプログラムデータとを更に有することを特徴とする付記１５のデータ圧縮プログラム。
【０１５４】
（付記１９）前記先頭部分が置き換えられた圧縮データ列の前記先頭部分と前記鍵との排他的論理和を取り、元の圧縮されたデータ列に変換するプログラムデータと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分と、所定のビット長の他の鍵との排他的論理和を取るプログラムデータと、前記排他的論理和で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるプログラムデータとを更に有することを特徴とする付記１７のデータ圧縮プログラム。
【０１５５】
（付記２０）前記先頭部分が置き換えられた圧縮データ列の前記先頭部分を前記鍵で解読して、元の圧縮されたデータ列に変換するプログラムデータと、前記変換された元の前記圧縮されたデータ列の先頭部分を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分を、所定のビット長の他の鍵で暗号化するプログラムデータと、前記暗号化で求めたデータ列で、前記元の圧縮されたデータ列の先頭部分を置き換えるプログラムデータとを更に有することを特徴とする付記１８のデータ圧縮プログラム。
【０１５６】
（付記２１）前記圧縮プログラムデータは、圧縮のための符号表に従い、前記圧縮データを生成するプログラムデータと、前記圧縮したデータ列に従って、前記符号表を更新するプログラムデータとからなることを特徴とする付記１５のデータ圧縮プログラム。
【０１５７】
（付記２２）前記符号表がスプレイ木構成であること特徴とする付記２１のデータ圧縮プログラム。
【０１５８】
（付記２３）付記１５で生成された圧縮データ列を復元するデータ復元プログラムであって、前記圧縮データ列を前記動的可変長符号化により展開するプログラムデータと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するプログラムデータとを有することを特徴とするデータ復元プログラム。
【０１５９】
（付記２４）付記１６で生成された圧縮データ列を復元するデータ復元プログラムであって、前記圧縮データ列から前記データサイズを除去するプログラムデータと、前記データサイズを除去された圧縮データ列を前記動的可変長符号化により展開するプログラムデータと、前記展開されたデータ列の先頭のスクランブル値を除去するプログラムデータと、前記展開されたデータ列又は前記圧縮データ列のデータサイズを求めるプログラムデータと、前記除去したデータサイズと前記求めたデータサイズとを比較するプログラムデータと、前記比較結果に応じて、前記スクランブル値を除去した展開データを出力するプログラムデータとを有することを特徴とするデータ復元プログラム。
【０１６０】
（付記２５）付記１７で生成された圧縮データ列を復元するデータ復元プログラムであって、前記圧縮されたデータ列の先頭部分を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分と、所定のビット長の鍵との排他的論理和を取るプログラムデータと、前記排他的論理和で求めたデータ列で、前記圧縮されたデータ列の先頭部分を置き換えるプログラムデータと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するプログラムデータと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するプログラムデータとを有することを特徴とするデータ復元プログラム。
【０１６１】
（付記２６）付記１８で生成された圧縮データ列を復元するデータ復元プログラムであって、前記圧縮されたデータ列の先頭部分又は全部を取得するプログラムデータと、前記取得した圧縮データ列の先頭部分又は全部を、所定のビット長の鍵で解読するプログラムデータと、前記解読されたデータ列で、前記圧縮されたデータ列の先頭部分又は全部を置き換えるプログラムデータと、前記置き換えられた圧縮データ列を前記動的可変長符号化により展開するプログラムデータと、前記展開されたデータ列の先頭のスクランブル値を除去し、前記被圧縮データに復元するプログラムデータとを有することを特徴とするデータ復元プログラム。
【０１６２】
（付記２７）前記展開プログラムデータは、展開のための符号表に従い、前記展開データを生成するプログラムデータと、前記展開したデータ列に従って、前記符号表を更新するプログラムデータとからなることを特徴とする付記２３のデータ復元プログラム。
【０１６３】
（付記２８）前記符号表がスプレイ木構成であること特徴とする付記２７のデータ復元プログラム。
【産業上の利用可能性】
【０１６４】
データ圧縮により、ランダム性の高い圧縮データを生成でき、簡単に対象データをランダマイズできるため、生成側と復元側とで、共通の初期値を共有する必要がなく、且つ処理も容易であり、特に、大量データの処理時間の短縮に有効である。
【図面の簡単な説明】
【０１６５】
【図１】本発明のデータ圧縮方法の第１の実施の形態の機能ブロック図である。
【図２】本発明のデータ復元方法の第１の実施の形態の機能ブロック図である。
【図３】図１のデータ圧縮動作の説明図である。
【図４】図１の圧縮処理の説明図である。
【図５】図４の静的可変長符号化処理の説明図である。
【図６】本発明に好適な図４の動的可変長符号化処理の説明図である。
【図７】図１のデータ圧縮方法の第１の具体例の機能ブロック図である。
【図８】図２のデータ復元方法の第１の具体例の機能ブロック図である。
【図９】図７の動的Huffman符号化の第１の説明図である。
【図１０】図７の動的Huffman符号化の第２の説明図である。
【図１１】図７の動的Huffman符号化の第３の説明図である。
【図１２】図７の動的Huffman符号化の第４の説明図である。
【図１３】図１のデータ圧縮方法の第２の具体例の機能ブロック図である。
【図１４】図２のデータ復元方法の第２の具体例の機能ブロック図である。
【図１５】図１３のSplay符号化の第１の説明図である。
【図１６】図１３のSplay符号化の第２の説明図である。
【図１７】本発明のデータ圧縮方法の第２の実施の形態の機能ブロック図である。
【図１８】本発明のデータ復元方法の第２の実施の形態の機能ブロック図である。
【図１９】本発明のデータ圧縮方法の第３の実施の形態の機能ブロック図である。
【図２０】本発明のデータ復元方法の第３の実施の形態の機能ブロック図である。
【図２１】図１９のデータ圧縮方法の第１の具体例の機能ブロック図である。
【図２２】図２０のデータ復元方法の第１の具体例の機能ブロック図である。
【図２３】図１９のデータ圧縮方法の第２の具体例の機能ブロック図である。
【図２４】図２０のデータ復元方法の第２の具体例の機能ブロック図である。
【図２５】本発明のデータ圧縮方法を適用した鍵かけなおし処理の第１の実施の形態の機能ブロック図である。
【図２６】本発明のデータ圧縮方法を適用した鍵かけなおし処理の第２の実施の形態の機能ブロック図である。
【図２７】従来のCBCモードの説明図である。
【符号の説明】
【０１６６】
１０、２０  データ入力部
１２  乱数発生部
１４  乱数付与部
１６  圧縮部
１８、２６  データ出力部
２２  データ展開部
２４  乱数除去部
３０  圧縮データ生成部
３２、３８  圧縮符号表更新部
３４、４０  圧縮符号表保持部
３６  展開データ生成部
【図１】
2005217842.tif 000003
【図２】
2005217842.tif 000004
【図３】
2005217842.tif 000005
【図４】
2005217842.tif 000006
【図５】
2005217842.tif 000007
【図６】
2005217842.tif 000008
【図７】
2005217842.tif 000009
【図８】
2005217842.tif 000010
【図９】
2005217842.tif 000011
【図１０】
2005217842.tif 000012
【図１１】
2005217842.tif 000013
【図１２】
2005217842.tif 000014
【図１３】
2005217842.tif 000015
【図１４】
2005217842.tif 000016
【図１５】
2005217842.tif 000017
【図１６】
2005217842.tif 000018
【図１７】
2005217842.tif 000019
【図１８】
2005217842.tif 000020
【図１９】
2005217842.tif 000021
【図２０】
2005217842.tif 000022
【図２１】
2005217842.tif 000023
【図２２】
2005217842.tif 000024
【図２３】
2005217842.tif 000025
【図２４】
2005217842.tif 000026
【図２５】
2005217842.tif 000027
【図２６】
2005217842.tif 000028
【図２７】
2005217842.tif 000029