(57)【要約】【課題】表現されているデータの「意味」、「品質」を全く変えずに、情報の埋め込み・読み出しが可能な情報埋め込み・改竄検出装置及び情報埋め込み・改竄検出装方法並びに情報埋め込み・改竄検出プログラムを提供する。【解決手段】情報埋め込み装置において、第１の規則に基づいて、複数の構造体データをソートし、ソート結果についてメッセージダイジェストを算出し、算出結果をキーとして、さらに、第１の規則と異なる第２の規則でソートする。情報改竄検出装置において、第１の規則に基づいて、複数の構造体データをソートし、ソート結果についてメッセージダイジェストを算出し、算出結果をキーとして、さらに、第２の規則でソートする。このソート結果と、第１の規則に基づいてソートする前のデータとを比較して一致すれば、改竄無しと判定し、一致しなければ改竄有りと判定する。【選択図】  図５
2004297347.tif 000002
【特許請求の範囲】
【請求項１】
複数の構造体データに情報を埋め込む情報埋め込み装置と、該情報埋め込み装置が情報を埋め込んだ複数の構造体データの改竄を検出する情報改竄検出装置とからなる原本性保障システムであって、
前記情報埋め込み装置が、
第１の規則に基づいて、前記複数の構造体データをソートするデータ標準化手段と、
該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、
該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートするデータ変換手段と
を具備し、
前記情報改竄検出装置が、
前記第１の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、
該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、前記ハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、
該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記第２の規則でソートするデータ変換手段と、
該データ変換手段がソートした複数の構造体データと、前記データ標準化手段がソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記データ標準化手段がソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する判定手段と
を具備する
ことを特徴とするデータ原本性保障システム。
【請求項２】
所定の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、
該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、
該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記規則と異なる規則でソートするデータ変換手段と
を具備することを特徴とする情報埋め込み装置。
【請求項３】
情報埋め込み装置のデータ標準化手段と同一の第１の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、
該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、
該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記情報埋め込み装置のデータ変換手段と同一の規則であって、前記第１の規則と異なる規則でソートするデータ変換手段と、
該データ変換手段がソートした複数の構造体データと、前記データ標準化手段がソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記データ標準化手段がソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する判定手段と
を具備することを特徴とする情報改竄検出装置。
【請求項４】
第１の規則に基づいて、複数の構造体データをソートし、
該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出し、
該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートする
ことを特徴とする情報埋め込み方法。
【請求項５】
請求項４に記載の情報埋め込み方法における第１の規則に基づいて、複数の構造体データをソートし、
該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出し、
該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記情報埋め込み方法における第２の規則でソートし、
該第２の規則でソートした複数の構造体データと、前記第１の規則に基づいてソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていると判定する
ことを特徴とする情報改竄検出方法。
【請求項６】
第１の規則に基づいて、複数の構造体データをソートする処理と、
該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出する処理と、
該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートする処理と、
をコンピュータに実行させるための情報埋め込みプログラム。
【請求項７】
請求項６に記載の情報埋め込みプログラムをコンピュータが実行して行われるソート処理における第１の規則に基づいて、複数の構造体データをソートする処理と、
該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出する処理と、
該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記情報埋め込み方法における第２の規則でソートする処理と、
該第２の規則でソートした複数の構造体データと、前記第１の規則に基づいてソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていると判定する処理と、
をコンピュータに実行させるための情報改竄検出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、主にデータ構造の記述方法について存在する冗長性を利用して情報を埋め込み、データの改竄や正当性を検出するための情報埋め込み・改竄検出装置及び情報埋め込み・改竄検出装方法並びに情報埋め込み・改竄検出プログラムに関する。特に本発明は３次元グラフィックスやＣＡＤ等で生成される３次元設計データなど、３次元形状を記述したデータヘ情報を埋め込む、データ・ハイディング技術、多面体や回転体等プリミティブな幾何学形状の組み合わせとして構成される３次元形状データの改竄や正当性を検出する技術に関する。
【０００２】
【従来の技術】
従来、電子透かし技術、データ・ハイディング技術として、以下のようなものが知られている。
例えば、特許文献１には、３次元形状モデルの幾何パラメータを変更することにより情報を埋め込む技術について記載されている。
具体的には、この従来技術では３次元形状モデルの幾何パラメータ、すなわち、幾何形状を定義するための記述を変更することにより、種々の情報を前記３次元形状モデルへ、可視または不可視の状態で埋め込む方法を採る。
埋め込み対象である３次元形状モデルは、通常、そのプリミティブ（構成要素）である、多面体、直線、点の集合、または曲面から構成される。また各プリミティブは幾何パラメータにより定義される。従って３次元形状モデルは多くの幾何パラメータの集合により、その全体の幾何形状が定義される。
よって、この従来技術では、３次元形状モデルを構成している複数のプリミティブの幾何パラメータを変更することにより、情報を埋め込むことが記載されている。
また、この従来技術では、幾何パラメータを数値パラメータ及び位相に分けて、各々を変更して情報を埋め込むこと、  逆に、抽出は上記変更された幾何パラメータを検出することにより、埋め込まれた情報を取り出すことについて記載されている。
【０００３】
また、特許文献２には、３次元形状モデルのデータにウェーブレット変換を施して、その結果に対して情報を埋め込む技術について記載されている。
具体的には、この従来例によれば、３次元形状変換手段が、オリジナルモデルＶ０  のデータにウェーブレット変換処理を行い、電子透かし埋め込み手段が、ウェーブレット変換処理により生成されるＷＴ係数ベクトルに透かしデータを埋め込んで、そのＷＴ係数ベクトルに基づいて、３次元形状逆変換手段が、透かしデータを埋め込んだ３次元形状モデル（流通モデルＶ’０  ）のデータを作成する。
したがって、この従来技術によれば、３次元形状データに、著作権情報等を含む電子情報データを埋め込む場合に、埋め込んだ３次元形状モデルの視覚的変化を考慮し、誤差の制御を行うことができ、また形状モデルの削除又は変形を受けた場合においても頑強な電子情報データ埋め込み方法について記載されている。
【０００４】
【特許文献１】
特開平１０−３３４２７２号公報
【特許文献２】
特開２０００−８２１５６号公報
【０００５】
【発明が解決しようとする課題】
一方で、電子透かし技術、データ・ハイディング技術についての設計要求としては、
・  透かし情報が編集、圧縮、伝送などの各種の処理に対して変質もしくは消失しないこと
・  透かし情報の埋め込みに伴うコンテンツの劣化が最小限であること
・  ヘッダ部や特定の領域に集中せず、コンテンツ全域にわたり分散配置すること
・  電子透かしの改ざんや消失などの悪意のある攻撃に対して強いこと．
・  透かし情報の埋め込み・検出処理が簡便で、処理所要時間が短いこと
等が挙げられるところ、上記先行技術文献１に記載の発明については、情報を埋め込むために本来の幾何データを変更する必要があること、透かし情報の検出アルゴリズムが複雑化することが問題となる。
また、上記先行上記先行技術文献２に記載の発明については、具体的な演算手法としてウェーブレット変換を用いることを特徴としているが、この発明の場合、元のデータとは異なるデータになってしまうことが問題となる。
【０００６】
本発明は、このような事情を考慮してなされたものであり、その目的は、表現されているデータの「意味」、「品質」を全く変えずに、情報の埋め込み・読み出しが可能な情報埋め込み・改竄検出装置及び情報埋め込み・改竄検出装方法並びに情報埋め込み・改竄検出プログラムを提供することにある。
【０００７】
【課題を解決するための手段】
この発明は上記の課題を解決すべくなされたもので、本発明は、複数の構造体データに情報を埋め込む情報埋め込み装置と、該情報埋め込み装置が情報を埋め込んだ複数の構造体データの改竄を検出する情報改竄検出装置とからなる原本性保障システムであって、前記情報埋め込み装置が、第１の規則に基づいて、前記複数の構造体データをソートするデータ標準化手段と、該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートするデータ変換手段とを具備し、前記情報改竄検出装置が、前記第１の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、前記ハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記第２の規則でソートするデータ変換手段と、該データ変換手段がソートした複数の構造体データと、前記データ標準化手段がソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記データ標準化手段がソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する判定手段とを具備することを特徴とする。
【０００８】
また、本発明は、所定の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記規則と異なる規則でソートするデータ変換手段とを具備することを特徴とする。
【０００９】
また、本発明は、情報埋め込み装置のデータ標準化手段と同一の第１の規則に基づいて、複数の構造体データをソートするデータ標準化手段と、該データ標準化手段がソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出するメッセージダイジェスト生成手段と、該メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、前記データ標準化手段がソートした複数の構造体データを、前記情報埋め込み装置のデータ変換手段と同一の規則であって、前記第１の規則と異なる規則でソートするデータ変換手段と、該データ変換手段がソートした複数の構造体データと、前記データ標準化手段がソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記データ標準化手段がソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する判定手段とを具備することを特徴とする。
【００１０】
また、本発明は、第１の規則に基づいて、複数の構造体データをソートし、該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出し、該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートすることを特徴とする。
【００１１】
また、本発明は、情報埋め込み方法における第１の規則に基づいて、複数の構造体データをソートし、該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出し、該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記情報埋め込み方法における第２の規則でソートし、該第２の規則でソートした複数の構造体データと、前記第１の規則に基づいてソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていると判定することを特徴とする。
【００１２】
また、本発明は、第１の規則に基づいて、複数の構造体データをソートする処理と、該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出する処理と、該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記第１の規則と異なる第２の規則でソートする処理とをコンピュータに実行させるための情報埋め込みプログラムである。
【００１３】
また、本発明は、情報埋め込みプログラムをコンピュータが実行して行われるソート処理における第１の規則に基づいて、複数の構造体データをソートする処理と、該ソートした複数の構造体データからなるビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出する処理と、該算出したメッセージダイジェストをキーとして、前記ソートした複数の構造体データを、前記情報埋め込み方法における第２の規則でソートする処理と、該第２の規則でソートした複数の構造体データと、前記第１の規則に基づいてソートする前の複数の構造体データとを比較し、該複数の構造体データが一致すれば、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていないと判定し、該複数の構造体データが一致しなければ、前記第１の規則に基づいてソートする前の複数の構造体データが改竄されていると判定する処理とをコンピュータに実行させるための情報改竄検出プログラムである。
【００１４】
【発明の実施の形態】
以下、図面を参照して、本発明の情報埋め込み・改竄検出装置を適用したデータ原本性保障システムの第１の実施形態について説明する。本実施形態のデータ原本性保障システムは、複数の構造体データ（後述する）に情報を埋め込む情報埋め込み装置と、情報埋め込み装置が情報を埋め込んだ複数の構造体データの改竄を検出する情報改竄検出装置とから構成される。
図１は、本実施形態の情報埋め込み装置の構成を示す構成図である。
本実施形態の情報埋め込み装置は、制御部１と、入力部２と、出力部３と、記憶部４と、データ標準化処理部５と、付加情報付与処理部６と、メッセージダイジェスト処理部７と、データ変換処理部８とをバス１０で接続して構成される。
【００１５】
制御部１は、入力部２、出力部３、記憶部４、データ標準化処理部５、付加情報付与処理部６、メッセージダイジェスト処理部７、データ変換処理部８におけるデータ入出力制御を行う。
入力部２は、透かし情報を埋め込む対象データである、複数の構造体データからなるオブジェクトの入力を受けるインターフェイス部である。
ここで、構造体データとは、１または複数のパラメータで記述されるデータ構造を持ったデータであって、該パラメータの値で順序付けることが可能なデータである。具体的には、データが複数のブロックに分かれて保持される形式の音声データ、図形形状等の記述データが複数のブロックに分かれて保持される形式の２次元画像データ、３次元画像データ、音声データ及び画像データが複数のブロックに分かれて保持される形式の動画像データ等であって、この順序を並べ替えてもデータの持つ意味が変わらない構造となっているデータである。
【００１６】
以下、３次元画像データとして、３次元グラフィックスやＣＡＤ等で生成される幾何形状データを例にとって説明する。３次元形状を記述するフォーマットとして、例えば
・ＶＲＭＬ（Ｖｉｒｔｕａｌ  Ｒｅａｌｉｔｙ  Ｍｏｄｅｌｉｎｇ  Ｌａｎｇｕａｇｅ）Ｗｅｂ等で用いられる３次元記述方式
・Ｘ３Ｄ（Ｅｘｔｅｎｓｉｂｌｅ  ３Ｄ）  ＶＲＭＬをＸＭＬに統合した新しい記述形式
・ＤＸＦ／ＤＷＧ  ＣＡＤでデファクトスタンダードのフォーマット
・ＨＰＧＬ  ＨＰのグラフィックスフォーマット
・Ｒａｗ  Ｔｒｉａｎｇｌｅ    ＡＳＣＩＩ  ＴＥＸＴで三角形の座標が書かれているだけのフォーマット
等がある。
【００１７】
図２、図３に構造体データとして、３次元形状のオブジェクトを記述するフォーマットの一例を示す。図２は、ｘｙｚ座標系で記述された６多角形のＶＲＭＬフォーマットの例を示す。本発明の観点において、ＶＲＭＬフォーマットは、ｘｙｚ座標値という１のパラメータで記述されるデータ構造を持ったテキストデータであって、このパラメータの値で順序付けることが可能なデータである（詳細は後述する）。
また、図３は、同様にｘｙｚ座標系で記述された３角形のＲａｗ  Ｔｒｉａｎｇｌｅフォーマットの例を示す。Ｒａｗ  Ｔｒｉａｎｇｌｅフォーマットも、同様に、ｘｙｚ座標で記述される３つの点が１つの三角形を表す。
このように、オブジェクト記述フォーマットとは、オブジェクトの種類、大きさ、位置、向きを定める幾何パラメータからなる。
【００１８】
出力部３は、透かし情報が埋め込まれた、複数の構造体データからなるオブジェクトを出力するインターフェイス部である。
記憶部４は、ヘッダ付加情報として、
・作成者や権利者を表す情報（名前、何らかのＩＤやメールアドレス、ＵＲＬ等）
・このデータを扱ったソフトウェアや装置に関する情報（シリアルナンバーやソフトウェアのバージョン情報等）
・作成日時やデータの大きさなどの情報
を記憶する。
【００１９】
データ標準化処理部５は、所定の規則（以下、第１の規則とする）に基づいて、複数の構造体データをソートする。
ここで、データ標準化処理部５が用いる規則、つまり、ソートアルゴリズム及びその実装形態は、いくつかの手法が考えられるが、基本的には何らかの基準で並ベ替えるという手法となる。
ソートアルゴリズムの適用対象、つまり、並ベ替える対象としては、
Ａ．オブジェクト自身の記述内容を標準化する
Ｂ．ファイル（ストリーム）内のオブジェクトの記載順序を標準化する
の２つがあり、それぞれに関しての具体的実装例として、例えば以下の方法が考えられる。
【００２０】
Ａ．オブジェクトを構成する構造体データの記述内容の標準化
１）．例えばポリゴンのように、点の順序集合として表現される形式の構造体データであれば、どの点から記述を始めるかについて、順序を変更してもオブジェクトとしての意味は変更されてしまうということがない。したがって、この順序には自由度が存在する。すなわち、例えば、第１の規則として、予め任意に定めた基準点までの距離が最も近いもの、もしくは最も違いものを記述開始点とすることが考えられる。
２）．ｃｙｌｉｎｄｅｒ（柱）や回転体のようなデータ構造の場合は、軸を持っており、この軸は線分を表すデータによって記述される。すなわち、この記述内容にも同様に自由度が存在し、基点と方向ベクトルで記述する、もしくは、始端と終端の２点で記述することが考えられる。
【００２１】
Ｂ．オブジェクトに順序を与える
１）．オブジェクトから予め任意に定めた基準点までの距離の近い順、または遠い順に並べ替える。このとき、特定の座標についてのみ並べ替え処理を適用する、あるいは、所定の座標系に座標変換したものに対して、並べ替え処理を適用してもよい。つまり、座標系は直交座標系であるか否かを問うものではない。
また、距離を測定するオブジェクトの代表点（代表となるパラメータ値）の選択の方法の例として、例えば、
・オブジェクト記述において最初に現れる点
・オブジェクトの重心
・  オブジェクトの中で、基準点に最も近い点（もしくは遠い点）
等が考えられる。
【００２２】
２）．オブジェクトの特性に応じた順序に並べ替える。
・たとえば、面オブジェクトならば面積、体積をもつオブジェクトならば体積でソートする。
・オブジェクトがテクスチャを持つようなものであれば、そのテクスチャを表現するデータに何らかの順序を定義し、それによってソートする。ここで言う「何らかの順序」とは、例えばテクスチャ表現データを数値であると解釈してその大きさによる順序を導入する、あるいはテクスチャ表現データを文字列であると解釈して辞書順による順序を導入する、等である。
３）．オブジェクトの位置の相対関係による順序に並べ替える。
１つのオブジェクトを指定し、そのオブジェクトからの距離によってツリー状のデータ構造を構成する。そして、そのツリーを何らかのルールで辿るという手法によって順序付けを行う。
等が考えられ、かつ、これらを組み合わせることも考えられる。
【００２３】
以下、標準化処理部５における標準化処理の例として、Ｒａｗ  Ｔｒｉａｎｇｌｅの例を用いて説明する。
すなわち、まず３次元空間内に、特定の基準点Ａを定義する（Ｓｔｅｐ０）。
次に、全ての三角形について、基準点Ａに近いものから記述する形式に変換する（Ｓｔｅｐ１）。つまり、Ｓｔｅｐ１の過程は、三角形を１つ選択し、この選択した三角形を記述する３点それぞれから、基準点Ａまでの距離を計算する。そして、距離が最も近い点が最初になるように、各点についての基準点Ａまでの距離の大小関係に基づいて、三角形の記述を変更する。
次に、３次元空間内に、特定の基準点Ｂを定義する（Ｓｔｅｐ２）。そして、Ｓｔｅｐ１と同様に、全ての三角形について、基準点Ｂまでの距離を計算する。なお、距離計算の対象は三角形の記述の第１の点とする規則とする。そして、基準点Ｂまでの距離算出結果に基づいて、基準点Ｂまでの距離が近い順に、三角形を並べ替える。
【００２４】
簡単な例について、上記第１の規則に基づく標準化処理の例を示す。
今、（０，０，０，  １，０，０，  ０．１，０）という三角形Ｔ１、（０，１，０，  １，１，０，  １，２，０）という三角形Ｔ２について考える。ＲａｗＥｉａｎｇｌｅフォーマットによる表記では、
……………
０００１０００１０
０１０１１０１２０
……………    …表記１
という記述となる。たとえば基準点Ａを（１０，０，０）とすると、上記Ｓｔｅｐ１により、
三角形の記述は、
Ｔ１（１、０、０．０．１．０．０、０．０）
Ｔ２（１，１．０，１．２．０．０．１．０）
という順番となる（標準化Ａ）。
【００２５】
次に、基準点Ｂを（０．１０．０）とすると、上記Ｓｔｅｐ３，Ｓｔｅｐ４により、Ｔ２のほうがＢに近いので、三角形の順番はＴ２が先となる。その結果、Ｒａｗ  Ｔｒｉａｎｇｌｅの表記は、上記の表記１から以下のように順序が並べ替えられる（標準化Ｂ）。
……………
１１０１２００１０
１０００１００００
……………    …表記２
以上で「標準化」が完了する。すなわち、基準点Ａ，Ｂが未知であれば、ソートアルゴリズムが既知であっても、正しく並べ替えることは不可能である。
また、距離の計算方法に関しても、例えば極座標や円筒座標系などに変換してから重み付け距離計算を行う等の様々なバリエーションが考えられる。
【００２６】
付加情報付与処理部６は、上記記憶部４に記憶された
・作成者や権利者を表す情報（名前、何らかのＩＤやメールアドレス、ＵＲＬ等）
・このデータを扱ったソフトウェアや装置に関する情報（シリアルナンバーやソフトウェアのバージョン情報等）
・作成日時やデータの大きさなどの情報
の付加情報を標準化処理部５の出力結果に付加する。なお、上記付加情報の内容は埋め込む側・受け取る側双方で共通鍵としておく。
【００２７】
メッセージダイジェスト処理部７は、データ標準化処理部５がソートした複数の構造体データからなるビットストリーム、または、さらに、付加情報付与処理部６がこれに付加情報を付加したビットストリームについて、所定のハッシュ関数を用いてメッセージダイジェストを算出する。
具体的なメッセージダイジェスト処理としては、例えば、１ｂｉｔ以上の任意のビット列を入力すると、固定長のビット列（１６０ｂｉｔのビットパターン）が出力されるというＭＤ５規格を用いる等が考えられる。
データ変換処理部８は、メッセージダイジェスト生成手段が算出したメッセージダイジェストをキーとして、データ標準化手段がソートした複数の構造体データを、上記第１の規則と異なる第２の規則でソートする。
【００２８】
上記の例の続きで、標準化された表記２を出発点として記述順序を決定する第２の規則の例を示す。
……………
１１０１２００１０
１０００１００００
……………    …表記２
まず標準化された複数の構造体データからなるビットストリーム、または、さらに、付加情報付与処理部６がこれに付加情報を付加したビットストリームについて、メッセージダイジェスト処埋にかけたら、例えば以下のようなビット列（２進数表記）のメッセージダイジェスト値が得られたとする。
１１１０１００１１０１０００１１１１００００１１０１０１０００１１１・・・
このビット列を用いて、表記２の記述をデータ変換する。
【００２９】
Ａ．個々の三角形の頂点の記述順序の変換
まず上記のビット列を最初から２ビットずつ取得する。この場合、２ｂｉｔであるので、４通りの組み合わせが考えられる。
最初の三角形Ｔ１の標準化された３頂点をＴ１ａ，Ｔ１ｂ，Ｔ１ｃとすると、得られるビットに応じて、次のように並べ替えることとする。
００：    Ｔ１ａ，Ｔ１ｂ，Ｔ１ｃ
０１：    Ｔ１ｂ．Ｔ１ｃ，Ｔ１ａ
１０：    Ｔ１ｃ，Ｔ１ａ，Ｔ１ｂ
１１：    Ｔ１ａ，Ｔ１ｂ，Ｔ１ｃ
メッセージダイジェスト値の先頭の２ビットについて“１１”であり、このままの並び替えを保持する。次の２ビットについて、“１０”であり、２つ目の三角形に関して、頂点の記述順序を（ｃ，ａ，ｂ）の順に入れ替える。
【００３０】
Ｂ．三角形そのものの並べ替え
続いて、オブジェクト（この説明では三角形２個）の順番を決定する。なお、以下、より適切な例として、１つの実施例として、今、オブジェクトＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｅ，Ｇの７個について考えるが、三角形２個の場合でもまったく同様に適用可能であり、本発明は、これによって限定されるものではない。
すなわち、メッセージダイジェストの結果のビットストリームの続きは今、“１００１１０”であり、これを左から順に使用することを考える。
最初：［Ａ］ＢＣＤＥＦＧ
まず、先頭のオブジェクトＡについて、先頭のｂｉｔが“１”なので、隣のＢと入れ替える。なお、並べ替え操作対象のオブジェクトは［］で囲んだものである。
［１］：Ｂ［Ａ］ＣＤＥＦＧ
次のビットは“０”であり、今度は隣とは入れ替えずに操作対象となるオブジェクトを隣のＣとする。
［２］：ＢＡ［Ｃ］ＤＥＦＧ
次も“０”であるので、さらに隣のＤを操作対象とする。
［３］：ＢＡＣ［Ｄ］ＥＦＧ
次は“１”であるので、隣のＥと入れ替える。
［４］：ＢＡＣＥ［Ｄ］ＦＧ
さらに“１”であるで、隣のＦとも入れ替える。
［５］：ＢＡＣＥＦ［Ｄ］Ｇ
最後は“０”であるで、並べ替えを終了する。
［６］：ＢＡＣＥＦＤＧ
【００３１】
以上で、データ変換処理部８による、メッセージダイジェスト値に基づく並べ替え処理が完了し、並べ替え処理された構造体データが出力部３に対して渡される。
すなわち、このようにしてメッセージダイジェスト関数が出力したビット列に従ってオブジェクトの記述順序を一意に決定することができる。
【００３２】
図２は、本実施形態の情報改竄検出装置の構成を示す構成図である。
本実施形態の情報改竄検出装置は、制御部１１と、入力部１２と、出力部１３と、記憶部１４と、データ標準化処理部１５と、付加情報付与処理部１６と、メッセージダイジェスト処理部１７と、データ変換処理部１８と、改竄判定処理部１９とをバス２０で接続して構成される。
制御部１１は、入力部１２、出力部１３、記憶部１４、データ標準化処理部１５、付加情報付与処理部１６、メッセージダイジェスト処理部１７、データ変換処理部１８、改竄判定処理部１９におけるデータ入出力制御を行う。
入力部１２は、上記情報埋め込み装置によって、透かし情報が埋め込まれた、複数の構造体データからなるオブジェクトを入力するインターフェイス部である。
出力部１３は、改竄判定処理部１９による改竄の有無の判定結果（後述する）を出力するインターフェイス部である。
記憶部１４は、上記情報埋め込み装置の記憶部４と同様と同一の付加情報を共通鍵として記憶する。
データ標準化処理部１５は、データ標準化処理部５と同様に、上記第１の規則に基づいて、入力部１２に入力される複数の構造体データをソートする。
付加情報付与処理部１６は、上記情報埋め込み装置の付加情報付与処理部６と同様に、記憶部１４が記憶する付加情報を標準化処理部５の出力結果に付加する。
メッセージダイジェスト処理部１７は、データ標準化部１５がソートした複数の構造体データからなるビットストリームについて、ハッシュ関数を用いてメッセージダイジェストを算出する。
データ変換処理部１８は、メッセージダイジェスト生成処理部１７が算出したメッセージダイジェストをキーとして、データ標準化処理部１５がソートした複数の構造体データ、または、さらに、付加情報付与処理部１６によって、付加情報が付与された複数の構造体データを上記データ変換処理部８と同様に、上記第２の規則でソートする。
改竄判定処理部１９は、データ変換処理部１８がデータ変換した複数の構造体データと、データ標準化処理部１５がソートする前の複数の構造体データとを比較し、これら２つの複数の構造体データが一致すれば、データ標準化処理部１５がソートする前の複数の構造体データ、つまり、入力された複数の構造体データが改竄されていないと判定し、これら２つの複数の構造体データが一致しなければ、データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する。
また、改竄判定処理部１９は、データ変換処理部１８がデータ変換した複数の構造体データについて、データ変換前に、付加データが付与されている場合は、これら２つの複数の構造体データが一致すれば、さらに、この付加データも改竄されていないと判定し、これら２つの複数の構造体データが一致しなければ、データ標準化手段がソートする前の複数の構造体データ、または、付加データのいずれか、あるいは、その両方が改竄されていると判定する。
【００３３】
次に、図面を参照して、本実施形態のデータ提供システムの動作について説明する。図５は、本実施形態の原本性保障システムによる情報埋め込み処理の過程を示すフローチャートである。また、図６はこれに伴う情報改竄検出処理の過程を示すフローチャートである。
情報埋め込み処理として、情報埋め込み装置において、まず複数の構造体データからなるオブジェクトの集合である３次元形状モデルのデータを用意する。入力部２にこの３次元形状モデルのデータが入力されると、データ標準化処理部５は、予め定めた第１の規則でソートを行い、標準データ表現形式に変換する。
次に、付加情報付与処理部６ｊは、ヘッダ情報、共通鍵等の付加情報を標準データ表現形式に変換された３次元形状モデルのデータに付与する。
次に、メッセージダイジェスト処理部７は、付加情報、標準化処理された３次元形状モデルのデータの全部または一部等についてメッセージダイジェスト処理を行ってメッセージダイジェスト値を得る。
データ変換処理部８は、このメッセージダイジェスト値のビットストリームに従って、第２の規則に基づいて、標準データ形式の表現を変換する。
以上で情報埋め込み処理が完了する。
【００３４】
次に、情報改竄検出処理として、情報改竄検出装置において、情報が埋め込まれていると思われる３次元形状モデルのデータを用意する。入力部１２にこの３次元形状モデルのデータが入力されると、データ標準化処理部１５は、データ標準化処理部５と同様に、予め定めた第１の規則でソートを行い、標準データ表現形式に変換する。
次に、付加情報付与処理部１６は、付加情報付与処理部６と同様にヘッダ情報、共通鍵等の付加情報を標準データ表現形式に変換された３次元形状モデルのデータに付与する。
次に、メッセージダイジェスト処理部１７は、メッセージダイジェスト処理部７と同様に、付加情報、標準化処理された３次元形状モデルのデータの全部または一部等についてメッセージダイジェスト処理を行ってメッセージダイジェスト値を得る。
データ変換処理部１８は、データ変換処理部８と同様に、このメッセージダイジェスト値のビットストリームに従って、第２の規則に基づいて、標準データ形式の表現を変換する。
改竄判定処理部１９は、データ変換処理部１８がデータ変換した複数の構造体データと、データ標準化処理部１５がソートする前の複数の構造体データとを比較し、これら２つの複数の構造体データが一致すれば、データ標準化処理部１５がソートする前の複数の構造体データ、つまり、入力された複数の構造体データが改竄されていないと判定し、これら２つの複数の構造体データが一致しなければ、データ標準化手段がソートする前の複数の構造体データが改竄されていると判定する。また、改竄判定処理部１９は、データ変換処理部１８がデータ変換した複数の構造体データについて、データ変換前に、付加データが付与されている場合は、これら２つの複数の構造体データが一致すれば、さらに、この付加データも改竄されていないと判定し、これら２つの複数の構造体データが一致しなければ、データ標準化手段がソートする前の複数の構造体データ、または、付加データのいずれか、あるいは、その両方が改竄されていると判定する。
【００３５】
したがって、本実施形態の原本性保障システムは、原本性保証の原理を利用して何らかのデータのハッシュ値をキーとしてオブジェクトの記述方法を変えることによって、データを表現する「冗長性」、すなわち、オブジェクトを記述する順序に情報を埋め込むので、表現されているデータの「意味」「品質」を全く変えることなく情報の埋め込みが可能となる。情報を陽に埋め込むのではなく、データの構造に意味がある。改竄した場合は適切な構造が変化するため、改竄を検出できる効果がある。
【００３６】
以下、本実施形態のデータ提供システムのより詳細な動作の例について説明する。今、オブシェクト（プリミティブ）が三角形の集合であった場合を考える。なお、一般の多角形や回転体、任意の数式モデルで表現される幾何学モデルであっても同様に適用可能である。
例えば三角形Ｔ１〜Ｔ１００があったとし、それぞれの頂点をＴ１（Ｔ１＿ａ，Ｔ１＿ｂ，Ｔ１＿ｃ）と表すことにする。ここでＴ１＿ａ等は３次元ベクトルを表現している。
データ構造中で、Ｔ１からＴ１００を記述する順序、また、三角形Ｔｉにおいて頂点（Ｔｉ＿ａ，Ｔｉ＿ｂ，Ｔｉ＿ｃ）を記述する順序には冗長性がある。最初に、例えば任意の基準点Ａを考え、それぞれの三角形の重心ベクトルがＡに近いものから順にソートする。
さらに、それぞれの三角形の頂点３つのうち、どれを最初に記述するかについても、例えば任意の基準点Ｂまでの距離が最も近いものを基点とするといった手法で、個々の三角形の記述方法も標準化する。
これによってデータが標準化される。
【００３７】
次に、このデータに附属する付加情報（ヘッダに記載される）や秘密のビット列、または標準化されたデータそのもの、およびそれらの組み合わせから、メッセージダイジェスト関数を用いて特定の長さのビット列を得る。
【００３８】
三角形の３頂点の記載する順序は３通り考えられるので、例えばメッセージダイジェストビットのｂｉｔごとに、どの頂点を最初に記述すべきかを決める。このようにして標準化されたデータの表現を変換する。
【００３９】
ここで、基準点ＡやＢの座標、またメッセージダイジェストを計算するための処理方法、ダイジェストを計算する際に用いるデータとして何を使うか、等を秘密にしておくことによって、改竄された場合に不正にデータを変換されることを防ぐことが出来る。
【００４０】
上述の情報埋め込み装置、情報改竄検出装置は、内部に、コンピュータシステムを有している。
そして、上述した情報埋め込み、情報改竄検出に関する一連の処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータが読み出して実行することによって、上記処理が行われる。
すなわち、情報埋め込み装置、情報改竄検出装置における、各処理手段、処理部は、ＣＰＵ等の中央演算処理装置がＲＯＭやＲＡＭ等の主記憶装置に上記プログラムを読み出して、情報の加工・演算処理を実行することにより、実現されるものである。
ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしても良い。
【図面の簡単な説明】
【図１】本実施形態の情報埋め込み装置の構成を示す構成図である。
【図２】ｘｙｚ座標系で記述された６多角形のＶＲＭＬフォーマットの例を示す図である。
【図３】ｘｙｚ座標系で記述された３角形のＲａｗ  Ｔｒｉａｎｇｌｅフォーマットの例を示す図である。
【図４】本実施形態の情報改竄検出装置の構成を示す構成図である。
【図５】本実施形態の原本性保障システムによる情報埋め込み処理の過程を示すフローチャートである。
【図６】情報改竄検出処理の過程を示すフローチャートである。
【符号の説明】
１、１１…制御部
２、１２…入力部
３、１３…出力部
４、１４…記憶部
５、１５…データ標準化処理部部
６、１６…付加情報付与処理部
７、１７…メッセージダイジェスト処理部
８、１８…データ変換部
１９…改竄判定処理部
【図１】
2004297347.tif 000003
【図２】
2004297347.tif 000004
【図３】
2004297347.tif 000005
【図４】
2004297347.tif 000006
【図５】
2004297347.tif 000007
【図６】
2004297347.tif 000008