System and method of reliable forward secret key sharing with physical random functions

• US 7,653,197 B2
• Filed: 10/28/2004
• Issued: 01/26/2010
• Est. Priority Date: 10/29/2003
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Van Dijk, Marten E.
• Primary Examiner(s): Chai; Longbit
• Application Number:
  US10/577,756
• Publication Number:
  US 20080044027A1
• Time in Patent Office: 1,916 Days
• Field of Search: 380/44
• US Class Current: 380/44
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes
• CPC Class Codes: H04L 9/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics

Abstract

A secure solution is provided to the problem of secret key agreement. In particular, a method of reliable forward secret key sharing is disclosed between two legitimate correspondents whose profiles match sufficiently. The invention relies on a physical random function, sometimes referred to as a physical unclonable function (PUF) to provide a secure solution to the problem of secret key agreement. In one embodiment, a one-pass protocol is introduced based on Reed-Solomon codes leading to an unconditionally secure solution. In a further embodiment, the solution of the first embodiment is improved upon by providing a conditionally secure solution based on a pseudo random family of functions. In a still further embodiment, a two-pass protocol is introduced which is used exclusively for purposes of identification and authentication. In accordance with the principles of the two-pass protocol, two communications are required and unlike the one-pass protocol, the second correspondent selects the secret key K.

Claims

1. A method of secret key agreement between a first and a second correspondent, the method comprising the acts of:

(a) said first correspondent receiving a response A, from a source P, said first correspondent comprising a first arithmetic logic unit of a processor;

(b) said second correspondent receiving a response B from said source P, said second correspondent comprising a second arithmetic logic unit of a processor;

(c) said first correspondent generating (d−

1) parity symbols as an output of a codeword W whose input includes said response A and a secret key K selected by said first correspondent;

(d) said first correspondent transmitting said (d−

1) parity symbols over a public communication channel to said second correspondent; and

(e) said second correspondent generating a codeword W′

whose input includes said (d−

1) parity symbols and said response B to determine said secret key K;

wherein the secret key K may be determined from said (d−

1) parity symbols and said response B by satisfying an inequality,

dH(A,B)<

=(d−

1−

k)/2

where

dH(A,B) is a Hamming distance between symbol sequences A and B,

d is a minimum distance, and

k is a number of symbols in the secret key K.

2. The method of claim 1, wherein said responses A and B are received by said respective first and second correspondents responsive to a challenge C generated from said respective first and second correspondents.

3. The method of claim 1, wherein said response A is comprised of a sequence of symbols of the form A=(a1, . . . an).

4. The method of claim 1, wherein said response B is comprised of a sequence of symbols of the form B=(b1, . . . bn).

5. The method of claim 1, wherein said secret key K is comprised of a sequence of symbols of the form K=(k1, . . . kk).

6. The method of claim 1, wherein the codeword W′

is a Reed-Solomon codeword.

7. The method of claim 1, wherein the secret key K cannot be determined by someone other than said first and second correspondent if the following inequality is satisfied,

dH(A,E)>

=d−

1

where;

B is a symbol sequence obtained by an attacker attempting to learn the secret key K,

dH(A,E) is a Hamming distance between the symbol sequences A and E.

8. A method of secret key agreement between a first and a second correspondent, the method comprising the acts of:

during an enrollment phase;

(a) sending to a source, a challenge C, from a first correspondent at a time t1, wherein said first correspondent is a first computer;

(b) said first correspondent receiving said response A to said challenge C;

(c) sending to said source, said challenge, from said second correspondent B at a time t2, wherein said second correspondent is a second computer;

(d) said second correspondent receiving a response B to said challenge C,

during an encoding phase, said first correspondent;

(a) selecting a secret key K;

(b) forming a codeword W using said secret key K and said response A to generate (d−

1) parity symbols P;

(c) transmitting said (d−

1) parity symbols P to said second correspondent (18) over a public communication channel;

during a decoding phase, said second correspondent;

(a) using said d−

1 transmitted parity symbols and said response B to construct a codeword W′

to determine the secret key K if said response A and response B match within a selected tolerance;

wherein d is a minimum distance for correcting erasures and errors to provide said second correspondent with an ability in conjunction with said response B to determine the secret key K transmitted from said first correspondent and where d is a distance that enforces a metric on a bit sequence.

9. The method of claim 8, wherein said response A is comprised of a sequence of symbols of the form A=(a1, . . . an).

10. The method of claim 8, wherein said response B is comprised of a sequence of symbols of the form B=(b1, . . . , bn).

11. The method of claim 8, wherein said secret key K is comprised of a sequence of symbols of the form K=(k1, . . . , kk).

12. The method of claim 8, wherein the secret key K may be determined from said codeword W′

if and only if an inequality is satisfied

dH(A,B)<

=(d−

1−

k)/2

where dH(A,B) is a Hamming distance between symbol sequences A and B,

d is the minimum distance, and

k is a number of symbols in the secret key K.

13. The method of claim 8, wherein the codeword W′

is a Reed-Solomon codeword.

14. The method of claim 8, wherein the secret key K cannot be determined from someone other than said first and second correspondent if and only if the following inequality is satisfied:

dH(A,E)>

=d−

1

where

E is a symbol sequence obtained by an attacker attempting to learn the secret key K,

dH(A,E) is a Hamming distance between the symbol sequences A and E.

15. A method of secret key agreement between a first and a second correspondent, the method comprising the acts of:

said first correspondent receiving a response A from a source, wherein said first correspondent is a first computer;

said second correspondent receiving a response B from a source, wherein said second correspondent is a second computer;

said first correspondent generating (d−

1) parity symbols as an output of a codeword W whose input includes said response A and a secret key K selected by said first correspondent;

said first correspondent transmitting said (d−

1) parity symbols and a pseudo-random function evaluated in A, over a public communication channel to said second correspondent; and

said second correspondent generating a codeword W′

whose input includes said (d−

1) parity symbols, said pseudo-random function evaluated A, and said response B, to determine said secret key K selected by said first correspondent if said response B matches response A within a minimum distance for correcting erasures and errors;

wherein d is a minimum distance for correcting erasures and errors to provide said second correspondent with an ability in conjunction with said response B to determine the secret key K transmitted from said first corespondent and wherein d is a distance that enforces a metric on a bit sequence.

16. The method of claim 15, wherein the pseudo-random function is a hash function of the form h(A)=(h(a1), . . . , h(an)), where A is the response A from said source P.

17. The method of claim 15, wherein said response A is comprised of a sequence of symbols of the form A=(a1, . . . an).

18. The method of claim 15, wherein said response B is comprised of a sequence of symbols of the form B=(b1, . . . , bn).

19. The method of claim 15, wherein said secret key K is comprised of a sequence of symbols of the form K=(k1, . . . , kk).

20. The method of claim 15, wherein the secret key K may be determined from said codeword W′

if the inequality is satisfied,

dH(A,B)<

=(d−

1−

k)

where

dH(A,B) is a Hamming distance between symbol sequences A and B,

and

k is a number of symbols in the secret key K.

21. The method of claim 15, wherein the codeword W′

is a Reed-Solomon codeword.

22. The method of claim 15, wherein the secret key K cannot be determined from someone other than said first and second correspondent if the following inequality is satisfied:

dH(A,E)>

=d−

1

where

E is an attacker attempting to learn the secret key K,

dH(A,E) is a Hamming distance between the symbol sequences A and E, and

d is the minimum distance.

23. A method of secret key agreement between a first and a second correspondent, the method comprising the acts of:

during an enrollment phase;

sending to a source, a challenge C, from said first correspondent at a time t1, wherein said first correspondent is a first arithmetic logic unit of a processor;

receiving said response A to said challenge C;

sending to said source, said challenge C, from said second correspondent at a time t2, wherein said second correspondent is a second arithmetic logic unit of a processor;

during an encoding phase;

said first correspondent selecting a secret key K;

forming a codeword W using said secret key K, a response A received by said first correspondent during an enrollment phase and d−

1 parity symbols P;

transmitting said d−

1 parity symbols P and h(A) a pseudo-random function of A from said first correspondent to said second correspondent over a public communication channel;

during a decoding phase;

using said d−

1 transmitted parity symbols and said pseudo-random function evaluated in A by said second correspondent to construct a codeword W′

to determine the secret key K if said response A matches response B match sufficiently;

wherein d is a minimum distance for correcting erasures and errors to provide said second correspondent with an ability in conjunction with said response B to determine the secret key K transmitted from said first correspondent by satisfying a Hamming distance inequality.

24. The method of claim 23, wherein the pseudo-random function is a hash function h(A)=(h(a_—

1), . . . , h(a_n)).

25. The method of claim 23, wherein said response A is comprised of a sequence of symbols of the form A=(a1, . . . an).

26. The method of claim 23, wherein said response B is comprised of a sequence of symbols of the form B=(b1, . . . , bn).

27. The method of claim 23, wherein said secret key K is comprised of a sequence of symbols of the form K=(k1, . . . , kk).

28. The method of claim 23, wherein the secret key K may be determined from said codeword W′

if the inequality is satisfied,

dH(A,B)<

=(d−

1−

k)

where

dH(A,B) is a Hamming distance between symbol sequences A and B,

and

k is a number of symbols in the secret key K.

29. The method of claim 23, wherein the codeword W′

is a Reed-Solomon codeword.

30. The method of claim 23, wherein the secret key K cannot be determined from someone other than said first and second correspondents if the following inequality is satisfied:

dH(A,E)>

=d−

1

where

E is a symbol sequence obtained by an attacker attempting to learn the secret key K,

dH(A,E) is a Hamming distance between the symbol sequences A and E.

31. A method of secret key agreement between a first and a second correspondent, the method comprising the acts of:

said first correspondent receiving a response A from a source P, where A is a set of symbols, said first correspondent being a first computer;

said second correspondent receiving a response B from said source P, where B is a set of symbols, said second correspondent being a second computer;

said first correspondent ordering the set of symbols A into a sequence, a1, . . . , aN;

said first correspondent computing a pseudo-random function of the ordered set of symbols A, h(A);

said first correspondent transmitting h(A)=(h(a1), . . . h(a_j)), where i=1 . . . n, to said second correspondent; and

;

said second correspondent computing a pseudo-random function of the ordered set of symbols B, h(b_j), where j=1 . . . n, for each symbol in the set B;

said second correspondent computing a set S which includes all positions j for which there exists an element in B such that h(a_j)=h(b_j);

said second correspondent transmitting the set S back to said first correspondent; and

both first and second correspondents extracting a joint key J based on the symbols aj, j in S and for those symbols b in set B for which h(a_j)=h(b_j).

32. The method of claim 31, further comprising the act of extracting a secret key K from said joint key J using privacy amplification.

33. The method of claim 32, wherein using said privacy amplification includes using one of a random matrix multiplier for multiplication with the joint key J and the joint key J evaluated in a hash function.

34. The method of claim 31, wherein said responses A and B are received by said respective first and second correspondents responsive to a challenge C generated from said respective first and second correspondents.

35. The method of claim 31, wherein said response A is comprised of a sequence of symbols of the form A=(a1, . . . a_j).

36. The method of claim 31, wherein said response B is comprised of a sequence of symbols of the form B=(b1, . . . , b_j).

37. The method of claim 31, wherein said secret key K is comprised of a sequence of symbols of the form K=(k1, . . . , kk).