System and method for utility sampling for trust metrics in pki

1. A computer implemented method for measuring trust in a transaction over a public key certificate network, the method performed by the computer comprising the steps of:

providing a public key certificate network comprising a directed acyclic graph whose nodes are public keys and wherein an edge K A →K B implies an owner of public key K A is in possession of a certificate for public key K B ;

associating each edge K A →K B of said public key certificate network connecting two public keys K A , owned by A, and K B , owned by B, with a probability p, according to A, that information about K B is reliable, and a confidence c that is a total dollar amount of transactions which have involved using edge K A →K B ;

forming one or more authentication paths in said public key certificate network starting from a certificate authority having public key K S and ending with a target public key K T ;

calculating a limit l on an amount of insurance that an owner of K S is willing to provide to a user interested in a transaction with an owner of K T ; and

for each amount m<l, calculating a premium for which the owner of K S is willing to sell insurance to said user for an amount of m, by

calculating a maximum amount insurable, f i , for each authentication path i, and

calculating an insurance premium rate s i for each authentication path by calculating, for each public key node in said authentication path, starting at K S , s i from a formula

( s i −a i ) p i −(1−δ i )(1 −p i )=γ,

wherein p i is a probability of accuracy for each authentication path i, S i is the selling price of said premium, a i is an amount that S, the owner of K S , pays to A, the owner of K A for insuring δ i , fraction of the amount, and γ is a fraction expected profit per transaction expected by S, and wherein for each subsequent public key node A i in said authentication path, the associated s i , will be the a i , paid from A i 's predecessor node and the a i , will be the amount paid to A i 's successor node.

2. The method of claim 1 , wherein said probability p and confidence c associated with each edge K A →K B are calculated using utility sampling.

3. The method of claim 2 , wherein using utility sampling comprises A acquiring over a time interval r positive observations and s negative observations of a reliability of information provided by B, wherein said edge probability

p

=

(

r

+

1

r

+

s

+

2

)

and said edge confidence c=r+s.

4. The method of claim 1 , wherein a total probability associated with an authentication path that terminates at said target key K T is a product of the probability of each edge in said authentication path, and a total confidence associated with said authentication path that terminates at said target key K T is a minimum value of the confidence values associated with each edge of said authentication path.

5. The method of claim 1 , wherein calculating said limit l on an amount of insurance for said one or more authentication paths ending with target public key K T comprises calculating a maximum K S -K T flow f in said directed graph, with a flow capacity on each edge being the c value of the edge.

6. The method of claim 5 , wherein calculating a premium for each amount m<l further comprises:

sorting the authentication paths in increasing order of rate S i , wherein said authentication paths are labeled P 1 to P n in increasing order of rate s i wherein n is a number of authentication paths; and

calculating said premium for said amount m<l from said sorted premium rates S i .

7. The method of claim 6 , wherein calculating said premium for said amount m<l comprises insuring a first f 1 dollars out of m according to P 1 using rate s 1 , and insuring subsequent amounts using each successive path P i using rate s i until all m dollars are allocated.

8. The method of claim 6 , wherein calculating said premium for said amount m<l comprises insuring a first f 1 dollars out of m at an average premium rate over all paths P i , and insuring subsequent amounts an average premium rate excluding a rate associated with the amount already insured, until all m dollars are allocated.

9. The method of claim 1 , further comprising: providing a list K T1 , . . . , K ti , . . . , K Tn of all public keys that B is attesting, wherein (p i , c i ) are the (p, c) values estimated by B about K Ti ;

having A attest T i for each i via B after a time period using Δc i additional samples wherein Δr i of the samples show positive behavior by T i ; and

updating the probability associated with each edge K A →K B from

p

K

A

→

K

B

←

p

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

⁡

(

1

-



1

-

Δ

⁢

⁢

r

i

⁢

p

i

Δ

⁢

⁢

c

i



)

c

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

,

and the confidence associated with each edge K A →K B from

c

K

A

→

K

B

←

c

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

.

10. A computer implemented method for measuring trust in a transaction over a public key certificate network, the method performed by the computer comprising the steps of:

providing a public key certificate network comprising a directed acyclic graph whose nodes are public keys and wherein an edge K A →K B implies an owner of public key K A is in possession of a certificate for public key K B ;

associating each edge K A →K B of said public key certificate network connecting two public keys K A , owned by A, and K B , owned by B, with a probability p, according to A, that information about K B is reliable, and a confidence c that is a total dollar amount of transactions which have involved using edge K A →K B ;

using utility sampling to estimate p and c by having A acquire over a time interval r positive observations and s negative observations of a reliability of information provided by B, wherein said edge probability

p

=

(

r

+

1

r

+

s

+

2

)

 and said edge confidence c=r+s;

forming one or more authentication paths in said public key certificate network starting from a certificate authority having public key K S and ending with a target public key K T ; and

calculating a limit l on an amount of insurance that an owner of K S is willing to provide to a user interested in a transaction with an owner of K T , and for each amount m<l, calculating a premium for which the owner of K S is willing to sell insurance to said user for an amount of m by calculating an insurance premium rate S i for each authentication path P i =V, i1 , V i2 , . . . , V im , wherein V i1 is a starting node S associated with public key K S and V im is target node T associated with public key K T by inductively calculating, for each public key node in said authentication path, starting at K S , s i from a formula

( b i(j−1) −b ij δ ij ) q ij −(1−δ ij )(1 −q ij )=γ

wherein b ij is the premium per unit insured amount price V ij pays V i(j+1) , and b i0 is the premium S i that the customer pays to the top node V i1 =S, q ij· =p ij ×p i(j+1) × . . . ×p i(m−1) is the accuracy of the path from V ij to V im for all j=1 to m−1 where p ij is the probability of accuracy on the edge V ij to V i(j+1) , wherein when j=m, δ im =0 and

b

i

⁡

(

m

-

1

)

=

(

1

-

q

i

⁡

(

m

-

1

)

)

+

γ

q

i

⁡

(

m

-

1

)

.

11. The method of claim 10 , wherein a total probability associated with an authentication path that terminates at said target key K T is a product of the probability of each edge in said authentication path, and a total confidence associated with said authentication path that terminates at said target key K T is a minimum value of the confidence values associated with each edge of said authentication path.

12. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for measuring trust in a transaction over a public key certificate network, the method comprising the steps of:

providing a public key certificate network comprising a directed acyclic graph whose nodes are public keys and wherein an edge K A →K B implies an owner of public key K A is in possession of a certificate for public key K B ;

associating each edge K A →K B of said public key certificate network connecting two public keys K A , owned by A, and K B , owned by B, with a probability p, according to A, that information about K B is reliable, and a confidence c that is a total dollar amount of transactions which have involved using edge K A →K B ;

forming one or more authentication paths in said public key certificate network starting from a certificate authority having public key K S and ending with a target public key K T ;

calculating a limit l on an amount of insurance that an owner of K S is willing to provide to a user interested in a transaction with an owner of K T ; and

for each amount m<l, calculating a premium for which the owner of K S is willing to sell insurance to said user for an amount of m, by

calculating a maximum amount insurable, f i , for each authentication path i, and

calculating an insurance premium rate s i for each authentication path by calculating, for each public key node in said authentication path, starting at K S , s i , from a formula

( s i −a i ) p i −(1−δ i )(1 −p i )=γ,

wherein p i is a probability of accuracy for each authentication path i, s i is the selling price of said premium, a i is an amount that S, the owner of K S , pays to A, the owner of K A for insuring δ i fraction of the amount, and γ is a fraction expected profit per transaction expected by S, and wherein for each subsequent public key node A i in said authentication path, the associated s i will be the a i paid from A i 's predecessor node and the a i will be the amount paid to A i 's successor node.

13. The computer readable program storage device of claim 12 , wherein said probability p and confidence c associated with each edge K A →K B are calculated using utility sampling.

14. The computer readable program storage device of claim 13 , wherein using utility sampling comprises A acquiring over a time interval r positive observations and s negative observations of a reliability of information provided by B, wherein said edge probability

p

=

(

r

+

1

r

+

s

+

2

)

and said edge confidence c=r+s.

15. The computer readable program storage device of claim 12 , wherein a total probability associated with an authentication path that terminates at said target key K T is a product of the probability of each edge in said authentication path, and a total confidence associated with said authentication path that terminates at said target key K T is a minimum value of the confidence values associated with each edge of said authentication path.

16. The computer readable program storage device of claim 12 , wherein calculating said limit l on an amount of insurance for said one or more authentication paths ending with target public key K T comprises calculating a maximum K S −K T flow f in said directed graph, with a flow capacity on each edge being the c value of the edge.

17. The computer readable program storage device of claim 16 , wherein calculating a premium for each amount m<l comprises:

sorting the authentication paths in increasing order of rate s i , wherein said authentication paths are labeled P 1 to P n , in increasing order of rate s i , wherein n is a number of authentication paths; and

calculating said premium for said amount m<l from said sorted premium rates s i .

18. The computer readable program storage device of claim 17 , wherein calculating said premium for said amount m<l comprises insuring a first f 1 dollars out of m according to P 1 using rate s 1 , and insuring subsequent amounts using each successive path P i , using rate s i until all m dollars are allocated.

19. The computer readable program storage device of claim 17 , wherein calculating said premium for said amount m<l comprises insuring a first f 1 dollars out of m at an average premium rate over all paths P i , and insuring subsequent amounts an average premium rate excluding a rate associated with the amount already insured, until all m dollars are allocated.

20. The computer readable program storage device of claim 12 , the method further comprising:

providing a list K T1 , . . . , K ti , . . . , K Tn of all public keys that B is attesting, wherein (p i , c i ) are the (p, c) values estimated by B about K Ti ;

having A attest T i for each i via B after a time period using Δc i additional samples wherein Δr i of the samples show positive behavior by T i ; and

updating the probability associated with each edge K A →K B from

p

K

A

→

K

B

←

p

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

⁡

(

1

-



1

-

Δ

⁢

⁢

r

i

⁢

p

i

Δ

⁢

⁢

c

i



)

c

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

,

and the confidence associated with each edge K A →K B from

c

K

A

→

K

B

←

c

K

A

→

K

B

+

∑

i

⁢

Δ

⁢

⁢

c

i

.

21. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for measuring trust in a transaction over a public key certificate network, the method comprising the steps of:

providing a public key certificate network comprising a directed acyclic graph whose nodes are public keys and wherein an edge K A →K B implies an owner of public key K A is in possession of a certificate for public key K B ;

associating each edge K A →K B of said public key certificate network connecting two public keys K A , owned by A, and K B , owned by B, with a probability p, according to A, that information about K B is reliable, and a confidence c that is a total dollar amount of transactions which have involved using edge K A →K B ;

using utility sampling to estimate p and c by having A acquire over a time interval r positive observations and s negative observations of a reliability of information provided by B, wherein said edge probability

p

=

(

r

+

1

r

+

s

+

2

)

 and said edge confidence c=r+s;

forming one or more authentication paths in said public key certificate network starting from a certificate authority having public key K S and ending with a target public key K T ; and

calculating a limit l on an amount of insurance that an owner of K S is willing to provide to a user interested in a transaction with an owner of K T , and for each amount m<l, calculating a premium for which the owner of K S is willing to sell insurance to said user for an amount of m by calculating an insurance premium rate s i for each authentication path P i =V i1 , V i2 , . . . , V im , wherein V i1 is a starting node S associated with public key K S and V im is target node T associated with public key K T by inductively calculating, for each public key node in said authentication path, starting at K S , s i from a formula

( b i(j−1) −b ij δ ij ) q ij −(1−δ ij )(1 −q ij )=γ

wherein b ij is the premium per unit insured amount price V ij pays V i(j+1 ), and b i0 is the premium S i that the customer pays to the top node V i1 =S, q ij· =p ij ×p i(j+1) × . . . ×p i(m−1 ) is the accuracy of the path from V ij to V im for all j=1 to m−1 where p ij is the probability of accuracy on the edge V ij to V i(j+1) , wherein when j=m, δ im =0 and

b

i

⁡

(

m

-

1

)

=

(

1

-

q

i

⁡

(

m

-

1

)

)

+

γ

q

i

⁡

(

m

-

1

)

.

22. The computer readable program storage device of claim 21 , wherein a total probability associated with an authentication path that terminates at said target key K T is a product of the probability of each edge in said authentication path, and a total confidence associated with said authentication path that terminates at said target key K T is a minimum value of the confidence values associated with each edge of said authentication path.