(57)【要約】【課題】データシャッフルの設計の自由度が高いデータシャッフル装置、データデシャッフル装置、その方法及びそのプログラムを提供する。【解決手段】予め定義されたデータの順序関係に基づいて、入力されるデータを整列するプロセスを、所与のビットシークエンスに応じて駆動する。所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、参照データを並べ替え、並べ替えた参照データを、データ順序関係の定義に基づいて整列する。このとき、並べ替えた参照データを、データ順序関係の定義に基づいて整列する際に、参照データのデータ順序関係の比較結果を所定のビットパターンとして記録し、記録したビットパターンを逆変換キーとして、入力されるデータについて、データを整列するプロセスを駆動する。【選択図】  図６
2004336341.tif 000002
【特許請求の範囲】
【請求項１】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列するデータ整列手段と、
所与のビットシークエンスに応じて、前記整列手段を駆動する整列駆動手段と
を具備することを特徴とするデータシャッフル装置。
【請求項２】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のデータ整列手段と、
所与のビットシークエンスに応じて、前記複数のデータ整列手段のうち、１のデータ整列手段を駆動する整列駆動手段と
を具備することを特徴とするデータシャッフル装置。
【請求項３】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列するデータ整列手段と、
該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録する記録手段と、
前記記録したビットパターンを逆変換キーとして、入力されるデータについて、前記データ整列手段を駆動する整列駆動手段と
を具備することを特徴とするデータデシャッフル装置。
【請求項４】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列するデータ整列手段と、
該並べ替えた参照データと、前記入力された参照データとの対応関係を記録する記録手段と、
該記録した対応関係に基づいて、入力されるデータについて、前記データ整列手段を駆動する整列駆動手段と
を具備することを特徴とするデータデシャッフル装置。
【請求項５】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列するプロセスを、所与のビットシークエンスに応じて駆動する
ことを特徴とするデータシャッフル方法。
【請求項６】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のプロセスのうち、所与のビットシークエンスに応じて、１のプロセスを駆動する
ことを特徴とするデータシャッフル方法。
【請求項７】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、
所与のビットシークエンスをキーとして、該参照データを並べ替え、
該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列し、
該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録し、
前記記録したビットパターンを逆変換キーとして、入力されるデータについて、該データを整列するプロセスを駆動する
ことを特徴とするデータデシャッフル方法。
【請求項８】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、
所与のビットシークエンスをキーとして、該参照データを並べ替え、
該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列し、
該並べ替えた参照データと、前記入力された参照データとの対応関係を記録し、
該記録した対応関係に基づいて、入力されるデータについて、入力されるデータについて、該データを整列するプロセスを駆動する
ことを特徴とするデータデシャッフル方法。
【請求項９】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列するプロセスを、所与のビットシークエンスに応じて駆動する処理
をコンピュータに実行させるためのデータシャッフルプログラム。
【請求項１０】
予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のプロセスのうち、所与のビットシークエンスに応じて、１のプロセスを駆動する処理
をコンピュータに実行させるためのデータシャッフルプログラム。
【請求項１１】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受ける処理と、
所与のビットシークエンスをキーとして、該参照データを並べ替える処理と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する処理と、
該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録する処理と、
前記記録したビットパターンを逆変換キーとして、入力されるデータについて、該データを整列するプロセスを駆動する処理と
をコンピュータに実行させるためのデータデシャッフルプログラム。
【請求項１２】
所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受ける処理と、
所与のビットシークエンスをキーとして、該参照データを並べ替える処理と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する処理と、
該並べ替えた参照データと、前記入力された参照データとの対応関係を記録する処理と、
該記録した対応関係に基づいて、入力されるデータについて、入力されるデータについて、該データを整列するプロセスを駆動する処理と
をコンピュータに実行させるためのデータデシャッフルプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データの出現順序を、予測が困難な順序に変更するシャッフル（スクランブル）アルゴリズムを実装するデータシャッフル装置、データデシャッフル装置、その方法及びそのプログラムに関する。
【０００２】
【従来の技術】
従来、データの出現順序を、予測が困難な順序に変更するシャッフル（スクランブル）アルゴリズムとして、例えば、画像圧縮率の低下を招かないスクランブル技術が先行技術文献１に記載されている。
この発明によれば、元画像を少なくとも２以上のブロックに分割し、各ブロックを特定する情報とその位置を含む組を各ブロックにおける輝度の代表値の順に並びかえ、代表値の順に各ブロックを配置させて変換画像を生成する。
【特許文献１】
特開２００２−７７５６８号公報
【発明が解決しようとする課題】
従来技術の問題点
しかし、上記発明を一例として、従来のシャッフルアルゴリズム及びデシャッフルアルゴリズムには、以下のような問題がある。
すなわち、シャッフルする対象（画像、音楽）に依存したアルゴリズムの場合、対象データよる制約等によって、アルゴリズムが容易に更新できないという問題がある。また、同様の理由により、パラメータの自由度が少ないため、シャッフル強度が自由に設定できないという問題点がある。また、これに伴い、シャッフル、デシャッフルに関わる便利さと、シャッフル強度に基づく安全さのバランスをユーザが自由に選択できないという問題点がある。
【０００３】
本発明は、このような事情を考慮してなされたものであり、その目的は、データシャッフルの設計の自由度が高いデータシャッフル装置、データデシャッフル装置、その方法及びそのプログラムを提供することにある。
【０００４】
【課題を解決するための手段】
この発明は上記の課題を解決すべくなされたもので、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列するデータ整列手段と、所与のビットシークエンスに応じて、前記整列手段を駆動する整列駆動手段とを具備することを特徴とする。
【０００５】
また、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のデータ整列手段と、所与のビットシークエンスに応じて、前記複数のデータ整列手段のうち、１のデータ整列手段を駆動する整列駆動手段とを具備することを特徴とする。
【０００６】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列するデータ整列手段と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録する記録手段と、前記記録したビットパターンを逆変換キーとして、入力されるデータについて、前記データ整列手段を駆動する整列駆動手段とを具備することを特徴とする。
【０００７】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列するデータ整列手段と、該並べ替えた参照データと、前記入力された参照データとの対応関係を記録する記録手段と、該記録した対応関係に基づいて、入力されるデータについて、前記データ整列手段を駆動する整列駆動手段とを具備することを特徴とする。
【０００８】
また、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列するプロセスを、所与のビットシークエンスに応じて駆動することを特徴とする。
【０００９】
また、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のプロセスのうち、所与のビットシークエンスに応じて、１のプロセスを駆動することを特徴とする。
【００１０】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列し、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録し、前記記録したビットパターンを逆変換キーとして、入力されるデータについて、該データを整列するプロセスを駆動することを特徴とする。
【００１１】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受けて、所与のビットシークエンスをキーとして、該参照データを並べ替え、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列し、該並べ替えた参照データと、前記入力された参照データとの対応関係を記録し、該記録した対応関係に基づいて、入力されるデータについて、入力されるデータについて、該データを整列するプロセスを駆動することを特徴とする。
【００１２】
また、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列するプロセスを、所与のビットシークエンスに応じて駆動する処理をコンピュータに実行させるためのデータシャッフルプログラムである。
【００１３】
また、本発明は、予め定義されたデータの順序関係に基づいて、入力されるデータを整列する複数のプロセスのうち、所与のビットシークエンスに応じて、１のプロセスを駆動する処理をコンピュータに実行させるためのデータシャッフルプログラムである。
【００１４】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受ける処理と、所与のビットシークエンスをキーとして、該参照データを並べ替える処理と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する処理と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する際に、前記参照データのデータ順序関係の比較結果を所定のビットパターンとして記録する処理と、前記記録したビットパターンを逆変換キーとして、入力されるデータについて、該データを整列するプロセスを駆動する処理とをコンピュータに実行させるためのデータデシャッフルプログラムである。
【００１５】
また、本発明は、所定のデータ順序関係の定義に基づいて予め整列された参照データの入力を受ける処理と、所与のビットシークエンスをキーとして、該参照データを並べ替える処理と、該並べ替えた参照データを、前記データ順序関係の定義に基づいて整列する処理と、該並べ替えた参照データと、前記入力された参照データとの対応関係を記録する処理と、該記録した対応関係に基づいて、入力されるデータについて、入力されるデータについて、該データを整列するプロセスを駆動する処理とをコンピュータに実行させるためのデータデシャッフルプログラムである。
【００１６】
【発明の実施の形態】
以下、図面を参照して、本発明のデータシャッフル装置、データデシャッフル装置の一実施形態について説明する。図１は、本実施形態のデータシャッフル装置の構成を示す構成図である。
本実施形態のデータシャッフル装置は、制御部１と、入力部２と、出力部３と、記憶部４と、データシャッフル処理部５とをバス１０で接続して構成される。
【００１７】
制御部１は、入力部２、出力部３、記憶部４、データシャッフル処理部５におけるデータ入出力制御を行う。
入力部２は、シャッフル対象である平文データ及び後述する整列アルゴリズム（ソートアルゴリズム）を駆動するためのキーであるシャッフルキーの入力を受けるインターフェイス部である。ここで、シャッフルキーは、例えば、１，０のビットシークエンスで定義することができる。
出力部３は、平文データをシャッフルしたシャッフルデータを出力するインターフェイス部である。
記憶部４は、当該データシャッフル装置のワークメモリである。
【００１８】
データシャッフル処理部５は、複数（本実施形態では４）の整列処理部６Ａ〜６Ｄと、整列駆動処理部７とから構成される。
整列処理部６Ａ〜６Ｄは、予め定義されたデータの順序関係に基づいて、入力される平文データを整列する。ここで、予め定義されたデータの順序関係とは、データ整列において、２つのデータを比較するための基準であって、例えば、各データの大きさの大小関係、名称等の五十音順の関係、アルファベット順の関係等で定義される。すなわち、整列処理部６Ａ〜６Ｄは、整列駆動処理部７からの駆動要求に応じて、１または複数のソートアルゴリズムの組み合わせ、及び、当該１または複数のソートアルゴリズムのパラメータの組み合わせで規定されるデータ整列処理を実行する。
整列駆動処理部７は、所与のビットシークエンスに応じて、複数の整列処理部６Ａ〜６Ｄのうち、１の整列処理部を駆動する。具体的には、整列駆動処理部７は、シャッフルキーの入力を受けて、当該シャッフルキーが示すビットの１、０に応じて、整列処理部６Ａ〜６Ｄに対して駆動要求を出力する。
【００１９】
すなわち、ソートアルゴリズムとしてバブルソートを採用する場合、例えば、整列駆動処理部７が整列処理部６Ａを駆動して、入力される平文データの配列について、注目するデータを１つずつ隣に移動しながら、配列内の隣のデータと入れ替える、入れ替えないという処理を全てのソートが完了するまでこの処理を繰り返す、あるいは、予め定めた回数だけ実行した時に処理を停止する。
このとき、データをシャッフルするためのアルゴリズムのパラメータ、つまり、整列処理部６Ａのシャッフル処理パラメータとして、
・配列のどの位置を初期値とするか
・どちら向きにｓｗａｐ処理（配列の２つの値を入れ替え）を行うか
・各走査ごとに、どちら向きに走査するか
を定義することができる。例えば、基本的なバブルソートであれば、毎回先頭から同じ方向に走査し、シェーカーソートであれば、毎回方向を反転する。ここで、走査回数がＮならば、２のＮ乗の自由度が生じる。
すなわち、このような駆動アルゴリズムの実装方法やパラメータが、送信側（シャッフル側）・受信側（デシャッフル側）で共通に持っている共通鍵になる。なお、データの並び順（シャッフル）の持つ情報表現能力は、例えば、わずか３２個のデータを並べ替えるだけでも３２！となり、ほぼ１１８ｂｉｔ程度の情報量、６４個ならば２９６ｂｉｔ程度の情報量となる。
【００２０】
また、ソートアルゴリズムとしてシェルソートを採用する場合、整列駆動処理部７が整列処理部６Ｂを駆動して、入力される平文データの配列について、ある間隔だけ離れたデータごとに、複数の配列に分割した後、分割後の配列内の隣のデータと入れ替える、入れ替えないという処理を全てのソートが完了するまでこの処理を繰り返す、あるいは、予め定めた回数だけ実行した時に処理を停止する。
この場合、シェルソートで比較する要素の間隔それ自体がシャッフル処理パラメータとなる。
【００２１】
今、例えば、整列駆動処理部７に図２に示すビット列が入力されたとする。
整列駆動処理部７は、入力される配列Ａ〜Ｍ（図３を参照）について、配列総数Ｎ＝１３、間隔Ｈ＝［Ｎ／２］＝６とすると、図２に示すビット列のビットを左から順に用いて、
・ｓｔｅｐ１−ａ  ＡとＧ、ＧとＭを入れ替えるか  （ビット１，と２を用いる）
・ｓｔｅｐ１−ｂ  ＢとＨ  を入れ替えるか  （ビット３を用いる）
・ｓｔｅｐ１−ｃ  ＣとＩ  を入れ替えるか  （ビット４を用いる）
・ｓｔｅｐ１−ｄ  ＤとＪ  を入れ替えるか  （ビット５を用いる）
・ｓｔｅｐ１−ｅ  ＥとＫ  を入れ替えるか  （ビット６を用いる）
・ｓｔｅｐ１−ｆ  ＦとＬ  を入れ替えるか  （ビット７を用いる）
を決定する。このとき、ビットが１であれば整列処理部６Ｂを駆動する、ビットが０であれば駆動しないと設定すれば、ソートアルゴリズムとしてシェルソートを採用する場合、ｓｔｅｐ１−ａ、ｃ、ｄでのみ、整列処理部６Ｂが駆動して入れ替えが行われ、図４に示すように、配列が並べ替えられる。
次に、整列駆動処理部７は入れ替え後の配列について、さらに、間隔Ｈ＝［Ｎ／４］＝３とすると、
・ｓｔｅｐ２−ａ  Ｇ，Ｊ，Ｍ，Ｄ，Ａを入れ替えるか  （ビット８，９，１０，１１を用いる）
・ｓｔｅｐ２−ｂ  Ｈ，Ｅ，Ｂ，Ｋを入れ替えるか  （ビット１２，１３，１４を用いる）
・ｓｔｅｐ２−ｃ  Ｃ，Ｆ，Ｉ，Ｌを入れ替えるか  （ビット１５，１６，１７を用いる）
を決定する。このとき、同様に、整列処理部６Ｂが駆動して入れ替えが行われ、配列が並べ替えられる。
次に、整列駆動処理部７は入れ替え後の配列について、さらに、間隔Ｈ＝［Ｎ／８］＝１とすると、例えば、整列処理部６Ｂを駆動して、最後にバブルソートと同じ処理をする。もちろん、この場合も、整列処理部６Ｂのシャッフル処理パラメータとして、予め定めた適当な段数を定義し、当該設定値でシャッフル処理を止めることができる。
【００２２】
また、ソートアルゴリズムとして、ヒープ・ソートを採用する場合、整列駆動処理部７が整列処理部６Ｃを駆動して、入力される平文データの配列について、整列２分木を構築し、ソートを実現する。具体的には、整列駆動処理部７が所与のビットシークエンスに基づいて、整列処理部６Ｃを駆動し、整列処理部６Ｃは、整列２分木を構築する過程において、データを１つずつツリーに追加していく。このとき、ツリーのどの位置にデータを追加するかについて、整列処理部６Ｃは、ツリーの頂点から順に、２つのデータのいずれを２つのポインタのいずれに追加するかを決定し、配列を並べ替える。
【００２３】
また、ソートアルゴリズムとして、クイックソートを採用する場合、整列駆動処理部７が整列処理部６Ｄを駆動して、入力される平文データの配列について、枢軸値として仮の基準値を選択し、それよりも大きい配列と小さい配列にグループ分けするという処理を再帰的に行う。また、ある程度、配列グループの規模が大きくなると別のソートアルゴリズムに切り替えたほうが効率がよいことから、データをシャッフルするためのアルゴリズムのパラメータ、つまり、整列処理部６Ｄのシャッフル処理パラメータとして、
・枢軸値をどのように選択するか
・どこでアルゴリズムを切り替えるか
を定義することができる。
【００２４】
具体的には、整列駆動処理部７が整列処理部６Ｄを駆動して、
・ｓｔｅｐ１  ソートするデータ区間のデータを得る
・ｓｔｅｐ２  区間内のデータ数が２以下のとき、
２−ａ  データ数が１以下ならば何もしない
２−ｂ  データ数が２ならば、２つのデータを並べ替えるかを決定する
・ｓｔｅｐ３  区間内のデータ数が３以上のとき、
３−ａ  区間内から基準とする値（例えば、配列の先頭データ）を得る
３−ｂ  区間内のデータに対して、基準値より小さいデータの区間と、基準値より大きいデータの区間とに分ける
３−ｃ  基準値より小さいデータの区間及び基準値より大きいデータの区間に対して、再帰的に処理を行う
というステップで定義される処理を行う。
【００２５】
今、例えば、図２に示すビット列が整列駆動処理部７に入力されたとする。
整列駆動処理部７は、入力される配列Ａ〜Ｇについて、区間内のデータ数Ｎ＝７より、図２に示すビット列のビットを左から順に用いて、
・ｓｔｅｐ１  Ａ  Ｂ  Ｃ  Ｄ  Ｅ  Ｆ  Ｇ
・ｓｔｅｐ２  Ｎ＝７よりｓｔｅｐ３へ
・ｓｔｅｐ３
３−ａ  先頭のＡを基準値とする
［Ａ］Ｂ  Ｃ  Ｄ  Ｅ  Ｆ  Ｇ
３−ｂ  整列駆動処理部７は、入力されるビット列の内、順に６ビット取り出して、入力される配列Ｂ〜Ｇに１対１に割り当てる。そして、当該割り当てられる各ビットの１、０に基づいて、整列処理部６Ａ〜６Ｄを駆動する。整列処理部６Ａ〜６Ｄは、基準値より小さいデータの区間と、基準値より大きいデータの区間とに分ける。
2004336341.tif 000003
ここでは、１が割り当てられた｛Ｂ，Ｃ，Ｄ，Ｆ｝は、基準値Ａより大きいグループ（以下、Ｓｕｂ−Ｇｒｏｕｐ１とする）、０が割り当てられた｛Ｅ，Ｇ｝は小さいグループ（Ｓｕｂ−Ｇｒｏｕｐ２）となる。
従って、入力される配列Ａ〜Ｇは、まず
｛Ｓｕｂ−Ｇｒｏｕｐ１｝，Ａ，｛Ｓｕｂ−Ｇｒｏｕｐ２｝
と分けられる。
【００２６】
次に、データをシャッフルするためのアルゴリズムのパラメータとして、さらに、例えば、常に大きいサブグループから処理すると定義したとする。
今、｛Ｓｕｂ−Ｇｒｏｕｐ１｝は、｛Ｓｕｂ−Ｇｒｏｕｐ２｝より大きいので、まず｛Ｓｕｂ−Ｇｒｏｕｐ１｝について、さらに、シャッフル処理する。すなわち、
・ｓｔｅｐ１  ｛Ｂ，Ｃ，Ｄ，Ｆ｝  について再帰的にアルゴリズムを実行
・ｓｔｅｐ２  スキップ
・ｓｔｅｐ３
３−Ａ  先頭のＢを基準値とする
３−Ｂ  整列駆動処理部７は、入力されるビット列の内、さらに、順に３ビット取り出して、入力される配列Ｂ，Ｃ，Ｄ，Ｆに１対１に割り当てる。そして、当該割り当てられる各ビットの１、０に基づいて、整列処理部６Ｄを駆動する。整列処理部６Ｄは、基準値より小さいデータの区間と、基準値より大きいデータの区間とに分ける。
2004336341.tif 000004
ここでは、１が割り当てられた｛Ｄ，Ｆ｝は、基準値Ｂより大きいグループ（以下、Ｓｕｂ−Ｇｒｏｕｐ３とする）、０が割り当てられた｛Ｃ｝は小さいグループ（Ｓｕｂ−Ｇｒｏｕｐ４）となる。
従って、入力される配列Ｂ，Ｃ，Ｄ，Ｆは、次に
｛Ｓｕｂ−Ｇｒｏｕｐ３｝，Ｂ，｛Ｓｕｂ−Ｇｒｏｕｐ４｝
と分けられる。
【００２７】
今、｛Ｓｕｂ−Ｇｒｏｕｐ３｝は、｛Ｓｕｂ−Ｇｒｏｕｐ４｝より大きいので、まず｛Ｓｕｂ−Ｇｒｏｕｐ３｝について、さらに、シャッフル処理する。すなわち、
・ｓｔｅｐ１  ｛Ｄ，Ｆ｝について再帰的にアルゴリズムを実行
・ｓｔｅｐ２  Ｎ＝２より比較（入れ替えを行うか）
２−ｂ  次のビット＝０より、整列処理駆動部７は、整列処理部６Ａ〜６Ｄを駆動しない。つまり、ＤとＦの入れ替え処理を行わない。
したがって、入力される配列Ｄ、Ｆはそのまま｛Ｄ，Ｆ｝として出力される。
以上により、整列処理駆動部７は、図２に示すビットシークエンスに基づいて、整列処理部６Ｄを駆動し、Ｓｕｂ−Ｇｒｏｕｐ１｛Ｂ，Ｃ，Ｄ，Ｆ｝を｛Ｄ，Ｆ，Ｂ，Ｃ｝にシャッフルする。
【００２８】
次に、次に大きいサブグループについて、シャッフル処理を行う。すなわち、Ｓｕｂ−Ｇｒｏｕｐ２について、
・ｓｔｅｐ１    ｛Ｅ，Ｇ｝  の処理
・ｓｔｅｐ２  Ｎ＝２より比較
２−ｂ  次のビット＝１より、整列処理駆動部７は、整列処理部６Ｄを駆動する。つまり、ＥとＧを入れ替える。
したがって、入力される配列Ｅ，Ｇは｛Ｇ，Ｅ｝として出力される。
以上により  Ｓｕｂ−Ｇｒｏｕｐ２｛Ｅ，Ｇ｝は｛Ｇ，Ｅ｝に入れ替わる。
【００２９】
以上、シャッフル処理結果として、
｛Ｄ，Ｆ，Ｂ，Ｃ｝，Ａ，｛Ｇ，Ｅ｝
が出力される。
つまり、入力されたビットシークエンスの一部である‘１１１０１００１１０１’により、整列処理駆動部７は、整列処理部６Ｄを駆動し、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝を｛Ｄ，Ｆ，Ｂ，Ｃ，Ａ，Ｇ，Ｅ｝とシャッフルする。
【００３０】
また、ソートアルゴリズムとして、マージソートを採用する場合、整列駆動処理部７が整列処理部６Ｄを駆動して、入力される平文データの配列について、まず配列を２分割して、２つの部分列の最小値のうち、より小さいものから順に取るという処理を再帰的に行い、最終的に、２つの部分列に分割された平文データを１つに合わせる。
この場合、データをシャッフルするためのアルゴリズムのパラメータ、つまり、シャッフル処理パラメータとして、
各階層ごとにどれだけのサブグループに分けるか
を定義することができる。
【００３１】
このように、本実施形態のシャッフル装置によれば、利用しているソートアルゴリズムが同じであっても、細かいパラメータのインプリメンテーションが異なると、シャッフルの結果が異なって出力される。
例えば上述したクイックソートでは、
・注目している区間の基準値を、区間の先頭とする
・常に、｛大きいサブグループ｝を先に処理する
・深さ優先処理を行う
というパラメータを採用したが、例えば、これを
・基準値は区間の最後にする
・深さによってサブグループの処理の順序を変える
・幅優先処理を行う
というようにパラメータの値を変更すると、同じアルゴリズムを利用していても、シャッフルの結果が異なって出力される。
【００３２】
また、通常のソート処理として、当該ソートアルゴリズムを用いる場合、処理の性質上、完全に処理が終わるまで手続きを続けなければならない。しかし、本実施形態のように、シャッフル処理として、当該ソートアルゴリズムを用いる場合、予め定めた方法で処理を停止してもかまわない。また、逆にソートの時に行われる以上に処理を継続してもよい。
したがって、ある条件を満たしたら処理を中断・停止することにより、演算負荷を調整することができる。したがって、コンピュータリソースに応じて、演算負荷の低減を図った設計を行うことができる黄河が得られえる。また、安全性を優先する場合は、逆に、シャッフルアルゴリズムの解析を困難にする設計が可能である。このように、当該シャッフルアルゴリズムの実装形態をユーザニーズに容易に適応させることができる効果が得られる。
【００３３】
次に、本実施形態のデータデシャッフル装置について説明する。
図５は、本実施形態のデータデシャッフル装置の構成を示す構成図である。
本実施形態のデータデシャッフル装置は、制御部１１と、入力部１２と、出力部１３と、記憶部１４と、データデシャッフル処理部１５とをバス２０で接続して構成される。
【００３４】
制御部１１は、入力部１２、出力部１３、記憶部１４、データデシャッフル処理部１５におけるデータ入出力制御を行う。
入力部１２は、シャッフル対象であるソート済み参照配列、上述のシャッフルキーの入力を受けるとともに、デシャッフル対象であるシャッフルデータの入力を受けるインターフェイス部である。ここで、ソート済み参照配列は、シャッフルキーから逆変換キーを算出するための予め整列済みの検証用データであって、例えば、上述した配列Ａ〜Ｇのように、シャッフル前後で対応関係が識別可能なデータである。
出力部１３は、シャッフルデータをデシャッフルした平文データを出力するインターフェイス部である。
記憶部１４は、当該データデシャッフル装置のワークメモリである。具体的には、データデシャッフル処理部１５が参照データをデータ順序関係の定義に基づいて整列する際に（後述する）、参照データのデータ順序関係の比較結果を所定のビットパターンとして記録する、あるいは、参照シャッフルデータと、参照データとの対応関係を記録する記憶部である。
【００３５】
データデシャッフル処理部１５は、複数（本実施形態では４）の整列処理部１６Ａ〜１６Ｄと、整列駆動処理部１７とから構成される。
整列処理部１６Ａ〜１６Ｄは、整列処理部６Ａ〜６Ｄと１対１に対応し、予め定義されたデータの順序関係に基づいて、入力されるソート済み参照配列データを整列する。また、整列処理部１６Ａ〜１６Ｄは、予め定義されたデータの順序関係に基づいて、入力されるシャッフルデータを整列する。すなわち、整列処理部１６Ａ〜１６Ｄは、整列駆動処理部１７からの駆動要求に応じて、１または複数のソートアルゴリズムの組み合わせ、及び、当該１または複数のソートアルゴリズムのパラメータの組み合わせで規定されるデータ整列処理を実行する。
整列駆動処理部１７は、所与のビットシークエンスに応じて、複数の整列処理部１６Ａ〜１６Ｄのうち、１の整列処理部を駆動する。具体的には、整列駆動処理部１７は、シャッフルキーの入力を受けて、当該シャッフルキーが示すビットの１、０に応じて、整列処理部１６Ａ〜１６Ｄに対して駆動要求を出力する。
【００３６】
次に、図面を参照して、本実施形態のデータシャッフル装置、データデシャッフル装置の動作について説明する。図６は、本実施形態のデータシャッフル装置によるデータシャッフル処理の過程を示すフローチャートである。
今、平文データをシャッフル処理することで暗号化する場合、ユーザは、データシャッフル装置に対して、平文データ３０、シャッフルキー（ビット列）３１を入力する。
このとき、シャッフルキーは、ユーザの要求によって、公開／非公開とすることができる。なお、これに伴い、シャッフルアルゴリズムの公開／非公開が設定される。本実施形態においては、シャッフルキー、シャッフルアルゴリズムについて、
Ａ．両方非公開の場合
Ｂ．シャッフルキーのみ公開の場合
Ｃ．アルゴリズムのみ公開の場合
のパターンが考えられる。
シャッフルキーを公開しない場合、別途、公開鍵暗号方式などでシャッフルキーを渡す、又は、コンテンツ自体からシャッフルキーを秘密の方式で演算することが考えられ、キーを公開する場合は、任意のビット列とする。
例えば、メールアドレス、ＵＲＬ、ファイル名といった意味のあるテキストから変換したビット列や予め定めたランダムなビット列、その他、コンテンツそのものに何らかの処理を施して生成されるビット列、メッセージダイジェスト関数やハッシュ値が適用可能である。
【００３７】
このように、本実施形態のデータシャッフル装置によれば、シャッフルキーについて、高い自由度が得られる。また、後述するように、キーとアルゴリズムが既知であれば、逆変換キーが容易に生成可能である。具体的には、適当な初期値でそのキーを使ってシャッフルすれば、変換テーブルが得られるため、逆変換可能になる。ただしキーとアルゴリズムのどちらか片方でもわからなければ、逆変換は出来ない。
【００３８】
データシャッフル装置は、当該平文データと、シャッフルキーの入力を受けて、上述したように、整列駆動処理部７が、当該シャッフルキーが示すビットの１、０に応じて、複数の整列処理部６Ａ〜６Ｄのうち、１の整列処理部を駆動する。また、このとき、駆動する整列処理部のシャッフル処理パラメータについても、予め設定しておく以外に、当該当該シャッフルキーが示すビットの１、０に応じて変更する。
駆動要求を受けた整列処理部は、シャッフル処理パラメータの設定の有無に基づいて、上述したシャッフル処理を平文データに対して実行する（図６のステップＳ１）。
なお、整列駆動処理部７が駆動要求を出力する整列処理部は１のみならず、複数組み合わせてもよい。また、上述したように、整列処理部内において、１または複数のシャッフルアルゴリズムを実装するようにしてもよい。
【００３９】
これにより、データシャッフル装置は、シャッフルキーであるビット列を用いて、ソートベースのシャッフルアルゴリズムを駆動してシャッフルデータ３２を作成する。そして、このシャッフルキー３１とシャッフルデータ３２が暗号文としてデータデシャッフル装置に送られる。
【００４０】
図７〜９は、本実施形態のデータデシャッフル装置によるデータデシャッフル処理の過程を示すフローチャートである。
データデシャッフル装置は、まず上述したシャッフルキー３１の入力を受けて、予め記憶されているソート済み参照配列、つまり、予め整列済みの検証用データを並べ替える（図７のステップＳ１１）。すなわち、整列駆動処理部１７が、当該シャッフルキー３１が示すビットの１、０に応じて、複数の整列処理部１６Ａ〜１６Ｄのうち、１の整列処理部を駆動する。このとき、整列駆動処理部１７は、シャッフル処理時に用いられるシャッフルキー３１と同様のキーを使用することから、整列駆動処理部７が駆動した整列処理部と対応する整列処理部が駆動される。
【００４１】
駆動要求を受けた整列処理部は、上述したシャッフル処理をソート済み参照配列４０に対して実行する。整列駆動処理部１７は、この並べ替えた結果（参照シャッフルデータ４１）を検証用出力とし、さらに、シャッフルキーを用いずに、予め定義されたデータの順序関係に基づいて、シャッフル処理する（ステップＳ１２）。このとき、シャッフル処理の際に実行される比較処理の結果を１，０のビットパターンとして比較結果記憶部１４−２に記録することで、参照シャッフルデータから逆変換キー４２を生成する。
【００４２】
例えば、データシャッフル装置側でソートアルゴリズムとして、クイックソートを採用する場合、図１０のＡに示すように、必ず比較処理が行われる部分が存在し、この比較演算が発生するたびに、その結果を１，０で記録しておく。これがこのアルゴリズムの実装において、シャッフルキーに対する逆変換キーとなる。
この逆変換キーを一旦計算すると、与えられた暗号文であるシャッフルデータ３２を同じアルゴリズムに通すことによって（ステップＳ２１）、平文データ３０に戻すことが出来る。
【００４３】
すなわち、整列駆動処理部１７は、生成した逆変換キー４２の入力を受けて、当該逆変換キー４２が示すビットの１、０に応じて、複数の整列処理部１６Ａ〜１６Ｄのうち、１の整列処理部を駆動する。駆動要求を受けた整列処理部は、入力されるシャッフルデータについて、上述のデシャッフル処理を行い、平文データ３０を出力する。
図１１、１２に、以上の処理をまとめた概念図を示す。図１１は、図１０に示すクイックソートアルゴリズムを用いて暗号化、復号化（シャッフル、デシャッフル）する様子を示す。このように、上述のデータシャッフル装置によって、平文データはキー（ａ）で暗号文に変換され、データデシャッフル装置によって、キー（ａ）の逆変換キー｛ａ｝が生成されて、これに基づいて、平文に変換される。
また、図１２は、同じクイックソートアルゴリズムで、キーを代えた例を示す。
このように、本実施形態のデータシャッフル装置、データデシャッフル装置によれば、同じアルゴリズムで動作する逆変換キーを作成できるため、メモリ効率や実装効率が高くなるといった効果が得られる。
【００４４】
なお、本実施形態においては、デシャッフルのために逆変換キーを生成する場合の例を示したが、本発明はこれに限られるものではない。すなわち、例えば、図１３に示すように、ソート済み参照配列４０と、参照シャッフルデータの対応関係から、対応テーブルを作成し（図１３のステップＳ１３）、これをシャッフルテーブル５０として記憶しておくようにしてもよい。
この場合、図１０に示す対応関係を例にとれば、
３  →  １
１２  →  ２
６  →  ３
５  →  ４
４  →  ５
１１  →  ６
８  →  ７
２  →  ８
９  →  ９
７  →１０
１０  →１１
１  →１２
のように、シャッフルテーブル５０を構成することができる。
そして、このシャッフルテーブル５０に基づいて、入力されるシャッフルデータ３２を並べ替え処理し（図１３のステップＳ１４）、平文データを得ることができる。
【００４５】
したがって、本実施形態のデータシャッフル装置、データデシャッフル装置によれば、初期状態のソート済み参照配列と参照シャッフルデータとの対応関係をテーブルとして持つことによって、デシャッフル処理のうち、逆変換キーによるシャッフル処理を省略することができ、高速に復号処理を行うことができる効果が得られる。
【００４６】
以上説明したように、本実施形態のデータシャッフル装置、データデシャッフル装置によれば、ビットシークエンスから、効率的にシャッフルを行うことができる効果が得られる。また、アルゴリズムの選択、そのアルゴリズムの実装の自由度、処理手順の自由度によって、解析されにくい、規則性の発見されにくいシャッフルを実現することができる効果が得られる。
さらに、上述したように、本実施形態のデータシャッフル装置、データデシャッフル装置によれば、暗号システムとして機能することが可能である。シャッフルキーとアルゴリズムのどちらかが秘密となればよいため、柔軟な暗号システムを構築可能である。
特に上記実施形態においては、アルゴリズムを秘密とし、シャッフルキーを公開（データに添付）という例を説明したが、逆にアルゴリズムを公開とし、シャッフルキーを他の暗号システムを利用して伝送するようにしてもよい。
【００４７】
上述のデータシャッフル装置、データデシャッフル装置は、内部に、コンピュータシステムを有している。
そして、上述したデータシャッフル処理、データデシャッフル処理に関する一連の処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記処理が行われる。
すなわち、データシャッフル装置、データデシャッフル装置における、各処理手段、処理部は、ＣＰＵ等の中央演算処理装置がＲＯＭやＲＡＭ等の主記憶装置に上記プログラムを読み出して、情報の加工・演算処理を実行することにより、実現されるものである。
ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。
【図面の簡単な説明】
【図１】本実施形態のデータシャッフル装置の構成を示す構成図である。
【図２】シャッフルキーの例を示す図である。
【図３】入力される配列Ａ〜Ｍについて、シェルソートを適用する様子を示す説明図である。
【図４】入力される配列Ａ〜Ｍについて、シェルソートでシャッフルした様子を示す説明図である。
【図５】本実施形態のデータデシャッフル装置の構成を示す構成図である。
【図６】データシャッフル処理の流れを示すフローチャートである。
【図７】データデシャッフル処理の流れを示すフローチャートである。
【図８】データデシャッフル処理部における、逆変換キー生成処理の過程を示す図である。
【図９】データデシャッフル処理部における、デシャッフル処理の過程を示す図である。
【図１０】クイックソートのプログラムリスト例を示す説明図である。
【図１１】全体の暗号化、復号化のシークエンスを示す説明図である。
【図１２】キーを代えた場合における、全体の暗号化、復号化のシークエンスを示す説明図である。
【図１３】逆変換キーの代わりにシャッフルテーブルを作成し、デシャッフル処理を行う流れを示す説明図である。
【符号の説明】
１、１１…制御部、２、１２…入力部、３、１３…出力部、４、１４…記憶部
５…データシャッフル処理部部、６Ａ〜６Ｄ、１６Ａ〜１６Ｄ…整列処理部、７、１７…整列駆動処理部、１４−１…比較結果記憶部、１４−２…逆変換キー記憶部、１５…データデシャッフル処理部部、１０、２０…バス、３０…平文データ、３１…シャッフルキー、３２…シャッフルデータ、４０…ソート済み参照配列、４１…参照シャッフルデータ、４２…逆変換キー
【図１】
2004336341.tif 000005
【図２】
2004336341.tif 000006
【図３】
2004336341.tif 000007
【図４】
2004336341.tif 000008
【図５】
2004336341.tif 000009
【図６】
2004336341.tif 000010
【図７】
2004336341.tif 000011
【図８】
2004336341.tif 000012
【図９】
2004336341.tif 000013
【図１０】
2004336341.tif 000014
【図１１】
2004336341.tif 000015
【図１２】
2004336341.tif 000016
【図１３】
2004336341.tif 000017