(57)【特許請求の範囲】
【請求項１】
走査システムおよび計算装置を含むシステムにおいて実施される方法であって、
前記走査システムが、認証物体を走査して、前記認証物体の複数の特徴を取り込むステップと、
前記計算装置の処理手段が、
前記取り込まれた前記複数の特徴を表すデータを圧縮するステップであって、前記圧縮するステップは、
特定の端点が前記認証物体の所定領域において出現する確率を表す確率密度関数を用いて、前記特徴の端点により定義されるベクトルを決定するステップと、
前記計算装置の記憶手段に格納されている算術符号化アルゴリズムを適用することにより、前記決定された一部のベクトルを、複数のベクトル間のポイントを接続するパスとして符号化するステップとを含む圧縮するステップと、
前記パスと、ハッシュされたテキストデータとを合成してメッセージを生成するステップと、
前記合成されたメッセージを記憶手段に格納されているプライベートキーで符号化するステップと、
前記認証物体および前記符号化されたメッセージを含むラベルを作成するステップと
を備えることを特徴とする方法。
【請求項２】
前記特徴は、前記認証物体内に位置するファイバであることを特徴とする請求項１に記載の方法。
【請求項３】
前記走査システムは、前記認証物体を照射する光源を含んでおり、
前記確率密度関数は、前記ファイバの第１端点が前記認証物体の照射領域内に位置するときに、前記ファイバの第２端点が非照射領域の所定の位置に出現する尤度として定義されるものであることを特徴とする請求項２に記載の方法。
【請求項４】
前記確率密度関数は、前記ファイバの長さに基づいて導出されるように構成されていることを特徴とする請求項２に記載の方法。
【請求項５】
前記ベクトルは、２本のファイバの端点を表すことを特徴とする請求項２に記載の方法。
【請求項６】
前記ラベルは、自己認証されるように構成された実物証明書であり、前記認証物体は、前記実物証明書に含まれることを特徴とする請求項１に記載の方法。
【請求項７】
前記符号化されたメッセージは、バーコードとして前記ラベルに含まれることを特徴とする請求項１に記載の方法。
【請求項８】
前記処理手段は、暗号化セキュアハッシュアルゴリズムを用いて、前記ハッシュされたテキストデータを生成するように構成されていることを特徴とする請求項１に記載の方法。
【請求項９】
前記アルゴリズムは、ＳＨＡ１暗号化アルゴリズムであることを特徴とする請求項８に記載の方法。
【請求項１０】
走査システムおよび計算装置を含むシステムであって、
前記走査システムは、認証物体を走査して、前記認証物体の複数の特徴を取り込み、
前記計算装置の処理手段は、
前記取り込まれた前記複数の特徴を表すデータを圧縮する処理であって、前記データを圧縮する処理は、
特定の端点が前記認証物体の所定領域において出現する確率を表す確率密度関数を用いて、前記特徴の端点により定義されるベクトルを決定し、
前記計算装置の記憶手段に格納されている算術符号化アルゴリズムを適用することにより、前記決定された一部のベクトルを、複数のベクトル間のポイントを接続するパスとして符号化する、前記データを圧縮する処理と、
前記パスと、ハッシュされたテキストデータとを合成してメッセージを生成する処理と、
前記合成されたメッセージを記憶手段に格納されているプライベートキーで符号化する処理と、
前記認証物体および前記符号化されたメッセージを含むラベルを生成する処理と
を実行するように構成されていることを特徴とするシステム。
【請求項１１】
前記特徴は、前記認証物体内に位置するファイバであることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記走査システムは、前記認証物体を照射する光源を含んでおり、
前記確率密度関数は、前記ファイバの第１端点が前記認証物体の照射領域内に位置するときに、前記ファイバの第２端点が非照射領域の所定の位置に出現する尤度として定義されるものであることを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記確率密度関数は、前記ファイバの長さに基づいて導出されるように構成されていることを特徴とする請求項１１に記載のシステム。
【請求項１４】
前記ベクトルは、２本のファイバの端点を表すことを特徴とする請求項１１に記載のシステム。
【請求項１５】
前記ラベルは、自己認証されるように構成された実物証明書であり、前記認証物体は、前記実物証明書に含まれることを特徴とする請求項１０に記載のシステム。
【請求項１６】
前記符号化されたメッセージは、バーコードとして前記ラベルに含まれることを特徴とする請求項１０に記載のシステム。
【請求項１７】
前記処理手段は、暗号化セキュアハッシュアルゴリズムを用いて、前記ハッシュされたテキストデータを生成するように構成されていることを特徴とする請求項１０に記載のシステム。
【請求項１８】
前記アルゴリズムは、ＳＨＡ１暗号化アルゴリズムであることを特徴とする請求項１７に記載のシステム。
【請求項１９】
認証物体の複数の特徴を表すデータを圧縮する手段であって、前記圧縮する手段は、
特定の端点が前記認証物体の所定領域において出現する確率を表す確率密度関数を用いて、前記特徴の端点により定義されるベクトルを決定する手段と、
記憶手段に格納されている算術符号化アルゴリズムを適用することにより、前記決定された一部のベクトルを、複数のベクトル間のポイントを接続するパスとして符号化するステップとを含む、圧縮する手段と、
前記パスと、ハッシュされたテキストデータとを合成してメッセージを生成する手段と、
前記合成されたメッセージを記憶手段に格納されているプライベートキーで符号化する手段と、
前記認証物体および前記符号化されたメッセージを含むラベルを生成する手段と
を備えることを特徴とする装置。
【請求項２０】
前記特徴は、前記認証物体内に位置するファイバであることを特徴とする請求項１９に記載の装置。
【請求項２１】
文字列を含むテキストデータを決定する手段と、
前記テキストデータをアルゴリズムでハッシュする手段と、
前記ハッシュされたテキストデータと、前記パスとを合成する手段と
をさらに備えたことを特徴とする請求項１９に記載の装置。
【請求項２２】
前記符号化されたデータと、前記認証物体を走査して得られる特徴を表すデータとを比較することにより、前記ラベルを認証する手段をさらに備えたことを特徴とする請求項１９に記載の装置。
【請求項２３】
前記特徴は、ランダムに分布されていることを特徴とする請求項１に記載の方法。
【請求項２４】
前記特徴は、ランダムに分布されていることを特徴とする請求項１０に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明するシステムおよび方法は、一般に、偽造されにくいラベルおよび／または改ざんされにくいラベルに関し、より詳細には、（埋め込まれているか、あるいは自然に内在するかどうかにかかわらず）物体の無秩序に分布したフィーチャ（ｆｅａｔｕｒｅ）を利用して、ラベルを偽造かつ／または改ざんしようとする不正な試みを制限することに関する。
【背景技術】
【０００２】
従来、ラベルの偽造および改ざんにより、販売業者および製造業者は、収益および顧客の損失の点で毎年何十億ドルもの損害を被っている。コンピュータ技術の浸透により、本物に似せたラベルを作成することが比較的簡単になった。例えば、スキャナを使用して本物のラベルを走査して高分解能画像を取得し、次いで、そのラベルを最小限のコストで繰り返し複写することができる。また、クーポンをスキャンし、改変し（例えば、より価値を高くし）、繰り返し印刷し、換金することができる。
【０００３】
近年、偽造および改ざんの氾濫を防止するために様々な技術が用いられてきた。ラベルの安全性を保護する一方法は、バーコードを組み込むことによるものである。一般に、バーコードは、ラベル上に印刷された機械可読コードである。バーコードスキャナを使用して、バーコード付きラベルを迅速に読み取り、認証することができる。現在のバーコード付きラベルに伴う１つの問題は、様々な商品に同じラベルが使用され得ることである。
【０００４】
現時点での別の解決策は、走査されたバーコードを、データベース（例えば、ＰＯＳ（販売時点情報管理）システム）に記憶させた安全なデータと比較して検査することである。ただし、この解決策は、販売業者または製造業者からの最新のデータを組み込むことを必要とする。このような解決策は、複数の事業体の時宜を得た緊密な協力を必要とする。また、このような解決策は、その実施形態の柔軟性に制限があり、必ずしも実現可能ではないことがある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、これらの技術には共通の欠点がある。すなわち、走査されるラベルは、所与の製品について物理的に同じものである。したがって、本物のラベルを作成する製造工程が極めて高度であったとしても、一般に、偽造者が偽物を作成する方法を見つけるのに多くの時間はかからない。ひとたびラベルのコピーに成功すれば、（例えば、低コストで複製されるマスタコピーを作成することによって）繰り返しそれを複写することができる。ラベルがある一定の回数使用された後でデータベースのブラックリストに載るとしても、初めて走査されるラベルが実際に本物であるという保証はない。
【０００６】
したがって、現在の解決策では、コピーするのが比較的難しく作成するのに費用がかからないラベルを提供することができない。
【課題を解決するための手段】
【０００７】
本明細書で説明するシステムおよび方法は、物体内で無秩序に分布したフィーチャを符号化することを対象とする。一つの態様では、認証物体内で無秩序に分布したフィーチャを求める。これら無秩序に分布したフィーチャを表すデータを圧縮し、署名で符号化する。ラベルを作成し、認証物体および符号化されたデータを含める。
【０００８】
別の態様では、認証物体に関連する確率密度関数を求めることによってデータを圧縮する。少なくとも部分的にこの確率密度関数に基づいて、無秩序に分布した属性に関連するベクトルを求める。算術符号化アルゴリズムを利用してこれらのベクトルを符号化する。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照しながら本発明の実施形態について詳細に説明する。
Ｉ．序論
本明細書で説明するシステムおよび方法は、ラベル内で使用する物体の無秩序に分布したフィーチャについての情報を符号化することを対象としている。ラベルは、商品に付けられているか商品に埋め込まれている、任意のタイプの識別手段を含むことができる。本明細書では、本物であると認証されるように構成されたラベルを、実物証明書と称する。本明細書では、実物証明書で使用する無秩序に分布したフィーチャを有する物体を、認証物体と称する。自己認証を可能にするために、実物証明書は、認証物体および無秩序に分布したフィーチャについての情報をともに含むことができる。圧縮方法を利用することにより、符号化し実物証明書に含めることができる無秩序に分布したフィーチャに関する情報量を増やすことができる。一計算例によれば、実物証明書を偽造するコストは、この情報の圧縮処理の向上に比例して、指数関数的に増加する。このように偽造コストを大きく増加させることによって、比較的安価に製造することができ、改ざんが難しい信頼性の高い実物証明書を得ることができる。
【００１０】
図１に、実物証明書などのラベルの一部として使用する認証物体１００の例を示す。実物証明書中で効果的に使用するために、一般に認証物体１００は、固有の複製困難な無秩序に分布したフィーチャを含んでいる。図１に示す認証物体１００の例は、ファイバをベースにした実物証明書の一部であり、この物体内に無作為に埋め込まれたファイバ１１０を含む。ファイバ１１０は、認証物体１００の無秩序に分布したフィーチャとして機能する。ファイバ１１０は、任意の手段によって認証物体１００に組み込むことができる。例えば、ファイバ１１０を認証物体１００に吹き付けることができる。製造工程中に、ファイバ１１０を認証物体１００に埋め込むこともできる。一実施形態では、ファイバ１１０は、その両端点間で光を透過することができる光ファイバである。したがって、認証物体１００のある領域１２０に光を当てることによって、この照らされた領域内に少なくとも１つの端点を有するファイバ１３１〜１３３の端点が照明される。
【００１１】
図１においては、認証物体１００は、κ本の無秩序に分布したファイバを含んでいる。認証物体１００を、Ｌ×Ｌ画素の分解能で走査することができる。各ファイバは固定長Ｒを有する。図１の認証物体１００の例はファイバを含んでいるが、他の無秩序に分布したフィーチャを有する認証物体も、実物証明書において同様に使用することができることを理解されたい。
【００１２】
実物証明書中で認証物体１００の無秩序に分布したフィーチャを使用して、製品など任意の物体の正当性の証明を保護することができる。例えば、実物証明書の無秩序に分布したフィーチャについてのある種の複製困難なデータをデジタル化し、発行者のプライベートキーによって署名する。そして、この署名を機械読取り可能な形式でこの実物証明書上に刷り込み、それによってこのように作成されたインスタンス（ｉｎｓｔａｎｃｅ）が正当であることを立証することができる。実物証明書の各インスタンスは、発行者が正当性を保証したい物体に関連する。一実施形態では、正当性の検証は、発行者のパブリックキーを使用して署名済みデータ（無秩序に分布したフィーチャについてのデータ）を抽出し、この抽出されたデータが、実物証明書のインスタンスに関連するデータと一致することを検証することによって行われる。保護された物体を偽造するためには、敵対者は、（ｉ）発行者のプライベートキーを見つけ出すか、（ii）実物証明書のすでに署名されたインスタンスを正確に複製することが可能な製造工程を考案するか、（iii）実物証明書の署名済みインスタンスを悪用するかのいずれかを行う必要がある。このような見地から、この実物証明書を使用することにより、成功した敵対的製造工程の開発を蓄積コストも含めて、一つの実物証明書インスタンスを偽造するコストを超えない程度の価値の製品を、保護することができる。
【００１３】
実物証明書システムの目標は、製品または製品に関連するある種の情報の正当性を保証することである。適用分野は、ソフトウエアおよび媒体（例えば、ＤＶＤ、ＣＤ）の海賊行為対策から、偽造不可能なクーポン、ならびに改ざん防止ハードウエアの設計に及ぶ数多く広範なものの集合である。例えば、改ざん防止チップを生成するには、そのパッケージに実物証明書を被覆することを必要とするだろう。保護するシリコンチップの正当性を検証するために、各チップを使用する前に実物証明書の完全性を検証すべきである。
【００１４】
以下に、ファイバをベースにした実物証明書の無秩序に分布したフィーチャを、費用をかけずに効率的に読み出すためのハードウエアプラットホームの例について論ずる。このハードウエアプラットホームは、バーコードを含むことができる。低コストリーダ用のバーコードの容量は約３キロビットに制限されるので、プライベートキーによって署名されたメッセージも同じ長さに制限される。また、実物証明書システムの目的の１つは、実物証明書の特定のインスタンスを偽造しようとする敵対者の労力を最大にすることである。したがって、固定長の署名済みメッセージ中に、ファイバをベースにした実物証明書の固有の無秩序に分布したフィーチャについて、できるだけ多くの情報を記憶させることに関連する問題を論じる。ファイバをベースにした実物証明書用の解析モデルの例を提供する。次いで、以下の考察では、１組の点の圧縮の問題を定式化し、実物証明書のインスタンス中のファイバの位置を最適に圧縮することが、ＮＰ完全問題であることも示す。発見的方法でこの問題に対処するために、従来の圧縮方法の圧縮比を大きく向上させるアルゴリズムを提供する。
【００１５】
II．実物証明書の発行および検証
図２は、実物証明書システム２００の例および実物証明書を発行し検証するためにこのシステムが採用する手順の例を示す概略図である。実物証明書システム２００は、実物証明書２１０、発行者２３０、および検証者２５０を含む。図２に示すように、実物証明書２１０は、図１の認証物体１００、バーコード２１３、およびテキスト２１５を含むことができる。
【００１６】
実物証明書に関して保護する必要がある情報には、（ａ）認証物体１００の、複製が難しい無秩序に分布したフィーチャを表現したものと、（ｂ）関連する任意のテキストデータとが含まれる。まず、ハードウエア装置を使用して、認証物体１００の無秩序に分布したフィーチャ、例えばファイバの位置を走査する。以下、図３に即して、この情報を収集し表現する方法の詳細を論じる。
【００１７】
考察を行うために、得られる情報ｆは、ｎＦビットの無作為な文字列であると仮定する。パラメータｎＦは一定であり、ｎＦ＝ｋ＊ｎＲＳＡ、ｋ∈Ｎに等しい。ただし、ｎＲＳＡはＲＳＡパブリックキーの長さ（例えば、ｎＲＳＡ＝1024）、ｋは一般にｋ∈［1,3］とする。ｎＦが一定なので、認証物体１００の無秩序に分布したフィーチャを表すデータ２３１のダイジェスト（ｄｉｇｅｓｔ）ｆにより、任意の２つの別個の実物証明書インスタンスの距離を統計的に最大にすることができる。これが達成されると直接、検証ステップ中において、false negative やfalse positiveの誤検出が生じる確度が最小限に抑えられる。
【００１８】
テキストデータｔは、応用例（例えば、有効期限、製造元の保証）によって決まる任意の文字列である。このテキストデータは、テキスト２１５から導出され、図２に示すように実物証明書２１０上に印刷される。
【００１９】
テキストデータからは、ＳＨＡ１などの暗号化セキュアハッシュアルゴリズム２３７を用いてハッシュ値を生成することができる。ハッシュ関数の出力を、ｎＴビットのメッセージｔと示す。発行者２３０は、ＲＳＡによって署名することができるメッセージｍを生成する。例えば、ｍの各ビットがｆおよびｔからのすべてのビットによって決まるようにする可逆演算子
【００２０】
【数１】
0004718843.tif 000002
【００２１】
を用いて、メッセージｆとメッセージｔを合成し、ｎＭ＝ｎＦの長さのメッセージｍにする。このステップにより、データ２３１およびテキスト２１５中で操作する必要があるビット数を最大にし、それによってある特定のメッセージｍを生成することができる。このような演算子の例は、ｔまたはｔからのビットのある特定の部分集合をキーとして用いて、
【００２２】
【数２】
0004718843.tif 000003
【００２３】
のようにｆを対称暗号化することである。発行者２３０のプライベートキー２３３を用いてＲＳＡ署名２３５でメッセージｍに署名する。ｍのｎＲＳＡ個のビットはそれぞれ別々に署名する。得られた署名ｓは、ｎＳ＝ｎＭ＝ｎＦ個のビットを有する。このメッセージを符号化し、実物証明書２１０上に（ＰＤＦ４１７標準に従うバーコードなどの）バーコード２１３として印刷する。
【００２４】
実物証明書２１０の検証はいくつかのステップを伴う。まず、検証者２５０により、印刷されたコンポーネントであるテキスト２１５およびバーコード２１３を走査する。バーコード２１３を復号して元の印刷された署名ｓにする。テキスト２１５を走査し、ハッシュ生成をしてメッセージｔを生成する。このテキストを印刷するのに用いるフォントは検証者２５０に既知のものであり、改良型ＯＣＲに最適化されているので、このタスクに汎用ＯＣＲ（光学式文字認識）は必要とされないことに留意されたい。実物証明書の検証をうまく行うには、テキスト２１５およびバーコード２１３をエラーなしに読み取る必要がある。これは、最新のスキャン技術によって容易に実現可能なタスクである。
【００２５】
検証者２５０により、発行者のパブリックキー２５３を用いてｓに対してＲＳＡ署名の検証２５５が実施され、署名済みのメッセージｍが得られる。次いで、検証者２５０により、
【００２６】
【数３】
0004718843.tif 000004
【００２７】
の計算を行うことができる。
【００２８】
【数４】
0004718843.tif 000005
【００２９】
として暗号化を利用する実施例では、これを解読化
【００３０】
【数５】
0004718843.tif 000006
【００３１】
によって実現する。次に、検証者２５０は、認証物体２５１内で無秩序に分布したフィーチャを表すデータ２５１を走査し、それらのプレゼンテーション（ｐｒｅｓｅｎｔａｔｉｏｎ）ｆ’を生成する。検証者２５０は、ｆ’と抽出されたｆとを比較する。検証者２５０では、２組のデータの相関を定量化する必要がある。２組のデータとは、１組は証明書に付いているものであり、１組は実物証明書の署名を生成するのに使用したものである。判定ブロック２５９で、これら２組のデータの相似レベルがある閾値よりも大きい場合、検証者２５０は、実物証明書２１０が本物であることを通知する。逆の場合も同様である。
【００３２】
図３Ａは、実物証明書に付随する認証物体３１０の無秩序に分布したフィーチャを取り込む走査システム３００の例の概略図である。走査システム３００は、光センサ３２２および光源３２４を含んでいる。光センサ３２２は、認証物体３１０を走査するように構成され、特定の分解能のＣＣＤ（電荷結合素子）マトリックスを含むことができる。一実施形態では、光センサ３２２は１２８×１２８画素の分解能を持っている。光源３２４は、特定の波長の光を供給して、認証物体３１０のある領域を照明するように構成される。光源３２４は、例えばＬＥＤ（発光ダイオード）を含むことができる。図３Ａに示すように、光源３２４によって、認証物体３１０中にあるファイバ３２６の一方の端部を照明する。この光は、ファイバ３２６の他方の端部へ透過し、光センサ３２２によって感知される。
【００３３】
図３Ｂは、図３Ａの認証物体３１０の上面図である。動作時には、走査システム３００は、認証物体３１０を領域３１１〜３１４などの領域に分割する。図３Ｂに示すように、走査システム３００の光源３２４は領域３１４に光を当てるが、領域３１１〜３１３は光源３２４から切り離されている。領域３１４を照明することで、認証物体３１０の領域３１１〜３１３内の端点の位置を光センサ３２２によって求めることができる。そのため、認証物体３１０内で無秩序に分布したフィーチャの読取り信号は、４つの異なる「点の組」を持った４枚のデジタル画像を含んでいる。各点の組は、特定の領域に関連するものであり、その領域を照明することによって求められる。
【００３４】
ナノテクノロジなどの技術が進歩すれば、電子デバイスが、実物証明書から無秩序に分布したフィーチャを復号し、これらのフィーチャに対応する光パターンを生成できることが考えられる。このようなデバイスにより、実物証明書は偽造することができる。一実施形態においては、走査システム３００は、光源３２４に用いられる光の波長（例えば色）を変化させることによって、このような偽造方法を妨害するように構成することができる。例えば、走査システム３００によって認証物体を走査するたびに、光の波長を無作為に選択することが可能である。光センサ３２２は、認証物体内のファイバから放出される光の波長を検出し、この波長が光源３２４から放出される光の波長に対応するかどうか判定するように構成することができる。放出光と検出光の波長が一致しない場合には、この実物証明書は偽物である可能性がある。
【００３５】
図４は、実物証明書を生成するのに用いることのできる工程４００の例のフロー図である。ブロック４０５において、実物証明書中の認証物体を走査する。この認証物体は、図３Ａの走査システム３００を使用して走査することができる。
【００３６】
ブロック４１０において、認証物体の無秩序に分布した属性を表すデータが決定される。ファイバをベースにした認証物体においては、このデータは、照明されたファイバの端点、例えば図３Ｂに示す端点の位置を含むことができる。
【００３７】
ブロック４１５において、このデータを圧縮して実物証明書のセキュリティレベルを強化する。データ圧縮は、図５に即して詳細に論じられる。簡単に述べれば、認証物体内で無秩序に分布した属性を表すデータの一部を圧縮するために、パスを決定することができる。
【００３８】
ブロック４２０においては、この圧縮されたデータを符号化する。例えば、図２のプライベートキー２３３を用いて、この圧縮されたデータに署名することができる。ブロック４２５において、この符号化されたデータを実物証明書に組み込む。例えば、図２のバーコード２１３などのバーコードとして、この符号化されたデータを実物証明書に印刷することができる。
【００３９】
図５は、認証物体の無秩序に分布した属性を表すデータを圧縮するのに用いることができる工程５００の例の流れ図である。この考察を行うために、ファイバをベースにした実物証明書の状況で工程５００を説明する。ただし、工程５００は、任意のタイプの実物証明書に適用することが可能である。
【００４０】
ブロック５０５において、認証物体に関連する確率密度関数を求める。確率密度関数は、セクションIII−Ａで論じることになる。式１１に、確率密度関数の例を示す。図８に、この確率密度関数の例のグラフを示す。簡単に述べれば、この確率密度関数は、１単位の無秩序に分布した属性が認証物体のある位置で見つかる尤度を表す。ファイバをベースにした実物証明書の状況においては、この確率密度関数は、認証物体のある領域中の特定の点が照明される確率を表すことができる。この確率密度関数を用いて、特定の領域において全ファイバの何本が照明されることになるかを計算することもできる。
【００４１】
ブロック５１０において、無秩序に分布した属性に関連するベクトルを求める。ファイバをベースにした実物証明書の状況においては、２点間のベクトル（ポイント−ポイント間ベクトル）が用いられ、これをセクションIＶ−Ａで論じる。具体的には、式１６を用いて２点間のベクトルを計算し、それによって、ファイバをベースにした実物証明書中の無秩序に分布した属性を表すことができる。
【００４２】
ブロック５１５において、算術符号化アルゴリズムを用いてこれらのベクトルを符号化する。算術符号化アルゴリズムは、セクションIＶ−Ａにおいて論じられる。表２は、アルゴリズムの例を示す。
【００４３】
ブロック５２０においては、一定量のデータ中のベクトルの一部を圧縮するパスを求める。セクションIＶ−Ｂで、このパスを計算する方法を論じる。このパスの例は、式２０を用いて計算することができる。ブロック５２５において、無秩序に分布した属性の一部を表す圧縮データのパスを返す。
【００４４】
III．実物証明書モデル
このセクションでは、ファイバをベースにした実物証明書の解析モデルを論じる。実物証明書Ｓの２つのフィーチャをモデル化する。この実物証明書の特定の領域Ｓｉが照明されると仮定すると、Ｓ−Ｓｉ中の特定の点が照明される確率密度関数が計算される。また、Ｓ中にＫ本のファイバがあると仮定すると、Ｓ−Ｓｉ中で照明されるファイバの予想数も計算される。
【００４５】
Ａ．照明されるファイバ端点の分布
認証物体（Ｌ，Ｒ，Ｋ）は、１辺がＬの単位長さを有する正方形としてモデル化される。この物体上には、固定長Ｒ≦Ｌ／２のＫ本のファイバが物体全体にわたって無秩序に分散している。可変ファイバ長または任意形状の認証物体などの他のモデル変形形態は、このモデルから導出することができる。図１に示すように、２次元直交座標系の正の象限にこの認証物体を配置する。さらに、この認証物体を４つの等しい正方形に分割し、Ｓ＝｛Ｓ１、Ｓ２、Ｓ３、Ｓ４｝とする。図３Ａおよび図３Ｂに即して上記で説明したように、これらの正方形をそれぞれ使用して、３次元ファイバ構造が記録される。次に、ファイバは、点Ａ，Ｂのタプル（ｔｕｐｌｅ）ｆ＝｛Ａ,Ｂ｝として表示される。ここで、Ａ,Ｂ⊂Ｓの２点間の距離は、‖Ａ−Ｂ‖＝Ｒとなる。
【００４６】
定義１．照明されるファイバ端点の分布。
これらの正方形Ｓｉの１つが照明されると仮定すると、端点Ｂが照明領域Ｓｉ中に位置するという条件で、任意の区域Ｐ⊂Ｓ−Ｓｉがファイバｆ＝｛Ａ,Ｂ｝の照明される他方の端点Ａを含む確率ζ（ｉ,Ｐ）によって、任意の点Ｑ（ｘ,ｙ）⊂Ｓ−Ｓｉについての確率密度関数（ｐｄｆ）
【００４７】
【数６】
0004718843.tif 000007
【００４８】
が定義される。より形式的には、任意のＰ⊂Ｓ−Ｓｉについて、
【００４９】
【数７】
0004718843.tif 000008
【００５０】
になる。
【００５１】
ファイバｆ＝｛Ａ,Ｂ｝を認証物体内で分散させることが、（ｉ）第１端点Ａが認証物体上に着地する、（ii）第２端点Ｂが認証物体に当たる、という２つの従属的なイベントからなると仮定する。ＡはＣＯＡ上の任意の場所に着地することができるが、Ｂの位置はＡの位置によって決まる。端点Ｂは、この認証物体内に含まれ、かつＡを中心とする半径Ｒの円の外周の一部の上に着地しなければならない。このサブセクションの残りの部分では、関数
【００５２】
【数８】
0004718843.tif 000009
【００５３】
を、上述したイベント（ｉ〜ii）の解析に基づいて解析的に計算する。簡単にするために、領域Ｓ１が照らされる場合について、
【００５４】
【数９】
0004718843.tif 000010
【００５５】
のみを計算する。
【００５６】
【数１０】
0004718843.tif 000011
【００５７】
は２つのステップで計算する。
【００５８】
定義２．外周の包含。
まず、所与の点Ａ⊂Ｓについて、外周包含関数（perimeter containment function）
【００５９】
【数１１】
0004718843.tif 000012
【００６０】
を定義する。この外周包含関数により、Ａを中心とする半径Ｒの円の外周のうち全認証物体Ｓに包含される部分（円弧）の長さが測定される。この認証物体内には、
【００６１】
【数１２】
0004718843.tif 000013
【００６２】
が一様に計算される（図６において、Ｐ１からＰ４と表示した）４つの異なる領域がある。
【００６３】
図６は、認証物体６００の例内の４つの異なる領域に対応する区域Ｐ１〜Ｐ４を図で表現したものである。ある領域Ｐｘ内の各点ごとに、以下で論じる式７〜式１０を用いるその区域特有の閉じた解析形式を使用して、外周包含関数を計算する。
【００６４】
区域Ｐ１。この区域は、この認証物体の中央の区域である。この区域では、任意の点Ｑ⊂Ｐ１について、Ｑを中心とする半径Ｒの円は、この認証物体の辺のどれとも交差しない。この区域は、Ｒ≦ｘ≦Ｌ−Ｒ、Ｒ≦ｙ≦Ｌ−Ｒによって境界づけられる。
【００６５】
【数１３】
0004718843.tif 000014
【００６６】
区域Ｐ２。４つの異なるＰ２領域がある。これらの領域では、任意の点Ｑ⊂Ｐ２を中心とする半径Ｒの円は、この認証物体の１辺と厳密に２回交差する。簡単にするために、Ｒ≦ｘ≦Ｌ−Ｒ、０≦ｙ＜Ｒの１つについてのみ検討する。他の３つの領域に関する式は、対称に計算することができる。
【００６７】
【数１４】
0004718843.tif 000015
【００６８】
区域Ｐ３。４つの異なるＰ３領域がある。これらの領域では、任意の点Ｑ⊂Ｐ３を中心とする半径Ｒの円は、この認証物体の異なる２辺とそれぞれ２回交差する。０≦ｘ＜Ｒ、０≦ｙ＜Ｒ、ｘ２＋ｙ２≧Ｒ２についてのみ考える。
【００６９】
【数１５】
0004718843.tif 000016
【００７０】
区域Ｐ４。４つの異なるＰ４領域がある。これらの領域では、任意の点Ｑ⊂Ｐ４を中心とする半径Ｒの円は、このＣＯＡの２辺とそれぞれ１回交差する。ｘ２＋ｙ２＜Ｒ２についてのみ考える。
【００７１】
【数１６】
0004718843.tif 000017
【００７２】
式８〜式１０ではすべて、｛０,π/2｝内の関数arcsine（・）およびarccos（・）の戻り値のみを考える。
【００７３】
第２ステップでは、Ｓ１に含まれ、かつＱ（ｘ,ｙ）を中心とする半径Ｒの円Ｃ（Ｑ,Ｒ）の１つ（または複数）の部分上にＢが位置する場合にのみ、ファイバｆ＝｛Ａ,Ｂ｝の照明される端点Ａが、位置Ａ＝Ｑ（ｘ,ｙ）にあることに基づいて、実際の
【００７４】
【数１７】
0004718843.tif 000018
【００７５】
を計算する。
【００７６】
補助定理３．
【００７７】
【数１８】
0004718843.tif 000019
【００７８】
の
【００７９】
【数１９】
0004718843.tif 000020
【００８０】
への従属性。関数
【００８１】
【数２０】
0004718843.tif 000021
【００８２】
を用いて、ｐｄｆ
【００８３】
【数２１】
0004718843.tif 000022
【００８４】
を、以下の積分を用いて計算する。
【００８５】
【数２２】
0004718843.tif 000023
【００８６】
ただし、
【００８７】
【数２３】
0004718843.tif 000024
【００８８】
は、Ｃ（Ｑ、Ｒ）⊂Ｓｉの外周を参照し、αは、
【００８９】
【数２４】
0004718843.tif 000025
【００９０】
となる定数である。
【００９１】
Ｂ⊂Ｓｉであるファイバｆ＝｛Ｑ,Ｂ｝によってのみ、点Ｑ⊂Ｓ−Ｓｉが照明される。このことは、Ｂが、Ｓｉに含まれる円Ｃ（Ｑ,Ｒ）の外周上のどこかに位置していることを示唆している。所与のファイバｆ＝｛Ａ,Ｂ｝について、長さがｄｌ⊂Ｓの特定の極めて短い円弧上にＡが着地する確率は、
【００９２】
【数２５】
0004718843.tif 000026
【００９３】
に等しい。したがって、
【００９４】
【数２６】
0004718843.tif 000027
【００９５】
になる。ただし、関数area（Ｓ−Ｓｉ）は、Ｓ−Ｓｉに属する面積を計算する。そのため、点Ｑ⊂Ｓ−Ｓ１におけるｐｄｆ
【００９６】
【数２７】
0004718843.tif 000028
【００９７】
は、
【００９８】
【数２８】
0004718843.tif 000029
【００９９】
の値の逆数をＣ（Ｑ,Ｒ）⊂Ｓ１にわたって積分したものに比例する。
【０１００】
図７は、式１１で値が求められる積分に対する解として別個の解析的な式を有する認証物体７００の例上の、１９個の異なる領域を図で表現したものである。簡単のために、
【０１０１】
【数２９】
0004718843.tif 000030
【０１０２】
を簡単な数値計算を用いて近似的に解く。図８に、その結果を示す。
【０１０３】
図８は、パラメータがＬ＝６４およびＲ＝２８である正方形の認証物体について、各単位点の場所においてサンプリングした確率密度関数の例のグラフである。図８は、ファイバの端点がある小さな区域Ｐ⊂Ｓ−Ｓ１に着地する尤度が、Ｓ−Ｓ１内でのＰの個々の位置に応じて大きく変化することを示す。Ｓ−Ｓｉ全体にわたる
【０１０４】
【数３０】
0004718843.tif 000031
【０１０５】
の変動についての情報を用いることによって、セクションIＶに示すように、点の部分集合の圧縮アルゴリズムを大きく改善することができる。区域Ｓ−Ｓｉ全体にわたって
【０１０６】
【数３１】
0004718843.tif 000032
【０１０７】
である認証物体を製造することは容易なタスクではなく、おそらくは元の認証物体を偽造するのと同じくらい難しい。
【０１０８】
【表１】
0004718843.tif 000033
【０１０９】
Ｂ．ファイバ端点の照明比
定義３．ファイバ端点の照明比。認証物体（Ｌ,Ｒ,Ｋ）およびその照明領域Ｓｉについて、ファイバｆ＝｛Ａ,Ｂ｝の一方の端点がＡ⊂Ｓｉにあるという条件で、他方の端点がＢ⊂Ｓ−Ｓｉにくるようにファイバｆ＝｛Ａ,Ｂ｝が着地する確率として、照明比λを次のように定義する。
λ＝Ｐｒ［Ｂ⊂Ｓ−Ｓｉ｜ｆ＝｛Ａ,Ｂ｝、Ａ⊂Ｓｉ］  （１４）
【０１１０】
定義４．照明される可能性がある円弧。任意の点Ａ⊂Ｓｉについて、Ｃ（Ａ,Ｒ）の外周のうちＳ−Ｓｉに含まれる部分の長さを測定する関数
【０１１１】
【数３２】
0004718843.tif 000034
【０１１２】
を定義する。
【０１１３】
図９は、区域Ｔ０〜Ｔ８を図で表現したものである。これらの区域では、別個の解析的な閉じた形を用いて、
【０１１４】
【数３３】
0004718843.tif 000035
【０１１５】
を計算した。
【０１１６】
【数３４】
0004718843.tif 000036
【０１１７】
は、セクションIII−Ａのイベント（ｉ〜ii）の解析に基づいて解析的に計算する。セクションIII−Ａと同様に、領域Ｓｉが照らされる場合についてのみ計算を行う。ＣＯＡ内には、（図９でＴ０からＴ８と示す）９個の異なる領域がある。これらの区域では、
【０１１８】
【数３５】
0004718843.tif 000037
【０１１９】
が一様に計算される。表１に、Ｓ１内のＱの位置によって決まる
【０１２０】
【数３６】
0004718843.tif 000038
【０１２１】
についての解析的な閉じた形を示す。
【０１２２】
補助定理４．
【０１２３】
【数３７】
0004718843.tif 000039
【０１２４】
、
【０１２５】
【数３８】
0004718843.tif 000040
【０１２６】
、およびλの従属性。定義３で定義した照明比は次のように計算することができる。
【０１２７】
【数３９】
0004718843.tif 000041
【０１２８】
点Ａ⊂Ｓを中心とする半径Ｒの円をＣ（Ａ,Ｒ）と示す。点Ｑ⊂Ｓｉごとに、ファイバｆ＝｛Ｑ,Ｂ｝の他方の端点ＢがＳ−Ｓｉ内に着地する尤度は、Ｃ（Ｑ,Ｒ）の外周のうちＳ−ＳｉおよびＳにそれぞれ含まれる部分の長さの比に等しい。Ｓｉ内のすべての点にわたってこの比を積分することによって、式１５を求める。
【０１２９】
認証物体（Ｌ,Ｒ,Ｋ）が与えられると、式１５を数値的に近似することによって計算したλと、表１からの
【０１３０】
【数４０】
0004718843.tif 000042
【０１３１】
についての閉じた形とを用いて、Ｓ１がλＫ／２で照明されるときにＳ−Ｓ１内で照明される点の予想数を計算することができる。例えば、認証物体（64,28,100）について、得られるλは約0.74になる。これは、Ｓｉが照明される場合に照明される端点の数は、平均して約0.74×50＝37になることを意味する。
【０１３２】
IＶ．ＣＯＡ内の点の部分集合の圧縮
この実物証明書システムの目標は、個々の認証物体のインスタンスを製造する（すなわち、偽造する）タスクができるだけ難しくなるようにすることである。この目標は、認証物体のファイバの位置をできるだけ多く記録する要求として定量化される。この圧縮アルゴリズムの例では、認証物体の領域数は４であり、したがって、領域Ｓｉごとに、署名済みメッセージ中のビットの１／４であるｎＭ／４を、Ｓｉに光を当てた後でＳ−Ｓｉ内で照明されるファイバ端点をできるだけ多く記憶するのに専用に使用する。一般に、照明される点すべてを記憶する必要はなく、ｎＭ／４個のビットを使用して符号化が可能なこれらの点の中の、最大の部分集合のみを記憶すればよいことに留意されたい。
【０１３３】
このセクションでは、認証物体内で照明される２点間の距離を符号化するように構成された手順を説明する。この手順は、算術符号化に基づくものである。次に、一定数のビットを使用してできるだけ多くのファイバ端点を圧縮する問題を定式化する。最後に、この考察では、この問題がＮＰ完全問題であり、準最適解としての構築的で発見的な方法が提示されることを示す。
【０１３４】
Ａ．２点間の（ポイント−ポイント間）ベクトルの符号化
このサブセクションでは、ほぼ最小のビット数を使用して、始点と終点で定義されるベクトルを符号化する方法を説明する。追加の制約は、検討している区域内の点が与えられたｐｄｆに従って出現するということである。
【０１３５】
１）算術符号化
ＡＣ（算術符号器）は、任意の長さの入力ストリームを、［0,1｝内の一つの有理数に変換する。ＡＣの主な長所は、エントロピー近くまで任意に圧縮し得るということである。以下の考察では、シンボル出現のｐｄｆが未知であるアルファベットを仮定して、語「ａｂａ」を符号化する方法を示す。
【０１３６】
図１０は、シンボル出現のｐｄｆが未知であるアルファベットＬ＝｛a,b｝を仮定して、算術符号器が文字列「ａｂａ」を符号化する方法の例の図式表現である。図１０にその例を示す。まず、ＡＣの範囲を［0,1｝にリセットし、Ｌ内で各記号が出現する確度をPr［ａ］＝Pr［ｂ］＝1/2とする。そのため、このＡＣはその範囲を、それぞれ「ｂ」および「ａ」を表す２つの副範囲［0,0.5｝および［0.5,1｝に分割する。記号ａは、ＡＣの範囲をこの記号に対応する範囲、すなわち［0.5,1｝に制約することによって符号化される。さらに、ＡＣは、記号「ａ」の出現カウンタを更新し、Pr［ａ］＝2/3、Pr［ｂ］＝1/3と計算し直す。次の反復において、更新されたPr［ａ］、Pr［ｂ］に従って、ＡＣはその範囲を、それぞれ「ｂ」および「ａ」を表す［0.5,0.6667｝および［0.6667,1｝に分割する。「ｂ」が次に到達すると、ＡＣはその範囲を、対応する［0.5,0.6667｝に小さくし、Pr［ａ］＝Pr［ｂ］＝2/4に更新し、この新しい範囲を、それぞれ「ｂ」および「ａ」を表す［0.5,0.5833｝および［0.5833,0.6667｝に分割する。最後の記号は「ａ」なので、ＡＣは出力として［0.5833,0.6667｝内の任意の数を選択することによって、この記号を符号化する。最小のビット（この例では桁）数で符号化される数である0.6を選択することによって、ＡＣはその最終出力を生成する。復号器は、圧縮メッセージのヘッダ内で明示的に、あるいは、特別な「ｅｎｄ−ｏｆ−ｆｉｌｅ」記号によってメッセージ長がわかる。
【０１３７】
ＡＣは、その動作範囲を、上限と下限の先頭桁が等しくなる範囲まで反復して小さくする。次いで、この先頭桁を送ることができる。再正規化と呼ぶこの工程では、精度に制限がある算術演算装置によって、任意の長さのファイルを圧縮することができる。従来型ＡＣの性能向上では、算術計算の近似をあらかじめ計算して、除算および乗算をシフト処理および加算に置き換えることに焦点が当てられる。
【０１３８】
ＡＣは、ソースのエントロピー
【０１３９】
【数４１】
0004718843.tif 000043
【０１４０】
に等しいいくつかのビットを使用して、一連の入力記号ｓ＝ｓ１,ｓ２,．．．を符号化する。したがって、独立した同一の分布記号からなる半無限ストリームについて、無限精度で算術を行うコンピュータ上では、このＡＣは最適なエントロピー符号器である。
【０１４１】
２．最小距離２点間（ポイント−ポイント間）ベクトルの算術符号化
認証物体（Ｌ,Ｒ,Ｋ）があるとして、その象限Ｓｉの１つに光が当たると仮定する。次に、この認証物体を、Ｌ×Ｌ個のユニットの正方形からなるグリッドＵ＝u(i,j)、ｉ＝１．．．Ｌ、ｊ＝１．．．Ｌに分割すると仮定する。ただし、各u(i,j)は、ｘ∈｛i−1、i｝、ｙ∈｛j−1、j｝内の正方形区域を含む。ユニット区域により、認証物体のデジタル走査画素がモデル化される。この走査の分解能はＬ×Ｌに等しい。次に、ユニットu(x,y)の主点を、座標が（x,y）の点Ｑｕと定義する。
【０１４２】
補助定理５．ユニットの照明尤度。一方の端点が正確にＳ−Ｓｉ内にあるκ本のファイバがあると仮定すると、任意のユニット区域u(x,y)⊂Ｓ−Ｓｉが、少なくとも１つの照明されたファイバ端点を含む確率は、
τ(u)＝Pr［（∃ｆ＝｛A,B｝∈Ｆ）A⊂u、B⊂Ｓｉ］＝1−［1−ζ（i,u）］κ  （１６）
になり、また
τ(u)＝Pr［（∃ｆ＝｛A,B｝∈Ｆ）Ａ⊂u,Ｂ⊂Ｓｉ］＝１−Pr［（┐∃ｃ∈Ｆ）Ａ⊂u,Ｂ⊂Ｓｉ］＝１−（１−Pr［Ａ⊂u,Ｂ⊂Ｓｉ│ｆ＝｛A,B｝］）κ
になる。
【０１４３】
式７から、式１６が結論づけられる。セクションIII−Ｂで、κの期待値が、Ｅ［κ］＝λＫ／２と計算される。
【０１４４】
問題１．ＣＯＡを符号化するデュアルベクトル（Dual Vector）。ユニットu⊂Ｓ−Ｓｉが照明されたファイバ端点を含むという条件で、できるだけ少ないビットを使用して、他の２つの照明されるユニットν１およびν２のユニットｕに対する相対的な位置を符号化することが目標である。追加の制約は、Ｓ−Ｓｉ内のすべての照明されたユニットの中で、ν１およびν２の主点Ｑ１およびＱ２がそれぞれ、ユークリッド的な意味において、ｕの主点Ｑｕから最も近接した距離の２つの位置にあることである。│Ｖ│＞１である１組のユニットＶが、ｕに対して同じ距離のところにある場合、照明される尤度ａｒｇｍａｘν⊂Ｖ（τ（ν））が最も高いものを最初に符号化するという優先ルールを設定する。
【０１４５】
【表２】
0004718843.tif 000044
【０１４６】
２つのユニット間のベクトルの符号化は、ＡＣを使用して行う。このＡＣは、アルゴリズムＡ１を利用して符号化記号ごとに、すなわち、ソースユニットuとは異なる各ユニットν⊂Ｓ−Ｓｉごとに、対応する範囲を符号化間隔に割り当てる。ユニットνごとに、アルゴリズムＡ１は、νが、ソースユニットｕに対して２つの最も近接した照明区域の１つである確率に等しい範囲を割り当てる。この確率をｐ（ν│ｕ）と示す。κ≫１の場合、Ｓ−Ｓｉ内でユニットが照明されると予想され、ｐ（ν│ｕ）は次のように計算することができる。
【０１４７】
【数４２】
0004718843.tif 000045
【０１４８】
ただし、ユニットの組Ｍν（u）は、アルゴリズムＡ１の場合と同様に計算される。ユニットνごとに、アルゴリズムＡ１は、ｕがすでに符号化されているという条件でＡＣがνを符号化するのに用いる範囲γ（v,u）を割り当てる。この範囲は、
【０１４９】
【数４３】
0004718843.tif 000046
【０１５０】
に等しい。
【０１５１】
そのため、これら２つの最も近接した照明されるユニットは、構築によってほぼ最適に符号化される（例えば、この符号化は、無限精度で算術を行うプロセッサ上で最適に行われる）。なぜならば、ソースのエントロピー
【０１５２】
【数４４】
0004718843.tif 000047
【０１５３】
にほぼ等しいいくつかのビットを使用して、一連の記号が符号化されるからである。
【０１５４】
基本要素としてデュアルベクトル符号化を用いて、セクションIＶ−Ｂで提示する全体的圧縮アルゴリズムによって点の部分集合を符号化する。この符号化アルゴリズムは、セクションIＶ−Ａ．２で提示した１組の仮定についてはほぼ最適であるが、この同じ１組の制約は全体的な圧縮目標については有効ではない。したがって、Ａ１による範囲の割当てとともに算術符号化を用いることの本来の最適性をセクションIＶ−Ｂで論じる。
【０１５５】
Ｂ．点の部分集合の圧縮
ビット数を固定して、できるだけ多くの可能な照明されるユニット区域の位置を圧縮する最適化問題をモデル化する。以下の重み付けしたエッジを伴う、有向完全グラフを考える。照明されるユニットｕ⊂Ｓ−Ｓｉごとに、ノードｎｕを生成する。ノードｎｕからノードｎνの有向エッジｅ（u,v）を、uがすでに符号化されているという条件で、式１９の場合と同様に、νを指すベクトルを符号化する符号語の最適な長さω（ｅ（u,v））＝−log２［γ（v,u）］で重み付けする。このグラフを、Ｇ（Ｎ,Ｅ,Ω）と示す。ただし、Ｎ、Ｅ、およびΩは、ノード、有向エッジ、および対応する重み付けのそれぞれの組を表す。
【０１５６】
問題２．点の部分集合の圧縮（ＣＰＳ）
インスタンス：負でない頂点関数Ωを伴い、有向、重み付けされた完全グラフＧ（Ｎ,Ｅ）：Ｅ→Ｒ、正の整数ｌｍｉｎ∈Ｚ＋、正の実数Λ∈Ｒ＋
問い：ｌ＞ｌｍｉｎ個のノードＮ＊⊂Ｎの部分集合が、これらのノードを通るパスとともに存在するか。これらのノードとは、このパスに沿う重みの和が、
【０１５７】
【数４５】
0004718843.tif 000048
【０１５８】
になる順列
【０１５９】
【数４６】
0004718843.tif 000049
【０１６０】
である。
【０１６１】
問題２により、一定の記憶量（すなわち、Λ）を用いて、認証物体内のできるだけ多く（すなわち、ｌ個）のファイバ端点を圧縮する最適化問題がモデル化される。Λについてのバイナリサーチ（ｂｉｎａｒｙ  ｓｅａｒｃｈ）によってＡＴＳＰ（非対称巡回セールスマン問題）をＣＰＳに変形すること、すなわち、
【０１６２】
【数４７】
0004718843.tif 000050
【０１６３】
を示すことができるので、この問題はＮＰ完全問題である。このセクションの残りの部分では、この問題を解くことに照準を合わせた効率的な構築的で発見的な方法Ａ２を提示する。この発見的方法に対する主要な設計要件は、実行時の性能が高速なことである。なぜならば、製造ラインでは各実物証明書に別々に署名しなければならないからである。
【０１６４】
まず、Ｎ内の２つのノード間の距離の尺度は、すべてのノードについての三角不等式に従わない。直感的には、セクションIＶ−Ａの符号化手順により、あるユニットがこれら２つの最も近接した照明点の１つである確度に比例するいくつかのビットを使用して、Ｓ−Ｓｉ内のベクトルが符号化される。したがって、ソースノードからより遠く離れたユニットは、かなり長い符号語で符号化される。これらが行われる可能性は小さいが、こうすると、解決パスにおけるこれらのノードへの近道が極めて望ましくないものになる。
【０１６５】
定理２．一般に、距離の尺度ωは次の三角不等式に従わない。
【０１６６】
ω（e（u,v））＋ω（e（v,w））≧ω（u,w）
簡単にするために、（∀u⊂Ｓ−Ｓｉ）ｔ＝τ（u）＝定数と仮定すると、u、v、およびwは、Ｓ−Ｓｉ内で同じ線に沿って位置する。ユークリッド距離‖u−v‖、‖v−w‖、および‖u−w‖はそれぞれ、a、b、およびa+bである。この三角不等式は、ｆ（u,v,w）＝log２［γ（w,u）］−log２［γ（v,u）］−log２［γ（w,v）］≧０であることを示唆している。式１７および式１８から、
【０１６７】
【数４８】
0004718843.tif 000051
【０１６８】
と計算することができ、ａｂπｔ≫１についてはこの三角不等式が成り立たない、すなわち、ｆ（a,b,t）＜０になることが示される。
【０１６９】
この三角不等式が成り立つＡＴＳＰに対する最適な近似アルゴリズムで得られる解は、最適な解に比べて最大でlog（｜Ｎ｜）倍劣っている。一方、本発明者の知る限り、この三角不等式が成り立たないＡＴＳＰの変形形態に対する近似アルゴリズムは、開発されていない。一般的な例では、距離計測関数ωが任意のときには、ＡＴＳＰ問題はＮＰＯ完全になり、すなわち、Ｐ＝ＮＰにならない限り、良好な近似アルゴリズムは存在しない。一方、この三角不等式をスケーリングしたバージョンμ（ω（e（u,v））＋ω（e（v,w）））≧ω（u,w）、μ＞１を満足するＴＳＰの変形形態に対する近似アルゴリズムにより解くことができる結果は、最悪の場合、最適解よりも（3μ＋1）μ/2倍劣っている。距離計測関数ωはこの制約に従わず、したがって、問題２についての発見的方法は、最悪の場合の保証なしに展開される。さらに、本発明者らは、最悪の場合の保証というよりは、発見的方法の性能が平均してできるだけ良好になることに照準を合わせている。満足に圧縮することができない認証物体インスタンスを、処理することができる。このイベントの尤度は、百万分の一未満と小さいはずである。
【０１７０】
【表３−１】
0004718843.tif 000052
【０１７１】
【表３−２】
0004718843.tif 000053
【０１７２】
セクションIＶ−Ａからの距離計測関数ωを用いるにあたって基礎となる原理は、良好な解は、２つの最も近接した隣接ノードを経由して、各ノードをうまく移動するという仮定に基づいている。したがって、問題２の範囲では、用いる計測値が最適になるのは、見つかった最適解がこの特性を満足する場合だけである。最終解がこの特性をもたない場合、単一のベクトルを符号化することの最適性は、この解に含まれるエッジの重み付けの分布によって決まる。
【０１７３】
開発した発見的方法Ａ２には、構築段階および反復改善段階の２つの段階がある。構築段階は、欲張りな（greedy法）発見的方法にしたがって、初期解を形成する。まず、Ａ２は、１組の支配的なエッジＥ’を識別する。ノードuとv間のエッジｅ（u,v）とｅ（v,u）の対ごとに、Ａ２は、これら２つのうち短いほうだけを選択し、それをＥ’内に記憶する。次に、Ｅ’内でエッジを分類し、加算された重みができるだけΛに近い上位Ｋ個の最短エッジを選択することによって、１組の初期サブパスＰを生成する。パスｐｉ内の第１ノードおよび最終ノードをそれぞれｓｉおよびｄｉと示す。次のステップにおいて、Ａ２は、Ｐからのサブパスをそれらの重みの小さい順に反復して連結する。任意の点において、すべての可能な結合が確立されるまで、共通のソース−デスティネーションノードｄｉ＝ｓｊを有する最短のサブパスｐｉとｐｊの対を連結する。可能性は小さいが｜Ｐ｜＝１になるときは、最適解が見つかり、サーチが停止する。そうでない場合には、すべての単一エッジサブパスをＰから取り除く。次いで、ダイクストラ（Ｄｉｊｋｓｔｒａ）アルゴリズムを用いて、Ａ２は、Ｐ内の各サブパスｐｉの各デスティネーション末端ｄｉと、他のすべてのサブパスｓｊ（i＝1・・・｜Ｐ｜、i≠j）のソース末端との間ですべての最短パスを見つける。これらの最短パスは、Ｐ内にないノードを経由してパス設定される。ｓｉとｄｊの間の最短パスをｑ（i,j）と示す。別の、欲張りな（greedy法）ステップにおいては、Ａ２は、すべての連結ｐｉ｜ｑ（i,j）｜ｐｊを、それらの重み／ノード計数の比に従って分類する。この計測値の小さい順に、Ａ２は、残りのパスの総数が｜Ｐ｜＝maxP（通常は、maxP＝9）になるまで、Ｎ−Ｐ内にあるノードを経由してＰ内のサブパスを継続して連結する。これらの残りのパスは、計測値が最適な、すなわち濃度が最大であり、重みの和がΛよりも小さいパスｐｈを見つける厳密なアルゴリズムを用いて連結される。最後のステップにおいて、パス再設定手順は、Ｐ内のすべてのノードを見渡し、ダイクストラアルゴリズムを用いて、Ｅ内の残りのノードを経由してＰ内の他のノードへの最短パスを見つけようと試みる。この同じ手順は、ｐｈ内に存在するものよりも良好な終了末端を見つけようとも試みる。変更されたパスごとに、Ａ２は、変更された新しいパスが現在の最適パスｐｈよりも良好な計測値を有するかどうかを調べる。
【０１７４】
図１１は、κ＝88個のノードとともに、認証物体（512,0.4・512,256）のインスタンスの例を示している。Ａ２は、太い線で図に示すパスを返す。このパスでは、重みの和がΛ＝512よりも小さくなる。このパスを記録するには、１つの点当たり12.11ビットが用いられる。
【０１７５】
反復による改善段階では、以下のループの巡回を数回繰り返す。第１ステップでは、Ａ２は、｜ｐｈ｜が最大になり、ｐｈに沿う重みの和がρΛの何分の一かよりも小さくなるように、現在見つかっている最適パスｐｂｅｓｔをｐｈに狭める。縮小パラメータρは、反復ごとにρ∈｛0.4,0.8｝内から無作為に選択する。ノードｎ０およびｎｌを、ｐｈ内の第１ノードおよび最終ノードと示す。ｐｈ内の重みの和がΛよりも小さい状態で、デスティネーションまたはソースとしてそれぞれｎ０またはｎｌを有するエッジの中から、重みが最小のエッジｅを見つけ、それをｐｈに連結する。新しいパスｐｈの候補が生成されると、その計測値がそれまでに生成された最適パスの計測値よりも良好な場合には、この新しいパス候補を最適解として採用する。この反復による改善ループの最後のステップとして、Ａ２は前に説明したパス再設定手順を実施する。
【０１７６】
個々の認証物体（Ｌ,Ｒ,Ｋ）クラスに対するＡ２の実行時間を１秒以内に収めるために、この改善ループをＩ＝｛100,10000｝回繰り返す。一般に、最悪時のＡ２の複雑さは、ダイクストラアルゴリズムによって複数のソースによる最短パスを計算するときには、Ｏ（｜Ｎ｜３log｜Ｎ｜）になる。すべての対の最短パスを計算するためにＦｌｏｙｄ−Ｗａｒｓｈａｌｌアルゴリズムを利用する実施形態の場合では、Ａ２の複雑さをＯ（｜Ｎ｜３）に減らすことができる。このグラフは元々完全であるが、重みが大きいエッジを取り除くことによって、疎グラフが生成され、この場合には、Ｊｏｈｎｓｏｎアルゴリズムをすべての対の最短パスに用いると、複雑さはＯ（｜Ｎ｜２log｜Ｎ｜＋｜Ｎ｜｜Ｅ｜）になる。
【０１７７】
Ｖ．実験による評価
このセクションでの考察では、認証物体（Ｌ,Ｒ,Ｋ）のパラメータが、アルゴリズムＡ．２．の性能にどのような影響を及ぼすかを示す。図１１に、この問題、すなわち認証物体（512,0.4・512,256）の単一のインスタンスに対する解を示す。走査グリッドは、Ｌ＝５１２個の走査セルである。この図は、認証物体の左下象限が照明される場合について示す。グラフＧ（Ｎ,Ｅ）を、対応する照明されるファイバ端点を用いて形成し、それを中程度の太い線で示す。このグラフには、κ＝88個の各ノードから始まる最短エッジの上位１０個だけを示している。得られたパスは４１個のノードからなり、これを太い線で図に示している。パスのエッジに沿う重みの和は、記憶容量制限のΛ＝512ビットよりも小さい。このパスは、１つのファイバ端点当たり１２．１１ビット（b/fep）を使用して圧縮される。圧縮せずにデータを記憶させると、４１×１８＝738ビットを必要とし、その結果、圧縮比は０．６１になる。この圧縮比は、圧縮されたメッセージのサイズと、元のメッセージのサイズの比として定義する。
【０１７８】
ＶＩ．ＣＯＡシステムの設計目的
実物証明書の設計者の目標は、制限された製造コストζｍで偽造コストζｆを最大にすることである。いくつかのパラメータがζｍに影響を及ぼし得る。簡潔かつ簡単にするために、以下の３つのパラメータについて論じる。
ファイバの全長  ＲＫ≦Φ
走査公差  ζ、および
バーコードの記憶容量  Λ
【０１７９】
システム性能は、以下の方法により最適化することができる。すなわち、敵対者が署名済みのファイバ端点からなる十分な数の部分集合を正確に位置決めするのに利用可能な試行回数を制限すること（セクションIＶ−Ａ）、および予想偽造コストζｆ（Ａ２）が最大になるようにシステムパラメータ｛ＲΦ,ＫΦ｝を選択する（セクションIＶ−Ｂ）ことの２つによる。
【０１８０】
Ａ．敵対者の試行回数を制限すること
Λに制限された記憶容量内においてκ個の照明されたファイバ端点のうち、Ｇ個を記憶する圧縮方式Ｃを考える。一般に、実物証明書を偽造するとき、敵対者は、κ本のファイバをすべて使用して、それらのうち少なくともＧζ個を、対応する位置に正確に配置しようと試みることができる。実物証明書の偽造コストは、利用可能な試行回数に大きく依存する。ここでは、検証中に署名済みのファイバ端点の周りでファイバの変則的な分布を検出することによって、敵対者の試行回数ＫＴを減らすことに照準を合わせた技法を提案する。
【０１８１】
【表４】
0004718843.tif 000054
【０１８２】
実物証明書の発行者および検証者は、認証物体の各象限ＳｉごとにアルゴリズムＡ３のそれぞれの部分を繰り返す。発行者はまず、認証物体のインスタンスを走査し、Ｓｉが照らされるときに明るくなる点の組Ｎについての情報を収集する。次に、発行者は、利用可能なΛ個のビットを使用して、Ａ２が返した｜Ｐ｜＝Ｇの最大の部分集合Ｐ⊂Ｎを圧縮する。次いで、Ａ３は、各ユニットｕｉ∈Ｕとその最も近接したユニットｐｊ∈Ｐのユークリッド距離が、大きくてもε１になる部分集合Ｕ⊂Ｓ−Ｓｉを見つける。複数のユニットからなる部分集合Ｕは、Ｐのε１近傍を表す。次いで、発行者は、Ｕの中に存在するＮ内の点の数ＫＴを計数する。誤検出（false negative）を防止するためにＫＴはＧよりも大きくなければならないので、発行者は、Ｐとともにメッセージｍ中の差ε２＝ＫＴ−Ｇを記憶する。これらは、後で発行者のプライベートキーを使用して署名する（セクションII参照）。検証者は、発行者のパブリックキーを使用して、添付の署名から圧縮された点の部分集合Ｐおよびε２を引き出し、対応するε１近傍であるＵを生成し直す。次いで、検証者は、Ｓｉが照らされるときに照明されるファイバの組Ｎ’について認証物体のインスタンスを走査する。検証者は、ＵおよびＮ’内の共通の点の数が多くてもＧ＋ε２であり、かつＮ’およびＰ内の共通の点の数が少なくともＧζであることを調べることによって、このインスタンスが本物であることを通知する。
【０１８３】
署名中にε２を記憶することによって、敵対者は、多くてもＫＴ＝Ｇ＋ε２回の試行を利用して、Ｐのε１近傍においてファイバを位置決めすることを強いられる。敵対者の目標は、Ｐから少なくともＧζ個のファイバ端点を正確に配置することであり、したがって、敵対者は、偽造工程中に、Ｐのε１近傍での配置をＧ（１−ζ）＋ε２回まで間違えてもよい。各試行は点ｐｉを目標とするが、それがうまくいかない場合には、ｐｉのε１近傍に留まることが予想される。検証者は、ε１を大きくすることによって、起こり得る配置間違いをより大きな近傍にわたって識別することができる。しかしながら、こうすることにより、実物証明書の設計者ができるだけ小さく抑えたい値であるε２の期待値も大きくなってしまう。
【０１８４】
以下に、所与のε１＝定数を採用し、次いで、いくつかの実物証明書パラメータの観点から、主目的ζｆ（Ａ２）を最大にしようと試みる実験的な設計方法を示す。
【０１８５】
Ｂ．ＣＯＡシステムの設計
問題３．ＣＯＡシステムの設計目的。所与の圧縮アルゴリズムＡ２、一定のＲＫ≦Φ、ζ、ε１、およびΛについて、
【０１８６】
【数４９】
0004718843.tif 000055
【０１８７】
を最大にする利用可能なファイバの切片｛ＲΦ,ＫΦ｝を見つける。ただし、ζｆは補助定理２で定義する。式２２中の試行回数κは、サブセクションIＶ−Ａで提示したＫＴに等しいことに留意されたい。式２２中の圧縮性能Ｇは、Ａ２の効果によって決まる。
【０１８８】
図１２は、コスト効果を最適化した実物証明書設計のグラフである。横軸は、Ｌに対してファイバ長Ｒを定量化したものであり、縦軸は、ファイバの数Ｋを示す。図の棒は、制約制限をΛ＝512ビット、１組の固定パラメータをζ＝0.9、ε１＝8、およびν＝0.8として、対数偽造コストlog１０（ζｆ（Ａ２,Ｒ,Ｋ））を示している。この図には、ＲＫ＝Φ＝１００Ｌの固定長ファイバのすべての切片について得られた解の質も示している。
【０１８９】
簡単な実験的技法を用いて、最適なファイバ切片｛ＲΦ,ＫΦ｝を探索することができる。図１２を用いてこの探索手順を示す。横軸および縦軸はそれぞれ、ＲおよびＫの値を示す。バーは、実物証明書のインスタンスを偽造する予想対数コストlog１０（ζｆ（Ａ２,ＲＫ））を示す。このコストは、ＲおよびＫに関して、かつ１組の固定パラメータであるΛ＝512、ζ＝0.9、ε１＝8、およびν＝0.8に対して与えられる。図１２のグラフは、実験的に計算したものである。５００個の無作為に生成した実物証明書（521,Ｒ,Ｋ）のインスタンスに、Ｒ＝｛0.05Ｌ,0.10Ｌ,．．．,0.45Ｌ｝およびＫ＝｛80,96,．．．,192,256,384,512,768,1024｝をそれぞれ組み合わせてＡ２を適用する。実験結果を内挿することによって、この｛Ｒ,Ｋ｝空間の残りの部分内の各点ごとに予想される圧縮性能を求めた。図１２から、ＫΦ≒900およびＲΦ≒0.1Ｌの近傍で最適なファイバ切片を見つけることができる。この結果は、上記で選択した設計環境では、十字の形の実物証明書が最適な任意選択肢であることを示している。ファイバ切片を注意深く選択すれば、ＲＫ＝Φ上で無作為に選択した点に関する偽造コストが１桁大きくなったことに留意されたい。この実施例で用いた実験原理は、異なる実物証明書環境および製造上の制約に対しても、ほぼ最適なパラメータ組の探索に適用することができる。
【０１９０】
図１３に、上記で説明したシステムおよび方法を、完全にまたは部分的に実施し得る計算装置の例１３００を示す。計算装置１３００は、計算システムの単なる一例であり、本発明の利用法または機能の範囲に関していかなる制限も示唆するものではない。
【０１９１】
計算装置１３００は、他の多くの汎用または特殊用途の計算システムの環境または構成で実施し得る。使用に適した周知の計算システム、環境、および／または構成の例には、パーソナルコンピュータ、サーバコンピュータ、シンクライアント（ｔｈｉｎ  ｃｌｉｅｎｔ）、シッククライアント（ｔｈｉｃｋ  ｃｌｉｅｎｔ）、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス（ｓｅｔ  ｔｏｐ  ｂｏｘ）、プログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、大型コンピュータ、ゲーム用コンソール、上記システムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれるが、これらに限定されるものではない。
【０１９２】
計算装置１３００のコンポーネントは、プロセッサ１３０２（例えば、マイクロプロセッサ、コントローラなどのいずれか）、システムメモリ１３０４、入力装置１３０６、出力装置１３０８、およびネットワーク装置１３１０を含み得るが、これらに限定されるものではない。
【０１９３】
一般に、計算装置１３００は、様々なコンピュータ読取り可能媒体を含む。このような媒体は、計算装置１３００がアクセス可能な任意の利用可能な媒体とすることができ、揮発性および不揮発性の媒体、着脱可能および固定式の媒体を含む。システムメモリ１３０４は、ＲＡＭ（ランダムアクセスメモリ）などの揮発性メモリ、および／またはＲＯＭ（読み出し専用メモリ）などの不揮発性メモリの形態のコンピュータ読取り可能媒体を含む。起動時などに計算装置１３００内の要素間で情報を転送する助けとなる基本ルーチンを含むＢＩＯＳ（基本入出力システム）は、システムメモリ１３０４中に格納される。一般に、システムメモリ１３０４は、プロセッサ１３０２が即座にアクセス可能な、かつ／またはプロセッサ１３０２が現在操作中のデータおよび／またはプログラムモジュールを含む。
【０１９４】
システムメモリ１３０４は、着脱可能／固定式で揮発性／不揮発性の他のコンピュータ記憶媒体も含み得る。例として、固定式不揮発性の磁気媒体に対して読書きを行うハードディスクドライブ、着脱可能な不揮発性のディスク（例えば、「フロッピー（登録商標）ディスク）に対して読書きを行う磁気ディスクドライブ、ＣＤ−ＲＯＭ、ＤＶＤその他の任意のタイプの光学式媒体など、着脱可能な不揮発性の光ディスクに対して読出しおよび／または書込みを行う光ディスクドライブを含めることができる。
【０１９５】
ディスクドライブおよびそれらに関連するコンピュータ可読媒体により、計算装置１３００用のコンピュータにより読取り可能な命令、データ構造、プログラムモジュールその他のデータの不揮発性記憶装置が得られる。磁気カセットその他の磁気記憶装置、フラッシュメモリカード、ＣＤ−ＲＯＭ、ＤＶＤ（デジタル多用途ディスク）その他の光記憶装置、ＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読出し専用メモリ）、ＥＥＰＲＯＭ（電気的に消去可能なプログラマブル読出し専用メモリ）など、計算装置１３００がアクセス可能なデータを記憶し得る他のタイプのコンピュータ可読媒体を利用して、計算装置の例１３００を実施することもできることを理解されたい。例として、オペレーティングシステム１３２０、アプリケーションプログラム１３２８、およびデータ１３３２を含めて、システムメモリ１３０４中に任意の数のプログラムモジュールを格納し得る。
【０１９６】
計算装置１３００は、通信媒体として識別される様々なコンピュータ可読媒体を含み得る。一般に、通信媒体は、搬送波その他の搬送メカニズムなどの変調データ信号内のコンピュータにより読取り可能な命令、データ構造、プログラムモジュールその他のデータを実施するものであり、任意の情報送達媒体を含む。「変調データ信号」という用語は、信号の中に情報を符号化するように、その特性の１つまたは複数が設定または変更された信号を指す。例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体、および音波、ＲＦ、赤外線その他の無線媒体などの無線媒体を含むが、これらに限定されるものではない。上記のいずれかの組合せも、コンピュータ読取り可能媒体の範囲に含まれる。
【０１９７】
使用者は、キーボードおよびポインティングデバイス（例えば「マウス」）などの入力装置１３０６を介して計算装置１３００にコマンドおよび情報を入力することができる。他の入力デバイス１３０６は、マイクロホン、ジョイスティック、ゲームパッド、コントローラ、衛星パラボラアンテナ、シリアルポート、スキャナ、タッチスクリーン、タッチパッド、キーパッドなどを含み得る。出力装置１３０８は、ＣＲＴモニタ、ＬＣＤスクリーン、スピーカ、プリンタなどを含み得る。
【０１９８】
計算装置１３００は、ＬＡＮ（ローカルエリアネットワーク）、ＷＡＮ（ワイドエリアネットワーク）などのコンピュータネットワークに接続するためのネットワーク装置１３１０を含み得る。
【０１９９】
構造上の特徴および／または方法ステップに固有の表現で本発明を説明してきたが、添付の特許請求の範囲で定義する本発明は、上記で説明した特定の特徴またはステップに必ずしも限定されないことを理解されたい。そうではなくて、これらの特定の特徴およびステップは、特許請求する本発明を実施する好ましい形態として開示されている。
【図面の簡単な説明】
【０２００】
【図１】実物証明書などのラベルの一部として使用する認証物体の例を示す図である。
【図２】実物証明書システムの例および実物証明書を発行し検証するためにこのシステムが採用する手順の例を示す概略図である。
【図３Ａ】実物証明書に付随する認証物体の無秩序に分布したフィーチャを取り込む走査システムの例を示す概略図である。
【図３Ｂ】図３Ａに示す認証物体を示す上面図である。
【図４】実物証明書を生成するのに用い得る工程の例を示す流れ図である。
【図５】認証物体の無秩序に分布した属性を表すデータを圧縮するのに用い得る工程の例を示す流れ図である。
【図６】認証物体の例の中の４個の異なる領域に対応する区域を示す図である。
【図７】認証物体の例の上の１９個の異なる領域を示す図である。
【図８】正方形認証物体に用いる確率密度関数の例を示すグラフである。
【図９】認証物体の区域を示す図である。
【図１０】算術符号器が文字列「ａｂａ」を符号化する方法の例を示す図である。
【図１１】認証物体のインスタンスの例をノードとともに示す図である。
【図１２】コスト効果が最適化されるように設計された実物証明書を示すグラフである。
【図１３】本明細書で説明したシステムおよび方法を完全にまたは部分的に実施し得る計算装置の例を示す図である。
【符号の説明】
【０２０１】
１００、３１０  認証物体
１１０、３２６  ファイバ
１３１、１３２、１３３  端点
２００  実物認証システム
２１０  実物証明書
２１３  バーコード
２５９  判定ブロック
３００  走査システム
３２２  光センサ
３２４  光源
１３００  計算装置
【図１】
0004718843.tif 000056
【図２】
0004718843.tif 000057
【図３Ａ】
0004718843.tif 000058
【図３Ｂ】
0004718843.tif 000059
【図４】
0004718843.tif 000060
【図５】
0004718843.tif 000061
【図６】
0004718843.tif 000062
【図７】
0004718843.tif 000063
【図８】
0004718843.tif 000064
【図９】
0004718843.tif 000065
【図１０】
0004718843.tif 000066
【図１１】
0004718843.tif 000067
【図１２】
0004718843.tif 000068
【図１３】
0004718843.tif 000069