(57)【要約】【課題】複数の利用者が動作に関与するコンピュータシステムの匿名性検査を比較的簡単な処理で行う。【解決手段】利用者情報、利用者が行う行為情報、上記コンピュータシステムの全ての挙動Ｓ、上記挙動Ｓの外部から観測される見え方を定義する写像Ｖを入力し、一方の利用者ｉが一方の行為ａを、他方の利用者ｊが他方の行為ｂを行う全ての動作Ｂを求め（３４）、Ｂにおける全ての状態を定義域とする写像ｇｉｊでＢと写像した動作ｇｉｊ（Ｂ）を求め（４０）、Ｂ中の各トレースと、当該トレースに対応するｇｉｊ（Ｂ）中の各トレースとが役割交換しているか否かを判定し（４４）、Ｂ及びｇｉｊ（Ｂ）を外部から観測したそれぞれの可能なトレースの集合が一致するか否かを判定し（４５）、上記２つの各判定が共に真であれば、匿名性有りを出力し、少なくとも一方の判定が真でなければ、ｇｉｊを更新入力させて、同様の処理を繰り返す。【選択図】図３
2007148624.tif 000002
【特許請求の範囲】
【請求項１】
複数の利用者の行為が動作に関与するコンピュータシステムにおける匿名性検査方法において、
上記コンピュータシステムの利用者ｉ、ｊを表す利用者情報ＩＤｉ、ＩＤｊ、利用者が行う行為ａ、ｂを表す行為情報ＩＤａ、ＩＤｂ、上記コンピュータシステムの挙動の全てを表すコンピュータシステム挙動Ｓ、利用者の行為に対する上記コンピュータシステム挙動Ｓの外部から観測される見え方を定義する写像Ｖが入力され、パラメータ記憶部に記憶するパラメータ記憶過程と、
一方の利用者ｉが一方の行為ａを、他方の利用者ｊが他方の行為ｂを、行った場合に生じ得る全ての上記コンピュータ挙動Ｓを含む動作Ｂを動作Ｂ生成部で求め、その動作Ｂを動作Ｂ記憶部に記憶する動作Ｂ生成過程と、
上記動作Ｂにおける全ての状態を定義域とする写像ｇｉｊが入力され、写像記憶部に記憶する写像記憶過程と、
上記動作Ｂの全ての状態を写像ｇｉｊで写像した動作ｇｉｊ（Ｂ）を動作ｇｉｊ（Ｂ）生成部で求め、その動作ｇｉｊ（Ｂ）を動作ｇｉｊ（Ｂ）記憶部に記憶する動作ｇｉｊ（Ｂ）生成過程と、
上記動作Ｂ中の各トレースと、当該トレースに対応する動作ｇｉｊ（Ｂ）中の各トレースが役割交換しているか否かを役割交換判定部で判定する役割交換判定過程と、
上記動作Ｂ及び上記動作ｇｉｊ（Ｂ）を外部から観測したそれぞれの可能なトレースの集合が一致するか否かをトレース等価性判定部で判定するトレース等価性判定過程と、
上記役割交換判定過程及び上記トレース等価性判定過程の各判定が共に真である否かを判定し、共に真であれば、匿名性判定結果成功と匿名性判定部で判定する匿名性判定過程と、
上記匿名性判定過程の判定結果を出力する判定結果出力過程と、
を有することを特徴とするトレース等価性を基準とした役割交換可能性を用いた匿名性検査方法。
【請求項２】
請求項１に記載の匿名性検査方法において、
上記役割交換判定過程及び／又は、上記トレース等価性判定過程の各判定が、偽であれば上記写像ｇｉｊを更新する指示を更新指示生成部により生成して出力し、その後、上記写像記憶過程に戻る写像更新過程を、
含むことを特徴とする匿名性検査方法。
【請求項３】
請求項２に記載の匿名性検査方法において、
上記匿名性判定過程は、あらかじめ定められた時間が経過しても、上記各判定が共に真であると判定しなければ、強制的に上記判定結果出力過程を実行し、匿名性判定結果不成功を出力する過程である、
ことを特徴とする匿名性検査方法。
【請求項４】
請求項１〜３何れかに記載の匿名性検査方法において、
上記トレース等価性判定過程は、上記動作Ｂ中の各トレースの外部からの観測結果と、上記トレースに対応する動作ｇｉｊ（Ｂ）中のトレースの外部からの観測結果が全て同じであるか否かを判定し、全て同じであれば、上記トレース等価性判定部で、真と判定する過程である、
ことを特徴とする匿名性検査方法。
【請求項５】
請求項１〜４に何れかに記載の匿名性検査方法において、
上記役割交換判定過程は、上記動作Ｂの中の上記利用者ｉが上記行為ａを行い、上記利用者ｊが上記行為ｂを行う任意のトレースに対して、上記動作ｇｉｊ（Ｂ）の中の当該トレースに対応するトレースで上記利用者ｊが上記行為ａを行い、上記利用者ｉが上記行為ｂを行うか否かを判定し、この判定が真であれば役割交換していると判定する過程である、
ことを特徴とする匿名性検査方法。
【請求項６】
複数の利用者の行為が動作に関与するコンピュータシステムにおける匿名性検査装置において、
パラメータなどが入力される入力部と、
上記入力部に接続され、その入力部に入力された上記コンピュータシステムの利用者ｉ、ｊを表す利用者情報ＩＤｉ、ＩＤｊ、利用者が行う行為ａ、ｂを表す行為情報ＩＤａ、ＩＤｂ、上記コンピュータシステムの挙動の全てを表すコンピュータシステム挙動Ｓ、利用者の行為に対する上記コンピュータシステム挙動Ｓの外部から観測される見え方との関係を定義する写像Ｖが記憶されるパラメータ記憶部と、
上記パラメータ記憶部に接続され、上記利用者情報ＩＤｉ、ＩＤｊ、上記行為情報ＩＤａ、ＩＤｂ、上記コンピュータシステム挙動Ｓが入力され、一方の利用者ｉが一方の行為ａを、他方の利用者ｊが他方の行為ｂを、行った場合に生じ得る全ての上記コンピュータ挙動Ｓを含む動作Ｂを生成し、その動作Ｂを動作Ｂ記憶部に記憶する動作Ｂ入力部と、
上記入力部に接続され、その入力部より入力された、上記動作Ｂにおける全ての状態を定義域とする写像ｇｉｊを記憶する写像記憶部と、
上記動作Ｂ記憶部と上記写像記憶部とに接続され、上記動作Ｂと上記写像ｇｉｊが入力され、上記動作Ｂの全ての状態を上記写像ｇｉｊで写像して動作ｇｉｊ（Ｂ）を生成し、その動作ｇｉｊ（Ｂ）を動作ｇｉｊ（Ｂ）記憶部に、記憶する動作ｇｉｊ（Ｂ）生成部と、
上記動作Ｂ記憶部と、上記動作ｇｉｊ（Ｂ）記憶部とに接続され、上記動作Ｂと上記動作ｇｉｊ（Ｂ）が入力され、上記動作Ｂ中の各トレースと、当該トレースに対応する動作ｇｉｊ（Ｂ）中の各トレースと、が役割交換しているか否かの判定を出力する役割交換判定部と、
上記パラメータ記憶部と、上記動作Ｂ記憶部と、上記動作ｇｉｊ（Ｂ）記憶部とに接続され、上記写像Ｖと上記動作Ｂと上記動作ｇｉｊ（Ｂ）が入力され、動作Ｖ（Ｂ）と動作Ｖ（ｇｉｊ（Ｂ））のそれぞれの可能なトレースの集合が一致する否かの判定を出力するトレース等価性判定部と、
上記役割交換判定部と上記トレース等価性判定部とに接続され、上記役割交換判定部よりの判定結果及び上記トレース等価性判定部よりの判定結果とが入力され、共に真であるか否かを判定する匿名性判定部と、
上記匿名性判定部に接続され、上記判定結果は共に真であれば、匿名性判定成功と出力する出力部と、
を備えることを特徴とするトレース等価性を基準とした役割交換可能性を用いた匿名性検査装置。
【請求項７】
請求項６記載の匿名性検査装置において、
上記匿名性判定部に接続され、偽の判定結果が入力され、上記写像ｇｉｊの更新指示を出力する更新指示出力部を上記出力部は備えることを特徴とする匿名性検査装置。
【請求項８】
請求項７記載の匿名性検査装置において、
匿名性検査開始からあらかじめ決められた時間が経過すると、タイムアウト信号を出力するタイマを備え、
上記匿名性判定部は上記タイマに接続され、上記タイムアウト信号が入力されると、匿名性判定結果不成功を上記出力部に出力するものである、
ことを特徴とする匿名性検査装置。
【請求項９】
請求項１〜５何れかに記載の匿名性検査方法の各過程をコンピュータに実行させるための匿名性検査プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の利用者が動作に関与するコンピュータシステムにおいて、このコンピュータシステムが、適切に、匿名性を持つか否かを判定する匿名性検査方法、その装置、そのプログラムに関する。
【背景技術】
【０００２】
複数のユーザが動作に関与するようなコンピュータシステムにおいて、利用者ｉが行為ａを行った時、ａを行った利用者ｉを高い確率で推測することができないならば当該システムはｉの行うａに関して匿名性を持つといい、システムＳが匿名性を持つか否かを判定することを、システムの匿名性検査という。
複数のユーザが動作に関与するコンピュータシステムの匿名性検査を行う技術として、役割交換可能性が成立しているか否かにより、検査することが知られている。（非特許文献１及び非特許文献２参照。）この従来技術においては、役割交換前後のシステムの動作Ｂと動作Ｂ’との弁別不能性の基準として、ひげ付き双模倣性（ｂａｒｂｅｄ−ｂｉｓｉｍｉｌａｒｉｔｙ）が用いられている。
【０００３】
ここで、役割交換可能性を説明する。利用者ｉ，ｊが関与するシステムにおいて、利用者ｉが行為ａを行い利用者ｊが行為ｂを行う動作Ｂと、その代わりに、利用者ｉがｂを行い、利用者ｊがａを行う動作Ｂ’を考える（以後、システムの動作とは、関与する利用者も含めた全体の動作を意味する）。このような動作Ｂと動作Ｂ’が弁別不能であるとき、システムはｉ、ｊ、ａ、ｂに関して役割交換可能であるという。
次に、ひげ付き双模倣性を説明する。システムの２つの動作Ｂと動作Ｂ’の等価性を調べる時、動作の全ステップにおいて実際にそのステップで行う行為だけでなく、他にどのような行為が可能もしくは不可能であるかということまで含めて一致するかどうか調べることを考える。そのようにしても、動作Ｂと動作Ｂ’で違いが見出せないならば、動作Ｂと動作Ｂ’はひげ付き双模倣であるという。
【０００４】
ｉ、ｊ、ａ、ｂに関する役割交換可能性が成り立つ時、ある前提の元にｉの行うａに関してシステムは匿名性を持つことが分かる。ある前提として様々なものが考えられるが、例えば「同じ行為を２人以上の利用者が行わない」といったものである。このような前提の下で動作Ｂから利用者ｉが行為ａを行ったと推測したと仮定すると、動作Ｂと区別できない動作Ｂ’からも利用者ｉが行為ａを行ったと推測するはずであるが、利用者ｊが行為ａを行っているのでこの前提から、動作Ｂ’で利用者ｉが行為ａを行うことはあり得ず、推測は誤りとなる。以上の方法によって、従来技術を用いて匿名性検査が可能である。
【０００５】
システムに対し、役割交換の前後の動作Ｂと動作Ｂ’の具体例を挙げて以下に説明する。２名の利用者ｉ、ｊがインターネットショピングサイトを利用する状況を考える。ショッピングサイトは１万円の商品ａと２万円の商品ｂを売っているとする。利用者ｉ、ｊは所持金に応じて、１万円所持していればａを、２万円所持していればｂを購入するとする。ただし利用者ｉはひやかしのみで、ショッピングサイトに入店することがあり、かつ、ひやかしかどうかは入店する前に決断するとする。一方ｊは入店したら必ず商品を購入するとする。
【０００６】
利用者ｉが１万円、利用者ｊが２万円所持している場合の（利用者ｉ、ｊを含めた全体の）システムの動作Ｂを図１Ａに示す。ｔ１、．．．、ｔ８はシステムの状態を表す。ｉｎは利用者ｉとｊがショッピングサイトに入店するという行為（簡単化のため、ここでは利用者ｉとｊが同時に入店する状況を考える）、ｘ．ｙはｘが商品ｙを購入するという行為、例えばｉ．ａは利用者ｉが商品ａを購入するという行為を表す。状態ｔ１、ｔ２、ｔ３、ｔ４を経る実行は、利用者ｉ、ｊが入店し、状態ｔ２で、利用者ｉがａを購入し、その結果の状態ｔ３で利用者ｊがｂを購入した結果の状態ｔ４となって実行が終了するということを表す。状態ｔ１、ｔ２、ｔ５、ｔ６を経る実行は利用者ｉ、ｊが入店し、状態ｔ２で利用者ｊがｂを購入し、その結果の状態ｔ５で、利用者ｉがａを購入した状態ｔ６で実行が終了するということを表す。状態ｔ１、ｔ７、ｔ８を経る実行は、利用者ｉ、ｊが入店し、状態ｔ７で、利用者ｊがｂを購入し、その結果の状態ｔ８で実行が終了し、つまり、利用者ｉはひやかしのみで入店したことを表す。
【０００７】
次に利用者ｉとｊの役割を交換して、利用者ｉが２万円、利用者ｊが１万円持っている場合のシステムの動作Ｂ’を図１Ｂに示す。この図１Ｂの表示は図１Ａと同時に、状態ｕ１、ｕ２、ｕ３、ｕ４を経る実行は、利用者ｉ、ｊが入店し、利用者ｊがａを購入し、利用者ｉがｂを購入するということを表し、状態ｕ１、ｕ２、ｕ５、ｕ６を経る実行は、利用者ｉ、ｊが入店し、利用者ｉがｂを購入し、利用者ｊがａを購入するということを表し、状態ｕ１、ｕ７、ｕ８を経る実行は、利用者ｉ、ｊが入店し、利用者ｊがａを購入し、利用者ｉはひやかしのみで入店したことを表す。
【０００８】
判定のための仮定として、ショッピングサイトの各ステップは匿名通信路を用いて行われるため、盗聴者（外部からの観測者）からは、ｘ．ｙという行為の行為者すなわちｘを直接観測することはできないとする。２つの動作Ｂ、Ｂ’を外部から見た動作Ｖ（Ｂ）を図２Ａに、動作Ｖ（Ｂ’）を図２Ｂに示す。図２Ａ、図２Ｂはそれぞれ、各状態と状態間の行為のみが表され、図１Ａと図１Ｂから行為を行った利用者ｉ、ｊが省略されたもの、つまり、行為の系列のみとなる。前記従来の技術では、システムの交換役割による動作Ｂと動作Ｂ’の行為の系列Ｖ（Ｂ）とＶ（Ｂ’）に対して、これらの等価性をひげ付き双模倣性を弁別不能性の基準として、役割交換可能性を用いて、匿名性検査を行っていた。
【０００９】
一方ひげ付き双模倣性よりも緩やかな弁別不能性の基準として、トレース等価性がある。トレース等価性は、システムの動作を単なる行為の系列としてとらえる等価性であり、ひげ付き双模倣性のようにステップごとの各行為の可能／不可能のチェックは行わず、手間がかからないという利点がある。しかしこのため、あるシステムに対して役割交換可能性による匿名性検査を行為の系列を用いて、行う時、ひげ付き双模倣性を基準とすると匿名性がないと判定されるが、判断基準が緩やかなため、トレース等価性を基準としたときには匿名性があると誤った判定される場合がある。つまり、トレース等価性を基準として、役割交換可能性を用いて、匿名性検査をすることは、全く考えられなかった。
【非特許文献１】Ｍａｒｔｉｎ  Ａｂａｄｉ、Ｃｅｄｒｉｃ  Ｆｏｕｒｎｅｔ“Ｐｒｉｖａｔｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ”  Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ３２２（２００４）４２７−４７６
【非特許文献２】Ｓｔｅｖｅ  Ｋｒｅｍｅｒ、Ｍａｒｋ  Ｒｙａｎ  “Ａｎａｌｙｓｉｓ  ｏｆ  ａｎ  Ｅｌｅｃｔｒｏｎｉｃ  Ｖｏｔｉｎｇ  Ｐｒｏｔｏｃｏｌ  ｉｎ  ｔｈｅ  Ａｐｐｌｉｅｄ  Ｐｉ  Ｃａｌｃｕｌｕｓ”
【発明の開示】
【発明が解決しようとする課題】
【００１０】
前記従来の技術ではこの方法では、正しい検査を行うことができないことを見出した。このことを図２Ａ、図２Ｂを参照して、行為ｉｎの後、ｂを行う場合を考え、具体的に説明する。外部から見た動作Ｖ（Ｂ）にはｔ１、ｔ７、ｔ８を経る実行、すなわち行為ｉｎ、行為ｂを行ったあと可能な行為が全くない状態ｔ８が存在するが、動作Ｖ（Ｂ’）では、状態ｕ１、ｕ２を経て、行為ｉｎ、行為ｂを行ったあとは状態ｕ５となるが、この状態ｕ５のあとは、行為ａを行うことが可能であり、可能な行為が全くない状態が存在せず、この状態ｕ５は、動作Ｖ（Ｂ）の状態ｔ８とは違う。つまり、２つの観測された動作Ｖ（Ｂ）と動作Ｖ（Ｂ’）は互いにひげ付き双模倣性ではない。従って、ひげ付双模倣性を弁別不能性の基準として観測された動作Ｖ（Ｂ）、動作Ｖ（Ｂ’）について等価性を判断した場合、このシステムでは、利用者ｉとｊの役割交換性が成立せず、よってコンピュータシステムの挙動Ｓは利用者ｉの行う行為ａに関して匿名性を持たないと判定されてしまう。
【００１１】
しかし、ある状態において購入するという行為が不可能であるのか、あるいは何らかの事情で遅れているだけなのかが上記盗聴者は現実的に、区別がつかない場合が多い。そのような場合、上記盗聴者は、動作Ｖ（Ｂ）と動作Ｖ（Ｂ’）を区別することができなくなり、ｉとｊとの役割交換が可能であるといえ、匿名性を持つことになる。すなわち、ひげ付き双模倣性を弁別不能性の基準とすると、誤判断をする場合がある。
以上のことから発明が解決しようとする課題として、（１）現実のシステムにおいては、ある行為が不可能なのか、あるいは単に遅れているだけなのかを上記盗聴者は区別できないことが多いので、上記のように誤った判定をしてしまうおそれがある、（２）ひげ付き双模倣性は各ステップごとの各行為の可能／不可能のチェックを行うため、手間がかかる、という２点が存在する。
【００１２】
この発明の目的は、ひげ付き双模倣性を弁別不能性の基準とした匿名性検査よりも、簡単な処理で、正しい検査を行うことができる匿名性検査方法、その装置、そのプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
この発明によれば、等価性の基準として、トレース等価性を用い、システムの役割交換可能性を判定する。
つまり、上記コンピュータシステムの利用者ｉ、ｊを表す利用者情報ＩＤｉ、ＩＤｊ、利用者が行う行為ａ、ｂを表す行為情報ＩＤａ、ＩＤｂ、上記コンピュータシステムの挙動の全てを表すこのコンピュータシステム挙動Ｓ、利用者の行為に対する上記コンピュータシステム挙動Ｓの外部から観測される見え方との関係を定義する写像Ｖが入力され、パラメータ記憶部で記憶し、一方の利用者ｉが一方の行為ａを、他方の利用者ｊが他方の行為ｂを、行った場合に生じ得る全ての上記コンピュータ挙動Ｓを含む動作Ｂを動作Ｂ生成部で求め、当該動作Ｂを動作Ｂ記憶部で記憶し、上記動作Ｂにおける全ての状態を定義域とする写像ｇｉｊが入力され、写像記憶部で記憶し、上記動作Ｂの全ての状態を写像ｇｉｊで写像した動作ｇｉｊ（Ｂ）を動作ｇｉｊ（Ｂ）生成部で求め、動作ｇｉｊ（Ｂ）記憶部で記憶し、上記動作Ｂ中の各トレースと、当該トレースに対応する動作ｇｉｊ（Ｂ）中の各トレースと、が役割交換しているか否かを役割交換判定部で判定し、上記動作Ｂ及び上記動作ｇｉｊ（Ｂ）を外部から観測したそれぞれの可能なトレースの集合が一致するか否かをトレース等価性判定部で判定し、上記役割交換判定過程及び上記トレース等価性判定過程が共に真である否かを判定し、共に真であれば、匿名性判定結果成功と匿名性判定部で判定する。
【発明の効果】
【００１４】
以上の構成によれば、動作Ｂ中の各トレースと、当該トレースに対応する動作ｇｉｊ（Ｂ）中の各トレースとが役割交換しているかを判定し、また、動作Ｂ及び動作ｇｉｊ（Ｂ）を外部から観測したそれぞれの可能なトレースの集合が一致するか否かを判定し、両判定が共に真であれば、匿名性判定結果が成功したと判定している。外部から観測した動作については、トレース等価性を弁別不能性の判定基準としているため、処理が、簡単であり、しかも、両判定が共に真であれば、匿名性があると判定しているため、正しく検査を行うことができる。
【発明を実施するための最良の形態】
【００１５】
図３にこの発明装置の実施形態の機能構成例を示す。複数の利用者が動作に関与するコンピュータシステムのすべての挙動をＳとし、このコンピュータシステムを利用する任意の２人の利用者ｉ、ｊの利用者情報をＩＤｉ、ＩＤｊとし、利用者が行う行為ａ、ｂの行為情報をＩＤａ、ＩＤｂとし、このコンピュータシステムを外部から観測した時の見え方を定義するための写像をＶとする。
前記インターネットショッピングを行うコンピュータシステムの匿名性検査を適用した場合は、写像Ｖは以下の通りである。
【００１６】
Ｖ（ｉｎ）＝ｉｎ
Ｖ（ｘ．ｙ）＝ｙ
以下において、具体例を示す場合は、前記インターネットショッピングを行うコンピュータシステムの匿名性検査に適用した例である。利用者情報ＩＤｉ、ＩＤｊ、行為情報ＩＤａ、ＩＤｂ、コンピュータシステムの挙動Ｓ、写像Ｖが例えばキーボードなどの入力部３０から入力され、パラメータ記憶部３２に記憶される。これらのうち、利用者情報ＩＤｉ、ＩＤｊ、行為情報ＩＤａ、ＩＤｂ、コンピュータシステムの挙動Ｓが動作Ｂ生成部３４に入力され、動作Ｂ生成部３４により、コンピュータシステムの動作Ｂ、例えば、図１Ａに示した動作Ｂが生成され、動作Ｂ記憶部３６に記憶される。
動作Ｂに現れる状態の全体を定義域とする状態から状態への写像ｇｉｊが例えば、入力部３０より入力され、写像記憶部３８に記憶される。上記動作Ｂ及び上記写像ｇｉｊが動作ｇｉｊ（Ｂ）生成部４０に入力され、動作ｇｉｊ（Ｂ）生成部４０により、動作ｇｉｊ（Ｂ）が生成され、動作ｇｉｊ（Ｂ）記憶部４２に記憶される。上記動作Ｂ及び上記動作ｇｉｊ（Ｂ）が役割交換判定部４４に入力され、当該２つの動作が役割交換されているか否かが判定される。つまり、役割交換判定は以下の２つを確認すればよい。
（１）上記動作Ｂに現れる全ての状態ｔ、その状態から可能な行為ｉ．ａ、およびその行為の結果ｔ’について、ｇｉｊ（ｔ）において、行為ｊ．ａが可能であり、その行為の結果ｇｉｊ（ｔ’）となること。
（２）上記動作Ｂに現れる全ての状態ｔ、その状態から可能な行為ｊ．ｂ、およびその行為の結果ｔ’について、ｇｉｊ（ｔ）において、行為ｉ．ｂが可能であり、その行為の結果ｇｉｊ（ｔ’）となること。
次に、写像Ｖ、動作Ｂ、動作ｇｉｊ（Ｂ）がトレース等価性判定部４５に入力され、これらを外部から観測したそれぞれのトレースの集合が一致するか否かが判定される。動作Ｂを外部から観測したものを動作Ｖ（Ｂ）とし、動作ｇｉｊ（Ｂ）を外部から観測したものを動作Ｖ（ｇｉｊ（Ｂ））とすると、トレース等価性判定部４５は具体的に例えば、上記写像Ｖ及び上記動作Ｂが、動作Ｖ（Ｂ）トレース生成部４６に入力され、動作Ｖ（Ｂ）トレース生成部４６により、動作Ｖ（Ｂ）の可能なトレースが生成され、動作Ｖ（Ｂ）トレース記憶部４８に記憶される。一方、上記写像Ｖ及び上記動作ｇｉｊ（Ｂ）が、動作Ｖ（ｇｉｊ（Ｂ））トレース生成部５０に入力され、動作Ｖ（ｇｉｊ（Ｂ））トレース生成部５０により、動作Ｖ（ｇｉｊ（Ｂ））の可能なトレースが生成され、動作ｇｉｊ（Ｂ）トレース記憶部５２に記憶される。上記動作Ｖ（Ｂ）トレース記憶部４８中の上記動作Ｖ（Ｂ）の可能なトレースの集合と、上記動作Ｖ（ｇｉｊ（Ｂ））トレース記憶部５２中の上記動作Ｖ（ｇｉｊ（Ｂ））の可能なトレースの集合とが一致するか否かを、等価性判定部５４により判定する。等価性判定部５４は要は、上記動作Ｂ中の各トレースの外部からの観測結果と、上記トレースに対応する動作ｇｉｊ（Ｂ）中のトレースの外部からの観測結果が、全て同じであるか否かを判定し、全て同じであれば、上記トレース等価性判定部４５で、真と判定する。更に、具体的に述べると、上記動作Ｂに現れる全ての状態ｔ、その状態から可能な行為ｚ、及びその行為の結果である状態ｔ’について、状態ｇｉｊ（ｔ）から可能な行為ｚ’で、行為ｚ及び行為ｚ’を外部から観測した見え方Ｖ（ｚ）及びＶ（ｚ’）が共に等しくなり、行為ｚ’の結果の状態がｇｉｊ（ｔ’）となることで、上記トレース等価性判定部４５で真と判定する。
【００１７】
上記役割交換判定部４４よりの判定結果及び上記等価性判定部５４よりの判定結果が共に真であるか否かを匿名性判定部５６により判定し、判定結果を出力部５８に入力する。上記役割交換判定部４４よりの判定結果及び上記等価性判定部５４よりの判定結果が共に真であれば、成功出力部６０より匿名性判定結果成功を出力する。つまり、そのことが例えば表示される。
上記役割交換判定部４４よりの判定結果及び上記等価性判定部５４よりの判定結果が少なくとも一方が真でない場合は、そのことを示す信号が更新指示生成部６２に入力され、上記写像ｇｉｊを更新する指示が生成され出力部５８中の、更新指示出力部６６により、上記写像ｇｉｊの更新指示が出力される。
【００１８】
また匿名性検査開始からあらかじめ定めていた時間が経過すると、タイマ６８からタイムアウト信号が匿名性判定部５６に入力され、上記匿名性判定部５６は出力部５８の不成功出力部６４から匿名性判定不成功を出力する。
上記動作Ｂ記憶部３６、上記記憶部３８、上記動作ｇｉｊ（Ｂ）記憶部４２、上記動作Ｂ外観トレース記憶部４８、上記動作Ｖ（ｇｉｊ（Ｂ））外観トレース記憶部５２はこの実施例では分けて記載しているが、これら記憶部の全部又は複数を大容量の記憶装置に記憶領域を分別して記憶するようにしても良い。
【００１９】
この装置の処理の流れ、つまりこの発明方法の実施形態を図４に示すフローチャートにより説明する。まず入力部３０に、上記コンピュータシステムの挙動Ｓ、上記利用者情報ＩＤｉ、ＩＤｊ、上記行為情報ＩＤａ、ＩＤｂ、写像Ｖが入力されるか否かを判定し（Ｓ４０２）、もし入力されると、入力されたパラメータを、パラメータ記憶部３２に記憶する（Ｓ４０４）。これら全てのパラメータが入力されると、一方の利用者ｉが一方の行為ａを行い、他方の利用者ｊが他方の行為ｂを行う場合のコンピュータシステムの動作Ｂを動作Ｂ生成部３４が生成し、動作Ｂ記憶部３６に、記憶する（Ｓ４０６）。次に、写像ｇｉｊが入力される（Ｓ４２８）か否かを判定し（Ｓ４０８）、もし写像ｇｉｊが入力されると、写像記憶部３８に記憶する（Ｓ４１０）。
【００２０】
上記動作Ｂ及び上記写像ｇｉｊから動作ｇｉｊ（Ｂ）を生成し、動作ｇｉｊ（Ｂ）記憶部４２に記憶する（Ｓ４１２）。上記動作Ｂと上記動作ｇｉｊ（Ｂ）とが役割交換されているか否かを判定し（Ｓ４１４）、役割交換されていれば、動作Ｂと動作ｇｉｊ（Ｂ）の外観動作、動作Ｖ（Ｂ）と動作Ｖ（ｇｉｊ（Ｂ））の各トレースを生成し（Ｓ４１６）、当該２つの各トレースの等価性が一致するか否かを判定する（Ｓ４１８）。もし、一致していれば、出力部５８により匿名性判定結果成功を出力する（Ｓ４２０）。
必要に応じて、ステップＳ４１４において、上記動作Ｂと上記動作ｇｉｊ（Ｂ）とが役割交換されていないと判定され、もしくは、ステップＳ４１８において、上記動作Ｖ（Ｂ）と上記動作Ｖ（ｇｉｊ（Ｂ））の各トレースの等価性が一致していないと判定され、検索開始からあらかじめ定めていた所定時間を経過していると（Ｓ４２２）、不成功出力部６４により判定結果不成功を出力する（Ｓ４２４）。またステップＳ４２２において、上記所定時間を経過していないと、更新指示出力部６６により上記写像ｇｉｊを更新する指示が生成出力され（Ｓ４２６）、上記写像ｇｉｊ入力待ちのステップ（Ｓ４２８）に戻る。なお、ステップＳ４１６の動作Ｖ（Ｂ）と動作Ｖ（ｇｉｊ（Ｂ））の各トレース生成処理とステップＳ４１８の等価性一致か否かの判定処理はトレース等価性ステップＳ４１５を構成している。
【００２１】
タイマ６８を省略し、ステップＳ４２２の処理をすることなく、役割交換判定、トレース等価性判定のいずれかでも真でなければステップＳ４２６の更新指示出力に移っても良い。更に、簡単な場合は、最初の２つの判定結果が真であれば、匿名性判定結果成功を出力するだけでもよい。
また一点鎖線で示すように、ステップＳ４１５のトレース等価性の判定を先にして、ステップＳ４１４の役割交換性の判定を後にする構成にしてもよい。
【００２２】
役割交換判定部４４の動作例
次に図３記載の役割交換判定部４４における具体的動作例を以下に説明する。ここで、動作Ｂは図１Ａに示したものとし、入力された写像ｇｉｊの一例として、動作Ｂと動作ｇｉｊ（Ｂ）の対応を図５に示す。
この図５においては動作Ｂの各状態から、動作ｇｉｊ（Ｂ）の各状態への写像は以下のようになる。
ｇｉｊ（ｔ１）＝ｕ１・・・（１）  ｇｉｊ（ｔ２）＝ｕ２・・・（２）
ｇｉｊ（ｔ３）＝ｕ３・・・（３）  ｇｉｊ（ｔ４）＝ｕ４・・・（４）
ｇｉｊ（ｔ５）＝ｕ５・・・（５）  ｇｉｊ（ｔ６）＝ｕ６・・・（６）
ｇｉｊ（ｔ７）＝ｕ２・・・（７）  ｇｉｊ（ｔ８）＝ｕ５・・・（８）  
また動作Ｂ記憶部３６に記憶された動作Ｂと動作ｇｉｊ（Ｂ）記憶部４２に記憶された動作ｇｉｊ（Ｂ）の各可能なトレースの記憶状態をそれぞれ図６Ａ、図６Ｂに示す。なお、図６Ａ、図６Ｂにおいて利用者情報ＩＤｉ、ＩＤｊ、行為情報ＩＤａ、ＩＤｂをそれぞれｉ、ｊ、ａ、ｂと簡略に示した。例えば、図６Ａａは状態ｔ１から行為ｉｎによりその行為の結果の状態ｔ２に移るトレースを示す。図６Ａｂは状態ｔ２から行為ｉ．ａによりその行為の結果の状態ｔ３に移るトレースと、行為ｊ．ｂによりその行為の結果の状態ｔ５に移るトレースを示す。図６Ａｃは状態ｔ３から行為ｊ．ｂによりその行為の結果の状態ｔ４に移るトレースを示す。図６Ａｄは状態ｔ４から可能な行為、その行為の結果が共に存在しないトレースを示す。
【００２３】
以下、図６Ａｅ〜図６Ａｉも同様な表示方法により各トレースの記憶状態を示す。図６Ｂも同様な表示方法であり、例えば、図６Ｂａは状態ｕ１から可能な行為ｉｎ、その行為の結果の状態ｕ２に移るトレースを示す。
次に、役割交換判定部４４の動作（図４中のステップＳ４１４の役割交換しているかの判定処理）の例を図７を参照して説明する。状態番号ｋを１に初期化し（Ｓ７００）、動作Ｂにおいて状態ｔｋ、それからの行為ｚ、その結果の状態ｔ’を動作Ｂ記憶部３６から取出し、また状態ｕｋ、それからの行為ｚ’、その結果の状態ｕ’を動作ｇｉｊ（Ｂ）記憶部４２から取出す（Ｓ７０２）。最初はｋ＝１であるから図６Ａａの状態ｔ１の行為ｚであるｉｎ、とその行為の結果の状態ｔ’である状態ｔ２とｔ７を取出し、動作ｇｉｊ（Ｂ）において、図６Ｂｂの状態ｕ１の行為ｚ’であるｉｎ、とその行為の結果の状態ｕ’である状態ｕ２を取出す（Ｓ７０２）。
【００２４】
次に、まず行為ｚ、ｚ’が取り出せたか否かを判定し（Ｓ７０３）、この場合は取り出せたから、行為ｚがｉｎである否かを判定し（Ｓ７０４）、ｋ＝１の場合、行為ｚがｉｎであると判定されるので、次にｚ’がｉｎであるか否かを判定する（Ｓ７０５）。行為ｚ’はｉｎであるので、次にｇｉｊ（ｔ’）がｕ’に等しいか否かを判定する（Ｓ７１０）。
ここで、式（２）よりｇｉｊ（ｔ２）＝ｕ２
式（７）よりｇｉｊ（ｔ７）＝ｕ２となり、ｔ２およびｔ７においても、ｇｉｊ（ｔ’）とｕ’は等しいと判定される。ステップＳ７１０で、状態番号ｋが状態の総数Ｋ（この場合であると、Ｋ＝８）と等しいか否かを判定し（Ｓ７１２）、状態番号ｋが状態の総数Ｋと等しくなければ、状態番号ｋを１インクリメントして（Ｓ７０１）、ステップＳ７０２に戻る。Ｓ７１２で、状態番号ｋがＫと等しければ、役割交換判定は真であると判定される（Ｓ７１４）。
【００２５】
次に例えば、ｋ＝３の場合を説明すると、ステップＳ７０２で、動作Ｂ記録部３６から、状態ｔとしてｔ３が、可能な行為ｚとしてｊ．ｂが、行為の結果の状態ｔ’としてｔ４、が取り出され、動作ｇｉｊ（Ｂ）記録部４２から、状態ｕとしてｕ３が、可能な行為ｚ’としてｉ．ｂが、行為の結果の状態ｕ’としてｕ４が取り出される。
ステップＳ７０４で、ｚはｉｎではないと判定され、ｚはｉ．ａか否かを判定する（Ｓ７０６）。ｚはｊ．ｂであるから、ｉ．ａではないと判定され、ｚ’はｉ．ｂか否かを判定する（Ｓ７１６）。ｚ’はｉ．ｂであると判定されるので、ステップＳ７１０でｇｉｊ（ｔ’）とｕ’が等しいか否かを判定する。
【００２６】
ここで式（４）よりｇｉｊ（ｔ４）＝ｕ４となり、ｇｉｊ（ｔ’）とｕ’が等しいと判定され、ステップＳ７１２に進む。
またｋ＝５になった場合は、ステップＳ７０２にて、動作Ｂの状態ｔとしてｔ５が、可能な行為ｚとしてｉ．ａが、行為の結果の状態ｔ’としてｔ６が、取出され、動作ｇｉｊ（Ｂ）の状態ｕとしてｕ５が、可能な行為ｚ’としてｊ．ａが、行為の結果の状態ｕ’としてｕ６が取出される。その結果、ステップＳ７０４でｚはｉｎではないと判定され、ステップＳ７０６でｚはｉ．ａであると判定され、更に、ｚ’をｊ．ａか否かを判定する（Ｓ７０８）。ｚ’はｊ．ａであるので、ステップＳ７１０に進む。
【００２７】
ｋ＝７の場合は、ステップＳ７０４、ステップＳ７０６、ステップＳ７１６を経て、ステップＳ７１０に到達し、式（７）のｇｉｊ（ｔ７）＝ｕ２により真と判定される。
またｋ＝４の場合は、ステップＳ７０２で、動作Ｂから、ｚが動作ｇｉｊ（Ｂ）からｚ’が取出せないから、ステップＳ７０３からステップＳ７１０に移り、式（４）のｇｉｊ（ｔ４）＝ｕ４が成立する。ステップＳ７０５においてｚ’がｉｎと等しくないと判定された場合、ステップＳ７０８においてｚ’がｊ．ａと等しくないと判定された場合、ステップＳ７１０においてｇｉｊ（ｔ’）がｕ’と等しくないと判定された場合、ステップＳ７１６においてｚ’がｉ．ｂと等しくないと判定された場合、のいずれにおいても更新指示生成部６２により、ｇｉｊ更新指示を生成し、更新指示出力部６６から出力する（Ｓ７１２）。
他の状態番号の場合も、同様な流れで処理を行い、ステップＳ７１２で、ｋ＝Ｋと判定されると、この写像ｇｉｊにより、動作Ｂと動作ｇｉｊ（Ｂ）とは役割交換をしている、つまり役割交換判定が真であるとする（Ｓ７１４）。
以上の処理は、動作Ｂ中の各トレースとこのトレースの対応する動作ｇｉｊ（Ｂ）中のトレースとが全て役割交換しているか否かを判定し、全て役割交換している場合はに動作Ｂと動作ｇｉｊ（Ｂ）とは、役割交換していると判定していることになる。図７中の判定ステップＳ７０４、Ｓ７０５、Ｓ７０６、Ｓ７０８、Ｓ７１６のｚとｚ’とを入れ替えても良い。
【００２８】
等価性判定部５４の動作例
次に図３中の等価性判定部５４の動作例を以下に説明する。ここで、観測される動作Ｖ（Ｂ）は図２Ａに示したものとし、入力された写像ｇｉｊの一例は上記役割交換判定部４４の具体例で使用したものと同じものとする。この場合の観測された動作Ｖ（Ｂ）とＶ（ｇｉｊ（Ｂ））との状態の対応関係を図８に示す。この図８は行為のみの系列となるから、図５中から利用者ｉ、ｊを削除したものと同一になる。また動作Ｖ（Ｂ）と動作Ｖ（ｇｉｊ（Ｂ））の可能なトレースの動作Ｖ（Ｂ）トレース記憶部４８と動作Ｖ（ｇｉｊ（Ｂ））記憶部５２における記憶状態の例をそれぞれ図９Ａ、図９Ｂに示す。図９Ａと図９Ｂはそれぞれ、図６Ａと図６Ｂ中の行為ｚ、ｚ’の欄が観測された行為Ｖ（ｚ）、Ｖ（ｚ’）となり、図６Ａと図６Ｂ中から利用者情報（この場合であるとｉとｊ）が削除されたものと同一である。
【００２９】
次に、図１０を参照して等価性判定部５４の処理手順を説明する。状態番号ｋを１に初期化し（Ｓ１０００）、上記動作Ｖ（Ｂ）トレース記憶部４８から状態ｔｋ、ｔｋからの行為Ｖ（ｚ）、その行為の従来の状態ｔ’を取り出し、また動作Ｖ（ｇｉｊ（Ｂ））記憶部５２から状態ｕｋ、ｕｋからの行為Ｖ（ｚ’）、その行為の結果の状態ｕ’を取り出す（Ｓ１００２）。最初は、ｋ＝１であるから、動作Ｖ（Ｂ）においては、状態ｔ１、行為Ｖ（ｚ）であるｉｎと、その行為の結果の状態ｔ’である状態ｔ２とｔ７が取り出され、動作Ｖ（ｇｉｊ（Ｂ））については、状態ｕ１、行為Ｖ（ｚ’）であるｉｎ、とその行為の結果の状態であるｕ’である状態ｕ２が取り出される（Ｓ１００２）。
【００３０】
ステップＳ１００２の後に、まず行為Ｖ（ｚ）と行為Ｖ（ｚ’）が等しいか否かを判定する（Ｓ１００４）。この場合、行為Ｖ（ｚ）と行為Ｖ（ｚ’）は共にｉｎであるため、等しいと判定される。等しいと判定されると、今度は、ｇｉｊ（ｔ’）とｕ’が等しいかを判定する（Ｓ１００６）。
この場合、式（２）よりｇｉｊ（ｔ２）＝ｕ２、式（７）よりｇｉｊ（ｔ７）＝ｕ２となり、ｇｉｊ（ｔ’）とｕ’は等しいと判定される。次に、状態番号ｋは状態の総数Ｋと等しいか否かを判定し（Ｓ１００８）、状態番号ｋは状態の総数Ｋと等しくなければ、状態番号ｋを１インクリメントし（Ｓ１０１０）、ステップＳ１００２に戻る。ｋ＝１の状態の動作Ｂと動作ｇｉｊ（Ｂ）の外部から観測したトレースが等価であると判定される。
【００３１】
次にｋ＝３になった場合、Ｓ１００２で、動作Ｖ（Ｂ）について、状態ｔとしてｔ３、可能な行為Ｖ（ｚ）としてｂ、行為の結果の状態ｔ’としてｔ４、が取り出され、また動作Ｖ（ｇｉｊ（Ｂ））について、状態ｕとしてｕ３、可能な行為Ｖ（ｚ’）としてｂ、行為の結果の状態ｕ’としてｕ４、が取り出される。ステップＳ１００４で、行為Ｖ（ｚ）と行為Ｖ（ｚ’）が共にｂであるから、等しいと判定され、ステップＳ１００６で、式（４）よりｇｉｊ（ｔ４）＝ｕ４となり、ｇｉｊ（ｔ’）とｕ’が等しいと判定され、ｋ＝３の状態の動作Ｂと動作ｇｉｊ（ｂ）の外部から観測したトレースが等価であると判定される。
【００３２】
次にｋ＝４になると、動作Ｂについて、状態ｔ４から可能な行為Ｖ（ｚ）が存在せず、その行為の結果の状態も存在しない。動作ｇｉｊ（Ｂ）についても、状態ｕ４から可能な行為Ｖ（ｚ’）が存在せず、その行為の結果の状態も存在しない。この場合も行為Ｖ（ｚ）と行為Ｖ（ｚ’）が等しく、ｇｉｊ（ｔ’）とｕ’が等しいと判定される。よってｋ＝４の状態の動作Ｂと動作ｇｉｊ（Ｂ）の外部から観測したトレース等価と判定され、ｋが１インクリメントされる。
ステップＳ１００６の判定が真であり、ステップＳ１００８において、動作Ｖ（Ｂ）の全ての状態を取出したと判定されると、等価性判定部５４では真と判定される（Ｓ１０１２）。
【００３３】
またステップＳ１００４、ステップＳ１００６のいずれにおいても、否と判定された場合は、更新指示出力部６２により、ｇｉｊ更新指示が更新指示出力部６６から出力される（Ｓ１０１４）。
他の状態番号の場合も、同様な処理の流れで判定が行われる。ステップＳ１０１２から真が出力されるとこの写像ｇｉｊを用いれば、観測された動作Ｖ（Ｂ）の可能なトレースの集合と、観測された動作Ｖ（ｇｉｊ（Ｂ））の可能なトレースの集合とが一致し、トレース等価性を基準とした動作Ｂと動作ｇｉｊ（Ｂ）との弁別不能性は真と判定される。
【００３４】
このように、この発明によれば、弁別不能性の基準として、トレース等価性を用いているが、対象となるコンピュータシステムの役割交換可能性も判定し、その結果が共に真であれば、当該コンピュータシステムは匿名性があると判定している。これは、利用者ｉが行為ａを利用者ｊが行為ｂを行う動作Ｂが与えられた時、その代わりに、以下の条件を満たす動作Ｂ’が存在することを満たすことである。
（１）動作Ｂ’で、ｉがｂをｊがａを行う。
（２）動作Ｂと動作Ｂ’は、外部から観測した時、トレース等価である。
【００３５】
この条件（１）は、上記役割交換判定部４４で判定し、条件（２）は上記トレース等価性判定部４５で判定している。
図５、図８に示した例のように比較的、簡単な動作の場合は、適切な写像ｇｉｊを人手で簡単に作ることができる。従って、図４に示した処理手順でｇｉｊを更新することを１回も行わず、匿名性の有無を検査することができる。ｇｉｊを適当に作り、入力することを繰り返して、匿名性検査が成功するまで行ってもよく、いつまでも匿名性検査が成功しない場合は、適当な時間で打ち切り、匿名性不成功をしてもよい。この打ち切るまでの適当な時間はコンピュータシステムの複雑さに応じて、変更される。
【００３６】
この発明の装置はコンピュータにより機能させることもできる。例えば、図１１に示すように、コンピュータとしての基本動作させる基本動作プログラムが記憶されたメモリ７０、例えば、図４に示した方法の各ステップをコンピュータに実行させるためのプログラムが記憶されたアプリケーションプログラムメモリ７２、ＣＰＵ７４、入力部３０、出力部５８を備え、更に、パラメータ記憶部３２、動作Ｂ記憶部３６、動作ｇｉｊ（Ｂ）記憶部４２、動作Ｖ（Ｂ）トレース記憶部４８、動作Ｖ（ｇｉｊ（Ｂ））トレース記憶部５２を備え、アプリケーションプログラムメモリ７２に、この発明による匿名性検査プログラムをＣＤ−ＲＯＭ、磁気ディスク、半導体メモリなどからインストールし、又は、通信回線を介して、ダウンロードして、このプログラムを実行させればよい。
【図面の簡単な説明】
【００３７】
【図１】Ａは役割交換前のコンピュータシステムの動作Ｂの例を示す図、Ｂは役割交換後のコンピュータシステムの動作Ｂ’を示す図である。
【図２】Ａは動作Ｂに対するコンピュータシステムの外部から観測される動作Ｖ（Ｂ）を示す図、Ｂは動作Ｂ’に対するコンピュータシステムの外部から観測される動作Ｖ（Ｂ’）を示す図である。
【図３】この発明の装置の機能構成例を示すブロック図。
【図４】この発明の方法の処理手順の例を示すフローチャート図。
【図５】動作Ｂの全ての状態を定義域とする写像ｇｉｊによる写像された動作ｇｉｊ（Ｂ）と動作Ｂと各状態の対応例を示す図。
【図６】Ａは動作Ｂ記憶部３６の記憶内容の例を示す図、Ｂは動作ｇｉｊ（Ｂ）記憶部４２の記憶内容の例を示す図である。
【図７】役割交換判定部４４の具体的動作の流れの例を示すフローチャート図。
【図８】観測動作Ｖ（Ｂ）観測動作Ｖ（ｇｉｊ（Ｂ））のそれぞれの状態の対応を示す図。
【図９】Ａは動作Ｖ（Ｂ）トレース記憶部４８の記憶内容の例を示す図、Ｂは動作Ｖ（ｇｉｊ（Ｂ））トレース記憶部５２の記憶内容の例を示す図である。
【図１０】等価性判定部４５の具体的の動作の流れの例を示すフローチャート図。
【図１１】この発明装置をコンピュータで構成した場合の簡略構成を示すブロック図。
【図１】
2007148624.tif 000003
【図２】
2007148624.tif 000004
【図３】
2007148624.tif 000005
【図４】
2007148624.tif 000006
【図５】
2007148624.tif 000007
【図６】
2007148624.tif 000008
【図７】
2007148624.tif 000009
【図８】
2007148624.tif 000010
【図９】
2007148624.tif 000011
【図１０】
2007148624.tif 000012
【図１１】
2007148624.tif 000013