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 D.sub.A; and obtaining, by device B, a data set D.sub.B. Then, for each of N subsets, D.sub.A.sup.i and D.sub.B.sup.i, respectively of D.sub.A and D.sub.B (i=1, 2, . . . , N; N>1) the following steps are carried out: determining, by device A, a first value, V.sub.A.sup.i=M.sub.A(D.sub.A.sup.i) based on D.sub.A.sup.i, wherein M.sub.A comprises an entropy-reducing function and/or a statistical function; determining, by device B, a second value, V.sub.B.sup.i=M.sub.B(D.sub.B.sup.i) based on D.sub.B.sup.i, wherein M.sub.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.sub.A.sup.i and V.sub.B.sup.i, is satisfied.

Claims

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.sub.A; obtaining, by device B, a data set D.sub.B; for each of N subsets, D.sub.A.sup.i and D.sub.B.sup.i, respectively of D.sub.A and D.sub.B(i=1, 2, . . . , N; N>1): determining, by device A, a first value, V.sub.A.sup.i=M.sub.A(D.sub.A.sup.i) based on D.sub.A.sup.i, wherein M.sub.A comprises an entropy-reducing function and/or a statistical function; determining, by device B, a second value, V.sub.B.sup.i=M.sub.B(D.sub.B.sup.i) based on D.sub.B.sup.i, wherein M.sub.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.sub.A.sup.i and V.sub.B.sup.i, is satisfied; obtaining, by device A, a reduced data set D.sub.A based on those subsets D.sub.A.sup.i for which the condition is satisfied; and obtaining, by device B, a reduced data set D.sub.B based on those subsets D.sub.B.sup.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.sub.A and D.sub.B, each comprise data sequences (e.g. bit sequences).

5. A method according to claim 1, wherein the N subsets, D.sub.A.sup.i and D.sub.B.sup.i, each comprise mutually exclusive subsets of D.sub.A and D.sub.B, respectively.

6. A method according to claim 1, wherein the N subsets, D.sub.A.sup.i and D.sub.B.sup.i, each comprise a set of n (e.g. n=4) data elements (e.g. consecutive bits) of D.sub.A and D.sub.B, respectively.

7. A method according to claim 1, wherein M.sub.A is the same function as M.sub.B.

8. A method according to claim 1, wherein M.sub.A and M.sub.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.sub.A; transmitting, by device B to device A, the second value, V.sub.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.sub.A and V.sub.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.sub.X; comparing, by device Y, the values V.sub.X and V.sub.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.sub.A, comprises: for each subset, D.sub.X.sup.i, for which the condition is satisfied, obtaining a corresponding subset, D.sub.X.sup.i, based on D.sub.X.sup.i; and combining the corresponding subsets, D.sub.X.sup.i, to generate the reduced data set, D.sub.X.

12. A method according to claim 11, wherein a corresponding subset, D.sub.X.sup.i, comprises one of: all elements of D.sub.X.sup.i; a predetermined subset of elements of D.sub.X.sup.i; a function, S, of all elements of D.sub.X.sup.i; and a function, S, of a predetermined subset of elements of D.sub.X.sup.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.sub.A and D.sub.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.

Description

BRIEF DESCRIPTION OF THE FIGURES

[0016] FIG. 1 illustrates the relationship between various quantities related to three random variables X, Y and Z;

[0017] FIG. 2 is a flow chart of an exemplary method for deriving shared secret information between a first device (device A) and a second device (device B);

[0018] FIG. 3 illustrates an example of deriving reduced data sets based on data sets;

[0019] FIG. 4 is a message flow diagram of a first exemplary technique for deriving shared secret information;

[0020] FIG. 5 is a message flow diagram of a second exemplary technique for deriving shared secret information; and

[0021] FIG. 6 is a block diagram of an exemplary device for deriving secret information shared with another device.

DETAILED DESCRIPTION

[0022] The following description of examples of the present disclosure, with reference to the accompanying drawings, is provided to assist in a comprehensive understanding of the present invention, as defined by the claims. The description includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the examples described herein can be made.

[0023] Certain examples of the present disclosure provide one or more techniques for deriving shared secret information between two or more devices (or apparatus). Certain examples of the present disclosure provide one or more techniques for performing a secure operation, for example secure communication, using the shared secret information.

[0024] A device capable of implanting one or more techniques described herein may be of any suitable type, for example a mobile device (such as a mobile telephone), a computer terminal, a relay device, a server, a node in a network (such as the Internet or a private network) or any other suitable type of device for communicating. Furthermore, such a device may be a manually operated device (e.g. one operated by a user), or may be a device that is partially or fully automated. In certain examples, one or more more of the techniques described herein may be applied to communication between internal components of one or more devices. Accordingly, references herein to a device that communicates with another device may also include references to an internal component of a device that communicates with another internal component of either the same device or a different device.

[0025] The techniques described herein may be used in a wide variety of different applications, including, but not limited to, financial transactions, Police, Armed Forces, Government, mobile data, mobile voice, navigation and location information (e.g. GPS), financial services, banking, shipping communications, subscriber services, mobile security services, distributed networking, remote access, Internet communications, virtual private networks, satellite communications, remote command and control systems, aircraft (e.g. drone aircraft), remote control, data storage and archiving, and identity management and security. The skilled person will appreciate that shared secret information obtained using one or more techniques described herein may be used in any suitable type of secure operation, not limited to secure communication.

[0026] The skilled person will appreciate that the techniques described herein may be used to enable a set of two or more devices to obtain shared secret information (i.e. obtain information that is known to those devices but not to any other entity). In certain examples, the techniques may be used by devices A and B to obtain first shared secret information (shared between A and B). In certain examples, the techniques may be also used by devices A and C to obtain second shared secret information (shared between A and C). In certain examples, the techniques may be used by a set of three or more devices {A, B, C, . . . } to obtain third shared secret information (shared between {A, B, C, . . . }).

[0027] Before proceeding with the following description, certain useful concepts in the field of information theory will now be briefly described.

[0028] Consider a discrete random variable, X, characterised by the probability distribution function P.sub.X. The entropy H of X is defined by:

[00001]$\begin{array}{cc}H\left(X\right)=-\underset{xX}{.Math.}{P}_x\left(x\right){\log }_b\left(P_x\left(x\right)\right)& \mathrm{Eq}.1\end{array}$

[0029] In Equation 1, x denotes a particular outcome of X, P.sub.X(x) is the probability of outcome x, and b is an arbitrary logarithmic base which determines the unit of the entropy. Frequently, the base b is chosen to be 2, in which case the unit of entropy is bits. The entropy of X may be regarded as a measure of the uncertainty associated with outcomes of X. One interpretation is that the entropy (in bits) gives the average number of yes/no type questions needed to guess an outcome of X, when using an optimum guessing strategy, and is the average number of bits per outcome needed to encode a sequence of outcomes of X.

[0030] The conditional entropy H(X|Y) for discrete random variables X and Y is defined by:

[00002]$\begin{array}{cc}H\left(X.Math.Y\right)=\underset{yY}{.Math.}{P}_Y\left(Y\right)\left[-\underset{xX}{.Math.}{P}_{X.Math.Y}\left(x.Math.y\right){\log }_b\left(P_{X.Math.Y}\left(x.Math.y\right)\right)\right]=-\underset{\underset{yY}{xX}}{.Math.}{P}_{\mathrm{XY}}\left(x,y\right){\log }_b\left(P_{X.Math.Y}\left(x.Math.y\right)\right)& \mathrm{Eq}.2\end{array}$

[0031] In Equation 2, x and y denote, respectively, particular outcomes of X and Y, P.sub.X(x) and P.sub.Y(y) are the probabilities, respectively, of outcomes x and y, P.sub.X|Y(x|y) is the conditional probability of outcome x given outcome y, P.sub.XY(x,y) is the joint probability distribution of X and Y, and b is an arbitrary logarithmic base. The conditional entropy H(X|Y) may be interpreted as a measure of the uncertainty in X after observing Y.

[0032] The mutual information |(X;Y) for discrete random variables X and Y is defined by:

[00003]$\begin{array}{cc}I\left(X;Y\right)=\underset{\underset{yY}{xX}}{.Math.}{P}_{\mathrm{XY}}\left(x,y\right){\log }_b\frac{P_{\mathrm{XY}}\left(x,y\right)}{P_X\left(x\right)P_Y\left(y\right)}=H\left(X\right)-H\left(X.Math.Y\right)& \mathrm{Eq}.3\end{array}$

[0033] In Equation 3, x and y denote, respectively, particular outcomes of X and Y, P.sub.X(x) and P.sub.Y(y) are the probabilities, respectively, of outcomes x and y, P.sub.XY(x,y) is the joint probability distribution of X and Y, and b is an arbitrary logarithmic base.

[0034] From Equation 3, it can be seen that the mutual information |(X;Y) may be interpreted as the reduction in uncertainty in X after observing Y. Equivalently, the mutual information |(X;Y) may be interpreted as the amount of information gained about X after observing Y, or as the amount of information shared between X and Y. If X and Y are relatively highly correlated, then the mutual information |(X;Y) will be relatively high. Conversely, if X and Y are relatively lowly correlated, then the mutual information |(X;Y) will be relatively low. If X and Y are totally uncorrelated then |(X;Y)=0 while if X=Y then |(X;Y)=H(X). Mutual information is symmetric in its arguments: |(X;Y)=|(Y;X).

[0035] As an example, in the one-time pad scheme described above, the mutual information between the message M and the enciphered message M.sup. is equal to zero, /(M;M.sup.)=0. Thus, Eve gains no information about the message M from the enciphered message M.sup.. It is this property which makes the one-time pad scheme described above unconditionally secure as long as the one time pad remains secret.

[0036] The definitions of conditional entropy and mutual information given above may be extended to consider more than two discrete random variables. For example, in the case of three discrete random variables X, Y and Z, the conditional entropy H(X|YZ) may be interpreted as the uncertainty in X after observing Y and Z. The mutual information |(X;Y;Z) may be interpreted as the information shared between X, Y and Z. The mutual information |(X;Y|Z) may be interpreted as the information shared between X and Y that is not shared with Z.

[0037] The relationships between various quantities related to random variables can be represented schematically by a venn-type diagram. For example, FIG. 1 illustrates the relationship between various quantities related to three random variables X, Y and Z. The three overlapping circles represent H(X), H(Y) and H(Z), respectively. The quantities |(X;Y), H(Y|X), H(Z|XY), |(X;Y|Z) and |(X;Y;Z) are indicated by shaded regions. The areas representing the conditional entropy and mutual information for other combinations of variables in FIG. 1 can be deduced by symmetry.

[0038] Various exemplary techniques for deriving shared secret information between a first device and a second device will now be described. In the following examples, the first device may be referred to as device A (Alice) and the second device may be referred to as device B (Bob). However, the skilled person will appreciate that these labels are merely exemplary.

[0039] FIG. 2 is a flow chart of an exemplary technique for deriving shared secret information between device A and device B. The left hand side of FIG. 2 illustrates operations carried out by device A and the right hand side of FIG. 2 illustrates operations carried out by device B.

[0040] In this technique, devices A and B separately obtain respective non-identical data sets (e.g. bit sequences). Then, by performing various operations and message exchanges, each device derives respective reduced data sets including by selectively discarding and retaining certain elements of the original data sets, such that the reduced data sets tend to comprise a higher proportion of matching elements (e.g. matching bits) than the original data sets. The decisions about which elements to discard and retain are made based on computing an entropy-reducing function or a statistical function (e.g. a parity fuction) of subsets of the data sets.

[0041] A statistical function may comprise a function in which the output comprises statistical information based on the input. For example, a statistical function may be regarded as a function in which the output summarises the input in some respect. An entropy-reducing function may comprise a function that reduces the information content, or entropy, of the input to generate the output. For example, the information content or entropy may be defined in accordance with any suitable known definition used in information theory. An entropy-reducing function may be regarded as a function in which the output has a lower complexity than the input. In certain examples, a statistical function may be regarded as a type of entropy-reducing function. However, in other examples, the output of a statistical function does not necessarily have a lower entropy than the input, depending on the definitions used. The use of an entropy-reducing function or a statistical function reduces the amount of information about the data sets revealed to a potential eavesdropper.

[0042] FIG. 3 illustrates an example of deriving reduced data sets from data sets.

[0043] These steps will now be described in greater detail with reference to FIGS. 2 and 3.

[0044] In step 201A, device A obtains a first data set D.sub.A.

[0045] In a corresponding step 201B, device B obtains a second data set D.sub.B.

[0046] The data sets, D.sub.A and D.sub.B may each comprise an indexable set of elements, where each element may take one of two or more values. For example, the data sets, D.sub.A and D.sub.B, may each comprise data sequences (e.g. bit sequences).

[0047] The data sets D.sub.A and D.sub.B may each comprise a random data set. However, in other examples, the data sets may be non-random.

[0048] The data sets, D.sub.A and D.sub.B, may be non-identical. However the data sets should comprise at least some matching elements (e.g. at least some elements of D.sub.A have the same value as the corresponding elements of D.sub.B at the same index value). For example, in the case that the data sets comprise sequences of bits the bit values of D.sub.A an D.sub.B match at at least some bit positions. In this case, there is at least some information overlap between the data sets: I(D.sub.A; D.sub.B)>0. Certain techniques described herein aim to increase the information overlap, for example until the data sets are identical or differ by less than a certain threshold.

[0049] The data sets D.sub.A and D.sub.B should remain confidential (i.e. remain unknown to unauthorised parties, such as a potential eavesdropper).

[0050] Devices A and B may obtain the data sets D.sub.A and D.sub.B using any suitable technique. For example, a random data set may be generated based on a pseudorandom number generator. In other examples, a random data set may be obtained based on one or more natural sources of randomness. For example, a known data set may be encoded into a signal and then the signal may be transmitted through a noisy communication channel to a device. The device may then compare the known data set with the data set obtained from the received signal to obtain an error signal that forms the data set. Alternatively or additionally, a random data set may be obtained by sampling random noise of an electronic component. In certain examples, a non-random data set may be obtained by sampling an audio signal (e.g. obtained using a microphone) and/or an image signal (e.g. obtained using an imaging device). In another example, a non-random data set may comprise a predetermined data set.

[0051] In the following, it is assumed that the data sets D.sub.A and D.sub.B comprise sequences of bits. However, the skilled person will appreciate that the techniques described herein apply to other types of data sets.

[0052] FIG. 3 illustrates an exemplary data set D.sub.A 301A comprising a 16-bit sequence [0101 1100 0111 0010] and an exemplary data set D.sub.B 301B comprising a 16-bit sequence [0101 1111 1001 0010].

[0053] Following steps 201A and 201B, various steps are carried out as described below to derive, from data sets D.sub.A and D.sub.B, respective reduced data sets D.sub.A and D.sub.A, comprising a higher proportion of matching elements (e.g. matching bits) than data sets D.sub.A and D.sub.B. In particular, subsets of D.sub.A and corresponding subsets of D.sub.B are considered individually. An entropy-reducing function or a statistical function is computed based on each subset, and elements of D.sub.A and D.sub.B are discarded or retained based on the results. These steps will now be described in more detail.

[0054] For each of N subsets, D.sub.A.sup.i and D.sub.B.sup.i, respectively of D.sub.A and D.sub.B(i=1, 2, . . . , N; N>1), the following steps 203A, 203B, 205A (including 205A) and 205B (including 205B) are carried out. This repetition is illustrated in FIG. 2 as the loop for i=1 to N and next i indicated with a dotted line. Each repetition of the loop corresponds to processing of a single pair of corresponding subsets DAi and D.sub.B.sup.i with a certain index value i (i=1, 2, . . . , N; N>1).

[0055] The N subsets, D.sub.A.sup.i and D.sub.B.sup.i, may each comprise mutually exclusive subsets of D.sub.A and D.sub.B, respectively. For example, the N subsets, D.sub.A.sup.i and D.sub.B.sup.i, may each comprise a set of n (e.g. n=4) data elements (e.g. consecutive bits) of D.sub.A and D.sub.B, respectively. Corresponding subsets of D.sub.A and D.sub.B may comprise elements of the respective data sets having the same index. For example, first corresponding subsets may comprise the the first four (or any other suitable number) bits of D.sub.A and D.sub.B, second corresponding subset may comprise the next four bits D.sub.A and D.sub.B, and so on. In other examples, the bits of a subset need not comprise a contiguous set of bits. The subsets may comprise the same number of bits. However, in other examples, at least some subsets may have different sizes.

[0056] FIG. 3 illustrates each data set D.sub.A 301A and D.sub.B 301B divided into four exemplary subsets of four consecutive bits each. In this example, D.sub.A.sup.1=[0101], D.sub.A.sup.2=[1100], D.sub.A.sup.3=[0111] and D.sub.A.sup.4=[0010] and D.sub.B.sup.1=[0101], D.sub.B.sup.2=[1111], D.sub.B.sup.3=[1001] and D.sub.B.sup.4=[0010].

[0057] In step 203A, device A determines a first value, V.sub.A.sup.i=M.sub.A(D.sub.A.sup.i) based on D.sub.A.sup.i. In certain examples, M.sub.A may comprise an entropy-reducing function or a statistical function. In certain examples, M.sub.A may comprise a filtering function.

[0058] In a corresponding step 203B, device B determines a second value, V.sub.B.sup.i=M.sub.B(D.sub.B.sup.i) based on D.sub.B.sup.i . In certain examples, M.sub.B may comprise an entropy-reducing function or a statistical function. In certain examples, M.sub.B may comprise a filtering function.

[0059] M.sub.A may be the same function as M.sub.B. For example, M.sub.A and/or M.sub.B may comprise one or more of: parity function, Hamming distance function, mean function, and variance function. When applied to bit sequences, these functions may be defined as follows. [0060] Given an ith subset D.sub.A.sup.i=[a.sub.0, a.sub.1, . . . , a.sub.j, . . . , a.sub.n], a.sub.j {0,1}, the parity value of D.sub.A.sup.i may be defined as:

[00004]$M_A\left(D_A^i\right)=\left(\underset{j=0}{\overset{n}{.Math.}}{a}_j\right)\mathrm{Mod}\left(2\right)$ [0061] Given an ith subset D.sub.A.sup.i=[a.sub.0, a.sub.1, . . . , a.sub.j, . . . , a.sub.n], a.sub.j {0,1}, and given a code B.sup.i=[b.sub.0, b.sub.1, . . . , b.sub.j, . . . , b.sub.n], b.sub.j {0,1}, the Haming Distance (HD) of D.sub.A.sup.i with respect to Bi may be defined as:

[00005]$\mathrm{HD}\left(D_A^i,B^i\right)=\underset{j=0}{\overset{n}{.Math.}}\left(\left(a_j+b_j\right)\mathrm{Mod}\left(2\right)\right)$

[0062] For example, the code B.sup.i may be a one-time code comprising random bits defined for the ith subset.

[0063] A two-part value may be defined as M.sub.A (D.sub.A.sup.i)=[HD(D.sub.A.sup.i, B.sup.i), B.sup.i] [0064] Given an ith subset D.sub.A.sup.i=[a.sub.0, a.sub.1, . . . , a.sub.j, . . . , a.sub.n], a.sub.j {0,1}, the mean value of D.sub.A.sup.i may be defined as:

[00006]$M_A\left(D_A^i\right)=\frac{1}{n}\left(\underset{j=0}{\overset{n}{.Math.}}{a}_j\right)=\stackrel{\_}{a}$ [0065] Given an ith subset D.sub.A.sup.i=[a.sub.0, a.sub.1, . . . , a.sub.j, . . . , a.sub.n], a.sub.j {0,1}, the variance value of D.sub.A.sup.i may be defined as:

[00007]$M_A\left(D_A^i\right)=\frac{1}{n-1}\underset{j=0}{\overset{n}{.Math.}}{\left(a_j=\stackrel{\_}{a}\right)}^2$

[0066] The function M.sub.B (D.sub.A.sup.i) in each of the above examples may be defined similarly.

[0067] FIG. 3 illustrates an example in which the values V.sub.A.sup.i 303A are derived from the subsets D.sub.A.sup.i 310A, and in which the values V.sub.B.sup.i 303B are derived from the subsets D.sub.B 301B, using a partiy function. For example:

[00008]$\begin{array}{cc}{D}_A^1=\left[0101\right].fwdarw.V_A^1=\left[0\right]& D_B^1=\left[0101\right].fwdarw.V_B^1=\left[0\right]\\ D_A^2=\left[1100\right].fwdarw.V_A^2=\left[0\right]& D_B^2=\left[1111\right].fwdarw.V_B^2=\left[0\right]\\ D_A^3=\left[0111\right].fwdarw.V_A^3=\left[1\right]& D_B^3=\left[1001\right].fwdarw.V_B^3=\left[0\right]\\ D_A^4=\left[0010\right].fwdarw.V_A^4=\left[1\right]& D_B^4=\left[0010\right].fwdarw.V_B^4=\left[1\right]\end{array}$

[0068] The functions M.sub.A and M.sub.B may be chosen such that the input values cannot be determined from the output value. That is, D.sub.A.sup.i cannot be determined from M.sub.A(D.sub.A.sup.i) and Dei cannot be determined from M.sub.B(D.sub.B.sup.i). For example, each of M.sub.A and M.sub.B may be defined such that multiple inputs map to the same output. This property allows confidentiality to be maintained since a potential eavesdropper cannot gain complete knowledge of D.sub.A.sup.i and Dei based on M.sub.A(D.sub.A.sup.i) and M.sub.B(D.sub.A.sup.i).

[0069] In addition, the functions may be chosen such that if M.sub.A(D.sub.A.sup.i)M.sub.B(D.sub.B.sup.i) then D.sub.A.sup.iD.sub.B.sup.i. That is, if the output values based on two subsets are different, then this means that the two subsets are not identical. For example, each of M.sub.A and M.sub.B may be defined such that two different outputs cannot map to the same input. This property allows devices A and B to identify corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i that definitely do not match. Such subsets may then be discarded in order to increase the probability of matches between the remaining subsets.

[0070] In steps 205A and 205B, devices A and B exchange one or more messages to determine whether a condition based on the first and second values, V.sub.A.sup.i and V.sub.B.sup.i, is satisfied. For example, if the functions M.sub.A and M.sub.B are the same then the condition may be determining whether V.sub.A.sup.i=V.sub.B.sup.i (illustrated separately as steps 205A and 205B in FIG. 2). In cases where the functions M.sub.A and M.sub.B are different then the condition may be modified accordingly. For example, if M.sub.A is defined as the number of 1's in a subset and M.sub.B is defined as the number of 0's in a subset then the condition may be determining whether V.sub.A.sup.i=sizeV.sub.B.sup.i, where size is the number of bits in a subset.

[0071] In one example, exchanging the messages and determining whether the condition is satisfied may comprise the following steps. First, device A may transmit, to device B, the first value, V.sub.A.sup.i, and device B may transmit, to device A, the second value, V.sub.B.sup.i. Then, since each of devices A and B knows both V.sub.A.sup.i and V.sub.B.sup.i, each of devices A and B may determine whether the condition is satisfied based on a comparison between the first and second values, V.sub.A.sup.i and V.sub.B.sup.i.

[0072] In another example, exchanging the messages and determining whether the condition is satisfied may comprise the following steps. First, one of the devices A and B (device X) may transmit, to the other one of the devices A and B (device Y), the value V.sub.X.sup.i. Next, device Y, which knows both V.sub.X.sup.i and V.sub.Y.sup.i, may compare the values V.sub.X.sup.i and V.sub.Y.sup.i. Then, device Y may transmit, to device X, a value C.sup.i indicating the result of the comparison (e.g. C.sup.i=0 denoting no match or C.sup.i=1 denoting match).

[0073] In the example of FIG. 2, each iteration of the loop corresponds to processing of a single pair of corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i. In this case, the steps are carried out in the order {203A/B then 205A/B}.sup.i where {X}.sup.i here denotes repeating X i times. Here, steps 205A/B are considered to be a part of steps 205A/B. FIG. 4 is a message flow diagram corresponding to this case.

[0074] In certain alternative examples, the steps may be carried out in a different order. For example, steps 203A/B may be repeatedly carried out for all pairs of corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i and then steps 205A/B may be repeatedly carried out for all pairs of corresponding subsets. In this case, the steps are carried out in the order {203A/B}.sup.i then {205A/B}.sup.i. In this case, information relating to different subsets communicated in steps 205A/B may be combined within a single message. For example: values of V.sub.A.sup.i for all values of i may be transmitted from device A to device B in a single message in the form of a list; values of V.sub.B.sup.i for all values of i may be transmitted from device B to device A in a single message in the form of a list; and/or values of C.sup.i for all values of i may be transmitted from device Y to device X in a single message in the form of a list. FIG. 5 is a message flow diagram corresponding to this case.

[0075] Following the above steps, devices A and B have acquired information allowing them to determine which corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i definitiely do not match (i.e. there is a zero probability of matching). For example, if M.sub.A and M.sub.B are the same function then subsets that definitely do not match are those for which V.sub.A.sup.iV.sub.B.sup.i. On the other hand, corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i for which V.sub.A.sup.iV.sub.B.sup.i may not match either, but there is a non-zero probability that they do match. By discarding corresponding subset which definitiely do not match, while retaining corresponding subsets that have a non-zero probability of matching, the overall probability of matching between the data sets is increased, and the information overlap between the data sets tends to increase accordingly (i.e. I (D.sub.A; D.sub.B) increases).

[0076] As illustrated in FIG. 3, in step 305, the values of V.sub.A.sup.i and V.sub.B.sup.i are compared and the subsets D.sub.A.sup.i and D.sub.B.sup.i are retained or rejected depending on whether the values of V.sub.A.sup.i and V.sub.B.sup.i match or do not match. In the example of FIG. 3, the values V.sub.A.sup.i and V.sub.B.sup.i do not match for i=3 and therefore the subsets D.sub.A.sup.i and D.sub.B.sup.i for i=3 are rejected as it is known from the mismatch between the values (i.e. V.sub.A.sup.3=[1] and V.sub.B.sup.3=[0]) that the corresponding subsets (i.e. D.sub.A.sup.3=[0111] and D.sub.B.sup.3=[1001]) are definitely not identical. On the other hand, the values V.sub.A.sup.i and V.sub.A.sup.i do match for i=1, 2 and 4 and therefore the subsets D.sub.A.sup.i and D.sub.B.sup.i for i=1, 2 and 4 are retained as the matching values V.sub.A.sup.i and V.sub.B.sup.i indicate that there is a non-zero probability that the corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i match. Among the subsets for which V.sub.A.sup.i and V.sub.B.sup.imatch, the corresponding subsets D.sub.A.sup.i and D.sub.B.sup.i match for i=1 and 4 but do not match for i=2. Although a pair of non-matching subsets (i.e. i=2) is retained, the rejection of a pair of definitely non-matching subsets (i.e. i=3) tends to increase the overall information overlap between the retained subsets.

[0077] When steps 203A, 203B, 205A and 205B have been carried out for each of the N subsets, c and D.sub.B.sup.i, then steps 207A and 207B are carried out.

[0078] In step 207A, device A obtains a reduced data set D.sub.A based on those subsets D.sub.A.sup.i for which the above-mentioned condition is satisfied (i.e. the retained subsets).

[0079] In a corresponding step 207B, device B obtains a reduced data set D.sub.B based on those subsets D.sub.B.sup.i for which the above-mentioned condition is satisfied (i.e. the retained subsets).

[0080] Obtaining the reduced data set, D.sub.A, may comprise the following steps. First, for each subset, D.sub.X.sup.i , for which the condition is satisfied, a corresponding subset, D.sub.X.sup.i, may be obtained based on D.sub.X.sup.i. Then, the corresponding subsets, D.sub.X.sup.i, may be combined to generate the reduced data set, D.sub.X.

[0081] In certain examples, a corresponding data set, D.sub.X.sup.i, may comprise all elements of D.sub.X.sup.i. For example, D.sub.X.sup.i may be the same as D.sub.X.sup.i.

[0082] In certain examples, a corresponding data set, D.sub.X.sup.i, may comprise a predetermined subset of elements of D.sub.X.sup.i. For example, certain bits of D.sub.X.sup.i at predetermined bit positions may be discarded, and the remaining bits may form D.sub.X.sup.i.

[0083] In certain examples, a corresponding data set, D.sub.X.sup.i, may comprise a function, S, of all elements of D.sub.X.sup.i. For example, the function, S, may comprise a parity function. For example, the parity of the set of bits of D.sub.X.sup.i may be computed, and the resulting single parity bit may form D.sub.X.sup.i.

[0084] In certain examples, a corresponding data set, D.sub.X.sup.i, may comprise a function, S, (e.g. parity function) of a predetermined subset of elements of D.sub.X.sup.i. For example, certain bits of D.sub.X.sup.i at predetermined bit positions may be discarded, the parity of the remaining bits may be computed, and the single parity bit may form D.sub.X.sup.i.

[0085] However, D.sub.X.sup.i is derived from Dxi, the resulting D.sub.X.sup.i may be combined in any suitable manner, for example by concatenation, interleaving or any other suitable technique, to form D.sub.X.sup.i.

[0086] FIG. 3 illustrates the subsets D.sub.A.sup.i retained by device A 307A and the subsets D.sub.B.sup.iretained by device B 307B. FIG. 3 also illustrates an example in which a reduced data set may be obtained by retaining the first two bits, and discarding the other bits, of each retained subset, and concatenating the retained bits to form the reduced data set. The reduced data set D.sub.A.sup.i for device A is shown at 309A and the reduced data set D.sub.B .sup.i for device B is shown at 309B. In an alternative example, the reduced data sets may simply comprise a concatenation of the retained subsets, as shown at 307A and 307B.

[0087] As noted above, since the reduced data sets D.sub.A.sup.i and D.sub.B.sup.i are derived by excluding definitely non-matching subsets of D.sub.A and D.sub.B, then the information overlap between D.sub.A and D.sub.B will tend to be higher than the information overlap between D.sub.A and D.sub.B, I(D.sub.A; D.sub.B)>I(D.sub.A; D.sub.B). However, D.sub.A and D.sub.B may still have one or more non-matching subsets since M(D.sub.A.sup.i)=M(D.sub.B.sup.i) does not guarantee D.sub.A.sup.i=D.sub.B.sup.i.

[0088] Accordingly, in certain examples, the above-mentioned process may be repeated to further tend to increase the information overlap. In particular, the steps of determining (steps 203A and 203B), exchanging (steps 205A and 205B) and obtaining a reduced data set (steps 207A and 207B) may be repeated one or more times until one or more termination criteria 209A, 209B are satisfied. When repeating these steps, the data sets D.sub.A, D.sub.B used in one iteration comprise the reduced data sets D.sub.A, D.sub.B obtained in the preceding iteration. As shown in FIG. 2, in steps 209A/B, if the one or more termination criteria are not satisfied then the method returns to steps 203A/B, otherwise the method ends.

[0089] The termination criteria 209A, 209B may be chosen such that, following the termination of the process, the data sets (e.g. bit sequences) of devices A and B match, or are highly likely to match (e.g. the probability of matching is greater than a certain threshold). For example, the one or more termination criteria may comprise: the number of iterations has reached a predetermined threshold. In this case, the threshold may be determined based on theoretical calculations, experiment and/or simulation. For example, a threshold of 3 or 4 may be used in certain examples.

[0090] In certain applications, an exact match between the resulting data sets (e.g. bit sequences) of devices A and B may be required. On the other hand, in other applications, an exact match may not be required. For example, if the data sets of devices A and B are used as a one-time pad for subsequent communication of data then errors between the data sets will result in errors in the data. However, some errors may be acceptable for some application, for example if the data includes an error correction code.

[0091] Once the data sets (e.g. bit sequences) have been obtained using the above technique, they may be used to perform a secure operation, for example secure communication between devices A and B. For example, the data sets may be used as a one-time pad for transmitting data. In certain examples, if errors are detected in the transmitted data, then this may be interpreted as indicating that the data sets did not match exactly. In this case, the above process may be repeated. In some cases, a further iteration of the method may be performed based on the existing data sets. However, in other examples, the entire process may be repeated starting from the beginning.

[0092] The technique described above allows two devices to derive shared secret information between them. However, the technique may be extended to allow more than two devices to derive shared secret information between them. For example, similar to the two-device case, in the case of three devices, each device obtains a respective data set. Then, considering subsets of the data sets, the three devices exchange messages between each other to identify and discard those subsets that definitely do not match between all three devices. Then, similar to the two-device case, each of the three devices derives a reduced data set based on the remaining subsets. Similar to the two-device case, the process may be repeated until one or more termination criteria are satisfied.

[0093] Certain examples of the present disclosure may obtain shared data sets based on processing abstract data sets. In certain examples, the data sets (e.g. binary data sequences) may be obtained based on one or more signals (e.g. physical signals), such as an audio signal and/or a light/image signal. A signal (e.g. an audio signal and/or a light/image signal) obtained by device A (e.g. via a user uttering a predetermined phrase and/or by capturing an image of a predetermined object) may be broken down into packets (corresponding to the subsets described above) and each packet may be filtered to generate a filtered signal (corresponding to an entropy-reducing function or a statistical function applied to the packet). For example, an averaging filter may be applied to a packet. A similar process may be carried out by device B.

[0094] Then, comparisons between filtered packets of devices A and B may be performed and filtered packets may be selectively discarded or retained based on the comparison to obtain a reduced signal (e.g. an audio signal and/or a light/image signal). The process may then be repeated as described above. Processing of the signal may be performed digitally or through analog processing, for example using any suitable electronic components.

[0095] FIG. 6 illustrates an exemplary device (or apparatus) for deriving shared secret information and/or for communicating with another device. For example, the techniques disclosed in relation to FIGS. 2-5 may be implemented using a device as disclosed in relation to FIG. 6. For example, device A and device B may comprise a device as disclosed in relation to FIG. 6. The device 600 comprises a processor (or controller) 601 for controlling the overall operation of the device 600. For example, the processor 601 may be configured for performing operations as described above for deriving shared secret information. The device 600 also comprises a memory 603 for storing information and data required for the aforementioned operations. The device 600 also comprises an external interface 605 for communicating with another device via any suitable communication link (e.g. wired or wireless). For example, under the control of the processor 601, the external interface 605 may be configured to transmit and receive messages as described above.

[0096] In certain examples, the device 600 may also comprise a user input/output (I/O) unit 607 for allowing a user to interact with the device 600. For example, the user I/O unit 607 may comprise one or more input devices (e.g. a keyboard, touch screen, etc.) for inputting commands to the device 600. The user I/O unit 607 may comprise one or more output devices (e.g. display, LEDs, speaker, etc.) for outputting information (e.g. status information) for a user. In certain examples, if the device 600 is configured to operate autonomously, then the user I/O unit 607 may be omitted. In some examples, the device 600 may be configured to interface with another device in close proximity. In this case, the interface between the device 600 and the other device may be a wired link or a relatively short-range communication link such as a Bluetooth or NFC link. In other examples, the device 600 may be configured to interface with another device located remotely. In this case, the device 600 may communicate with the other device via a network, for example the Internet.

[0097] The terms and words used in this specification are not limited to the bibliographical meanings, but are merely used to enable a clear and consistent understanding of the present disclosure.

[0098] The same or similar components may be designated by the same or similar reference numerals, although they may be illustrated in different drawings.

[0099] Detailed descriptions of elements, features, components, structures, constructions, functions, operations, processes, characteristics, properties, integers and steps known in the art may be omitted for clarity and conciseness, and to avoid obscuring the subject matter of the present disclosure.

[0100] Throughout this specification, the words comprises, includes, contains and has, and variations of these words, for example comprise and comprising, means including but not limited to, and is not intended to (and does not) exclude other elements, features, components, structures, constructions, functions, operations, processes, characteristics, properties, integers, steps and/or groups thereof.

[0101] Throughout this specification, the singular forms a, an and the include plural referents unless the context dictates otherwise. For example, reference to an object includes reference to one or more of such objects.

[0102] By the term substantially it is meant that the recited characteristic, parameter or value need not be achieved exactly, but that deviations or variations, including for example, tolerances, measurement errors, measurement accuracy limitations and other factors known to those of skill in the art, may occur in amounts that do not preclude the effect the characteristic, parameter or value was intended to provide.

[0103] Throughout this specification, language in the general form of X for Y (where Y is some action, process, function, activity, operation or step and X is some means for carrying out that action, process, function, activity, operation or step) encompasses means X adapted, configured or arranged specifically, but not exclusively, to do Y.

[0104] Elements, features, components, structures, constructions, functions, operations, processes, characteristics, properties, integers, steps and/or groups thereof described herein in conjunction with a particular aspect, embodiment, example or claim are to be understood to be applicable to any other aspect, embodiment, example or claim disclosed herein unless incompatible therewith.

[0105] It will be appreciated that examples of the present disclosure can be realized in the form of hardware, software or any combination of hardware and software. Any such software may be stored in any suitable form of volatile or non-volatile storage device or medium, for example a ROM, RAM, memory chip, integrated circuit, or an optically or magnetically readable medium (e.g. CD, DVD, magnetic disk or magnetic tape).

[0106] Certain examples of the present disclosure provide 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 any example, embodiment, aspect and/or claim disclosed herein. Certain examples of the present disclosure provide a computer or processor-readable data carrier having stored thereon such a computer program.

[0107] The techniques described herein may be implemented using any suitably configured apparatus and/or system. Such an apparatus and/or system may be configured to perform a method according to any aspect, embodiment, example or claim disclosed herein. Such an apparatus may comprise one or more elements, for example one or more of receivers, transmitters, transceivers, processors, controllers, modules, units, and the like, each element configured to perform one or more corresponding processes, operations and/or method steps for implementing the techniques described herein. For example, an operation/function of X may be performed by a module configured to perform X (or an X-module). An apparatus and/or one or more elements thereof may be implemented in the form of hardware, software, a virtualised function instantiated on an appropriate platform (e.g. on a cloud infrastructure), or any combination of these.

[0108] While the invention has been shown and described with reference to certain examples, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the scope of the invention, as defined by the appended claims.