(57)【要約】【課題】自らと直接接点のない相手のトラストを確率論に基づかず定量的に評価する。【解決手段】≦をt≦t' iff ∃t1,t2 t+t1=t2*t'で定義される二項関係とする。トラストの並列合成+およびトラストの直列合成*は、二項関係≦が、反射性：t≦t、推移性：t≦t'かつt'≦t"ならばt≦t"、反対称性：t≦t'かつt'≦tならばt=t'、減少性：t*t'≦t'、単調性：t≦t'ならばt"+t≦t"+t'、準分配性：t*(t'+t")≦t*t'+t*t"、強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'、を満たすように定義される。応答受信部１３は、計算対象の参加者に関する複数のトラストを受信する。合成演算部１４は、並列合成+および直列合成*を用いて複数のトラストを合成し、計算対象の参加者に関するトラスト計算結果を計算する。【選択図】図７
2017059975.tif 000002
【特許請求の範囲】
【請求項１】
t, t', t", Δt, t1, t2を質と量とからなるトラストとし、+をトラストの並列合成を表す演算子とし、*をトラストの直列合成を表す演算子とし、q(t)をトラストtの量を表す関数とし、≦をt≦t' iff ∃t1,t2t+t1=t2*t'で定義される二項関係とし、≦Δtをt≦Δtt' iff t'≦t+Δt∧q(t)≦q(t')を表すものとし、
上記並列合成+および上記直列合成*は、上記二項関係≦が、
反射性：t≦t、
推移性：t≦t'かつt'≦t"ならばt≦t"、
反対称性：t≦t'かつt'≦tならばt=t'、
減少性：t*t'≦t'、
単調性：t≦t'ならばt"+t≦t"+t'、
準分配性：t*(t'+t")≦t*t'+t*t"、
強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'、
を満たすように定義されるものとし、
計算対象の参加者に関する複数のトラストを受信する応答受信部と、
上記並列合成+および上記直列合成*を用いて上記複数のトラストを合成し、上記計算対象の参加者に関するトラスト計算結果を計算する合成演算部と、
を含むトラスト計算装置。
【請求項２】
請求項１に記載のトラスト計算装置であって、
tを上記トラスト計算結果とし、t'を上記計算対象の参加者に関する直接的かつ排他的な経験に基づいて決定される基礎トラストの総和とし、
上記合成演算部は、t≦t'を満たすように、上記トラスト計算結果を計算するものである、
トラスト計算装置。
【請求項３】
請求項２に記載のトラスト計算装置であって、
Tを相異なる二者間の基礎トラストを出力する基礎トラスト付値とし、f(T, P1, P2)を基礎トラスト付値Tにおけるある参加者P1からある参加者P2への計算され得るトラストの全体集合を出力する関数とし、Τ, Τ'をトラスト集合とし、⊆をΤ⊆Τ' iff ∀t∈Τ ∃t'∈Τ' t≦t'で定義される二項関係とし、T+P3P4Δtを基礎トラスト付値Tにおいてある参加者P3からある参加者P4への基礎トラストをΔtだけ増やした基礎トラスト付値とし、
上記合成演算部は、ある参加者P2に対する基礎トラストの総和が0ならばf(T, P1, P2)⊆{0}を満たし、かつ、f(T+P3P4Δt, P1, P2)⊆f(T, P1, P2)+Δtを満たすように、上記トラスト計算結果を計算するものである、
トラスト計算装置。
【請求項４】
請求項１から３のいずれかに記載のトラスト計算装置であって、
計算対象の参加者を示す情報Cと当該要求の転送に関わった参加者を示す情報の列Pとからなる要求<C, P>を受信する要求受信部と、
計算対象の参加者でなく上記列Pに含まれておらず自身からの基礎トラストが存在する参加者B1, …, Bn（n≧1）に対して、上記列Pに自身を表す識別子Aを追加した要求<C, P・A>を送信する要求送信部と、
をさらに含み、
上記応答受信部は、i=1, …, nについて上記参加者Biから上記計算対象の参加者へのトラストsBiCと上記トラストsBiCの計算に用いた基礎トラストを示す情報を含む線形項SBiCとからなる応答<sBiC, SBiC>を受信し、上記線形項SB1C, …, SBnCにおいて含まれる基礎トラストが重複しないk（≦n）個の応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を選択するものであり、
上記合成演算部は、上記応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を用いて、上記トラスト計算結果sAC=tAB'1*sB'1C+…+tAB'k*sB'kCと線形項SAC=~tAB'1*SB'1C+…+~tAB'k*SB'kCとを計算するものであり、
上記トラスト計算結果sACと上記線形項SACとからなる応答<sAC, SAC>を上記要求<C, P>の送信元である参加者へ送信する応答送信部、
をさらに含むトラスト計算装置。
【請求項５】
請求項４に記載のトラスト計算装置であって、
上記列Pは、上記要求の転送に関わった参加者を示す情報を一方向性関数により暗号化してビット連接したものであり、
上記線形項は、上記基礎トラストを示す情報を一方向性関数により暗号化してビット連接したものである、
トラスト計算装置。
【請求項６】
t, t', t", Δt, t1, t2を質と量とからなるトラストとし、+をトラストの並列合成を表す演算子とし、*をトラストの直列合成を表す演算子とし、q(t)をトラストtの量を表す関数とし、≦をt≦t' iff ∃t1,t2t+t1=t2*t'で定義される二項関係とし、≦Δtをt≦Δtt' iff t'≦t+Δt∧q(t)≦q(t')を表すものとし、
上記並列合成+および上記直列合成*は、上記二項関係≦が、
反射性：t≦t、
推移性：t≦t'かつt'≦t"ならばt≦t"、
反対称性：t≦t'かつt'≦tならばt=t'、
減少性：t*t'≦t'、
単調性：t≦t'ならばt"+t≦t"+t'、
準分配性：t*(t'+t")≦t*t'+t*t"、
強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'、
を満たすように定義されるものとし、
応答受信部が、計算対象の参加者に関する複数のトラストを受信する応答受信ステップと、
合成演算部が、上記並列合成+および上記直列合成*を用いて上記複数のトラストを合成し、上記計算対象の参加者に関するトラスト計算結果を計算する合成演算ステップと、
を含むトラスト計算方法。
【請求項７】
請求項１から５のいずれかに記載のトラスト計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、特定の対象に対する信頼を表すトラストを計算する技術に関する。
【背景技術】
【０００２】
近年、IT技術の革新的な進歩により、amazon（登録商標）や価格.com（登録商標）などの通販サイトや、Yahoo!知恵袋（登録商標）などのエキスパートサイトに見られるエンドユーザによる評判システムや、google（登録商標）などの検索サイトにおけるページランク（登録商標）や、SNS（Social Networking Service）における友達申請の場面などにおいて、自らがあまりもしくは全く知らない相手に対する信頼性判断をエンドユーザが能動的に行っている。また、ネットワーク技術においては、他社との接続においてBGP（Border Gateway Protocol）に代表されるダイナミックルーティングにより、通信事業者が相互接続しており、結果的に見知らぬ相手と間接的に接続されている。
【０００３】
前述の評判システムにおいては、サービス提供事業者のサーバに全トラスト情報が管理され、エンドユーザはそこにアクセスすることで情報を得ることができる。しかしながら、そのトラスト情報はエンドユーザの全く見知らぬ者による情報であり、場合によってはエンドユーザ自らが情報収集も行い、信頼することができるのか判断を行う必要がある。また、ネットワーク技術における通信プロトコルでは、通信経路としての正常性（例えば、回線品質や回線速度、隣接する相手が故障等により利用不能となった場合の処理など）に重点が置かれており、他社や中継事業者と接続する際において、直接接続される相手の先にいる者について知ることは困難である。
【０００４】
トラストとは、上述のような信頼に関する部分的な情報である。トラストが複数存在する場合に、確率論に基づいてそれらを総合して新たなトラストを計算する技術が、非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jingwei Huang, David Nicol, “A Calculus of Trust and Its Application to PKI and Identity Management”, 8th Symposium on Identity and Trust on the Internet (IDTrust), ACM, pp. 23-37, April 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載のトラスト計算技術は、各参加者のトラストを接続関係まで含めて全部集めて集中的に計算することが前提になっており、ネットワーク上に分散しているトラストを計算することは考慮されていない。また、トラスト計算の正しさが明示されておらず、個々のトラストが独立であるといった強い仮定の下で確率論的な方法に基づいて正当化することを念頭に置いているため、計算結果の健全性は満たすものの、計算手順の安定性は満たさない。さらに、トラストを3値（信頼する、信頼しない、わからない）で定義した場合の計算方法を与えているが、2値および4値以上の場合など、より一般の場合の計算方法は明示されていない。
【０００７】
この発明の目的は、このような点に鑑みて、ネットワーク上に分散している複数のトラストから、自らと直接接点のない相手を確率論に基づかず定量的に評価することができるトラスト計算技術を提供することである。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明のトラスト計算装置は、t, t', t", Δt, t1, t2を質と量とからなるトラストとし、+をトラストの並列合成を表す演算子とし、*をトラストの直列合成を表す演算子とし、q(t)をトラストtの量を表す関数とし、≦をt≦t' iff ∃t1,t2t+t1=t2*t'で定義される二項関係とし、≦Δtをt≦Δtt' iff t'≦t+Δt∧q(t)≦q(t')を表すものとし、並列合成+および直列合成*は、二項関係≦が、反射性：t≦t、推移性：t≦t'かつt'≦t"ならばt≦t"、反対称性：t≦t'かつt'≦tならばt=t'、減少性：t*t'≦t'、単調性：t≦t'ならばt"+t≦t"+t'、準分配性：t*(t'+t")≦t*t'+t*t"、強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'、を満たすように定義されるものとし、計算対象の参加者に関する複数のトラストを受信する応答受信部と、並列合成+および直列合成*を用いて複数のトラストを合成し、計算対象の参加者に関するトラスト計算結果を計算する合成演算部と、を含む。
【発明の効果】
【０００９】
この発明によれば、ネットワーク上に分散している複数のトラストから、自らと直接接点のない相手のトラストを確率論に基づかず定量的に評価することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、重複勘定について説明するための図である。
【図２】図２は、重複勘定について説明するための図である。
【図３】図３は、重複勘定について説明するための図である。
【図４】図４は、線形項について説明するための図である。
【図５】図５は、線形項について説明するための図である。
【図６】図６は、トラスト計算プロトコルの具体例を示す図である。
【図７】図７は、トラスト計算装置の機能構成を例示する図である。
【図８】図８は、トラスト計算方法の処理手続きを例示する図である。
【発明を実施するための形態】
【００１１】
この発明のトラスト計算技術では、トラストを質と量の組を用いて定量的に定式化する。従来技術では、トラストが確率あるいは何らかの割合、もしくはそれらの組として定式化されることが多かった。この発明では、質と量を用いて並列合成と直列合成の二種類の合成演算を定義し、確率論によらずに計算の正しさを定式化し、その正しさを担保するトラスト計算を実行するプロトコルを示す。
【００１２】
従来技術では、ネットワーク上の参加者のトラストを接続関係まで含めて全部集めて集中的に計算することが前提になっていた。この発明では、ネットワーク上の参加者が分散的にトラストを保持しており、自らと直接接点のない相手を定量的に評価することを前提とする。例えば、参加者A, B, Cが存在するネットワークにおいて、AとBとの間、BとCとの間にそれぞれトラストが存在するが、AとCとの間にはトラストが存在しない場合に、Aに対してCのトラストを提供する場合である。なお、ネットワーク上の参加者は人間の場合もあれば、機械などのハードウェアやプログラムなどのソフトウェアの場合もある。また、参加者は同種のオブジェクトである必要はなく、多種のオブジェクトが混在してネットワークを構成していてもよい。
【００１３】
この明細書では、数式中で以下の記号を用いるが、テキスト記法の制限により、文中では「≦」と表記する。
【００１４】
【数１】
2017059975.tif 000003
【００１５】
また、数式中で文字の真上に記述する「~」「-」の記号は、テキスト記法の制限により、当該文字の直前に記載する。すなわち、文中の「~t, -P」という記載は、数式中の以下の記載に対応する。
【００１６】
【数２】
2017059975.tif 000004
【００１７】
［トラストの質と量］
まず、トラストの質と量について説明する。ここでは、参加者が人間同士である場合を考える。問題設定としては、以下の二点を前提として、信頼をどのように測定するか、ということである。
【００１８】
１．各自が他人に対する自分のトラストを保持しており、聞かれたら答える（例えば、「質問したら正しい答えが返ってくるか」、「お金を払ったらちゃんと商品が届くか」といった評価を個々人が持っている）。
【００１９】
２．返事をしない、知っていても「知らない」と答える、嘘の値を答える、という場合もある（つまり、trusted third partyの存在は仮定しない）。
【００２０】
この発明では、信頼には、質と量があるものと考える（例えば、「あいつはいつも頼りになる」、「あいつとは長い付き合いだ」など）。そこで、次式のようにトラストを質と量で定義する。
【００２１】
【数３】
2017059975.tif 000005
【００２２】
tABはAのBに対するトラストを表す。pABはpAB∈[0, 1]と仮定し、トラストtABの質と呼ぶ。意図された解釈は、やり取りの中でBがAの期待に応えた割合である。qABは非負実数であり、トラストtABの量と呼ぶ。意図された解釈は、AとBのやり取りの量（例えば、やり取りの回数や取引額など）である。以下では、qAB=0ならばpAB=0と仮定し、簡単のために(0, 0)を0と書くことがある。例えば、トラストの量を“質問の回数”とし、質を“正しい返事が得られた割合”とする。AがBに過去100回質問し、その中で90回正しい返事が得られたならば、AのBに対するトラストは(0.9, 100)となる。
【００２３】
なお、上記は質が2値（例えば、「信用できる」、「信用できない」）のときの定式化であるが、この発明のトラスト計算技術は3値以上の場合にも適用することができる。3値以上の場合の具体的な定式化については後述する。
【００２４】
［トラストの合成］
トラストの合成には、直列合成と並列合成とがある。
【００２５】
トラストの並列合成は、二つの情報源から来たトラストを“足す”という合成である。以下では、トラストの並列合成演算を「+」で表すものとする。例えば、Cに対するトラストをAとBに聞いたところ、tAC=(pAC, qAC), tBC=(pBC, qBC)であったとする。このとき、仮にAとBを100％信頼するとして、それらを総合してどのように評価すればよいかを示すのが並列合成である。例えば、並列合成は以下の演算と定義できる。
【００２６】
【数４】
2017059975.tif 000006
【００２７】
すなわち、量は単なる足し算、質は量で重み付けした平均である。ただし、(0, 0)+(0, 0)=(0, 0)と定める。質の定義を確率の類推で考えると、量を独立な試行の回数とみなし、qAC回のうちpACの確率で真でありqBC回のうちpBCの確率で真である場合に、qAC+qBC回全体で真となる確率である。tAC+tBCの量が0となるのは(0, 0)+(0, 0)の場合のみであり、tAC+tBCの質が必ず[0, 1]に入ることから、この演算はwell-definedである。例えば、tAC=(0.9, 100)，tBC=(0.8, 1000)のとき、tAC+tBC=(0.81, 1100)となる。
【００２８】
並列合成+の性質は以下のとおりである。
・結合的かつ可換的
・0+t=t
トラストの直列合成は、トラストが伝聞されてきたときに用いる合成である。以下ではトラストの直列合成演算を「*」で表すものとする。例えば、BがAに、Cに対するトラストがtBC=(pBC, qBC)であることを知らせてきたとする。さらに、AのBに対するトラストがtAB=(pAB, qAB)だったとする。そのとき、AのCに対するトラストはいくらだと思えばよいかを示すのが直列合成である。例えば、直列合成は以下のように定義できる。
【００２９】
【数５】
2017059975.tif 000007
【００３０】
質の定義は、確率の類推で考えると、確率pABでpBCかつ確率1-pABで0であるときの期待値である。別な言葉で言えば、AがBを信頼し、かつBがCを信頼する割合である。量の定義は、AはBから伝えられたトラストについてBに対するトラストの量以上の信をおかない、という考えに基づいている。tAC*tBCの量が0となるのはtAC=0あるいはtBC=0の場合のみであり、そのときtAC*tBCの質は0であり、tAC*tBCの質が必ず[0, 1]に入ることから、この演算はwell-definedである。例えば、tBC=(0.9, 1000), tAB=(0.8, 100)のとき、tAB*tBC=(0.72, 100)となる。
【００３１】
トラストの直列合成は、伝達によるトラストの劣化を表す。伝達によって劣化すると考える理由は、伝達者が嘘をつく可能性があるからである。嘘には、トラストの量や質を過少に答える場合と過大に答える場合とが考えられる。この発明の問題設定では、一般にすべてのトラストを集めることはできないため、量的に過少に評価されるのは不可避である。さらにトラストという問題の性質から考えても、嘘としてより深刻なのは過大な評価であり、上記の定義もそれを反映している。
【００３２】
大雑把に言って、上記直列合成は、嘘に関して以下の仮定をしていることになる。逆に、以下の条件が成り立つことが直列合成の妥当性とも言える。例えば、AのBに対するトラストが(pAB, qAB)のとき、BはAへのトラストの伝達に際して、
１．質を過大に偽るとしても高々元の値の1/pAB倍である。
２．量qAB以下のトラスト情報についてはその量を過大に偽らない。
【００３３】
直列合成*の性質は以下のとおりである。
・結合的かつ可換的
・0*t=0
なお、合成演算の定義は上記のものが唯一のものでも最適のものでもない。むしろ、用途やユーザの好みによって変形が可能である。例えば、並列合成のバリエーションとして、以下の定義が考えられる。
【００３４】
【数６】
2017059975.tif 000008
【００３５】
この定義は実際的な意味はあまりないが、この発明のトラスト計算の妥当性が確率的な議論に依らないことを明確化する意図がある。
【００３６】
また、例えば、直列合成のバリエーションとして、以下の定義が考えられる。
【００３７】
【数７】
2017059975.tif 000009
【００３８】
この定義では、合成値の量において、minの第１引数としてqABの代わりにpAB・qABが用いられているので、pABが低ければ低いほど合成値の量は小さくなる。直観的には、トラストの低い参加者の意見には質的にだけでなく量的にも重きを置かないことを意味する。ただし、ここで注意すべきことは、この直列合成は結合的でも可換的でもないということである。バリエーションは他にも、例えば多値化など様々なものが考えられる。非結合性／非可換性を含めたさらなる議論については後述する。
【００３９】
［重複勘定の問題］
式（２）で示した並列合成の演算は、常に妥当であるとは限らない。これは、重複勘定および加法性と深い関係がある。ここでは、上記演算が妥当とならない場合として三つのタイプの重複勘定を提示する。
【００４０】
例えば、参加者A, B1, …, B100, C, Dが、図１に示すようなネットワークを構成しており、各参加者の間のトラストを、tABi=(1, 1), tBiC=(1, 1), tCD=(1, 10)（ただし、i=1, …, 100）と仮定する。このとき、以下のようなトラスト計算が妥当か否かを考える。
１．AのDに対するトラストtADは、tAB1*tB1C*tCD+…+tAB100*tB100C*tCD=(1, 100)
２．AのCに対するトラストtACは、tAB1*tB1C+…+tAB100*tB100C=(1, 100)
１は量的に10しか原資がないのに重複勘定のために誤って100に増幅されてしまっている（ように見える）ことを問題にしている。一方、２は表面的には重複勘定はないが、tB1C, …, tB100Cというトラストがどのように定められたかが問題になる。もしCの唯一の行為をB1, …, B100が同時に目の当たりにした結果tB1C, …, tB100Cを決定したのであれば、その量は全体で1と勘定されるべきではないかという問題である。
【００４１】
例えば、100人の構成員B1, …, B100からなる非政府組織（NGO）があったとする。そのNGOの活動趣旨に賛同してCが1万円の寄付を行い、その事実に基づきすべてのB1, …, B100が「Cを量的に1万円分信頼する」と決心したとする。そのとき、それらの信頼を加算して、「Cは100万円分信頼できる」と判断するのは妥当だろうか、という問題とも言える。１と２は似ているが違う問題である。後者は計算の基礎となるトラストの値をいかに決めるかという問題なのに対し、前者はそのように決めた値を使っていかに計算するかという問題である。
【００４２】
まず、２について考える。解決として、トラストを基礎トラストとそうでないものとに区別する考え方を導入する。基礎トラストとは、直接的かつ排他的な経験に基づいて各参加者によって決定されるトラストである。一方、そうでないトラストとは、伝聞情報から計算されたトラストである。直接的な経験とは自分の目や耳で見聞きしたことをいう。伝聞や推測は直接的ではない。排他的な経験とは自分だけで経験したことをいう。もし複数人で一つのことを経験した場合は、総和が1となるように量を分配する（例えば、n人で一緒に経験したならひとりあたまの量はn分の1にする、など）。分け前が決定できないような場合は直接的ではないと考える。このような仮定のもとで、並列合成において量を加算することが正当化される。
【００４３】
参加者の全体集合をΡとし、Ρは有限集合と仮定する。任意のA, B∈Ρについて、AのBに対する基礎トラストをtABと表す。単に「Bに対する基礎トラスト」あるいは「基礎トラスト」と呼ぶこともある。ここでは、トラストを加法的な値と捉え、Bの総基礎トラストtBを以下のようにBに対する基礎トラストの総和として定義する。なお、加法的とはシステム全体の値がサブシステムの値の総和となることである。
【００４４】
【数８】
2017059975.tif 000010
【００４５】
次に、１について考える。図１の例において、Dに対する0でない基礎トラストがtCDだけならば、この例は重複勘定のために総基礎トラストを量において上回ってしまっていることになる。加法的な値を正しく計算するためには、このような事態は避ける必要がある。
【００４６】
では、Dに対するトラストを計算するとき、Dに対する基礎トラスト以外のトラスト、すなわち伝達経路の基礎トラストは重複勘定してもよいかを考える。例えば、図２の例において、A→Bi→C→D→Ei→F（ただし、i=1, …, 100）という100本の経路それぞれでトラストを計算し、その後それらの和をとるという計算を考える。この例では、計算結果はFの総基礎トラストを超えてはいない。しかし、100本の経路はC-D辺を共有しているので、
【００４７】
【数９】
2017059975.tif 000011
【００４８】
という計算では、C-Dという小さな量の辺に、大きな量のトラストが100回に分けて流れこんでいると言える。これは合計で考えると、「CはDから伝えられたトラストについてDに対するトラストの量以上の信をおかない」という、直列合成における量の基本的な考え方に反している。実際、もし新たな経験によってtCDが(0.5, 2)に更新されたとすると、計算結果は(0.5, 100)に変化する。つまり、量100の計算結果がたった量1の変化に大きく左右されることになり、健全とは言えない。よって、このような事態は避けなければならない。
【００４９】
［健全性と安定性］
ここでは、トラストの計算の正しさを、その具体的な計算方法に依存せずに定式化する。その理由は以下のとおりである。
【００５０】
重複勘定に関係するトラスト計算の問題は上述した。しかし、重複が起きているかどうかは具体的な計算方法に強く依存する。もし想定外の計算方法が新たに見つかったら、そのような定義は適用できなくなる恐れがある（例えば、後述する、トラスト計算と最大フロー問題との関連がある）。計算の正しさの概念を普遍的なものとするためには、具体的な計算方法に依存しない定式化が必要である。また、そのような定式化は、計算値が計算方法のみによって規定されない場合（例えば、嘘が混ざる場合など）に対しても、親和的であることが期待できる。
【００５１】
まず、トラスト上の二項関係≦を以下のように定義する。
【００５２】
【数１０】
2017059975.tif 000012
【００５３】
式（８）は、左辺がt'をt2分だけ劣化させたものに等しく、かつそれがtにt1を加えたものであることを主張する。その直観的な意味は、tがt'に比べて部分的かつ劣化しているということであり、情報の多寡を表す関係とみなすことができる。
【００５４】
例えば、(0.8, 10)≦(0.9, 100)は明らかに成り立つ。また、(0.8, 100)≦(0.9, 100)（ただし、t1=(0, 0), t2=(8/9, 100)ととる）, (0.9, 50)≦(0.8, 100)（ただし、t1=(0.7, 50), t2=(1, 100)ととる）も成り立つ。一方、(0.8, 100)≦(0.9, 10), (0.9, 90)≦(0.8, 100)は成り立たない。
【００５５】
（補題１）≦は以下の性質を満たす。
【００５６】
１．反射性：t≦t
２．推移性：t≦t'かつt'≦t"ならばt≦t"
３．反対称性：t≦t'かつt'≦tならばt=t'
４．減少性：t*t'≦t'
５．単調性：t≦t'ならばt"+t≦t"+t'
６．準分配性：t*(t'+t")≦t*t'+t*t"
７．強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'
ただし、Δtはトラストであり、t≦Δtt' iff t'≦t+Δt∧q(t)≦q(t')である。なお、q(t)はトラストtの量を表す関数である。
【００５７】
（補題１の証明）多くの性質は、以下のような≦の特徴づけを用いて証明される。詳細な証明は後述する。
【００５８】
【数１１】
2017059975.tif 000013
【００５９】
なお、≦の*に関する単調性は成り立たない。t≦t'のとき、t"+t≦t"+t'である場合も、t"+t≧t"+t'である場合もあり、さらにそのどちらでもない（すなわち≦で比較不能の）場合もある。もちろん単調性が成り立つか否かは合成の定義に依存する。例えば、式（４）に例示した並列合成を用いて定義される関係を≦1とすると、≦1は+と*の両方に関して単調であり、以下のように特徴づけられる。
【００６０】
【数１２】
2017059975.tif 000014
【００６１】
*に関する単調性の欠如は、トラスト計算の正しさの証明における困難のひとつである。補題１の７で導入されている関係≦Δtは、この困難を解決するために必要となる。
【００６２】
0+t=tから、0≦tやt≦t+t'などが導かれる。以下では、上記で定義したトラスト上の半順序≦を用いて、トラスト計算の健全性を定式化する。
【００６３】
（定義１：計算されたトラストの健全性）Bに対する計算されたトラストtは、t≦tBのとき健全であるという。ただし、tBはBに対する基礎トラストの総和である。
【００６４】
この発明の問題設定では、Bに対するトラストを計算する際、一般にtB=Σρ∈ΡtρBをすべて完全に計算することはできない。上記の健全性は、tは不完全かつ部分的かもしれないが、重複計算などを含まず、各tρBを正しく加法的に取り扱うという意味で正しい計算結果のひとつとみなせることを表している。
【００６５】
例えば、基礎トラストが図３に示すように存在する状況を考える。AのCに対する計算されたトラストs=tAB1*tB1C+tAB1*tB1B2*tB2C=(0.7695, 20)を考えると、(0.7695, 20)≦(0.9, 20)=tCなので、sはAからCへの計算されたトラストとして健全である。また、s'=tAB2*tB2C=tCも同様である。しかし、s+s'=(0.765, 22)は、(0.765, 22)≦tCが成り立たないので、AのCに対する計算されたトラストとして健全ではない。実際、ここではtB2Cが重複勘定されている。
【００６６】
しかしながら、健全性は個々の計算されたトラストを考えるだけでは不十分である。図２の例で示したように、計算結果自体は総基礎トラストを超えないが、基礎トラストのわずかな変化に大きく左右されてしまう場合がある。以下ではこのような問題も考慮に入れた健全性を、計算手順の安定性として定式化する。
【００６７】
ここで問題となるのは、この発明で扱う計算手順は一般に部分的かつ非決定的だということである。トラストを非決定的プロトコルで分散計算する方法は後述するが、それは要求を送る相手の選択や応答の構成に関して非決定性を含むものである。また問題設定から、要求を受け取った参加者は嘘をついたり答えなかったりすることが想定されている。以下では、そのような手順を入力から可能な出力の集合への関数とみなし、その健全性をいわゆるホーア（Hoare）前順序を用いて定義する。
【００６８】
（定義２：基礎トラスト付値）基礎トラスト付値Tは、相異なる参加者の対からトラストへの関数である。T(A, B)はTにおけるAからBへの基礎トラストを表し、tTABとも書く。さらに、Tが文脈から明らかな場合は、従来通り単にtABと書く。
【００６９】
（定義３：トラスト計算手順）トラスト計算手順fとは、基礎トラスト付値Tと相異なる参加者A， Bを与えられて、停止したら計算されたトラストを出力する手順である。f(T, A, B)は入力T, A, Bに対する可能な出力の全体集合を表す。
【００７０】
（定義４：トラスト集合上のHoare前順序）トラスト集合上の前順序⊆を、Τ, Τ'をトラスト集合とし、以下のように定義する。
【００７１】
【数１３】
2017059975.tif 000015
【００７２】
さらに、トラスト集合Τとトラストtに対して、演算Τ+tを以下のように定義する。
【００７３】
【数１４】
2017059975.tif 000016
【００７４】
（定義５：トラスト計算手順の安定性）トラスト計算手順fは、任意の相異なる参加者A, Bについて、以下の二つの条件を満足するとき、安定であるという。
１．TにおけるBの総基礎トラストが0ならば、f(T, A, B)⊆{0}
２．任意の相異なる参加者C, DとトラストΔtについて、f(T+CDΔt, A, B)⊆f(T, A, B)+Δt（ただし、T+CDΔtは、TにおけるtCDへの付値をΔtだけ増やしたものを表す。）
大雑把に言って、トラスト計算手順の安定性は、手順がすべての基礎トラストを加法的に取り扱うことである。
【００７５】
例えば、図２において、tCDのみ(1, 0.5)に変更した基礎トラスト付値をTとし、さらにT'=T+CD(1, 0.5)とする。このとき、式（７）を用いた決定的な計算手順を考えると、次式のとおりとなる。
【００７６】
【数１５】
2017059975.tif 000017
【００７７】
よって、この手順は安定ではない。
【００７８】
（補題２）手順が健全ならば、その手順が出力する個々の計算されたトラストも健全である。
【００７９】
（補題２の証明）fを健全なトラスト計算手順とし、Tを任意の基礎トラスト付値とし、A, Bを相異なる参加者とする。P0, P2, …, PnをB以外のすべての参加者の列とし、TにおけるtPkB, …, tPnBの付値をすべて0に置き換えた基礎トラスト付値をTkとする（ただし、k=0, …, n）。すると、fの健全性から、f(T0, A, B)⊆{0}である。また、f(Tk+1, A, B)⊆f(Tk, A, B)+tPkB（ただし、k=0, …, n-1）、かつf(T, A, B)⊆f(Tn, A, B)+tPnBである。よって、f(T, A, B)⊆{tB}となる。したがって、すべての計算されたトラストは健全である。
【００８０】
次に、上述した嘘に関する仮定を、≦を用いてより一般的な形で定式化する。この発明では、各伝達者の嘘をトラスト上の関数として表せると仮定する。参加者BがトラストをAに伝えるときにつく嘘を表す関数をBのAに対する嘘関数と呼び、LABで表す。Bが計算されたトラストsをAに送るとき、実際にAに送られるのはLAB(s)である。そのとき、LABには以下の不等式が成り立つと仮定する。
【００８１】
【数１６】
2017059975.tif 000018
【００８２】
すなわち、BのAに対する任意の嘘は、“tAB*_”によってキャンセルできるということである。これを嘘の上限仮定と呼ぶ。
【００８３】
この発明では、嘘はトラストの伝達時のみつかれるとし、基礎トラスト自体が間違っているということは考えない。これは、健全性を総基礎トラストを用いて定義していることと呼応する。
【００８４】
もし一部の参加者の基礎トラストが間違っているならば、むしろ正しい基礎トラストのみの総和を健全性の基準とすべきかもしれない。しかし、基礎トラスト自体が正しいか否かを決定するのは難しい。仮にAから伝えられるトラストが間違っているとわかったとしても、それは基礎トラスト自体が間違っているのかもしれないし、伝達時に嘘をついたのかもしれない。両者は一般に識別不能である。また、たとえ一部の参加者の基礎トラストが間違っていたとしても、総基礎トラストを超えないことは依然として健全性の十分条件である。よって、この発明では健全性と嘘の上限を上記のように定式化する。
【００８５】
［線形項］
参加者を頂点とする有向グラフ（各辺はトラストする側からされる側へ向かう）を考え、その上で基礎トラストの計算手順を考える。このとき、重複勘定のない手順を表現するために、線形項を定義する。相異なる参加者の対A, Bに対して基礎トラスト記号と呼ばれる定数記号~tABを導入し、それと+および*から構成される項を考える。
【００８６】
（定義６：線形項）A, B, Cを相異なる任意の頂点として、A-B線形項と、それらが表すグラフ（有向辺の集合）を以下のように定義する。
１．~tABはA-B線形項であり、A-B辺の単一要素集合を表す。
２．A-B線形項S1, …, Sn（ただし、n≧1）が、それらの表すグラフが互いに有向辺を共有しないならば、S1+…+SnはA-B線形項であり、S1∪…∪Snを表す。
３．SがB-C線形項であり、Sの表すグラフにAが現れないとき、~tAB*SはA-C線形項であり、Sが表すグラフにA-B辺を加えたものを表す。
【００８７】
例えば、図４に示す有向グラフであれば、線形項~tAB1*(~tB1C1*~tC1D+~tB1C2*~tC2D)+~tAB2*~tB2Dで表すことができる。図１の有向グラフを表す線形項は存在しない。図１のグラフ中において線形項で表せるのは、例えば個々の経路~tABi*~tBiC*~tCDである。
【００８８】
C, Dを任意の参加者とする。A-B線形項Sの以下の性質は定義からすぐに導かれる。
・Sが表すグラフにC-D辺が含まれる場合に限り、Sに~tCDが現れる
・（線形性）~tCDはSに高々一度しか現れない
よって、A-B線形項Sと基礎トラスト付値Tを与えられたとき、Sに出現する任意の~tCDをtTCDと解釈して得られる値を、TにおいてSを用いて線形に計算されたトラストと呼び、[S]Tで表す。
【００８９】
A-B線形項Sが表すグラフは、大雑把に言って、いったん分岐したら目的地であるBまで合流しないようなA-Bパスの集まりである。しかし、これを木のすべてのリーフに唯一の終端頂点を付加したようなものだと考えるのは誤りである。線形項が表すグラフは、一般にはダグですらない。例えば、線形項~tAB1*~tB1B2*~tB2C+~tAB2*~tB2B1*~tB1Cが表すグラフは、図５に示すとおりループを含む。
【００９０】
（補題３：線形に計算されたトラストの健全性）任意のA-B線形項Sと基礎トラスト付値Tについて、[S]T≦tBを満たす。
（補題３の証明）Sの中の~tPP'*sP'Bという形の任意の部分項で最外のものをひとつ選んでsP'Bで置き換えたものをS'とすると、単調性と減少性から[S]T≦[S']Tである。これを繰り返してすべての*を除去すると、~S=~tP1B+…+~tPnBという形の和が残るが、線形性と単調性から[~S]T≦tBが成り立つ。よって、[S]T≦tBである。
【００９１】
この証明に、単純な項の構成に関する帰納法を用いることはできないことに注意されたい。なぜならば、*に単調性がないからである。
【００９２】
［トラスト計算プロトコル］
以下、トラストを分散的に計算するためのプロトコルを示す。このプロトコルで得られた結果は、演算の結合性、可換性、ゼロ元、補題１の性質のみに依存し、合成演算の具体的な定義には依存しない。同様の性質を満たす他の定式化（例えば、後述する多値化）にも適用できる。
【００９３】
基本プロトコルは、要求と応答のメッセージをやり取りする非決定的プロトコルである。要求メッセージは、トラストを計算したい対象の参加者を示す情報Cと、要求が辿ってきた参加者を示す情報の列Pの組<C, P>で定義される。応答メッセージは、計算されたトラストsと、それを計算するために用いた線形項Sの組<s, S>で定義される。
【００９４】
AがCとやり取りした経験がない場合は、tAC=0とする。AがDから要求<C, P>を受け取ったら、以下のステップを順に実行する。
ステップ１．tAC≠0ならば、応答<tAC, ~tAC>を自分に送る。
ステップ２．以下の条件を満たすB1, …, Bnを非決定的に選んで、要求<C, P・A>を送る。
・Biは自分自身でもCでもない
・tABiが0でない
・BiがPに含まれない
ステップ３．応答をできるだけ待つ。
ステップ４．得られた応答の中から、その第２要素である線形項が互いに同じ基礎トラスト記号を含まないように、<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を非決定的に選ぶ。このとき、ひとつも選ばなかったら、すぐに終了する。選択した応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を用いて、sAC=tAB'1*sB'1C+…+tAB'k*sB'kC, SAC=~tAB'1*SB'1C+…+~tAB'k*SB'kCを計算し、その組<sAC, SAC>をDに送る。ただし、B'i=Aの場合、tAB'i*sB'iCはsB'iCを表し、~tAB'i*SB'iCはSB'iCを表すものとする。
【００９５】
ただし、個々のメッセージがどの要求の処理に直接関わるかを決定する手段が提供されているものと仮定する。例えば、要求を受け取るたびに新たな番号を生成し、その要求の処理に関わる要求／応答メッセージにはすべてその番号を付加する。自分がCに対するトラスト計算セッションを開始したいなら、自分自身に要求<C, λ>を送る。ただし、λは空列である。
【００９６】
（補題４：線形性）Tを、各参加者が保持する基礎トラストによって定められる基礎トラスト付値とする。プロトコルの参加者が嘘をつかないとする。Aが要求<C, P>に対して応答<s, S>を返すとき、SはA-C線形項かつs=[S]Tである。
【００９７】
（補題４の証明）Sの構成に関する帰納法による。帰納段階において、基本プロトコルのステップ４で“線形項が互いに同じ基礎トラスト記号を含まないように”B'iを選ぶことから、線形項の定義の２にある条件“それらの表すグラフが互いに有向辺を共有しない”が満足される。また、基本プロトコルのステップ２で“Pに含まれない”相手を選んで要求を送ることから、線形項の定義の３にある条件“Sの表すグラフにAが現れない”が満足される。
【００９８】
上述の基本プロトコルを用いて、トラスト計算手順を以下のように定める。入力T, A, Bを与えられたら、以下のステップを順に実行する。
ステップ１．Tに従って各参加者の保持する基礎トラストを定める。
ステップ２．AがBに対するトラスト計算セッションを開始する。
ステップ３．Aが応答を受け取ったら、その第１要素を出力する。
【００９９】
図６に、基本プロトコルとそれによって定まる計算手順の実行例を示す。ここでは、AのDに対するトラストを計算している。図６において、実線矢印は存在する基礎トラストを示し、点線矢印は要求と応答の流れを示している。図６に示すように、Dに対する0でない基礎トラストはtB1D=(0.8, 10), tCD=(1, 10)のみとし、さらにtB1C=(0.9, 30), tB2C=(0.9, 5), tAB1=(0.9, 15), tAB2=(0.9, 20)とする。また、プロトコルの参加者は嘘をつかないとする。トラスト計算手順f(T, A, D)は以下のように実行される。
ステップ１．Aは自分自身に要求<D, λ>を送り、自分で受け取る。要求を送る相手としてB1, B2を選び、要求<D, A>を送って応答を待つ。
ステップ２．Aから要求<D, A>を受け取ったB1は、Dに対する0でない基礎トラストを保持しているので、自分自身に応答<(0.8, 10), ~tB1D>を送る。さらに、要求を送る相手としてCを選び、要求<D, A・B1>を送って応答を待つ。
ステップ３．B1から要求<D, A・B1>を受け取ったCは、Dに対する0でない基礎トラストを保持しているので、自分自身に応答<(1, 10), ~tCD>を送る。要求を送る相手としては誰も選ばず、それが唯一の得られる応答なので、応答<(1, 10), ~tCD>をB1に送る。
ステップ４．B1は得られた二つの応答を総合して、応答<sB1, SB1>=<(0.85, 20), ~tB1D+~tB1C*~tCD>をAに送る。
ステップ５．一方Aから要求<D, A>を受け取ったB2は、Dに対する基礎トラストが0なので、要求を送る相手としてCを選び、要求<D, A・B2>を送って応答を待つ。CはB1のときと同様にこの要求を処理し、応答<(1, 10), ~tCD>をB2に送る。それを受け取ったB2は、応答<sB2, SB2>=<(0.9, 5), ~tB2C*~tCD>をAに送る。
ステップ６．B1とB2から応答<sB1, SB1>, <sB2, SB2>を受け取ったAは、二つの応答の線形項が同じ基礎トラスト記号~tCDを含むため、B1からの応答<sB1, SB1>のみを選び、応答<sA, SA>=<(0.765, 15), ~tAB1*(~tB1D+~tB1C*~tCD)>を自分自身に送る。
ステップ７．Aは応答<sA, SA>を受け取って、(0.765, 15)を出力する。
【０１００】
（定理１：基本プロトコルに関する健全性と安定性）基本プロトコルを用いて定められるトラスト計算手順をfとする。このとき、以下のことが言える。
【０１０１】
１．fの実行中、基本プロトコルの参加者が応答の第１要素を決定するときにおいてのみ、上限仮定の範囲内で嘘をつくとする。このとき、fによって計算されたトラストは健全である。
【０１０２】
２．基本プロトコルの参加者が嘘をつかないならば、fは健全である。
【０１０３】
（定理１の証明）出力sを決定した際にAが受け取った応答を<s, S>とする。仮定より、参加者はSの構成において嘘はつかない。基本プロトコルの任意の参加者C, Dに対して、関数記号~LCDを導入し、その解釈をDのCに対する嘘関数とする。S中の*の適用は“~tCD*_”（ただし、C≠D）の形をしているが、それらをすべて“~tCD*~LCD(_)”に置き換えたものをSLとすると、s=[SL]Tである。そのとき、減少性の代わりに嘘の上限仮定を使うことで、補題３の証明と同様の議論によって、SLから*と~LCDを除去できる。よってsは健全である。
【０１０４】
参加者が嘘をつく場合、基本プロトコルを用いて定められるトラスト計算手順は安定ではない。例えば、BがAにトラストsBCを伝えるときに嘘をつく、という状況を考える。AのBに対する基礎トラストがtABおよびtAB+Δtのとき、BのAに対する嘘関数をそれぞれLAB, L'ABとする。さらに、
【０１０５】
【数１７】
2017059975.tif 000019
【０１０６】
とする。上記の状況において、LABとL'ABとが嘘の上限仮定を満たしていること、さらにtAB=(1,1)であることから、LABは≦の意味でこれ以上の値をとり得ないことに注意されたい。しかしこのとき、
【０１０７】
【数１８】
2017059975.tif 000020
【０１０８】
となる。よって、トラスト計算手順の安定性の条件２を満たさない。大雑把に言えば、付値がΔt増加することで、（嘘なしの）計算結果が変化するが、それと共に許される嘘の程度も変化する。定理１で示したように、Δtは前者の上界であるが、後者を含めた上界にはならない。
【０１０９】
嘘を含む場合の上界を別途与えることは可能だが、そのためには≦や演算子の基本性質だけでは不十分であり、*の具体的定義に依存した議論が必要となる。
【０１１０】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【０１１１】
実施形態のトラスト計算装置は、上述のトラスト計算プロトコルを実行する情報処理装置である。このトラスト計算装置は、図７に示すように、トラスト記憶部１０、要求受信部１１、要求送信部１２、応答受信部１３、合成演算部１４、および応答送信部１５を含む。このトラスト計算装置が後述する各ステップの処理を行うことにより実施形態のトラスト計算方法が実現される。
【０１１２】
トラスト計算装置は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。トラスト計算装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。トラスト計算装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。また、トラスト計算装置の各処理部の少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。トラスト計算装置の各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【０１１３】
図８を参照して、実施形態のトラスト計算方法の処理手続きを説明する。ここでは、識別子Aが与えられたトラスト計算装置の処理を中心に説明するものとし、参加者Aが直接の接点をもたない参加者Cのトラストを、参加者Dから要求される場面を想定する。また、参加者Aは他の参加者B1, …, Bnと直接の接点があり基礎トラストをもつものとする。
【０１１４】
トラスト記憶部１０には、自身（参加者A）が直接的かつ排他的な経験に基づいて決定した他の参加者に対する基礎トラストがすべて記憶されている。直接の接点がない参加者に対する基礎トラストは0とする。
【０１１５】
ステップＳ１１において、要求受信部１１は、参加者Dから要求<C, P>を受信する。ここで、要求の第１要素Cは計算対象の参加者Cを示す情報であり、要求の第２要素Pは要求の転送に関わった参加者を示す情報の列である。参加者を示す情報とは、例えば、各参加者を一意に識別する識別子である。
【０１１６】
ステップＳ１２において、要求送信部１２は、計算対象の参加者Cへの基礎トラストtACをトラスト記憶部１０から取得し、基礎トラストが存在する（すなわち、tAC≠0）の場合には、応答<tAC, ~tAC>を自身に対して送信する。また、要求送信部１２は、自身からの基礎トラストが存在し、かつ列Pに含まれていない参加者B1, …, Bn（n≧1）に対して、列Pに自身を表す識別子Aを追加した要求<C, P・A>を送信する。その後、要求<C, P・A>を送信した先の参加者B1, …, Bnからの応答を所定の時間待機する。
【０１１７】
ステップＳ１３において、応答受信部１３は、計算対象の参加者Cに関する複数のトラストを受信する。具体的には、参加者B1, …, Bnからの応答<sB1C, SB1C>, …, <sBnC, SBnC>を受信する。このとき、自身に向けて送信した応答<tAC, ~tAC>があれば、参加者B1, …, Bnのいずれか（例えば、Bj（j∈{1, …, n}））からの応答<sBjC, SBjC>として取り扱う。ここで、応答の第１要素sBiC（i=1, …, n）は参加者Biから参加者Cへのトラストであり、応答の第２要素SBiCはトラストsBiCの計算に用いた基礎トラストを示す情報を含む線形項である。基礎トラストを示す情報とは、例えば、各基礎トラストを一意に識別する識別子である。その後、応答受信部１３は、線形項SB1C, …, SBnCにおいて含まれる基礎トラストが重複しないk（≦n）個の応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を選択する。選択した応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>は合成演算部１４へ送られる。
【０１１８】
ステップＳ１４において、合成演算部１４は、並列合成+および直列合成*を用いて複数のトラストを合成し、計算対象の参加者に関するトラスト計算結果を計算する。具体的には、応答<sB'1C, SB'1C>, …, <sB'kC, SB'kC>を用いて、トラスト計算結果sAC=tAB'1*sB'1C+…+tAB'k*sB'kCと線形項SAC=~tAB'1*SB'1C+…+~tAB'k*SB'kCとを計算する。ただし、+はトラストの並列合成を表す演算子であり、*はトラストの直列合成を表す演算子であり、並列合成+および直列合成*は、t≦t' iff ∃t1,t2 t+t1=t2*t'で定義される二項関係≦が、以下の性質を満たすように定義される。
【０１１９】
反射性：t≦t
推移性：t≦t'かつt'≦t"ならばt≦t"
反対称性：t≦t'かつt'≦tならばt=t'
減少性：t*t'≦t'
単調性：t≦t'ならばt"+t≦t"+t'
準分配性：t*(t'+t")≦t*t'+t*t"
強単調性：t≦Δtt'ならばt"+t≦Δtt"+t'かつt"*t≦Δtt"*t'
ただし、t, t', t", Δt, t1, t2は質と量とからなるトラストであり、≦Δtはt≦Δtt' iff t'≦t+Δt∧q(t)≦q(t')を表す。
【０１２０】
このとき、合成演算部１４は、以下の条件を満たすように、トラスト計算結果を計算する。
【０１２１】
１．tをトラスト計算結果とし、t'を計算対象の参加者Cに関する直接的かつ排他的な経験に基づいて決定される基礎トラストの総和とし、t≦t'を満たす。
【０１２２】
２．Tを相異なる二者間の基礎トラストを出力する基礎トラスト付値とし、f(T, P1, P2)を基礎トラスト付値Tにおけるある参加者P1からある参加者P2への計算され得るトラストの全体集合を出力する関数とし、Τ, Τ'をトラスト集合とし、⊆をΤ⊆Τ' iff ∀t∈Τ ∃t'∈Τ' t≦t'で定義される二項関係とし、T+P3P4Δtを基礎トラスト付値Tにおいてある参加者P3からある参加者P4への基礎トラストをΔtだけ増やした基礎トラスト付値とし、ある参加者P2に対する基礎トラストの総和が0ならばf(T, P1, P2)⊆{0}を満たし、かつ、f(T+P3P4Δt, P1, P2)⊆f(T, P1, P2)+Δtを満たす。
【０１２３】
計算したトラスト計算結果sACおよび線形項SACは、応答送信部１５へ送られる。
【０１２４】
ステップＳ１５において、応答送信部１５は、トラスト計算結果sACと線形項SACとからなる応答<sAC, SAC>を要求<C, P>の送信元である参加者Dへ送信する。
【０１２５】
［プライバシ強化］
上述のトラスト計算プロトコルでは、要求の第２要素（要求が辿ってきた参加者の列）や応答の第２要素（線形項）からメッセージの送受信関係がわかる。これはプライバシ漏洩となるおそれがあるため、プロトコルのプライバシ強化を考える。
【０１２６】
秘密計算など高度なセキュリティ技術を適用することでプライバシを強化することは可能であるが、ここではより簡便な方法がプライバシを強化することを考える。幸い上述のトラスト計算プロトコルでは、列や項に対しては要素や辺が出現するかどうかの簡単なチェックしかしていないため、それらをハッシュされた値の集合に置き換えることで、同等な計算を行いつつ、送受関係をある程度隠蔽することができる。
【０１２７】
まず、Aには固有のidAが定められているとする。また、Hを衝突のない一方向性ハッシュ関数とし、||をビット連接とする。要求メッセージは、トラストを計算したい対象Cの識別子idCと、要求が辿ってきた参加者の識別子のハッシュ値の集合-Pの組<idC, -P>とする。応答メッセージは、計算されたトラストsと、応答が辿ってきた参加者の識別子のハッシュ値の集合-Sの組<s, -S>とする。
【０１２８】
AがDから要求<idC, -P>を受け取ったら、以下のステップを順に実行する。
ステップ１．tAC≠0ならば、応答<tAC, {H(idA||idC)}>を自分に送る。
ステップ２．以下の条件を満たすB1, …, Bnを非決定的に選んで、要求<idC, -P∪{H(idA)}>を送る。
・Biは自分自身でもCでもない
・tABiが0でない
・H(idBi)が-Pに含まれない
ステップ３．応答をできるだけ待つ。
ステップ４．得られた応答の中から、その第２要素である集合が互いに同じ要素を含まないように<sB'1C, -SB'1C>, …, <sB'kC, -SB'kC>を非決定的に選ぶ。このとき、ひとつも選ばなかったら、すぐに終了する。選択した応答<sB'1C, -SB'1C>, …, <sB'kC, -SB'kC>を用いて、sAC=tAB'1*sB'1C+…+tAB'k*sB'kC, SAC={H(idA, idB'i)|1≦i≦kかつB'i≠A}∪SB'1C∪…∪SB'kCを計算し、その組<sAC, SAC>をDに送る。ただし、B'i=Aの場合、tAB'i*sB'iCはsB'iCを表すものとする。
【０１２９】
自分がCに対するトラスト計算セッションを開始したいなら、自分自身に要求<idC, 0>を送る。プライバシ強化プロトコルを用いたトラスト計算手順は、基本プロトコルの場合と同様に定めることができる。
【０１３０】
（定理２：プライバシ強化プロトコルに関する健全性と安定性）プライバシ強化プロトコルを用いて定められるトラスト計算手順をfとする。このとき、以下のことが言える。
【０１３１】
１．fの実行中、プライバシ強化プロトコルの参加者が応答の第１要素を決定するときにおいてのみ、上限仮定の範囲内で嘘をつくとする。このとき、fによって計算されたトラストは健全である。
【０１３２】
２．プロトコルの参加者が嘘をつかないならば、fは安定である。
【０１３３】
（定理２の証明）一方向性ハッシュ関数Hに衝突がないため、プライバシ強化プロトコルを基本プロトコルで模擬できる。
【０１３４】
上述のプライバシ強化プロトコルの例ではハッシュ値により経路情報の秘匿化と重複の判定をしたが、情報の秘匿化と秘匿されたままでの経路情報の比較が可能であれば、ハッシュ値に限定されない。
【０１３５】
実施形態のトラスト計算装置においてプライバシ強化プロトコルを実行する場合には、以下のように構成すればよい。要求の第２要素である列Pは、要求の転送に関わった参加者を示す情報を一方向性関数により暗号化してビット連接したものとする。応答の第２要素である線形項は、上記基礎トラストを示す情報を一方向性関数により暗号化してビット連接したものとする。
【０１３６】
［安定性の緩和］
上述したとおり、嘘の上限仮定のもとでも、基本プロトコルを用いて定められるトラスト計算手順は安定ではない。そこで、安定性条件を緩和することを考える。以下では、トラストtの質をp(t)、量をq(t)で表す。
【０１３７】
（定義７：トラスト計算手順の弱安定性）トラスト計算手順fは、任意の相異なる参加者A, Bについて以下の条件を満足するとき、弱安定であるという。
１．TにおけるBの総基礎トラストが0ならば、f(T, A, B)⊆{0}
２．任意の相異なる参加者C, DとトラストΔtについて、f(T+CDΔt, A, B)⊆f(T, A, B)+(max(p(tCD), p(Δt)), q(Δt))
弱安定性は、個々の計算されたトラストの健全性を含意する(max(p(0), p(Bi)), q(Bi))=Biであることから、補題２と同じ議論で、弱い安定性から個々の計算されたトラストの健全性を導くことができる。
【０１３８】
（定理３：基本プロトコルに関する健全性と弱安定性）基本プロトコルを用いて定められるトラスト計算手順をfとする。fの実行中、プロトコルの参加者が応答の第１要素を決定するときにおいてのみ上限仮定の範囲内で嘘をつくとする。さらに、任意の嘘関数LABとトラストΔtについて以下が成り立つことを仮定する。
【０１３９】
【数１９】
2017059975.tif 000021
【０１４０】
このとき、fは弱安定である。
【０１４１】
［質の多値化］
上述の定式化では、質を、信頼する／信頼しない、の2値の割合で表現している。これを3値に拡張することを考える。例えば、信頼する／信頼しない／わからない、の3値を考え、それぞれの割合でトラストを表現することを考える。トラストの合成を定義するためには、いくつかの問いに答える必要がある。例えば、AがBからCに対するトラストの情報を受け取ったとする。
問１．BがCを信頼すると言い、AはBを信頼しないとする。そのとき、AはCを信頼する／信頼しない／わからない？
問２．BがCを信頼しないと言い、AはBを信頼できるかわからないとする。そのときは？
問３．BがCを信頼できるかわからないと言い、AはBを信頼しないとする。そのときは？
問４．BがCを信頼しないと言い、AはBを信頼するとする。そのときは？
問５．BがCを信頼すると言い、AはBを信頼しないとする。そのときは？
ここでは、問１に対してAはCを「信頼しない」、問２に対して「わからない」と答えるとする。すると、*の可換性から、問３の答えは「わからない」でなければならない。また、問４の答えは「信頼しない」が最も妥当だと考えられるが、そのとき同じく可換性から、問５の答えは「信頼しない」でなくてはならない。これらの答えを表にまとめると以下のようになる。
【０１４２】
【表１】
2017059975.tif 000022
【０１４３】
そのとき3値の質を持つトラストを、例えば（(pT, pF), q）という質と量の組として以下のように定義できる。ただし、pTは信頼する割合、pFは信頼しない割合を表し、pT, pF, pT+pF∈[0, 1]と仮定する。並列合成は、2値の場合と同様重み付き平均とする。
【０１４４】
【数２０】
2017059975.tif 000023
【０１４５】
ただし、量が0のとき質は(0, 0)とし、((0, 0), 0)を0と書く。さらに、0+0=0と定める。直列合成は、表１にもとづき以下のように定義する。
【０１４６】
【数２１】
2017059975.tif 000024
【０１４７】
上述した健全性と安定性がこのような多値化においても成り立つが、それを確かめるためには演算と順序の基本性質を証明すればよい。
【０１４８】
この問題にはバリエーションが考えられるが、ここではそのいくつかを検討する。まず、問１に「信頼する」と答える、いわば二重否定を肯定と解釈する場合がある。
【０１４９】
【表２】
2017059975.tif 000025
【０１５０】
表２に基づくと、直列合成の定義は、以下のようになる。しかし、この場合、反対称性が成り立たない。
【０１５１】
【数２２】
2017059975.tif 000026
【０１５２】
次に、問３や問５で上記以外の選択をする、すなわち*の可換性を認めないという場合である。実は健全性を導くのに*の可換性は必須ではない。その代わりに、減少性とともに以下の４'が、準分配性の代わりに以下の６'が成り立てばよい。
４'．右減少性：t'*t≦t'
６'．右準分配性：(t'+t")*t≦t'*t+t"*t
式（５）に示した直列合成のバリエーションの場合、右減少性、右準分配性を含む必要な基本性質が成り立つので、プライバシ強化プロトコルに関する健全性と安定性が成り立つ。一方、問３で「信じない」を答えた場合、反対称性が成り立たない。
【０１５３】
最後に、4値以上の場合を考える。実は、表１はウカシェヴィッチの3値論理における論理積の真理値表となっている。ウカシェヴィッチは一般にn値の多値論理を提示しているが、それらの論理積の解釈を用いて、同様に4値以上のトラストを定義できる。
【０１５４】
［補題１の詳細な証明］
（補題１Ａ）∃t1,t2 t+t1=t2*t'であるとき、一般性を損なうことなく、p(t1)=0, q(t2)=q(t')と仮定できる。
【０１５５】
（補題１Ａの証明）∃t1,t2 t+t1=t2*t'と仮定する。まず、t+t'1=t'2*t'であって、かつq(t'2)=q(t')であるような、t'1, t'2が存在することを示す。
【０１５６】
もしq(t2)>q(t')ならば、t'1=t1, t'2=(p(t2), q(t'))とおくと、t2*t'=(p(t2)・p(t'), q(t'))=t'2*t'となり条件を満たす。もしq(t2)<q(t')ならば、q(t+t1)=q(t2)となる。そこで、t'1=t1+(p(t+t1), q(t')-q(t2)), t'2=(p(t2), q(t'))とおくと、t+t'1=t+t1+(p(t+t1), q(t')-q(t2))=(p(t+t1), q(t'))=(p(t2)・p(t'), min(q(t'), q(t')))=t'2*t'となり条件を満たす。
【０１５７】
次に、t+t"1=t"2*t'であって、かつp(t"1)=0, q(t"2)=q(t'2)であるようなt"1, t"2が存在することを示す。
【０１５８】
【数２３】
2017059975.tif 000027
【０１５９】
質の量辺にr=(q(t)・p(t)-q(t'1)・0)/(q(t)・p(t)+q(t'1)・p(t'1))≦0をかけると、
【０１６０】
【数２４】
2017059975.tif 000028
【０１６１】
である。よって、t"1=(0, q(t'1)), t"2=(r・p(t'2), q(t'2))とすればよい。
【０１６２】
（補題１Ｂ）t≦t' iff q(t)≦q(t')かつq(t)・p(t)≦q(t')・p(t')
（補題１Ｂの証明）まず、∃t1,t2 t+t1=t2*t'を仮定して、q(t)≦q(t')とq(t)・p(t)≦q(t')・p(t')を導く。q(t)=0のときは明らかなので、q(t)≠0と仮定する。
【０１６３】
補題１Ａから、∃t1,t2 t+t1=t2*t'のときp(t1)=0, q(t2)=q(t')と仮定できる。また、そのとき、q(t1)=q(t')-q(t)である。よって、q(t)・p(t)/q(t')=p(t2)・p(t')かつq(t)+q(t1)=q(t')である。p(t2)∈[0, 1]より、q(t)・p(t)/q(t')≦p(t')である。よって、q(t)≧0より、q(t)・p(t)≦q(t')・p(t')である。また、q(t1)≧0より、q(t)≦q(t')である。
【０１６４】
次に、q(t)≦q(t')かつq(t)・p(t)≦q(t')・p(t')と仮定して、∃t1,t2 t+t1=t2*t'を導く。q(t)≦q(t')より、q(t')-q(t)≧0である。さらに、0≦q(t)・p(t)≦q(t')・p(t')より、q(t)・p(t)/q(t')・p(t')∈[0, 1]である。そこで、t1=(0, q(t')-q(t)), t2=(q(t)・p(t)/(q(t')・p(t')), q(t'))とおくと、t+t1=t2*t'である。
【０１６５】
（補題１の証明）補題１Ａ、１Ｂを用いて、補題１を証明する。
１．t1=0, t2=(1, q(t))と取ると、t+t1=t2*t。
２．補題１Ｂより明らか。
３．t≦t'かつt'≦tと仮定する。補題１Ｂより、q(t)≦q(t'), q(t)・p(t)≦q(t')・p(t'), かつq(t')≦q(t), q(t')・p(t')≦q(t)・p(t)。そのときq(t)=q(t')。よってp(t)≦p(t')かつp(t')≦p(t)。したがってp(t)=p(t')。
４．t1=0, t2=tと置くと、t*t'+t1=t2*t'。
５．t≦t'と仮定する。補題１Ｂより、q(t)≦q(t'), q(t)・p(t)≦q(t')・p(t')。よって、q(t")+q(t)≦q(t")+q(t'), q(t")・p(t")+q(t)・p(t)≦q(t")・p(t")+q(t')・p(t')。よってふたたび補題１Ｂよりt"+t≦t"+t'。
６．補題１Ｂより以下の二点（ａ）（ｂ）が証明できればよい。
（ａ）q(t*(t'+t"))≦q(t*t'+t*t")、すなわちmin(q(t), q(t')+q(t"))≦min(q(t), q(t'))+min(q(t), q(t")).
（ｂ）q(t*(t'+t"))・p(t*(t'+t"))≦q(t*t'+t*t")・p(t*t'+t*t")、すなわちmin(q(t), q(t')+q(t"))・p(t)・(q(t')・p(t')+q(t")・p(t"))/(q(t')+q(t"))≦min(q(t), q(t'))・p(t)・p(t')+min(q(t), q(t"))・p(t)・p(t").
一般性を失うことなく、q(t')≦q(t")と仮定できる。以下の４つに場合分けする。
【０１６６】
１．q(t)≦q(t')の場合
（ａ）q(t)≦2q(t)より成り立つ。
（ｂ）q(t)・p(t)・(q(t')・p(t')+q(t")・p(t"))/(q(t')+q(t"))
=(q(t)・p(t)・q(t')・p(t')+q(t)・p(t)・q(t")・p(t"))/(q(t')+q(t"))
=q(t)・p(t)・p(t')・(q(t')/(q(t')+q(t")))+q(t)・p(t)・p(t")・(q(t")/(q(t')+q(t")))
≦q(t)・p(t)・p(t')+q(t)・p(t)・p(t")．
よって成り立つ。
【０１６７】
２．q(t')<q(t)≦q(t")の場合
（ａ）q(t)≦q(t')+q(t)より成り立つ。
（ｂ）q(t)・p(t)・(q(t')・p(t')+q(t")・p(t"))/(q(t')+q(t"))
=q(t')・p(t)・p(t')・(q(t)/(q(t')+q(t")))+q(t)・p(t)・p(t")・(q(t")/(q(t')+q(t")))
≦q(t')・p(t)・p(t')+q(t)・p(t)・p(t")．
よって成り立つ。
【０１６８】
３．q(t")<q(t)≦q(t')+q(t")の場合
（ａ）q(t)≦q(t')+q(t")より成り立つ。
（ｂ）q(t)・p(t)・(q(t')・p(t')+q(t")・p(t"))/(q(t')+q(t"))
=q(t')・p(t)・p(t')・(q(t)/(q(t')+q(t")))+q(t")・p(t)・p(t")・(q(t)/(q(t')+q(t")))
≦q(t')・p(t)・p(t')+q(t")・p(t)・p(t")．
よって成り立つ。
【０１６９】
４．q(t')+q(t")<q(t)の場合
（ａ）q(t')+q(t")≦q(t')+q(t")より成り立つ。
（ｂ）(q(t')+q(t"))・p(t)・(q(t')・p(t')+q(t")・p(t"))/(q(t')+q(t"))
=q(t')・p(t)・p(t')+q(t")・p(t)・p(t").
よって成り立つ。
【０１７０】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１７１】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１７２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１７５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７６】
１  トラスト計算装置
１０  トラスト記憶部
１１  要求受信部
１２  要求送信部
１３  応答受信部
１４  合成演算部
１５  応答送信部
【図１】
2017059975.tif 000029
【図２】
2017059975.tif 000030
【図３】
2017059975.tif 000031
【図４】
2017059975.tif 000032
【図５】
2017059975.tif 000033
【図６】
2017059975.tif 000034
【図７】
2017059975.tif 000035
【図８】
2017059975.tif 000036