System and Method of Reliable Foward Secret Key Sharing with Physical Random Functions
First Claim
1. A method of secret key agreement between a first (16) and a second (18) correspondent, the method comprising the acts of:
- (a) said first correspondent receiving a response A, from a source P (20);
(b) said second correspondent receiving a response B from said source P (20);
(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 (16);
(d) said first correspondent (16) transmitting said (d−
1) parity symbols over a public communication channel (22) to said second correspondent (18); and
(e) said second correspondent (18) generating a word W′
whose input includes said (d−
1) parity symbols and said response B to determine said secret key K.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
38 Claims
-
1. A method of secret key agreement between a first (16) and a second (18) correspondent, the method comprising the acts of:
-
(a) said first correspondent receiving a response A, from a source P (20); (b) said second correspondent receiving a response B from said source P (20); (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 (16);(d) said first correspondent (16) transmitting said (d−
1) parity symbols over a public communication channel (22) to said second correspondent (18); and(e) said second correspondent (18) generating a word W′
whose input includes said (d−
1) parity symbols and said response B to determine said secret key K. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method of secret key agreement between a first and a second correspondent (18), the method comprising the acts of:
-
during an enrollment phase; (a) sending to a source (20), a challenge C, from a first correspondent (16) at a time t1; (b) said first correspondent (16) receiving said response A to said challenge C; (c) sending to said source (20), said challenge, from said second correspondent (18) B at a time t2; (d) said second correspondent (18) receiving a response B to said challenge C. during an encoding phase, said first correspondent (16); (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 (18); (a) using said d−
1 transmitted parity symbols and said response B to construct a word W′
to determine the secret key K. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
16. A method of secret key agreement between a first and a second correspondent (18), the method comprising the acts of:
-
said first correspondent (16) receiving a response A from a source P (20); said second correspondent (18) receiving a response B from said source P (20); said first correspondent (16) 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 (16);said first correspondent (16) transmitting said (d−
1) parity symbols and a pseudo-random function evaluated in A, over a public communication channel to said second correspondent (18); andsaid second correspondent (18) generating a word 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 (16). - View Dependent Claims (17, 18, 19, 20, 21, 22, 23)
-
-
24. A method of secret key agreement between a first and a second correspondent (18), the method comprising the acts of:
-
during an enrollment phase; sending to a source (20), a challenge C, from said first correspondent (16) at a time t1; receiving said response A to said challenge C; sending to said source (20), said challenge C, from said second correspondent (18) at a time t2; during an encoding phase; said first correspondent (16) selecting a secret key K; forming a codeword W using said secret key K, a response A received by said first correspondent (16) 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 (16) to said second correspondent (18) 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 (18) to construct a word W′
to determine the secret key K. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31)
-
-
32. A method of secret key agreement between a first and a second correspondent (18), the method comprising the acts of:
-
said first correspondent (16) receiving a response A from a source P (20), where A is a set of symbols; said second correspondent (18) receiving a response B from said source P (20), where B is a set of symbols; said first correspondent (16) ordering the set of symbols A into a sequence, a1, . . . , aN; said first correspondent (16) computing a pseudo-random function of the ordered set of symbols A, h(A); said first correspondent (16) transmitting h(A)=(h(a1), . . . h(an)) to said second correspondent (18); and
;said second correspondent (18) computing a pseudo-random function of the ordered set of symbols B, h(b) for each symbol b in the set B; said second correspondent (18) computing a set S which includes all positions j for which there exists an element in B such that h(aj)=h(b); said second correspondent (18) transmitting the set S back to said first correspondent (16); and both first and second correspondents (16, 18) extracting a joint key J based on the symbols aj, j in S and for those symbols b in set B for which h(aj)=h(b). - View Dependent Claims (33, 34, 35, 36, 37, 38)
-
Specification