JP6040313B2 - Multi-party secure authentication system, authentication server, multi-party secure authentication method and program - Google Patents

Description

  The present invention relates to a technology in which a plurality of servers simultaneously securely authenticate users in authentication on a network.

  When a user receives a service spanning a plurality of servers, the techniques described in Non-Patent Documents 1 to 3 are known as techniques for simultaneously securely authenticating each server (for example, Non-Patent Documents 1 to 3). reference.). The technologies described in Non-Patent Documents 1 to 3 are authentication technologies in a secure storage service, in which a user sets a password, and data is distributed and stored in a plurality of servers by a secure method called secret sharing. If the password entered at the time of authentication is correct, the user can restore the correct data, and if the password is incorrect, the restoration fails.

Ali Bagherzandi, Stanislaw Jarecki, Nitesh Saxena, and Yanbin Lu, “Password-protected secret sharing”, ACM Conference on Computer and Communications Security, pp. 433-444, 2011. Jan Camenisch, Anna Lysyanskaya, and Gregory Neven, “Practical yet universally composable two-server password-authenticated secret sharing”, ACM Conference on Computer and Communications Security, pp. 525-536, 2012. Waka Ogata, “Security and Efficiency of Information Theoretically Secure Secret Sharing with Passwords”, SCIS 2013

  However, the prior art is based on the premise that the user and the storage server are directly connected, and safety cannot be guaranteed when an intermediate server as a gateway exists like a Web server in a Web service or the like. There is also a problem that it cannot be applied to other than storage services.

  An object of the present invention is to provide a multi-party secure authentication technique capable of guaranteeing safety even when an intermediate server exists.

  In order to solve the above problems, a multi-party secure authentication method according to a first aspect of the present invention includes a password distribution step, a password distribution value encryption step, a password distribution value transfer step, a password distribution value decryption step, and an intermediate server verification. Value generation step, intermediate server verification value encryption step, intermediate server verification value decryption step, intermediate server verification step, authentication server verification value generation step, authentication server verification value encryption step, authentication server verification value decryption step, and authentication server verification step including.

In the following, n ≧ 3, 2k-1 ≦ n, k ≦ m, m ≦ n, and a ₁ ,..., _Am are m different integers of 1 to n. , (K, n) secret sharing is a secret sharing that can be restored if there are k or more of n shared values, and [r ^(W) ] ₁ , ..., [r ^(W) ] _n is restored Then, the random value r ^(W) is the (k, n) secret sharing value, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) The random value r ⁽ⁱ⁾ is a (k, n) secret sharing value, and [0 ^(W) ] ₁ , ..., [0 ^(W) ] _n becomes 0 when restored (k, n) secret sharing [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (i = 1, ..., m) is 0 when restored (k, n) And

In the password distribution step, the user device distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n . In the password distributed value encryption step, the user device encrypted the distributed value [w ′] _i using a common key between the user device and the i-th authentication server for i = 1,..., N. The ciphertext Enc _{US_i} ([w '] _i ) is obtained. In the password distributed value transfer step, the intermediate server _transmits the cipher text Enc _{US_i} ([w ′] _i ) received from the user device to i-th authentication server for i = 1,..., _N. In the password distributed value decryption step, the authentication server decrypts the ciphertext Enc _{US_i} ([w '] _i ) received from the intermediate server using the common key between the user device and the authentication server, and distributes the value [w '] get _i . In the intermediate server verification value generation step, λ _{a_i} ^(W) (i∈1, ..., m) is a constant that satisfies the following equation:

^ λ _{a_i} ^(W) (i∈1,…, m) is a constant that satisfies

λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1,…, m) is a constant that satisfies

Authentication server obtains the following equation verification value q _{a_i} ^(W).

In the intermediate server verification value encryption step, the authentication server uses the common key between the intermediate server and the authentication server to encrypt a ciphertext Enc _{WS_a_i} (q _{a_i} ^(W) ) obtained by encrypting the verification value q _{a_i} ^(W). obtain. In the intermediate server verification value decryption step, the ciphertext Enc received from the a _i th authentication server by the intermediate server for i = 1,..., M using a common key between the intermediate server and the a _i th authentication server. _{WS_a_i} (q _{a_i} ^(W) ) is decoded to obtain a verification value q _{a_i} ^(W) . In the intermediate server verification step, the intermediate server verifies whether the sum of the verification values q a — ₁ ^(W) ,..., Q a — _m ^(W) is equal to zero. In the authentication server verification value generation step, the authentication server ^{obtains a} verification value q _{a_i} ^(a_j) for j = 1 ^,.

In the authentication server verification value encryption step, the authentication server encrypts the verification value q _{a_i} ^(a_j) using the common key between the _jth authentication server and the authentication server for j = 1, ..., m. The encrypted ciphertext Enc _{S_a_iS_a_j} (q _{a_i} ^(a_j) ) is obtained. In the authentication server verification value decoding step, authentication servers, j = 1, ..., for m, using a common key between a _j-th authentication server and the authentication server, the cipher text received from a _j-th authentication server Enc _{S_a_iS_a_j} (q _{a_j} ^(a_i) ) is decoded to obtain a verification value q _{a_j} ^(a_i) . In the authentication server verification step, the authentication server verifies whether or not the sum of verification values q a — ₁ ^(a_i) ,..., Q a — _m ^(a_i) is equal to zero.

  The multi-party secure authentication method according to the second aspect of the present invention includes a password distribution step, a password distribution value encryption step, a password distribution value transfer step, a first password distribution value decryption step, a second password distribution value decryption step, a first Authentication server verification value generation step, second authentication server verification value generation step, first authentication server verification value encryption step, second authentication server verification value encryption step, first authentication server verification value decryption step, second authentication server verification A value decoding step, a first authentication server verification step, and a second authentication server verification step are included.

In the following, n ≧ 3, 2k-1 ≦ n, k ≦ m, m ≦ n, and a ₁ ,..., A _m are different from each other by a _m = n and 1 or more and n or less. m integers, and (k, n) secret sharing is a secret sharing that can be restored if there are k or more of n sharing values, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ^{( i)} ] _n (i = 1, ..., n) is a random value r ^{(i) when} restored, (k, n) is a ^shared value by secret sharing, and [0 ^(a_i) ] ₁ , ..., [0 ^{(a_i )} ] _n (i = 1, ..., m) is 0 when restored (k, n)
λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies the following equation.

In the password distribution step, the user device distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n . In the password distributed value encryption step, the user device encrypts the distributed value [w ′] _i using a common key between the user device and the i-th authentication server for i = 1,..., N−1. phased ciphertext _{Enc US_i ([w '] i} ) give, using the common key between the user device and the intermediate authentication server, variance [w'] encrypt _n ciphertext Enc _{US_n} ([w ' ] get _n ). In the password distributed value transfer step, the intermediate authentication server _transmits the cipher text Enc _{US_i} ([w ′] _i ) received from the user device to i-th authentication server for i = 1,..., N−1. In the first password distributed value decryption step, the authentication server decrypts and distributes the ciphertext Enc _{US_i} ([w '] _i ) received from the intermediate authentication server using a common key between the user device and the authentication server. Get the value [w '] _i . In the second password distributed value decryption step, the intermediate authentication server decrypts the ciphertext Enc _{US_n} ([w ′] _n ) using the common key between the user device and the intermediate authentication server, and the distributed value [w ′ ] get _n . In the first authentication server verification value generation step, the authentication server ^{obtains a} verification value q _{a_i} ^(a_j) for j = 1 ^,.

In the second authentication server verification value generation step, the intermediate authentication server ^{calculates a} verification value q _{a_m} ^(a_j) for j = 1 ^,.

In the first authentication server verification value encryption step, with respect to j = 1,..., M, the a _j- th authentication server and the a _m- th intermediate authentication server and a common key of the authentication server, A ciphertext Enc _{S_a_iS_a_j} (q _{a_i} ^(a_j) ) obtained by encrypting the verification value q _{a_i} ^(a_j ) is obtained. In the second authentication server verification value encryption step, for the j = 1,..., M−1, the intermediate authentication server uses a common key between the a _jth authentication server and the intermediate authentication server to verify the verification value q _{a_m} ^A ciphertext Enc _{S_a_mS_a_j} (q _{a_m} ^(a_j) ) obtained by encrypting ^(a_j ) is obtained. In the first authentication server verification value decryption step, for the j = 1,..., M, the authentication server uses a common key between the a _j- th authentication server and the a _m- th intermediate authentication server and the authentication server to _The ciphertext Enc _{S_a_iS_a_j} (q _{a_j} ^(a_i) ) received from the _j- th authentication server is decrypted to obtain a verification value q _{a_j} ^(a_i) . In the second authentication server verification value decoding step, intermediate authentication server, j = 1, ..., the m-1, using a common key between a _j-th authentication server and the intermediate authentication server, a _j-th authentication The ciphertext Enc _{S_a_mS_a_j} (q _{a_j} ^(a_m) ) received from the server is decrypted to obtain a verification value q _{a_j} ^(a_m) . In the first authentication server verification step, the authentication server verifies whether or not the sum of the verification values q a — ₁ ^(a_i) ,..., Q a — _m ^(a_i) is equal to zero. In the second authentication server verification step, the intermediate authentication server verifies whether the sum of the verification values q a — ₁ ^(a_m) ,..., Q a — _m ^(a_m) is equal to 0 or not.

  According to the present invention, even when an intermediate server exists, a plurality of servers can simultaneously securely authenticate users.

FIG. 1 is a diagram illustrating a functional configuration of a multi-party secure authentication system according to the first embodiment. FIG. 2 is a diagram illustrating a functional configuration of the user device according to the first embodiment. FIG. 3 is a diagram illustrating a functional configuration of the intermediate server according to the first embodiment. FIG. 4 is a diagram illustrating a functional configuration of the authentication server according to the first embodiment. FIG. 5 is a diagram illustrating a process flow of the password registration phase of the multi-party secure authentication method according to the first embodiment. FIG. 6 is a diagram illustrating a processing flow of the random number generation phase of the multi-party secure authentication method according to the first embodiment. FIG. 7 is a diagram illustrating a processing flow of the authentication phase of the multi-party secure authentication method according to the first embodiment. FIG. 8 is a diagram illustrating a processing flow in an authentication phase of the multi-party secure authentication method according to the first embodiment. FIG. 9 is a diagram illustrating a processing flow of the authentication phase of the multi-party secure authentication method according to the first embodiment. FIG. 10 is a diagram illustrating a functional configuration of the multi-party secure authentication system according to the second embodiment. FIG. 11 is a diagram illustrating a functional configuration of the user device according to the second embodiment. FIG. 12 is a diagram illustrating a functional configuration of the intermediate server according to the second embodiment. FIG. 13 is a diagram illustrating a functional configuration of the authentication server according to the second embodiment. FIG. 14 is a diagram illustrating a processing flow of a random number generation phase of the multi-party secure authentication method according to the second embodiment. FIG. 15 is a diagram illustrating a processing flow of the authentication phase of the multi-party secure authentication method according to the second embodiment. FIG. 16 is a diagram illustrating a functional configuration of a multi-party secure authentication system according to the third embodiment. FIG. 17 is a diagram illustrating a functional configuration of the user device according to the third embodiment. FIG. 18 is a diagram illustrating a functional configuration of the intermediate server according to the third embodiment. FIG. 19 is a diagram illustrating a functional configuration of the authentication server according to the third embodiment. FIG. 20 is a diagram illustrating a processing flow of a random number generation phase of the multi-party secure authentication method according to the third embodiment. FIG. 21 is a diagram illustrating a processing flow of the random number generation phase of the multi-party secure authentication method according to the third embodiment.

  Hereinafter, embodiments of the present invention will be described in detail. In addition, the same number is attached | subjected to the component which has the same function in drawing, and duplication description is abbreviate | omitted.

[Notation]
Prior to the description of the embodiments, notation methods and terms used in this specification are defined.
• _ (underscore) represents a subscript. For example, ^xy_z represents that _yz is a superscript to x, and _{xy_z} represents that _yz is a subscript to x.
・ ^ (Caret) indicates that circumflex is added immediately after the character. For example, ^ λ represents the following characters in the formula:

• ^→ (superscript right arrow) represents a vector.
-[] (Square brackets) represents the variance of the data in parentheses. For example, [w] is a variance value of w.
Enc _AB (X) represents a ciphertext obtained by encrypting the data X with the common key between the node A and the node B.

[basic way of thinking]
The basic concept of the multi-party secure authentication technique of the present invention will be described.

Characters throughout are a user terminal (also called user device) 1, an intermediate server 2, and n authentication servers 3 ₁ ,..., 3 _n . However, n is an integer of 3 or more.

First, the fact that the password of the user terminal 1 using the system is w is registered in the authentication server group 3 ₁ ,..., 3 _n . Some random numbers used together with the authentication are also generated by the user and sent to the authentication servers 3 ₁ ,..., 3 _n . At this time, the distributed value to be transmitted is encrypted with a common key with each authentication server 3 ₁ ,..., 3 _{n so} that the intermediate server 2 in the middle does not impersonate the user terminal 1 by misusing these information. deep. The password itself also uses secret sharing, and only the password sharing value is stored in each authentication server 3 ₁ ,..., 3 _n . Therefore, each authentication server 3 ₁ ,..., 3 _n does not know the password itself.

Next, an authentication procedure will be described. When the user terminal 1 tries to authenticate with the password w ′, w and w ′ are used to confirm that the password w of the registered user terminal 1 matches the input password w ′. The difference of 0 is derived by collaborative calculation. Each participant is responsible for authentication so that the authority of authentication is not biased to any of the participants constituting the system (specifically, the intermediate server 2 and the authentication servers 3 ₁ ,..., 3 _n ). Perform the calculation. The collaborative calculation is performed in combination with a random number so that the password w registered by the collaborative calculation and the input password w ′ are not known to each participant. Also, the random number is updated at the end of the authentication procedure so that the random number used at this time is not reused in the next authentication.

Further, in order to cope with a replay attack by misusing the ciphertext exchanged via the intermediate server 2 in the authentication procedure, a random number is generated in advance by the authentication servers 3 ₁ ,..., 3 _n and shared with the user terminal 1. Thus, an improved method for making it impossible to reuse the ciphertext of the password transmitted during authentication will be described. Note that the replay attack is an attack in which the ciphertext that has been successfully authenticated is reused, and the intermediate server 2 impersonates the user device 1 and succeeds in authentication.

[Secret sharing technology]
In the present invention, a secret sharing technique is used as a component. The secret sharing technique used in the present invention uses (k, n) secret sharing such that 2k-1 <n. (k, n) Secret sharing is a technology that divides certain data into n pieces, and even if k-1 pieces are collected, nothing is known about the original data, but if more than k pieces are collected, the original data can be restored. is there.

  Specifically, the secret sharing technique includes a Share algorithm and a Reconst algorithm described below.

  The Share algorithm is an algorithm for dividing data. The divided data is called a share or a variance value. The Share algorithm takes the secret s as input and divides it into n pieces for output. This procedure is described as follows:

The Reconst algorithm is an algorithm for restoring data. The Reconst algorithm takes m (k ≦ m ≦ n) shares as input and outputs the original secret s. The secret sharing technique utilized in the present invention, m and _{{a 1, ..., a m} } and determining from _{λ a_i (i = 1, ...} , m) is present, the following equation holds. a ₁ ,..., a _m are m integers different from 1 to n.

[First embodiment]
An example of a functional configuration of the multi-party secure authentication system according to the first embodiment will be described with reference to FIG. The multi-party secure authentication system includes a user device 1, an intermediate server 2, and n authentication servers 3 ₁ ,..., 3 _n .

  An example of the functional configuration of the user device 1 will be described with reference to FIG. The user device 1 includes a control unit 101, a memory 102, a common key storage unit 11, a password distribution unit 12, and a password distribution value encryption unit 13. The user device 1 is, for example, a special device configured by reading a special program into a known or dedicated computer having a central processing unit (CPU), a main storage device (Random Access Memory, RAM), and the like. Device. For example, the user apparatus 1 executes each process under the control of the control unit 101. The data input to the user device 1 and the data obtained in each process are stored in the memory 102, for example, and the data stored in the memory 102 is read out as needed and used for other processes. . Each storage unit included in the user device 1 includes, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory, or It can be configured with middleware such as a relational database or key-value store.

  An example of the functional configuration of the intermediate server 2 will be described with reference to FIG. The intermediate server 2 includes a control unit 201, a memory 202, a common key storage unit 21, a password distribution value transfer unit 22, an intermediate server verification value decryption unit 23, and an intermediate server verification unit 24. The intermediate server 2 has a special configuration in which a special program is read into a known or dedicated computer having a central processing unit (CPU), a main storage device (Random Access Memory, RAM), and the like. Device. For example, the intermediate server 2 executes each process under the control of the control unit 201. The data input to the user device 1 and the data obtained in each process are stored in the memory 202, for example, and the data stored in the memory 202 is read out as needed and used for other processes. . Each storage unit included in the intermediate server 2 is, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory, or a relational device. It can be configured with middleware such as a database or key-value store.

  An example of a functional configuration of the authentication server 3 will be described with reference to FIG. The authentication server 3 includes a control unit 301, a memory 302, a random number distribution value generation unit 31, a zero distribution value generation unit 32, a password distribution value decryption unit 33, an intermediate server verification value generation unit 34, an intermediate server verification value encryption unit 35, An authentication server verification value generation unit 36, an authentication server verification value encryption unit 37, an authentication server verification value decryption unit 38, an authentication server verification unit 39, a common key storage unit 41, and a distributed value storage unit 42 are included. The authentication server 3 has a special configuration in which a special program is read into a known or dedicated computer having a central processing unit (CPU), a main storage device (Random Access Memory, RAM), and the like. Device. For example, the authentication server 3 executes each process under the control of the control unit 301. The data input to the authentication server 3 and the data obtained in each process are stored in the memory 302, for example, and the data stored in the memory 302 is read out as necessary and used for other processes. Each storage unit included in the authentication server 3 is, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory, or a relational device. It can be configured with middleware such as a database or key-value store. Each storage unit included in the authentication server 3 only needs to be logically divided, and may be stored in one physical storage device.

  With reference to FIGS. 5 to 10, an example of the processing flow of the multi-party secure authentication method will be described in the order of procedures actually performed.

The common key storage unit 11 of the user terminal 1 stores a common key with each device with which the user terminal 1 performs encrypted communication. Specifically, it is a common key for the user terminal 1 and each authentication server 3 ₁ ,..., 3 _n , and a total of n common keys are stored.

The common key storage unit 21 of the intermediate server 2 stores a common key with each device with which the intermediate server 2 performs encrypted communication. Specifically, it is a common key for the intermediate server 2 and each of the authentication servers 3 ₁ ,..., 3 _n , and a total of n common keys are stored.

The common key storage unit 41 of the i-th authentication server 3 _i stores a common key with each device with which the authentication server 3 _i performs encrypted communication. Specifically, it is a common key with the user terminal 1, the intermediate server 2, and other n-1 authentication servers 3 _j (j = 1,..., N, j ≠ i), and one authentication server 3 common key storage units 41 store a total of n + 1 common keys.

  The common key cryptosystem used in the present invention may be any existing common key cryptosystem, and may be selected in consideration of the safety and processing speed required in the information system to which the present invention is applied. The common key stored in each device is a common key generated according to the selected common key encryption method, and may be shared by a key exchange method allowed by the common key encryption method.

<< Password registration phase >>
With reference to FIG. 5, the process of the password registration phase of the multi-party secure authentication method will be described. The password registration phase is executed when a new user is registered or when a password of a registered user is changed.

In step S101, the password distribution unit 12 of the user terminal 1 distributes the password w into n distributed values [w] ₁ ,..., [W] _n . The password w is an arbitrary password entered by operating the user terminal 1 by the user U. That is, the password distribution unit 12 calculates the following formula (3).

In step S102, the password distributed value encryption unit 13 of the user terminal 1 uses the common key between the user apparatus 1 and the i-th authentication server 3 _i for i = 1,. get the encrypted cipher text Enc _{US_i} ([w] _i) a w] _i.

In step S103, the password distributed value encryption unit 13 of the user terminal 1 uses the n ciphertexts Enc _{US_1} ([w] ₁ ),..., Enc _{US_n} ([w] _n ) obtained in step S102 as intermediate servers. 2 to send.

In step S201, the password distribution value transfer unit 22 of the intermediate server 2 receives n ciphertexts Enc _{US_1} ([w] ₁ ),..., Enc _{US_n} ([w] _n ) received from the user terminal 1. , I = 1,..., N, the ciphertext Enc _{US_i} ([w] _i ) is transmitted to the authentication server 3 _i .

In step S301, the password distribution value decryption unit 33 of the authentication server 3 _i receives the ciphertext Enc _{US_i} ([w] _i ) transferred from the intermediate server 2.

In step S302, the authentication server 3 _i password variance value decoding unit 33 of by using the common key of the user terminal 1 and the authentication server 3 _i, the ciphertext received from the intermediate server _{2 Enc US_i ([w] i} ) To obtain the variance value [w] _i . The variance value [w] _i is stored in the variance value storage unit 42.

<< Random number generation phase >>
With reference to FIG. 6, the process of the random number generation phase of the multi-party secure authentication method will be described. The random number generation phase needs to be executed at least before the user who has registered the password authenticates.

In step S311, the authentication server 3 _i random variance value generator 31 of the random number r ₁ Restoring, ..., d pieces of variance which is a _{r d [r 1] i,} ..., to produce a [r _{d] i} . The generated variance values [r ₁ ] _i ,..., [R _d ] _i are stored in the variance value storage unit 42. Here, d ≧ 1.

In step S312, the zero variance value generation unit 32 of the authentication server 3 _i generates d variance values [0 ₁ ] _i ,..., [0 _d ] _i that become 0 when restored. The generated variance values [0 ₁ ] _i ,..., [0 _d ] _i are stored in the variance value storage unit 42.

  The processing from step S311 to step S312 may be executed in parallel with the processing from step S101 to step S302, or may be performed in advance independently.

<< Certification phase >>
Processing in the authentication phase of the multi-party secure authentication method will be described with reference to FIGS. The authentication phase is executed when a user who has registered a password requests authentication. The authentication phase process need not be performed by all the _n authentication servers 3 ₁ ,..., 3 _n , and may be performed only by arbitrarily selected m servers. In the following description, a _1, ..., a 1 to n phases m different integers a _m, m stand authentication server 3 _{a_1,} ..., 3 _{a_m} is assumed to perform the processing of the authentication phase.

The authentication server 3 _{a_i} includes the distributed values [r ₁ ] _{a_i} ,..., [R _d ] _{a_i} stored in the distributed value storage unit 42 to [r ^(W) ] _{a_i} , [r ⁽¹⁾ ] _{a_i,.} [r ^(m) ] Select _{a_i} . Similarly, the authentication server 3 _{a_i} uses the distributed values [0 ₁ ] _{a_i} ,..., [0 _d ] _{a_i} stored in the distributed value storage unit 42 to [0 ^(W) ] _{a_i,} [0 ⁽¹⁾ ] _{a_i} , ..., [0 ^(m) ] Select _{a_i} .

  In step S121 shown in FIG. 7, the user U who has registered the password w operates the user terminal 1 and inputs the password w 'for requesting authentication.

In step S122, the password distribution unit 12 of the user terminal 1 distributes the password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n . That is, the password distribution unit 12 performs the following calculation.

In step S123, the password variance encryption unit 13 of the user terminal 1, i = 1, ..., for m, variance [w '] _{a_i} the user device 1 and a _i-th of the authentication server 3 _{a_i} A ciphertext Enc _{US_a_i} ([w '] _{a_i} ) encrypted using the common key is obtained.

In step S124, the password distributed value encryption unit 13 of the user terminal 1 uses the n ciphertexts Enc _{US_1} ([w ′] ₁ ),..., Enc _{US_n} ([w ′] _n ) obtained in step S123. Transmit to the intermediate server 2.

In step S221, the password distribution value transfer unit 22 of the intermediate server 2 receives the n ciphertexts Enc _{US_1} ([w ′] ₁ ),..., Enc _{US_n} ([w ′] _n ) received from the user terminal 1. Then, for i = 1,..., _M , the ciphertext Enc _{US_a_i} ([w ′] _{a_i} ) is transmitted to the authentication server 3 _{a_i} .

In step S321, the password distribution value decryption unit 33 of the authentication server 3 _{a_i} receives the ciphertext Enc _{US_a_i} ([w ′] _{a_i} ) transferred from the intermediate server 2.

In step S322, the password distribution value decryption unit 33 of the authentication server 3 _{a_i} uses the ciphertext Enc _{US_a_i} ([w ′] _{a_i} ) received from the intermediate server 2 using the common key of the user terminal 1 and the authentication server 3 _{a_i.} To obtain the variance [w ′] _{a_i} .

In step S331 shown in FIG. 8, the intermediate server verification value generation unit 34 of the authentication server 3 _{a_i} stores the distributed values [w] _{a_i} , [r ^(W) ] _{a_i} , [0 ^{( W)]} _{a_i} and output variance of the password variance value decoding unit 33 by using the [w '] _{a_i,} obtains the verification value q _{a_i} ^(W) by the following equation (5).

Here, λ a — _i ^(W) is a known constant that satisfies Equation (6), and ^ λ a — _i ^(W) is a known constant that satisfies Equation (7).

In step S332, the authentication server 3 _{a_i} intermediate server verification value encryption section 35 of the by using the common key between the intermediate server 2 and the authentication server 3 _{a_i,} verification value q _{a_i} ^(W) ciphertext Enc _{WS_a_i} encrypted (q _{a_i} ^(W) ) is obtained.

In step S333, the authentication server 3 _{a_i} intermediate server verification value encryption unit 35 of the transmitting ciphertext Enc _{WS_a_i} obtained at step S332 the ^(q _{a_i} ^(W)) to the intermediate server 2.

In step S231, the intermediate server verification value decoding unit 23 of the intermediate server 2, m stand authentication server 3 _{a_1,} ..., 3 m pieces of encrypted text received from ^{_{a_m Enc WS_a_1 (q a_1 (W}} )), ..., Enc _{WS_a_m} (q _{a_m} ^(W) ) is received.

In step S232, the intermediate server verification value decryption unit 23 of the intermediate server 2 uses, for i = 1,..., _M , the ciphertext Enc _{WS_a_i} using the common key between the intermediate server 2 and the _ai- th authentication server 3 _{a_i.} It decodes the ^(q _{a_i} ^(W)) to obtain a verification value q _{a_i} ^(W). The intermediate server verification value decoding unit 23 outputs m verification values q a — ₁ ^(W) ,..., Q a — _m ^(W) to the intermediate server verification unit 24.

In step S233, the intermediate server verification unit 24 of the intermediate server 2 verifies whether the sum of the verification values q a — ₁ ^(W) ,..., Q a — _m ^(W) is equal to zero. Specifically, the intermediate server verification unit 24 checks whether or not the equation (8) is satisfied.

  The intermediate server verification unit 24 notifies the user device 1 of the authentication success when the equation (8) is satisfied, and notifies the user device 1 of the authentication failure when the equation (8) does not hold.

In step S341i shown in FIG. 9, the authentication server verification value generation unit 36 of the authentication server 3 _{a_i} sets the distributed values [w] _{a_i} , [r] stored in the distributed value storage unit 42 for j = 1,. ^(a_j) ] Using _{a_i} , [0 ^(a_j) ] _{a_i} and the distributed value [w ′] _{a_i} output from the password distributed value decryption unit 33, a verification value q _{a_i} ^(a_j) is obtained by the following equation (9). .

Here, lambda _{a_i} ^(j) is a known constant that satisfies the equation ^{_{(10), ^ λ a_i (}} j) is a known constant that satisfies the equation (11).

In step S342i, the authentication server 3 _{a_i} authentication server verification value encryption section 37 of, j = 1, ..., m (j ≠ i) For, a _j-th authentication server 3 of _{a_j} and a _i-th authentication server 3 _{a_i} The ciphertext Enc _{S_a_iS_a_j} (q _{a_i} ^(a_j) ) obtained by encrypting the verification value q _{a_i} ^(a_j) is obtained using the common key. As a result, the authentication server verification value encryption unit 37, m-1 pieces of ciphertext ^{_{Enc S_a_iS_a_1 (q a_i (a_1)}} ), ..., Enc S_a_iS_a_m (q a_i (a_m)) ( provided that, Enc _{S_a_iS_a_i} ^(q _{a_i} ( ^a_i) except)).

In step S343i, the authentication server 3 _{a_i} authentication server verification value encryption section 37 of, j = 1, ..., m (j ≠ i) the step m-1 pieces of ciphertext obtained by S342i Enc _{S_a_iS_a_1} (q _{a_i} ^(a_1) ),..., Enc _{S_a_iS_a_m} (q _{a_i} ^(a_m) ) (however, except for Enc _{S_a_iS_a_i} (q _{a_i} ^(a_i) )) are transmitted to the authentication server 3 _{a_j} .

In step S344i, the authentication server verification value decryption unit 38 of the authentication server 3 _{a_i} receives m−1 ciphertext Enc from the m−1 authentication servers 3 _{a_j} (j = 1,..., _M (j ≠ i)). _{S_a_1S_a_i} (q _{a_1} ^(a_i) ), ..., Enc _{S_a_mS_a_i} (q _{a_m} ^(a_i) ) (however, except for Enc _{S_a_iS_a_i} (q _{a_i} ^(a_i) )) is received.

In step S345i, the authentication server verification value decryption unit 38 of the authentication server 3 _{a_i} determines the a _jth authentication server 3 _{a_j} and the a _i th authentication server 3 _{a_i} for j = 1,..., _M (j ≠ i). The ciphertext Enc _{S_a_jS_a_i} (q _{a_j} ^(a_i) ) is decrypted using the common key to obtain the verification value q _{a_i} ^(a_j) . The authentication server verification value decryption unit 38 combines m verification values q _{a_1} ^(a_i) ,..., Q _{a_m} together with the verification values q _{a_i} ^(a_i) generated by the authentication server verification value generation unit 36 in step S341i. ^(a_i) is output to the authentication server verification unit 39.

In step S345i, the authentication server verification unit 39 of the authentication server 3 _{a_i} verifies whether or not the sum of the verification values q _{a_1} ^(a_i) ,..., Q _{a_m} ^(a_i) is equal to zero. Specifically, the authentication server verification unit 39 checks whether or not the equation (12) is satisfied.

  The authentication server verification unit 39 notifies the user device 1 of the authentication success when the equation (12) is satisfied, and notifies the user device 1 of the authentication failure when the equation (12) does not hold.

<< Random number update phase >>
Each time the authentication phase process is executed, the random number update phase process is executed. The random number update phase is a process of updating the random number so that the random number is not reused in the next authentication. In the random number update phase, if there is an unused random number generated by the process of the previous random number generation phase, the random number is set to be used in the next authentication phase process. If there is no unused random number, a new random number is generated in the same manner as the processing contents of the random number generation phase. The random number update phase process may be performed in parallel with the authentication phase process. That is, it is only necessary to check whether there are enough unused random numbers when random numbers are used in the authentication phase.

[Second Embodiment]
In addition to the success or failure of authentication, the ciphertext exchanged between the user terminal and the authentication server is known to intermediate servers such as Web servers that exist between the user terminal used by the user and each authentication server. . If the intermediate server succeeds in the authentication, there is a risk that the authentication may succeed by impersonating the user by misusing the ciphertext of the password or random number distributed value used in the authentication procedure. The multi-party secure authentication system of the second embodiment is an improved method for preventing a replay attack by an intermediate server that misuses a transmitted ciphertext.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

With reference to FIG. 10, an example of a functional configuration of the multi-party secure authentication system according to the second embodiment will be described. Multi-party secure authentication system, user device 4, the intermediate server 5 and n stand authentication server _61, ..., contains a 6 _n.

An example of a functional configuration of the user device 4 will be described with reference to FIG. Similar to the user device 1 according to the first embodiment, the user device 4 includes a control unit 101, a memory 102, a common key storage unit 11, and a password distribution unit 12. The user device 4 according to the second embodiment further includes a password distributed value encryption unit 14 and a random number decryption unit 15. The password distributed value encryption unit 14 is different in processing from the password distributed value encryption unit 13 according to the first embodiment.

  An example of the functional configuration of the intermediate server 5 will be described with reference to FIG. Similar to the intermediate server 2 according to the first embodiment, the intermediate server 5 includes a control unit 201, a memory 202, a common key storage unit 21, an intermediate server verification value decryption unit 23, and an intermediate server verification unit 24. The intermediate server 5 according to the second embodiment further includes a password distributed value transfer unit 25 and a random number transfer unit 26. The password distribution value transfer unit 25 is different in processing from the password distribution value transfer unit 22 according to the first embodiment.

  An example of a functional configuration of the authentication server 6 will be described with reference to FIG. Similar to the authentication server 3 according to the first embodiment, the authentication server 6 includes a control unit 301, a memory 302, a random number distribution value generation unit 31, a zero distribution value generation unit 32, an intermediate server verification value generation unit 34, and an intermediate server verification. A value encryption unit 35, an authentication server verification value generation unit 36, an authentication server verification value encryption unit 37, an authentication server verification value decryption unit 38, an authentication server verification unit 39, a common key storage unit 41, and a distributed value storage unit 42 are included. . The authentication server 6 according to the second embodiment further includes a password distributed value decryption unit 43, a random number generation unit 44, a random number encryption unit 45, and a random number verification unit 46. The password distribution value decryption unit 43 is different in processing from the password distribution value decryption unit 33 according to the first embodiment.

  With reference to FIGS. 14 and 15, an example of the processing flow of the multi-party secure authentication method according to the second embodiment will be described in the order of procedures actually performed.

With reference to FIG. 14, a procedure for generating a random number used for preventing a replay attack will be described. This random number generation needs to be performed in advance before executing the authentication phase. Since this process is a relatively light process, the process may be performed immediately before the authentication phase is executed. This process does not have to be performed by all _n authentication servers 6 ₁ ,..., 6 _n , and only m m selected arbitrarily may be performed. In the following description, a _1, ..., a a _m as 1 to n distinct m integers, m stand authentication server 6 _{a_1,} ..., 6 _{a_m} is assumed to perform the processing.

In step S351, the random number generation unit 44 of the authentication server 6 _{a_i} generates a random number t _{a_i} .

In step S352, the authentication server 6 _{a_i} random number encryption section 45 by using the common key of the user device 4 and a _i-th authentication server 6 _{a_i,} ciphertext obtained by encrypting the random number t _{a_i} Enc _{US_a_i} (t _{a_i} ) is obtained.

In step S353, the authentication server 6 _{a_i} random number encryption unit 45 transmits the ciphertext Enc _{US_a_i} a (t _{a_i)} to the intermediate server 5.

In step S251, the random number transfer unit 26 of the intermediate server 5, m stand authentication server _{6 a_i (i = 1, ...} , m) m pieces of ciphertext from _{Enc US_a_i (t a_i) (i} = 1, ..., m ). Received m pieces of ciphertext _{Enc US_a_i (t a_i) (i} = 1, ..., m) is sent to the user terminal 4.

In step S151, the random number decoder 15 of the user terminal 4, m pieces of ciphertext from the intermediate server _{5 Enc US_a_i (t a_i) (} i = 1, ..., m) to receive.

In step S152, the random number decoder 15, i = 1, ..., the m, to obtain a dispersion value t _{a_i} decrypts the ciphertext Enc _{US_a_i} (t _{a_i).} The distributed value _{ta_i} is stored in any storage unit such as the memory 102 or the common key storage unit 11.

  With reference to FIG. 15, the process of the authentication phase improved in order to prevent a replay attack is demonstrated. The difference from the authentication phase of the first embodiment is that the processes in steps S123 and S221 are different and the process in step S323 is added.

In step S123, the password distributed value encryption unit 14 of the user terminal 4 sets the _shared value [w ′] _{a_i} together with the random number t _{a_i} and the user device 4 and the a _i th authentication server for i = 1 _,. ciphertext was encrypted using a common key with _{6 a_i Enc US_a_i (t a_i,} [w '] a_i) obtained.

In step S221, the password variance value transfer section 25 of the intermediate server 5, the user the m encrypted text received from the terminal _{4 Enc US_a_1 (t a_i, [} w '] a_1), ..., Enc US_a_m (t a_i, [ 'I receive _{a] a_m), i = 1,} ..., for m, the ciphertext _{Enc US_a_i (t a_i, [w} ' w be transmitted to the authentication server 6 _{a_i} a] _{a_i).}

In step S323, the random number verification unit 46 of the authentication server 6 _{a_i} determines whether the random number t _{a_i} obtained by decrypting the ciphertext Enc _{US_a_i} (t _{a_i} , [w ′] _{a_i} ) is equal to the random number t _{a_i} generated in step S351. Confirm whether or not. The random number verification unit 46 notifies the user device 4 of an authentication failure when the random number t _{a_i} obtained by decryption is not equal to the random number t _{a_i} generated in step S351. In other cases, the processing after step S331 in the authentication phase is continued.

[Third embodiment]
In the multi-party secure authentication system according to the first embodiment, each authentication server executes a random number generation phase process. In the multi-party secure authentication system according to the third embodiment, the user terminal executes a random number generation phase process. In the following, an example of application to the multi-party secure authentication system of the first embodiment will be described. However, the configuration method of the third embodiment is similarly applied to the multi-party secure authentication system of the second embodiment. Can do.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

An example of a functional configuration of the multi-party secure authentication system according to the third embodiment will be described with reference to FIG. Multi-party secure authentication system, user device 7, the intermediate server 8 and n stand authentication server 9 _1, ..., including 9 _n.

  An example of the functional configuration of the user device 7 will be described with reference to FIG. Similar to the user device 1 according to the first embodiment, the user device 7 includes a control unit 101, a memory 102, a common key storage unit 11, a password distribution unit 12, and a password distribution value encryption unit 13. The user device 7 according to the third embodiment further includes a random number distribution value generation unit 16, a random number distribution value encryption unit 17, a zero distribution value generation unit 18, and a zero distribution value encryption unit 19.

  An example of a functional configuration of the intermediate server 8 will be described with reference to FIG. Similar to the intermediate server 2 according to the first embodiment, the intermediate server 8 includes a control unit 201, a memory 202, a common key storage unit 21, a password distribution value transfer unit 22, an intermediate server verification value decryption unit 23, and an intermediate server verification unit. 24. The intermediate server 8 according to the third embodiment further includes a random number distributed value transfer unit 27 and a zero distributed value transfer unit 28.

  An example of a functional configuration of the authentication server 9 will be described with reference to FIG. Similar to the authentication server 3 according to the first embodiment, the authentication server 9 includes a control unit 301, a memory 302, an intermediate server verification value generation unit 34, an intermediate server verification value encryption unit 35, an authentication server verification value generation unit 36, An authentication server verification value encryption unit 37, an authentication server verification value decryption unit 38, an authentication server verification unit 39, a common key storage unit 41, and a distributed value storage unit 42 are included. The authentication server 9 according to the third embodiment further includes a random number distributed value decoding unit 47 and a zero distributed value decoding unit 48.

  With reference to FIGS. 20 and 21, an example of the processing flow of the multi-party secure authentication method according to the third embodiment will be described in the order of procedures actually performed.

<< Random number generation phase >>
Processing of the random number generation phase according to the third embodiment will be described with reference to FIGS.

In step S111 shown in FIG. 20, the random number distribution value generation unit 16 of the user terminal 7 generates n + 1 random numbers r ^(W) , r ⁽¹⁾ ,..., R ⁽ⁿ⁾ .

In step S112, the random number distribution value generation unit 16 of the user terminal 7 converts each random number r ^(W) , r ⁽¹⁾ ,..., R ⁽ⁿ⁾ into n distribution values [r ^(W) ] ₁ , …, [R ^(W) ] _n , [r ⁽¹⁾ ] ₁ ,…, [r ⁽¹⁾ ] _n ,…, [r ⁽ⁿ⁾ ] ₁ ,…, [r ⁽ⁿ⁾ ] _n . That is, the random number distribution value generation unit 16 calculates the following equations (13) and (14).

In step S113, the random number distributed value encryption unit 17 of the user terminal 7 uses the common key between the user device 7 and the i-th authentication server 9 _i for i = 1,. _{^{r (W)] i, [}} r (1)] i, ..., [r (n)] ciphertext _i was encrypted ^{_{Enc US_i ([r (W)}} ] i, [r (1)] i, ... , [r ⁽ⁿ⁾ ] _i ).

In step S114, the random number distributed value encryption unit 17 of the user terminal 7 generates the n ciphertexts Enc _{US_1} ([r ^(W) ] ₁ , [r ⁽¹⁾ ] _{1 ,.} r ⁽ⁿ⁾ ] ₁ ),..., Enc _{US_n} ([r ^(W) ] _n , [r ⁽¹⁾ ] _n ,..., [r ⁽ⁿ⁾ ] _n ) are transmitted to the intermediate server 8.

In step S211, the random number distributed value transfer unit 27 of the intermediate server 8 receives n ciphertexts Enc _{US_1} ([r ^(W) ] ₁ , [r ⁽¹⁾ ] _{1 ,.} r ⁽ⁿ⁾ ] ₁ ), ..., Enc _{US_n} ([r ^(W) ] _n , [r ⁽¹⁾ ] _n , ..., [r ⁽ⁿ⁾ ] _n ) are received and i = 1, ..., n _Ciphertext Enc _{US_i} ([r ^(W) ] _i , [r ⁽¹⁾ ] _i ,..., [R ⁽ⁿ⁾ ] _i ) is transmitted to the authentication server 9 _i .

In step S313, the random number distributed value decryption unit 47 of the authentication server 9 _{i transmits the} ciphertext Enc _{US_i} ([r ^(W) ] _i , [r ⁽¹⁾ ] _i ,..., [R ^{( n)} ] _i ) is received.

In step S314, the authentication server 9 _i of the random number variance decoding unit 47 by using the common key of the user terminal 7 and the authentication server 9 _i, the ciphertext received from the intermediate server ^{_{8 Enc US_i ([r (W}} ) ] _i , [r ⁽¹⁾ ] _i , ..., [r ⁽ⁿ⁾ ] _i ) and n + 1 variance values [r ^(W) ] _i , [r ⁽¹⁾ ] _i , ..., [r ⁽ⁿ⁾ ] _i is obtained. The variance values [r ^(W) ] _i , [r ⁽¹⁾ ] _i ,..., [R ⁽ⁿ⁾ ] _i are stored in the variance value storage unit 42.

In step S115 shown in FIG. 21, the zero dispersion value generator 18 of the user terminal 7, restoring becomes 0 m + 1 set of variance _{^{[0 (W)] 1,}} ..., [0 (W)] n , [0 ⁽¹⁾ ] ₁ , ..., [0 ⁽¹⁾ ] _n , ..., [0 ^(m) ] ₁ , ..., [0 ^(m) ] _n .

In step S116, the zero distributed value encryption unit 19 of the user terminal 7 uses the common key between the user device 7 and the i-th authentication server 9 _i for i = 1,. _{^{0 (W)] i, [}} 0 (1)] i, ..., [0 (m)] ciphertext _i was encrypted ^{_{Enc US_i ([0 (W)}} ] i, [0 (1)] i, ... , [0 ^(m) ] _i ).

In step S117, the zero distributed value encryption unit 19 of the user terminal 7 generates n ciphertexts Enc _{US_1} ([0 ^(W) ] ₁ , [0 ⁽¹⁾ ] _{1 ,.} 0 ^(m) ] ₁ ),..., Enc _{US_n} ([0 ^(W) ] _n , [0 ⁽¹⁾ ] _n ,..., [0 ^(m) ] _n ) are transmitted to the intermediate server 8.

In step S212, the zero variance value transfer unit 28 of the intermediate server 8 receives n ciphertexts Enc _{US_1} ([0 ^(W) ] ₁ , [0 ⁽¹⁾ ] _{1 ,.} 0 ^(m) ] ₁ ), ..., Enc _{US_n} ([0 ^(W) ] _n , [0 ⁽¹⁾ ] _n , ..., [0 ^(m) ] _n ) are received and i = 1, ..., n Cipher text Enc _{US_i} ([0 ^(W) ] _i , [0 ⁽¹⁾ ] _i ,..., [0 ^(m) ] _i ) is transmitted to the authentication server 9 _i .

In step S315, the zero distributed value decryption unit 48 of the authentication server 9 _{i transmits the} ciphertext Enc _{US_i} ([0 ^(W) ] _i , [0 ⁽¹⁾ ] _i ,..., [0 ^{( m)} ] _i ) is received.

In step S316, the zero dispersion value decoding unit 48 of the authentication server 9 _i by using the common key of the user terminal 7 and the authentication server 9 _i, the ciphertext received from the intermediate server ^{_{8 Enc US_i ([0 (W}} ) ] _i , [0 ⁽¹⁾ ] _i , ..., [0 ^(m) ] _i ) and m + 1 variance values [0 ^(W) ] _i , [0 ⁽¹⁾ ] _i , ..., [0 ^(m) ] _i is obtained. The variance values [0 ^(W) ] _i , [0 ⁽¹⁾ ] _i ,..., [0 ^(m) ] _i are stored in the variance value storage unit 42.

  The processing from step S111 to step S316 may be executed in parallel with the processing from step S101 to step S302, or may be performed in advance independently, as in the multi-party secure authentication method of the first embodiment. I do not care.

[Fourth embodiment]
The multi-party secure authentication system of the fourth embodiment differs from the above-described embodiment only in the random number generation phase processing. The configuration method of the fourth embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

<< Random number generation phase >>
Processing in the random number generation phase according to the fourth embodiment will be described. In this embodiment, the authentication server 3 ₁ of n units, ..., 3 arbitrary n of _n - k + 1 single {b _1, ..., b _B} the set of combinations of the. However, B is defined by the following equation.

the authentication server 3 ₁ of n units, ..., 3 arbitrary n of _n - m + 2 units a set of combinations {c _1, ..., c _C} to. However, C is defined by the following formula.

the authentication server 3 ₁ of n units, ..., 3 arbitrary n of _n - m + 1 single set of combinations {d _1, ..., d _D} and. However, D is defined by the following equation.

In step S311 shown in FIG. 6, the random number variance value generator 31 of the authentication server 3 _i are random or pseudo-random number u ^(W) _1, ..., generates u ^(W) _B, the i∈b _j {u ^{( W)} _{b_j} } is held, and this is set as a variance value [r ^(W) ] _i . Random number _{^{u (W) 1, ...,}} u (W) B , each authentication server 3 ₁ generates the user terminal 1, ..., or may be transmitted to 3 _n, the authentication server 3 _1, ..., 3 _n may be generated mutually and sent to each other, or may be generated from a seed of pseudorandom numbers held in advance by the authentication servers 3 ₁ ,..., 3 _n .

Next, the authentication server 3 _i random variance generator 31 of, j = 1, ..., for n, a random number or pseudo-random number u ^(j) _1, ..., generates a u ^(j) _B, j∈b _h for holding the _{u ^(j) b_h}, which is a dispersion value [r ^(j)] _i. Random number _{^{u (j) 1, ...,}} u (j) B is the authentication server 3 ₁ generates the user terminal 1, ..., or may be transmitted to 3 _n, the authentication server 3 _1, ..., 3 _n may be generated mutually and sent to each other, or may be generated from a seed of pseudorandom numbers held in advance by the authentication servers 3 ₁ ,..., 3 _n .

The generated variance values [r ^(W) ] _i , [r ⁽¹⁾ ] _i ,..., [R ⁽ⁿ⁾ ] _i are stored in the variance value storage unit 42.

In step S312 shown in FIG. 6, the authentication server 3 _i zero dispersion value generator 32 of the random number or pseudo-random number u ^(W) _1, ..., generates u ^(W) _C, the i∈c _j {u ^{( W)} _{c_j} } is held , and the variance [0 ^(W) ] _i is calculated by the following equation (15).

Here, δ _{c_1} ,..., Δ _{c_D} are known constants.

Next, the authentication server 3 _i random variance generator 31 of, j = 1, ..., the m, a random number or pseudo-random number u ^(j) _1, ..., generates a u ^(j) _C, i∈c _{h Holds} {u ^(j) _{c_h} } and calculates the variance [0 ^(j) ] _i by the following equation (16).

The generated variance values [0 ^(W) ] _i , [0 ⁽¹⁾ ] _i ,..., [0 ^(m) ] _i are stored in the variance value storage unit 42.

[Fifth embodiment]
The multi-party secure authentication system of the fifth embodiment is different from the above-described embodiment only in the process of the random number generation phase. The configuration method of the fifth embodiment can be applied to the multi-party secure authentication system of the first embodiment to the third embodiment.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

<< Random number generation phase >>
Processing in the random number generation phase according to the fifth embodiment will be described. In the random number generation phase of this embodiment, the process of step S311 is the same as that of the fourth embodiment, and only the process of step S312 is different from the fourth embodiment.

In step S312, the zero variance value generation unit 32 of the authentication server 3 _i generates random numbers or pseudo-random numbers u ^(W) ₁ ,..., U ^(W) _C, and {u ^(W) _{c_j} } for i∈c _j . And the variance [0 ^(W) ] _i is calculated by the following equation (17).

Where f _{c_j} is a unique function for each u ^(W) _{c_j} (1 ≦ j ≦ C), f _{c_j} (0) = 1, f _{c_j} (g) = 0 (g does not belong to c _j ) Holds.

Next, the authentication server 3 _i random variance generator 31 of, j = 1, ..., the m, a random number or pseudo-random number u ^(j) _1, ..., generates a u ^(j) _C, i∈c _{h Holds} {u ^(j) _{c_h} }, and calculates the variance [0 ^(j) ] _i by the following equation (18).

[Sixth embodiment]
The multi-party secure authentication system of the sixth embodiment differs from the above-described embodiment only in the random number generation phase processing. The configuration method of the sixth embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

<< Random number generation phase >>
Processing in the random number generation phase according to the sixth embodiment will be described. In the random number generation phase of this embodiment, the process of step S312 is the same as that of the fourth embodiment, and only the process of step S311 is different from the fourth embodiment.

In step S311, the random number distribution value generation unit 31 of the authentication server 3 _i generates random numbers or pseudo-random numbers u ^(W) ₁ ,..., U ^(W) _B, and {u ^(W) _{b_j} } for i∈b _j And the variance [r ^(W) ] _i is calculated by the following equation (19).

Where f _{b_j} is a unique function for each u ^(W) _{b_j} (1 ≦ j ≦ B), f _{b_j} (0) = 1, f _{b_j} (g) = 0 (g does not belong to b _j ) Holds. This method is described in “Ronald Cramer, Ivan Damgard, and Yuval Ishai,“ Share conversion, pseudorandom secret-sharing and applications to secure computation ”, TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005. (Reference 1) ”is described in detail.

Next, the authentication server 3 _i random variance generator 31 of, j = 1, ..., the m, a random number or pseudo-random number u ^(j) _1, ..., generates a u ^(j) _B, i∈b _{h Holds} {u ^(j) _{b_h} } and calculates the variance [r ^(j) ] _i by the following equation (20).

[Seventh embodiment]
The multi-party secure authentication system of the seventh embodiment differs from the above-described embodiment only in the random number generation phase processing. The configuration method of the seventh embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

  Regarding the processing content of the random number generation phase of the seventh embodiment, the processing content of step S311 is the same as that of the sixth embodiment, and the processing content of step S312 is the same as that of the fifth embodiment. For the detailed processing procedure, refer to the description of the sixth embodiment and the fifth embodiment described above.

[Eighth embodiment]
The multi-party secure authentication system of the eighth embodiment differs from the above-described embodiment only in the random number generation phase processing. The configuration method of the eighth embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

  In the following description, points different from the first embodiment will be mainly described, and description of the same parts as those in the first embodiment will be omitted.

<< Random number generation phase >>
Processing in the random number generation phase according to the eighth embodiment will be described. In this embodiment, it is assumed that arbitrary q servers satisfying k ≦ q ≦ n among _n authentication servers 3 ₁ ,..., 3 _n participate. In the following, a ₁ ,..., A _q are q integers different from 1 to n.

In step S311 shown in FIG. 6, the random number variance value generator 31 of the authentication server 3 _{a_i} generates a random number u _i, the random number u _i (k, n) n pieces of variance using the secret sharing [u _i ] ₁ ,…, [u _i ] Distribute to _n . The random number distributed value generation unit 31 _encrypts the distributed value [u _i ] _{a_j} for j = 1,..., Q using a common key of the a _j th authentication server 3 _{a_j} and the a _i th authentication server 3 _{a_i.} The encrypted ciphertext Enc _{S_a_iS_a_j} ([u _i ] _{a_j} ) is obtained. The random number distribution value generation unit 31 transmits the ciphertext Enc _{S_a_iS_a_j} ([u _i ] _{a_j} ) to the authentication server 3 _{a_j} for j = 1 _,.

Next, the random number distribution value generation unit 31 of the authentication server 3 _{a_i} receives q−1 ciphertexts Enc _{S_a_1S_a_i} from q−1 authentication servers 3 _{a_j} (j = 1,..., Q, a _j ≠ a _i ). ([u ₁ ] _{a_i} ), ..., Enc _{S_a_qS_a_i} ([u _q ] _{a_i} ) (excluding Enc _{S_a_iS_a_i} ([u _i ] _{a_i} )) _{S_a_jS_a_i} ([u _{j] a_i)} a variance value by decoding by using the common key between a _j-th authentication server 3 _{a_j} and a _i-th authentication server 3 _{a_i} obtain [u _{j] a_i.} As a result, the random number variance value generator 31 itself generated variance value in conjunction with [u _{i] a_i,} q pieces of variance [u _{1] a_i,} ..., will get a [u _{q] a_i.}

Next, the random number distribution value generation unit 31 of the authentication server 3 _{a_i} considers A to be a q × (q−k + 1) matrix, and [u ₁ ] _{a_i} ,..., [U _q ] _{a_i} to be a column vector ^→ u. , Vector ^→ u ′ = A ^→ u is calculated.

  As the matrix A, for example, a vandermonde matrix or a Hyper-Invertible matrix can be used. For more information on Hyper-Invertible matrices, see “Zuzana Beerliova-Trubiniova and Martin Hirt,“ Perfectly-secure mpc with linear communi-cation complexity ”, TCC, Vol. 4948 of Lecture Notes in Computer Science, pp. 213-230, 2008. Please refer to.

Next, the random number distribution value generation unit 31 of the authentication server 3 _{a_i converts} each element of the vector ^→ u ′ into [r ^(W) ] _{a_i} , [r ⁽¹⁾ ] _{a_i} ,..., [R ^(m) ] _{a_i} It is considered. When q − k + 1 <m + 1, step S311 is executed again from the beginning to generate additional vector ^→ u ′, and is repeated until m + 1 elements are obtained. Conversely, if there are many, store them for use in the next authentication.

In step S312 shown in FIG. 6, the zero dispersion value generator 32 of the authentication server 3 _{a_i} generates a random number u _i, the random number _{u i (m-1, n} ) n pieces of variance using the secret sharing [ u _i ] ₁ , ..., [u _i ] are distributed over _n . The random number distributed value generation unit 31 _encrypts the distributed value [u _i ] _{a_j} for j = 1,..., Q using a common key of the a _j th authentication server 3 _{a_j} and the a _i th authentication server 3 _{a_i.} The encrypted ciphertext Enc _{S_a_iS_a_j} ([u _i ] _{a_j} ) is obtained. The random number distribution value generation unit 31 transmits the ciphertext Enc _{S_a_iS_a_j} ([u _i ] _{a_j} ) to the authentication server 3 _{a_j} for j = 1 _,.

Next, the random number distribution value generation unit 31 of the authentication server 3 _{a_i} receives q−1 ciphertexts Enc _{S_a_1S_a_i} from q−1 authentication servers 3 _{a_j} (j = 1,..., Q, a _j ≠ a _i ). ([u ₁ ] _{a_i} ), ..., Enc _{S_a_qS_a_i} ([u _q ] _{a_i} ) (excluding Enc _{S_a_iS_a_i} ([u _i ] _{a_i} )) _{S_a_jS_a_i} ([u _{j] a_i)} a variance value by decoding by using the common key between a _j-th authentication server 3 _{a_j} and a _i-th authentication server 3 _{a_i} obtain [u _{j] a_i.} As a result, the random number variance value generator 31 itself generated variance value in conjunction with [u _{i] a_i,} q pieces of variance [u _{1] a_i,} ..., will get a [u _{q] a_i.}

Next, the random number distribution value generation unit 31 of the authentication server 3 _{a_i} considers A to be a q × (q−k + 1) matrix, and [u ₁ ] _{a_i} ,..., [U _q ] _{a_i} to be a column vector ^→ u. , Vector ^→ u ′ = A ^→ u is calculated.

Next, random variance value generator 31 of the authentication server 3 _{a_i} is a vector ^→ u 'respectively a value obtained by multiplying the a _i to each element of _{^{[0 (W)] a_i,}} [0 (1)] a_i, ..., [0 ^(m) ] _{Consider a_i} . When q − k + 1 <m + 1, step S312 is executed again from the beginning to generate additional vector ^→ u ′ and repeat until m + 1 elements are obtained. Conversely, if there are many, store them for use in the next authentication.

[Ninth embodiment]
The multi-party secure authentication system of the ninth embodiment differs from the above-described embodiment only in the random number update phase processing. The configuration method of the ninth embodiment can be applied to the multi-party secure authentication system of the first embodiment to the third embodiment.

  Since the processing content of the random number update phase of the ninth embodiment is the same as the processing content of the random number generation phase of the fourth embodiment, refer to the description of the above fourth embodiment.

[Tenth embodiment]
The multi-party secure authentication system of the tenth embodiment differs from the above-described embodiment only in the process of the random number update phase. The configuration method of the tenth embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

Since the processing content of the random number update phase of the tenth embodiment is the same as the processing content of the random number generation phase of the fifth embodiment, refer to the description of the fifth embodiment described above.

[Eleventh embodiment]
The multi-party secure authentication system of the eleventh embodiment is different from the above-described embodiment only in the random number update phase processing. The configuration method according to the eleventh embodiment can be applied to the multi-party secure authentication system according to the first to third embodiments.

Since the processing content of the random number update phase of the eleventh embodiment is the same as the processing content of the random number generation phase of the sixth embodiment, refer to the description of the above sixth embodiment.
[Twelfth embodiment]
The multi-party secure authentication system of the twelfth embodiment differs from the above-described embodiment only in the random number update phase processing. The configuration method of the twelfth embodiment can be applied to the multi-party secure authentication system of the first embodiment to the third embodiment.

Since the processing content of the random number update phase of the twelfth embodiment is the same as the processing content of the random number generation phase of the seventh embodiment, refer to the description of the seventh embodiment described above.

[Thirteenth embodiment]
The multi-party secure authentication system of the thirteenth embodiment differs from the above-described embodiment only in the random number update phase processing. The configuration method of the thirteenth embodiment can be applied to the multi-party secure authentication system of the first to third embodiments.

  Since the processing content of the random number update phase of the thirteenth embodiment is the same as the processing content of the random number generation phase of the eighth embodiment, refer to the description of the above eighth embodiment.

[Modification]
In the above embodiments, multi-party secure authentication system, user apparatus 1, the intermediate server 2 and n stand authentication server 3 _1, ..., although the described example the structure containing 3 _n, the intermediate server 2 It is also possible to configure one authentication server 3 as one intermediate authentication server. That is, the multi-party secure authentication system includes, for example, a user device 1, n-1 authentication servers 3 ₁ ,..., 3 _n-1 and one intermediate authentication server 3 _n. Can do.

The intermediate authentication server 3 _n is configured by having both a configuration unit included in the intermediate server 2 and a configuration unit included in the authentication server 3. However, in the above-described embodiment, the data transmitted and received between the intermediate server 2 and the authentication server 3 can be transferred inside the server via the memory 102, and therefore it is not necessarily encrypted. Specifically, it is not necessary to encrypt the intermediate server verification value q a — _n ^(W) encrypted with the common key between the intermediate server 2 and the authentication server 3 . Therefore, the intermediate authentication server 3 _n may not include the intermediate server verification value encryption unit 35. Further, since the verification at the intermediate authentication server 3 _n is possible with the authentication server verification value, the intermediate server verification value is not necessary. Therefore, the intermediate authentication server 3 _n may not include the intermediate server verification value generation unit 34, the intermediate server verification value encryption unit 35, the intermediate server verification value decryption unit 23, and the intermediate server verification unit 24.

Further, in case where the intermediate server 2 and the authentication server 3 as a single intermediate authentication server 3 _n, the intermediate server 2 and the authentication server 3 _1, ..., a common key with 3 _n, and the authentication server 3 _n Since it can be used together with a common key with the other authentication servers 3 ₁ ,..., 3 _n−1 , the number of common keys in the entire system can be reduced by n.

[Application example]
The multi-party secure authentication technology of the present invention can be applied to various application systems that use password authentication.

  For example, when a user receives an information system service by an external third party via a web page, each service provider is used as an authentication server to authenticate the first embodiment or the second embodiment. The service may be configured to provide the service to the user. Note that the external service may be a service performed by a plurality of servers in cooperation, or may be a service that can be implemented by each single server.

  In addition, for example, an application example in which the multi-party secure authentication technique of the third embodiment is used as a single sign-on scheme is conceivable. If comprised in this way, the user can receive each service of each server with one password. If this invention is used, the risk of leakage due to impersonation in the authentication process by single sign-on can be reduced.

  Furthermore, for example, an application example in which the multi-party secure authentication technology of the third embodiment is used as a storage service using (k, n) secret sharing is conceivable. (k, n) secret sharing is a division method that divides data into n distributed values, and it is impossible to obtain information on the original data with any k-1 distributed values. This is a secret sharing scheme that can completely restore the original data if there are any k distributed values. In the storage service using (k, n) secret sharing, the servers cooperate with each other, but the servers do not need to communicate directly with each other. Since the multi-party secure authentication technology of the present invention does not require communication between servers, it can be said that this is an application example that can fully enjoy the advantages.

[Effect of the invention]
By using this invention, even if an intermediate server such as a Web server is used, an unauthorized person cannot impersonate a user and succeed in authentication. An unauthorized person is also assumed to be an intermediary or a server. That is, it includes that neither the intermediate person nor the server knows the password.

In addition to the fact that the Web service model can be applied, the present invention realizes the following four requirements.
1. 1. Users do not need to install multiple passwords or cumbersome certificates. 2. Even an intermediary or a server cannot impersonate. 3. No communication path is required between servers. The response time to the user can be minimized so that the response time can be minimized in the Internet environment.

The requirements 1 and 4 are obvious. The requirement 2 above is that the server has its own data in the single-server model, so there is little merit of fraudulently through authentication from the outside, but there are multiple servers and each has different data In such a case, there is an advantage in browsing data held by other servers from the outside. Especially in secret sharing, this problem is serious because the security effect is lost when two pieces of data are collected. The requirement 3 above means that a linked service can be developed even on servers that do not have a communication path between each other during system construction. For example, the application providers can expand their service on an appropriate multiple cloud services. In other words, cloud services do not need to be linked.

  In the present invention, there is one password for the above requirement 1, and the password is protected by secret sharing that neither the server nor the intermediate person can know the password for the requirement 2. Note that the hash value of the password is insufficient because a dictionary attack is possible locally on the server. In addition, because of the requirements 3 and 4, a well-known secret circuit calculation may be used if communication between servers is allowed (corresponding to the requirement 3), and an encrypted communication path is used if the number of communications is increased. Although it can be set to the same setting as the case where there is no intermediary (corresponding to the above requirement 4), a secret circuit calculation with a low communication count via the intermediary is designed exclusively.

[Program, recording medium]
The present invention is not limited to the above-described embodiment, and it goes without saying that modifications can be made as appropriate without departing from the spirit of the present invention. The various processes described in the above-described embodiments are not only executed in time series according to the order described, but may be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes.

  When various processing functions in each device described in the above embodiment are realized by a computer, the processing contents of the functions that each device should have are described by a program. Then, by executing this program on a computer, various processing functions in each of the above devices are realized on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

Claims (10)

n ≧ 3, 2k−1 ≦ n, k ≦ m, m ≦ n, a ₁ ,..., a _m are m different integers of 1 to n and (k , n) Secret sharing is secret sharing that can be restored if there are k or more of n shared values, and [r ^(W) ] ₁ , ..., [r ^(W) ] _n is a random number r when restored. ⁽ K, n) is a shared value by secret sharing, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) is restored to a random number r ^{( i)} (k, n) is a variance value due to secret sharing, and [0 ^(W) ] ₁ , ..., [0 ^(W) ] _n is 0 when restored, (k, n) a variance value due to secret sharing [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (i = 1, ..., m) is 0 when restored (k, n) is a distributed value by secret sharing,
A multi-party secure authentication system including a user device, an intermediate server, and n authentication servers,
The user device is
A password distribution unit that distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n ;
For i = 1,..., n, a ciphertext Enc _{US_i} ([w ′] _i ) _obtained by encrypting the distributed value [w ′] _i using a common key between the user device and the i-th authentication server A password distributed value encryption unit to obtain
Including
The intermediate server
For i = 1,..., n, a password distributed value transfer unit that transmits the ciphertext Enc _{US_i} ([w ′] _i ) received from the user device to the i-th authentication server;
For i = 1,..., m, the ciphertext Enc _{WS_a_i} (q _{a_i} ^(W) ) received from the a _i th authentication server is obtained using a common key between the intermediate server and the a _i th authentication server. An intermediate server verification value decoding unit for decoding and obtaining a verification value q _{a_i} ^(W) ;
An intermediate server verification unit that verifies whether or not the sum of the verification values q _{a_1} ^(W) ,..., Q _{a_m} ^(W) is equal to 0;
Including
The authentication server
Dispersion value of the password w dispersed in the n _{[w] 1, ..., [} w] i -th variance value of the _n [w] _{i, i-th} of the dispersion values _{^{[r (W)] i,}} i -th, respectively A variance value storage unit for storing the variance values [r ⁽¹⁾ ] _i ,..., [R ⁽ⁿ⁾ ] _i of
Password sharing to obtain the distributed value [w ′] _i by decrypting the ciphertext Enc _{US_i} ([w ′] _i ) received from the intermediate server using a common key between the user device and the authentication server A value decoding unit;
λ _{a_i} ^(W) (i∈1,…, m) is a constant that satisfies the following equation:

^ λ _{a_i} ^(W) (i∈1,…, m) is a constant that satisfies

λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1,…, m) is a constant that satisfies

An intermediate server verification value generation unit for determining the verification value q _{a_i} ^(W) by the following equation:

An intermediate server verification value encryption unit that obtains the ciphertext Enc _{WS_a_i} (q _{a_i} ^(W) ) obtained by encrypting the verification value q _{a_i} ^(W) using a common key between the intermediate server and the authentication server;
For j = 1,..., m, an authentication server verification value generation unit for ^{obtaining a} verification value q _{a_i} ^(a_j) by the following equation;

Cipher text Enc _{S_a_iS_a_j} (q _{a_i} ^(a_j) _obtained by encrypting the verification value q _{a_i} ^(a_j) using a common key between the a _j th authentication server and the authentication server for j = 1 ^,. Authentication server verification value encryption unit to obtain
For j = 1, ..., m, using the common key between the a _j th authentication server and the authentication server, the cipher text Enc _{S_a_iS_a_j} (q _{a_j} ^(a_i) ) received from the a _j th authentication server An authentication server verification value decryption unit that decrypts and obtains the verification value q _{a_j} ^(a_i) ;
An authentication server verification unit that verifies whether the sum of the verification values q _{a_1} ^(a_i) ,..., Q _{a_m} ^(a_i) is equal to 0;
Multi-party secure authentication system including The multi-party secure authentication system according to claim 1,
The authentication server
A random number generator for generating a random number t _{a_i} ;
By using the common key between the user device and the authentication server, the random number encryption unit for the random number t _{a_i} obtain encrypted ciphertext Enc _{US_a_i} (t _{a_i),}
Ciphertext received from the intermediate server _{Enc US_a_i (t a_i, [w} '] a_i) verifies whether the random number t _{a_i} obtained by decoding is equal to the generated the random number t _{a_i} by the random number generating unit A random number verification unit to
Further including
The intermediate server
a random number transfer unit that transmits the cipher text Enc _{US_a_j} ( _{ta_j} ) received from the a _j- th authentication server to j = 1, ..., m,
The user device is
For i = 1,..., m, the ciphertext Enc _{US_a_i} (t _{a_i} ) received from the intermediate server is decrypted using the common key between the user device and the a _i th authentication server, and the random number t _{a_i} A random number decryption unit for obtaining
The password distributed value encryption unit
i = 1, ..., for n, using the common key between the user device and the i-th the authentication server, variance [w '] ciphertext _i encrypted with the random number t _{a_i} Enc _{US_a_i} (t _{a_i} , [w '] Multi-party secure authentication system that obtains _{a_i} ). The multi-party secure authentication system according to claim 1 or 2,
The authentication server
A random number variance generating unit for generating the variance [r ^(W) ] _i , [r ⁽¹⁾ ] _i , ..., [r ⁽ⁿ⁾ ] _i ;
A zero variance value generator for generating the variance values [0 ^(W) ] _i , [0 ^(a_1) ] _i ,..., [R ^(a_m) ] _i ,
A multi-party secure authentication system. The multi-party secure authentication system according to claim 1 or 2,
The user device is
The random number ^{r (W), r (1} ), ..., and generates an r ^(n), the random number ^{r (W), r (1} ), ..., by distributing each r ⁽ⁿ⁾ into n the dispersion Generate the values [r ^(W) ] ₁ , ..., [r ^(W) ] _n and the variances [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) A random number distributed value generation unit for
For i = 1,..., n, using the common key between the user device and the i-th authentication server, the distributed values [r ^(W) ] _i , [r ⁽ⁱ⁾ ] _i ,. ^(n)] ciphertext _i encrypted ^{_{Enc US_i ([r (W)}} ] i, [r (i)] i, ..., [r (n)] i) and the random number variance encryption unit to obtain,
The variance [0 ^(W) ] ₁ , ..., [0 ^(W) ] _n and the variance [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (i = 1, ..., m) A zero variance value generation unit for generating
i = 1, ..., for m, using the common key between the user device and a _i-th of said authentication server, variance _{^{[0 (W)] i,}} [0 (1)] i, ..., [ 0 ^(m)] ciphertext _i encrypted ^{_{Enc US_i ([0 (W)}} ] i, [0 (a_1)] i, ..., [0 (a_m)] i) and the random number variance encryption unit to obtain ,
Further including
The intermediate server
For i = 1,..., n, the ciphertext Enc _{US_i} ([r ^(W) ] _i , [r ⁽ⁱ⁾ ] _i ,..., [r ⁽ⁿ⁾ ] _i ) received from the user device is i A random number distributed value transfer unit to be transmitted to the authentication server
For i = 1, ..., n, the ciphertext Enc _{US_i} ([0 ^(W) ] _i , [0 ^(a_1) ] _i , ..., [0 ^(a_m) ] _i ) received from the user device is i A zero distributed value transfer unit to send to the authentication server
Multi-party secure authentication system including n ≧ 3, 2k-1 ≦ n, k ≦ m, m ≦ n, and a ₁ ,..., a _m are _{m m} = n and m different from 1 to n, respectively. It is an integer, and (k, n) secret sharing is a secret sharing that can be restored if there are k or more of n sharing values, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) is a random value r ⁽ⁱ⁾ and (k, n) is a ^shared value by secret sharing. [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (I = 1, ..., m) is a (k, n) secret sharing value that is 0 when restored.
λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1,…, m) is a constant that satisfies

A multi-party secure authentication system including a user device, an intermediate authentication server, and n-1 authentication servers,
The user device is
A password distribution unit that distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n ;
For i = 1,..., n−1, the ciphertext Enc _{US_i} ([w ′]) is _obtained by encrypting the distributed value [w ′] _i using the common key between the user device and the i-th authentication server. _i ) to obtain a ciphertext Enc _{US_n} ([w '] _n ) obtained by encrypting the distributed value [w ′] _n using the common key between the user device and the intermediate authentication server. And
Including
The intermediate authentication server
N of the distributed values [w] ₁ ,..., [W] _n in which the password w is distributed to _n , and the nth distributed value [r ⁽¹⁾ ] _n ,. [r ⁽ⁿ⁾ ] a distributed value storage unit for storing _n ;
For i = 1,..., n−1, a password distributed value transfer unit that transmits the ciphertext Enc _{US_i} ([w ′] _i ) received from the user device to the i-th authentication server;
A password distributed value decryption unit that decrypts the ciphertext Enc _{US_n} ([w ′] _n ) and obtains the distributed value [w ′] _n using a common key between the user device and the intermediate authentication server;
For j = 1,..., m, an authentication server verification value generation unit for ^{obtaining a} verification value q _{a_m} ^(a_j) by the following equation;

For j = 1,..., m−1, the encrypted text Enc _{S_a_mS_a_j} (q _{a_m} ⁾ is ^obtained by encrypting the verification value q _{a_m} ^(a_j) using the common key between the _{j j} authentication server and the intermediate authentication server. ^(a_j) ) to obtain an authentication server verification value encryption unit;
j = 1, ..., the m-1, a _j-th by using the common key between the authentication server and the intermediate authentication server, a _j-th ciphertext received from the authentication server Enc _{S_a_mS_a_j} ^(q _{a_j} ^{(a_m )} ) To obtain the verification value q _{a_j} ^(a_m), and an authentication server verification value decoding unit;
An authentication server verification unit that verifies whether the sum of the verification values q _{a_1} ^(a_m) ,..., Q _{a_m} ^(a_m) is equal to 0;
Including
The authentication server
a variance value storage unit for storing the i-th variance value [w] _i and the i-th variance value [r ⁽¹⁾ ] _i ,..., [r ⁽ⁿ⁾ ] _i , respectively.
A password for decrypting the ciphertext Enc _{US_i} ([w ′] _i ) received from the intermediate authentication server by using a common key between the user device and the authentication server to obtain the distributed value [w ′] _i A distributed value decoding unit;
For j = 1,..., m, an authentication server verification value generation unit for ^{obtaining a} verification value q _{a_i} ^(a_j) by the following equation;

For j = 1,..., m, a ciphertext Enc _{S_a_iS_a_j} (encrypting the verification value q _{a_i} ^(a_j) using a common key between the _{j j} authentication server or the intermediate authentication server and the authentication server ( q _{a_i} ^(a_j) ) to obtain the authentication server verification value encryption unit,
For j = 1,..., m, the ciphertext Enc _{S_a_iS_a_j} (q _{a_j} received from the a _j th authentication server using a common key between the a _j th authentication server or the intermediate authentication server and the authentication server ^(a_i) ) is decrypted to obtain the verification value q _{a_j} ^(a_i) , an authentication server verification value decoding unit;
An authentication server verification unit that verifies whether the sum of the verification values q _{a_1} ^(a_i) ,..., Q _{a_m} ^(a_i) is equal to 0;
Multi-party secure authentication system including The authentication server used in the multi-party secure authentication system according to any one of claims 1 to 5 . n ≧ 3, 2k−1 ≦ n, k ≦ m, m ≦ n, a ₁ ,..., a _m are m different integers of 1 to n and (k , n) Secret sharing is secret sharing that can be restored if there are k or more of n shared values, and [r ^(W) ] ₁ , ..., [r ^(W) ] _n is a random number r when restored. ⁽ K, n) is a shared value by secret sharing, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) is restored to a random number r ^{( i)} (k, n) is a variance value due to secret sharing, and [0 ^(W) ] ₁ , ..., [0 ^(W) ] _n is 0 when restored, (k, n) a variance value due to secret sharing [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (i = 1, ..., m) is 0 when restored (k, n) is a distributed value by secret sharing,
A password distribution step in which the user device distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n ;
The user device, for i = 1,..., N, uses a common key between the user device and the i-th authentication server, and encrypts the distributed value [w ′] _i into a ciphertext Enc _{US_i} ([[ w '] _i ) to obtain a password distributed value encryption step;
An intermediate server _{transmits the} ciphertext Enc _{US_i} ([w ′] _i ) received from the user device for i = 1,..., N to the i-th authentication server;
The authentication server decrypts the ciphertext Enc _{US_i} ([w ′] _i ) received from the intermediate server by using a common key between the user device and the authentication server, and the distributed value [w ′] _a password distributed value decryption step to obtain _i ;
λ _{a_i} ^(W) (i∈1,…, m) is a constant that satisfies the following equation:

^ λ _{a_i} ^(W) (i∈1,…, m) is a constant that satisfies

λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1,…, m) is a constant that satisfies

An intermediate server verification value generation step in which the authentication server obtains the verification value q _{a_i} ^(W) by the following equation:

The intermediate server verification value cipher in which the authentication server obtains a ciphertext Enc _{WS_a_i} (q _{a_i} ^(W) ) obtained by encrypting the verification value q _{a_i} ^(W) using a common key between the intermediate server and the authentication server. Step,
The intermediate server uses ciphertext Enc _{WS_a_i} (q _{a_i} received from the a _i th authentication server for i = 1,..., _M using a common key between the intermediate server and the a _i th authentication server. ^(W) ) intermediate server verification value decoding step to obtain verification value q _{a_i} ^(W) by decoding
An intermediate server verification step in which the intermediate server verifies whether the sum of the verification values q _{a_1} ^(W) ,..., Q _{a_m} ^(W) is equal to 0;
The authentication server generates an authentication server verification value generation step for ^{obtaining a} verification value q _{a_i} ^(a_j) for j = 1 ^,.

The authentication server encrypts the verification value q _{a_i} ^(a_j) using a common key between the a _j- th authentication server and the authentication server for j = 1,..., _M. Enc _{S_a_iS_a_j} ( q _{a_i} ^(a_j) ) to obtain an authentication server verification value encryption step;
The authentication server, j = 1, ..., m for, using the common key between a _j-th of the authentication server and the authentication server, a _j-th ciphertext received from the authentication server Enc _{S_a_iS_a_j} (q _{a_j} ^(a_i) ) is decrypted to obtain the verification value q _{a_j} ^(a_i) , an authentication server verification value decoding step;
An authentication server verification step in which the authentication server verifies whether the sum of the verification values q _{a_1} ^(a_i) ,..., Q _{a_m} ^(a_i) is equal to 0;
A multi-party secure authentication method including: n ≧ 3, 2k-1 ≦ n, k ≦ m, m ≦ n, and a ₁ ,..., a _m are _{m m} = n and m different from 1 to n, respectively. It is an integer, and (k, n) secret sharing is a secret sharing that can be restored if there are k or more of n sharing values, and [r ⁽ⁱ⁾ ] ₁ , ..., [r ⁽ⁱ⁾ ] _n (i = 1, ..., n) is a random value r ⁽ⁱ⁾ and (k, n) is a ^shared value by secret sharing. [0 ^(a_i) ] ₁ , ..., [0 ^(a_i) ] _n (I = 1, ..., m) is a (k, n) secret sharing value that is 0 when restored.
λ _{a_i} ^(j) (i∈1, ..., m) is a constant that satisfies

^ λ _{a_i} ^(j) (i∈1,…, m) is a constant that satisfies

A password distribution step in which the user device distributes the input password w ′ into n distributed values [w ′] ₁ ,..., [W ′] _n ;
_Ciphertext Enc _{US_i} obtained by encrypting the distributed value [w ′] _i using the common key between the user device and the i-th authentication server for i = 1,..., N−1. ([w '] _i ) is obtained, and the ciphertext Enc _{US_n} ([w'] _n ) obtained by encrypting the distributed value [w '] _n is obtained using the common key between the user device and the intermediate authentication server. A password distributed value encryption step;
The intermediate authentication server _{transmits the} ciphertext Enc _{US_i} ([w '] _i ) received from the user device to i-th authentication server for i = 1,..., N−1. Steps,
The authentication server decrypts the ciphertext Enc _{US_i} ([w ′] _i ) received from the intermediate authentication server by using a common key between the user device and the authentication server, and the distributed value [w ′ ] a first password distribution value decryption step to obtain _i ;
The intermediate authentication server decrypts the ciphertext Enc _{US_n} ([w ′] _n ) and obtains the distributed value [w ′] _n by using a common key between the user device and the intermediate authentication server. Two password distributed value decryption step;
The authentication server generates a verification value q _{a_i} ^(a_j) for j = 1,..., ^M by the following equation:

The intermediate authentication server, for j = 1, ..., m, a second authentication server verification value generation step for ^{obtaining a} verification value q _{a_m} ^{(a_j) according} to the following equation:

The authentication server encrypts the verification value q _{a_i} ^(a_j) using a common key between the _j- th authentication server or the intermediate authentication server and the authentication server for j = 1 ^,. A first authentication server verification value encryption step for obtaining ciphertext Enc _{S_a_iS_a_j} (q _{a_i} ^(a_j) );
The intermediate authentication server encrypts the verification value q _{a_m} ^(a_j) by using a common key between the _j- th authentication server and the intermediate authentication server for j = 1,..., ^M−1. A second authentication server verification value encryption step to obtain the sentence Enc _{S_a_mS_a_j} (q _{a_m} ^(a_j) );
Ciphertext received by the authentication server from the a _j th authentication server for j = 1,..., M using the a _j th authentication server or the common key between the intermediate authentication server and the authentication server. A first authentication server verification value decoding step of decoding Enc _{S_a_iS_a_j} (q _{a_j} ^{(a_i) )} to obtain the verification value q _{a_j} ^(a_i) ;
The intermediate authentication server, j = 1, ..., the m-1, a _j-th by using the common key between the authentication server and the intermediate authentication server, ciphertext received from a _j-th of the authentication server Enc a second authentication server verification value decoding step of obtaining the verification value q _{a_j} ^(a_m) decodes the ^{_{S_a_mS_a_j (q a_j (a_m))}} ,
A first authentication server verification step in which the authentication server verifies whether the sum of the verification values q _{a_1} ^(a_i) ,..., Q _{a_m} ^(a_i) is equal to 0;
A second authentication server verification step in which the intermediate authentication server verifies whether the sum of the verification values q _{a_1} ^(a_m) ,..., Q _{a_m} ^(a_m) is equal to 0;
A multi-party secure authentication method including: Program for causing a computer to function as an authentication server according to claim 6. A program for causing a computer to execute each step of the multi-party secure authentication method according to claim 7 or 8.

Images