Secure communication

Abstract

“There is disclosed a method for deriving shared secret information between a first device (A) and a second device (B). The method comprises: obtaining, by device A, a data set DA; and obtaining, by device B, a data set DB. Then, for each of N subsets, DAi and DBi, respectively of DA and DB (i=1, 2, . . . , N; N>1) the following steps are carried out: determining, by device A, a first value, VAi=MA(DAi) based on DAi, wherein MA comprises an entropy-reducing function and/or a statistical function; determining, by device B, a second value, VBi=MB(DBi) based on DBi, wherein MB comprises an entropy-reducing function and/or a statistical function; and exchanging one or more messages between devices A and B to determine whether a condition based on the first and second values, VAi and VBi, is satisfied.”

What is claimed is: 
     
         1 . A method for deriving shared secret information between a first device (A) and a second device (B), the method comprising:
 obtaining, by device A, a data set D A ;   obtaining, by device B, a data set D B ;   for each of N subsets, D A   i  and D B   i , respectively of D A  and D B (i=1, 2, . . . , N; N>1):
 determining, by device A, a first value, V A   i =M A (D A   i ) based on D A   i , wherein M A  comprises an entropy-reducing function and/or a statistical function; 
 determining, by device B, a second value, V B   i =M B (D B   i ) based on D B   i , wherein M B  comprises an entropy-reducing function and/or a statistical function; and 
 exchanging one or more messages between devices A and B to determine whether a condition based on the first and second values, V A   i  and V B   i , is satisfied; 
   obtaining, by device A, a reduced data set D A ′ based on those subsets D A   i  for which the condition is satisfied; and   obtaining, by device B, a reduced data set D B ′ based on those subsets D B   i  for which the condition is satisfied.   
     
     
         2 . A method according to  claim 1 , further comprising:
 repeating the steps of determining, exchanging and obtaining a reduced data set one or more times until one or more termination criteria are satisfied,   wherein the data sets used in one iteration comprise the reduced data sets obtained in the preceding iteration.   
     
     
         3 . A method according to  claim 2 , wherein the one or more termination criteria comprise: the number of iterations has reached a predetermined threshold. 
     
     
         4 . A method according to  claim 1 , wherein the data sets, D A  and D B , each comprise data sequences (e.g. bit sequences). 
     
     
         5 . A method according to  claim 1 , wherein the N subsets, D A   i  and D B   i , each comprise mutually exclusive subsets of D A  and D B , respectively. 
     
     
         6 . A method according to  claim 1 , wherein the N subsets, D A   i  and D B   i , each comprise a set of n (e.g. n=4) data elements (e.g. consecutive bits) of D A  and D B , respectively. 
     
     
         7 . A method according to  claim 1 , wherein M A  is the same function as M B . 
     
     
         8 . A method according to  claim 1 , wherein M A  and M B  comprise one or more of: parity function, Hamming distance function, mean function, and variance function. 
     
     
         9 . A method according to  claim 1 , wherein exchanging the messages and determining whether the condition is satisfied comprise:
 transmitting, by device A to device B, the first value, V A ;   transmitting, by device B to device A, the second value, V B ; and   determining, by each of devices A and B, whether the condition is satisfied based on a comparison between the first and second values, V A  and V B .   
     
     
         10 . A method according to  claim 1 , wherein exchanging the messages and determining whether the condition is satisfied comprise:
 transmitting, by one of the devices A and B (device X) to the other one of the devices A and B (device Y), the value V X ;   comparing, by device Y, the values V X  and V Y ; and   transmitting, by device Y to device X, a message indicating the result of the comparison.   
     
     
         11 . A method according to  claim 1 , wherein obtaining the reduced data set, D A ′, comprises:
 for each subset, D X   i , for which the condition is satisfied, obtaining a corresponding subset, D X   i ′, based on D X   i ; and 
 combining the corresponding subsets, D X   i ′, to generate the reduced data set, D X ′. 
 
     
     
         12 . A method according to  claim 11 , wherein a corresponding subset, D X   i ′, comprises one of:
 all elements of D X   i ; 
 a predetermined subset of elements of D X   i ; 
 a function, S, of all elements of D X   i ; and 
 a function, S, of a predetermined subset of elements of D X   i . 
 
     
     
         13 . A method according to  claim 12 , wherein the function, S, comprises a parity function. 
     
     
         14 . A method according to  claim 1 , wherein the data sets D A  and D B  each comprise a random data set. 
     
     
         15 . A computer program comprising instructions which, when the program is executed by a computer or processor, cause the computer or processor to carry out a method according to  claim 1 . 
     
     
         16 . A computer or processor-readable data carrier having stored thereon a computer program according to  claim 15 .