Method of generating key

This application is a National Stage of International Application No. PCT/JP2011/080583 filed Dec. 27, 2011, claiming priority based on Japanese Patent Application No. 2010-293094 filed Dec. 28, 2010, the contents of all of which are incorporated herein by reference in their entirety.

The present invention relates to generation of a key for controlling steps of a cryptographic algorithm.

Secure and usable mutual authentication systems have been demanded in order to perform ad hoc data transmission between devices having a wireless interface. The following examples have been known as technology relating to such mutual authentication systems.

For example, some techniques using PIN (Personal Identification Number) have been known for mutual authentication between devices having a wireless interface. Those techniques are hereinafter referred to as “Related Art 1.”

As in Patent Literature 1, there have also been known techniques of detecting whether a button provided in a device is pushed, generating a unique group connection ID, and using the unique group connection ID as a common key (authentication key) for mutual authentication. Those techniques are hereinafter referred to as “Related Art 2.”

In Non-Patent Literature 1, devices each having a non-contact IC reader are held up over each other to exchange keys. The devices mutually use those keys as authentication keys. Those techniques are hereinafter referred to as “Related Art 3.”

Patent Literature 2 and Non-Patent Literatures 2 to 6 disclose means using an acceleration sensor, which is more advantageous in implementation cost than a non-contact IC reader. In those references, the same motion is supplied to two devices having an acceleration sensor from an external source (for example, those devices are vigorously shaken). Thus, a common variation is shared with those devices. Based upon such a common variation, an authentication key is shared with those devices. Those techniques are hereinafter referred to as “Related Art 4.”

In Related Art 1, data with a large number of digits should be inputted without any error in order to obtain high cipher strength by a sufficient key length. Such a process is troublesome and difficult. Therefore, there has been a problem in usability.

In Related Art 2, to push a button is a process that can readily be performed by anyone. When a button is accidentally or intentionally pushed by a third party, an authentication key is needlessly provided to the third party. Thus, there has been a problem in security.

In Related Art 3, a non-contact IC reader should be mounted on each of devices that are to be subjected to mutual authentication. Thus, there has been a problem in cost for those devices.

In Related Art 4, a user should aggregately hold two devices and vigorously shake those devices. Such an operation may be difficult in itself.

Furthermore, in Related Art 4, since two devices are aggregately held, many restrictions are imposed on the size, shape, weight of the devices, and the like. In order to apply this technology to a device, the device should have a size and a shape that allow two devices to be held aggregately. Thus, it is difficult or even impossible to apply this technology if one of two devices is a fixed device or if any one of two devices has a shape, size, or weight that makes it difficult to hold those two devices aggregately.

Moreover, in Related Art 4, since two devices are aggregately held and shaken, each of the devices should have a resistance to such vibration. Generally, a user of a device is not specified in a design phase. Supposing that an unspecified user vibrates a device, the device should be designed with some margins of the vibration resistance in consideration of individual differences in amplitude or speed of vibration to be applied. In this regard, there is also a restriction on design of the device.

Patent Literature

Patent Literature 1: JP-A 2001-36638

Patent Literature 2: JP-A 2008-311726

Non-Patent Literature

Non-Patent Literature 1: SDK for FeliCa Products, the Internet (http://www.sony.co.jp/Products/felica/pdt/data/SDK_Products.pdf).

Non-Patent Literature 2: J. Lester, B. Hannaford, and G. Borriello, “Are You With Me?”—Using accelerometers to determine if two devices are carried by the same person, Pervasive 2004, LNCS 3001, pp. 33-50, 2004.

Non-Patent Literature 3: Y. Huynh and B. Schiele, Analyzing features for activity recognition, sOc-EUSAI '05, pp. 159-163, 2005.

Non-Patent Literature 4: D. Bichler, G. Stromberg, M. Huemer, and M. Low, Key generation based on acceleration data of shaking processes, UbiComp 2007, LNCS 4717, pp. 304-417, 2007.

Non-Patent Literature 5: R. Mayrhofer and H. Gellersen, Shake well before use: Authentication based on accelerometer data, Pervasive 2007, LNCS 4480, pp. 144-161, 2007.

Non-Patent Literature 6: Takahiro Minami, Yuichi Nino, Jun Noda, Yoshitaka Nakamura, and Hiroyuki Seki, Key Generation from Human Movements for Secure Device Pairing, the Internet (http://www-higashi.ist.osaka-u.ac.jp/˜y-nakamr/research/csec/44csec.pdf).

Problem(s) to be Solved by Invention

It is an object of the present invention to provide key generation technology that does not require a user's difficult operation such as aggregately holding and shaking two devices and that has loose restrictions on the shape, size, weight of devices, and the like, and to provide mutual authentication technology based upon this key generate technology.

Means for Solving Problem(s)

According to the present invention, a method of generating a key includes a vibration detection step in which a vibrator generates vibration in a state in which a first device and a second device are brought into contact with the vibrator and a first acceleration sensor provided in the first device and a second acceleration sensor provided in the second device detect the vibration, a transmission step in which the first device transmits a first feature value based upon the detection result of the first acceleration sensor to the second device, a reception step in which the first device receives a second feature value based upon the detection result of the second acceleration sensor from the second device, and a key generation step in which the first device compares the received second feature value with the first feature value and generates a key based upon the comparison result.

Furthermore, according to the present invention, a computer-readable storage medium stores a program executable in an apparatus having an acceleration sensor, data communication means, and a processor. The program executes, with the processor, a procedure including a detection step of detecting, with the acceleration sensor, an acceleration of the apparatus that is produced in accordance with vibration generated by a vibrator when the apparatus and another apparatus are brought into contact with the vibrator, a transmission step of transmitting, with the data communication means, a first feature value based upon the detection result of the acceleration sensor to the other apparatus, a reception step of receiving, with the data communication means, a second feature value based upon an acceleration generated in the other apparatus in accordance with vibration generated by the vibrator from the other apparatus, and a key generation step of comparing the second feature value received by the reception step with the first feature value and generating a key based upon the comparison result.

Advantageous Effects of Invention

According to the present invention, a first device and a second device are brought into contact with the same vibrator, and the vibrator is vibrated. Thus, the first and second devices are supplied with vibration from the same vibration source. A key is generated based upon this vibration. Therefore, a user's operation such as aggregately holding and shaking the first and second devices is not required. Furthermore, the first and second devices do not need to be aggregately held in order to generate a key. Mere contact of those devices with the vibrator suffices. Accordingly, design restrictions on the size, outside shape, weight of the devices, and the like are remarkably loosened. Thus, one of the devices may be of a fixed type. Moreover, the amplitude, speed of the vibration applied to those devices, and the like can be grasped in advance from the specification of the vibrator. Therefore, it is not necessary to consider individual differences of the amplitude or speed of vibration by unspecified users. In this regard, design restrictions can also be loosened.

FIG. 1 is a block diagram showing a key generation system according to an exemplary embodiment of the present invention;

FIG. 2 is a block diagram showing a first device used in the key generation system illustrated in FIG. 1 ;

FIG. 3 is a block diagram showing a second device used in the key generation system illustrated in FIG. 1 ;

FIG. 4 is a diagram explanatory of a state of contact of the first device, the second device, and a vibration device used in the key generation system illustrated in FIG. 1 when a key is to be generated;

FIG. 5 is a flow chart explanatory of an operation of a vibrator controller in the vibration device used in the key generation system illustrated in FIG. 1 ;

FIG. 6 is a flow chart explanatory of an example of operations of vibration quantizers in the first and second devices illustrated in FIGS. 2 and 3 to divide an output of an acceleration sensor into time windows;

FIG. 7 is a diagram explanatory of an example of an output of an acceleration sensor that has been divided into time windows;

FIG. 8 is a diagram explanatory of the relationship between a feature vector and candidate vectors;

FIG. 9 is a flow chart explanatory of operations of feature vector generators in the first and second devices illustrated in FIGS. 2 and 3 when pulselike quantized values are modified to generate a feature vector and candidate vectors;

FIG. 10 is a flow chart explanatory of operations of key generators in the first and second devices illustrated in FIGS. 2 and 3 to generate a key piece from a feature vector and candidate vectors;

FIG. 11 is a block diagram of a first device according to an example of the present invention; and

FIG. 12 is a block diagram of a second device according to an example of the present invention.

A key generation system 100 according to an exemplary embodiment of the present invention will be described below.

(1) As shown in FIG. 1 , the key generation system 100 comprises a first device 1 , a second device 2 , and a vibration device 3 . The vibration device 3 may be included in either the first device 1 or the second device 2 . Hereinafter, the first device 1 and the second device 2 are referred to as “Device A” and “Device B,” respectively.

FIG. 2 is a block diagram showing a configuration of the first device (Device A) 1 .

For example, each of the first device (Device A) 1 and the second device (Device B) 2 is a device having an acceleration sensor, a key generator, and a communication part as illustrated in FIG. 2 . More specifically, each of the first device (Device A) 1 and the second device (Device B) 2 is a cellular phone terminal, a PDA (Personal Data Assistant), a notebook computer, or the like.

As shown in FIG. 2 , the first device (Device A) 1 comprises a first acceleration sensor 10 A, a first vibration quantizer 11 A, a first feature vector generator 12 A, a first key generator 13 A, a first communication part 14 A, and a first mutual authentication part 15 A.

Although FIG. 2 illustrates a configuration example of the first device (Device A) 1 , the second device (Device B) 2 may have the same configuration as the first device (Device A) 1 . In such a case, as shown in FIG. 3 , the second device (Device B) 2 comprises a second acceleration sensor 10 B, a second vibration quantizer 11 B, a second feature vector generator 12 B, a second key generator 13 B, a second communication part 14 B, and a second mutual authentication part 15 B.

The first and second communication parts 14 A and 14 B are communication interface devices that can communicate data with each other. It does not matter whether the first and second communication parts are of wireless or wire, the number and types of networks connecting the first and second communication parts, and the like. For convenience, the first and second communication parts 14 A and 14 B preferably comprise a wireless communication interface but may be a wire communication interface. When the first device (Device A) 1 and the second device (Device B) 2 are cellular phone terminals, the first and second communication parts 14 A and 14 B may be wireless communication devices operable to perform wireless communication with a base station of a mobile communication network, infrared communication devices such as IrDA (Infrared Data Association), which is provided on most of cellular phone terminals, or transceivers for short-distance wireless communication such as Bluetooth.

As shown in FIG. 1 , the vibration device 3 includes a vibrator 4 and a vibrator controller 5 operable to control an operation of the vibrator 4 .

Generally, a cellular phone terminal comprises a vibrator to generate vibration for informing a user of an incoming call or the like. Such a vibrator may be used as the vibrator 4 of the vibration device 3 . When the first device (Device A) 1 and the second device (Device B) 2 are both a cellular phone terminal, both of the devices have a vibrator 4 . In such a case, the vibrator of one of the devices serves as a vibrator used for key generation in the exemplary embodiment of the present invention.

Next, an operation for generating a key will be described.

(2) First, as shown in FIG. 4 , both of the first device (Device A) 1 and the second device (Device B) 2 are brought into contact with the vibration device 3 . When the vibrator 4 is included in either one of the first device (Device A) 1 and the second device (Device B) 2 , the first device (Device A) 1 and the second device (Device B) 2 are brought into direct contact with each other.

(3) Then, as shown in FIG. 4 , the vibrator controller 5 turns the vibrator 4 on and off in a state in which the first device (Device A) 1 , the second device (Device B) 2 , and the vibration device 3 are held in contact with each other. FIG. 5 shows an example of a control operation of the vibrator controller 5 at that time. The control operation of the vibrator controller 5 illustrated in FIG. 5 will be described in detail later. An example of vibration methods of the vibrator may include varying amplitudes in a stepped manner, particularly binary vibration of vibrating between a predetermined amplitude and zero. Another example may include varying amplitudes in a continuous manner.

(4) Subsequently, the first device (Device A) 1 and the second device (Device B) 2 detect vibration with the first and second acceleration sensors 10 A and 10 B, respectively.

(5) The first and second vibration quantizers 11 A and 11 B respectively divide outputs of the first and second acceleration sensors 10 A and 10 B into time windows having a predetermined length and quantize a value of each of the divided time windows. FIG. 6 shows an example of an operation in which the first and second vibration quantizers 11 A and 11 B divide an output of the acceleration sensor into time windows. The operation of the vibration quantizers illustrated in FIG. 6 will be described in detail later. FIG. 7 shows an example of an output of the acceleration sensor that has been divided into time windows. Those examples assume that the vibrator 4 performs a binary operation of vibrating and not vibrating.

Depending upon states and methods of contact between the first device (Device A) 1 , the second device (Device B) 2 , and the vibration device 3 , some differences are produced in analog values of the acceleration detected by the first and second acceleration sensors 10 A and 10 B. Therefore, if a key is generated based upon analog values of the acceleration, it is difficult to generate the same key having a key length sufficient for practical use on both of the first device (Device A) 1 and the second device (Device B) 2 .

In contrast, as shown in FIG. 7 , analog values of the acceleration are divided into time windows, and a key is generated with use of quantized outputs of the acceleration sensor. Thus, an error generated in accelerations that are to be shared with the first device (Device A) 1 and the second device (Device B) 2 is absorbed. Accordingly, an authentication key having a key length sufficient for practical use can be shared with the first device (Device A) 1 and the second device (Device B) 2 .

(6) Subsequently, the first feature vector generator 12 A generates a first feature vector group of V fa0 , V fa1 , V fa2 , . . . based upon the output values of the first acceleration sensor 10 A that have been divided into time windows and quantized. Furthermore, the first feature vector generator 12 A generates candidate vector groups corresponding to the feature vectors of the first feature vector group, i.e., a candidate vector group V ca01 , V ca02 , V ca03 , . . . corresponding to the first feature vector V fa0 , a candidate vector group V ca11 , V ca12 , V ca13 , . . . corresponding to the second feature vector V fa1 , and a candidate vector group V ca21 , V ca22 , V ca23 , . . . corresponding to the third feature vector V fa2 .

Similarly, the second feature vector generator 12 B generates a second feature vector group V fb0 , V fb1 , V fb2 , . . . and also generates candidate vector groups corresponding to the feature vectors of the second feature vector group, i.e., a candidate vector group V cb01 , V cb02 , V cb03 , . . . corresponding to the first feature vector V fb0 , a candidate vector group V cb11 , V cb12 , V cb13 , . . . corresponding to the second feature vector V fb1 , and a candidate vector group V cb21 , V cb22 , V cb23 , . . . corresponding to the third feature vector V fb2 .

Hereinafter, the first feature vector group of V fa0 , V fa1 , V fa2 , . . . , which are generated by the first device (Device A) 1 , is collectively denoted by V fai where i is an integer more than 0 and is a time-series index of feature vectors. The candidate vector group corresponding to the first feature vector V fa0 of the first feature vector group that is generated by the first device (Device A) 1 is collectively denoted by V ca0j where j is an integer more than 0 and is a time-series index of candidate vectors. The first candidate vector groups generated by the first device (Device A) 1 are collectively denoted by V caij .

The feature vectors and the candidate vectors generated by the second device (Device B) 2 are defined in the same manner as described above. Specifically, the second feature vector group of v fb0 , V fb1 , V fb2 , . . . , which are generated by the second device (Device B) 2 , is collectively denoted by V fbi where i is an integer more than 0 and is a time-series index of feature vectors. The candidate vector group corresponding to the first feature vector V fb0 of the second feature vector group that is generated by the second device (Device B) 2 is collectively denoted by V cb0j where j is an integer more than 0 and is a time-series index of candidate vectors. The second candidate vector groups generated by the second device (Device B) 2 are collectively denoted by V cbij .

A feature vector is generated by combining the number of time windows in an interval continuously holding the same quantized value, i.e., a continuation interval, with the quantized value. For example, a feature vector has a structure in which a quantized value is connected to a binary notation of the number of time windows in which the quantized value continues.

Quantized values of time windows illustrated in FIG. 7 are “0,” “1,” “1,” “1,” “1,” “1,” “0,” “0,” “0,” “1,” and “0” from the left. There is a continuation interval in which five quantized values of “1” continue rightward from the second time window to the sixth time window. Thus, a feature vector based upon this continuation interval is “1101,” which is obtained by connecting the quantized value of “1” to the number of the continuing time windows, i.e., 5, or “101” in the binary notation.

A candidate vector is generated by changing, into other values, one or both of the beginning time window and the ending time window of the continuation interval for which a feature vector has been generated and, as with a feature vector, combining the number of time windows in an interval continuously holding the same quantized value with the quantized value. A beginning time window of a continuation interval is the first time window of the continuation interval. An ending time window of a continuation interval is a time window right after the continuation interval. In a state in which one or both of quantized values of the beginning time window and the ending time window have been changed, a candidate vector is generated based upon the number of time windows in a continuation interval of time windows continuously holding the same quantized value.

The candidate vectors have three types. A first one of the candidate vectors is generated by changing a quantized value of a beginning time window of a continuation interval without changing a quantized value of an ending time window of the continuation interval. A second one of the candidate vectors is generated by changing a quantized value of an ending time window of a continuation interval without changing a quantized value of a beginning time window of the continuation interval. A third one of the candidate vectors is generated by changing quantized values of a beginning time window and an ending time window of a continuation interval. Among these three types, the third type generated by changing both of a beginning time window and an ending time window results in shifting the whole continuation interval and thus has the same value as a feature vector. Therefore, the third type does not need to be generated. In the example illustrated in FIG. 8 , for the feature vector of “1101,” a candidate vector of “1100” is generated by changing only a quantized value of the beginning time window, and a candidate vector of “1110” is generated by changing only a quantized value of the ending time window. Because a candidate vector of “1101” that is generated by changing both of the beginning time window and the ending time window has the same value as the feature vector, it is not generated in this example.

Candidate vectors are generated along with feature vectors in this manner for the following reason: A first vector group including the first feature vector group and the first candidate vector group generated by the first device (Device A) 1 and a second vector group including the second feature vector group and the second candidate vector group generated by the second device (Device B) 2 are compared with each other. If there is matched vectors in both of the vector groups, a key is generated based upon the matched vectors. The “matched” vectors include not only matched vectors between the first feature vector group and the second feature vector group, but also matched vectors between the first feature vector group and the second candidate vector group, matched vectors between the first candidate vector group and the second feature vector group, and matched vectors between the first candidate vector group and the second candidate vector group.

Such a comparison is made between the first vector group and the second vector group for the following reason: As described later in the operation ( 10 ), the first device (Device A) 1 and the second device (Device B) 2 generate key pieces based upon the matched feature vectors/candidate vectors and concatenate a predetermined number of key pieces to generate a key. Therefore, at least a predetermined number of matched feature vectors/candidate vectors are required to generate a key.

Meanwhile, detection timing of the acceleration may differ between the first acceleration sensor 10 A and the second acceleration sensor 10 B depending upon a state of contact between the first device (Device A) 1 , the second device (Device B) 2 , and the vibration device 3 . In such a case, the beginning or ending timing of the continuation interval differs between the first device (Device A) 1 and the second device (Device B) 2 . Therefore, feature vectors generated by the first device (Device A) 1 and the second device (Device B) 2 do not match with each other. If such mismatching occurs many times, it becomes difficult to generate a required number of key pieces from comparison between feature vectors.

In view of such circumstances, the beginning quantized value and the ending quantized value of a continuation interval in which feature vectors have been generated are changed. The continuation interval subjected to such changes is a sort of adjustment of the difference in assumed detection timing. Thus, candidate vectors are generated based upon the changed continuation interval and subjected to comparison between the first device (Device A) 1 and the second device (Device B) 2 in addition to the feature vectors. Accordingly, the difference of the detection timing can be absorbed to some degree. As a result, an authentication key having a key length sufficient for practical use can be shared with Devices A and B.

Furthermore, when the devices are brought into contact with each other, pulselike vibration may be generated only in one of the devices because the device is held in an unstable manner by hands, for example. Such vibration may be mixed as a noise, so that a pulselike quantized value is generated. In order to cope with such a pulselike quantized value, the first and second feature vector generators 12 A and 12 B may modify a value of the time window having the pulselike quantized value prior to the generation of the first and second feature vector groups and the first and second candidate vector groups. Assuming three consecutive time windows W n−1 , W n , and W n+1 where n is a natural number, the time window having a pulselike quantized value refers to a time window W n having a value that is different from W n−1 and W n+1 having the same value. The time window having a pulselike quantized value is W n =1 where W n−1 =W n+1 =0, or W n =0 where W n−1 =W n+1 =1. If time windows are sufficiently shortened, such a pulselike quantized value may be considered as an error. Such an error can be eliminated if a value of such a time window is modified so as to be equal to values of its preceding and following time windows.

For example, the quantized value of the second time window from the right in FIG. 8 is “1,” and both of quantized values of its preceding and following time windows are “0.” Thus, the quantized value of the second time window is considered as a pulselike quantized value. Therefore, while the quantized value of this time window may be modified into “0,” the first and second feature vector groups and the first and second candidate vector groups may be generated. FIG. 9 shows an operation of the first and second feature vector generators 12 A and 12 B when the first and second feature vector groups and the first and second candidate vector groups are generated while a pulselike quantized value is modified.

(7) Furthermore, as shown in FIG. 10 , the first feature vector generator 12 A generates all of a hash value H(V fai ) of an ith feature vector of the first feature vector group and hash values H(V caij ) of first candidate vectors corresponding to the ith feature vector. As described above, two first candidate vectors V cai0 and V cai1 are generated so as to correspond to the ith feature vector V fai of the first feature vector group. Accordingly, three first hash values H(V fai ), H(V cai0 ), and H(V cai1 ) are generated so as to correspond to the ith feature vector V fai of the first feature vector group. Similarly, the second feature vector generator 12 B generates all of a hash value H(V fbi ) of the second feature vector and second hash values H(V cbij ) of second candidate vectors (Step S 42 ). H(X) represents a value obtained by one-way hash of X, and i is an index indicative of a feature vector in question. An initial value of i is zero. The operations described in the operation (7) and the following operations (8) and (9) are performed for the same index i. Those operations (7) to (9) are repeated with increasing i by 1 until key pieces required for generating a key having a desired key length are obtained. Those skilled in the art would recognize that the generation of hash values may be omitted so that feature vectors and candidate vectors are directly be transmitted for subsequent processes, which is not preferable for security reasons.

(8) All of the second hash values H(V fbi ) and H(V cbij ) generated in the operation (7) by the second device (Device B) 2 are transmitted to the first device (Device A) 1 via the first and second communication parts 14 A and 14 B. Similarly, all of the first hash values H(V fai ) and H(V caij ) generated in the process (7) by the first device (Device A) 1 are transmitted to the second device (Device B) 2 (Step S 42 ).

(9) The first key generator 13 A of the first device (Device A) 1 compares a plurality of first hash values including the hash values H(V fai ) of the first feature vectors V fai and the hash values H(V caij ) of the corresponding first candidate vectors generated by the first feature vector generator 12 A of the first device (Device A) 1 , with a plurality of second hash values including the hash values H(V fbi ) of the second feature vectors V fbi corresponding to the first feature vector V fai and the hash values H(V cbij ) of the second candidate vectors, which have been received from the second device (Device B) 2 via the first communication part 14 A. Thus, the first key generator 13 A compares a group of first hash values corresponding to the ith one V fai of the first feature vectors with a group of second hash values corresponding to the ith one V fbi of the second feature vectors. If any of the hash values in one of the groups matches with any of the hash values in the other group, then a feature vector or a candidate vector corresponding to that hash value is used as a key piece (Step S 43 ). If there is no hash value matched between the former group and the latter group, then no key piece is generated based upon the first feature vectors V fai . This holds true for the second device (Device B) 2 .

As described above, a plurality of candidate vectors corresponds to one feature vector. Therefore, either one of the groups of the hash values includes a hash value of one feature vector and hash values of a plurality of candidate vectors corresponding to that feature vector. For example, it is assumed that the first hash value H(V fa0 ) of the first group A matches with the second hash value H(V cb01 ) of the second group B when a first group A of the first hash values including the hash value H(V fa0 ) of the first feature vector V fa0 and the hash values H(V ca00 ) and H(V ca01 ) of the first candidate vectors corresponding to the first feature vector V fa0 is compared with a second group B of the second hash values including the hash value H(V fb0 ) of the second feature vector V fb0 and the hash values H(V cb00 ) and H(V cb01 ) of the second candidate vectors corresponding to the second feature vector V fb0 . In this case, it is assumed that the first feature vector V fa0 matches with the second candidate vector V cb01 . Thus, the first key generator 13 A of the first device (Device A) 1 sets the first feature vector V fa0 as a key piece. The same comparison is also made in the second device (Device B) 2 , and the same results are obtained. Therefore, the second key generator 13 B sets the second candidate vector V cb01 as a key piece. In this example, the first feature vector of the first group A matches with the second candidate vector of the second group B. The first and second feature vectors of both of the groups may match with each other, or the first and second candidate vectors of both of the groups may match with each other.

(10) The operations (7) to (9) are performed for all of the feature vectors (Step S 44 ). In other words, 1 is added to the current value of i, and the operations (7) to (9) are repeated.

(11) The number of key pieces obtained in the operation (10) is compared with a threshold for the number of key pieces. If the number of key pieces exceeds the threshold, the key pieces are concatenated to each other to generate a key (Step S 45 ).

(12) The first device (Device A) 1 and the second device (Device B) 2 perform authentication using the generated key. Examples of authentication include challenge-response authentication. In the challenge-response authentication, the first device (Device A) 1 generates a random value, which is called a challenge, and sends it to the second device (Device B) 2 . When the second device (Device B) 2 receives this challenge, it performs an arithmetic process by combining the key generated in the operation (11) by the second device (Device B) 2 with the challenge received from the first device (Device A) 1 . As a result, the second device (Device B) 2 generates a hash value and sends it as a second response to the first device (Device A) 1 . When the first device (Device A) 1 receives the response, it performs a similar arithmetic process with use of the challenge previously generated and the key generated in the operation (11) by the first device (Device A) 1 to thereby generate a first response. The first device (Device A) 1 compares the first response with the second response received from the second device (Device B) 2 . If the first and second responses match with each other, the first device (Device A) 1 authenticates the second device (Device B) 2 .

(13) The first device (Device A) 1 sends data encrypted with the key to the second device (Device B) 2 . The second device (Device B) 2 decrypts the encrypted data with use of the key.