WO2025169283A1 - Asymmetric secret sharing device, secret information recovery device, asymmetric secret sharing program, and secret information recovery program - Google Patents

Abstract

An asymmetric secret sharing device in a system in which one set of secret information is converted into n distributed values, and the secret information can be recovered by collecting k of the n distributed values, but cannot be recovered by collecting k-1 or fewer of the n distributed values, where n is an integer at least equal to 2 and k is an integer having a minimum value of 2 and a maximum value of n, said asymmetric secret sharing device being characterized by comprising: a generation unit that acquires one or more true random numbers as first secret information and generates t (< k) distributed values for each true random number from a first key; and a calculation unit that calculates n-t distributed values from the t distributed values and the first secret information.

Description

Asymmetric secret sharing device, secret information recovery device, asymmetric secret sharing program, and secret information recovery program

The technology disclosed herein relates to an asymmetric secret sharing device, a secret information recovery device, an asymmetric secret sharing program, and a secret information recovery program.

In recent years, cloud computing has been attracting attention as a new network technology. Cloud computing is a technology that distributes and stores user data in large-capacity virtual storage on multiple servers on a network known as the cloud, allowing users to access that data as needed from anywhere via the network. However, for security reasons, it is desirable to encrypt information stored in the cloud. Furthermore, in addition to encrypting and storing data, it is also expected that data distributed and stored on the cloud will be able to be used to perform various confidential calculations while keeping the data confidential. Furthermore, with the recent spread of IoT (Internet of Things) devices, there is also a demand for security technology that can safely and confidentially transmit information from IoT devices.

The use of secret sharing schemes has attracted attention as a way to achieve such secret storage and secure computation. Secret sharing schemes are a technology characterized by converting a single piece of secret information into n (i.e., a natural number) values (hereinafter referred to as shares) and allowing the original secret information to be restored by collecting k (i.e., a natural number) shares (k≦n) of these, while no information about the secret information can be obtained from shares less than k. Well-known examples of this type of secret sharing scheme include Shamir's (k,n) threshold secret sharing scheme (hereinafter referred to as the Shamir scheme) and additive secret sharing scheme, as shown below. Conventional secret sharing systems, including the Shamir scheme, consist of n data servers that store shares, a dealer (i.e., a communication terminal) that distributes the secret information, and a restorer (i.e., a communication terminal) that restores the secret information. In other words, when sharing, the owner of the secret information acts as the dealer and shares the information, or requests a dealer who exists only during secret sharing to share the secret information. The dealer then performs the secret sharing process, calculates n shares, and distributes and stores these values across n data servers. On the other hand, when restoring the secret, a restorer collects and restores k shares from the n shared values.

The Shamir method is carried out as follows.
[Shamir method]
[Dispersion]
1. The dealer chooses an arbitrary prime number p such that s (i.e., secret information)<p and n<p.
2. The dealer selects n different x _i (i=1, 2, . . . , n) from Z/pZ (i.e., the coset ring) and publishes them as server IDs (i.e., sends them to the restorer).
3 The dealer selects k-1 random numbers a _l (l=1, 2, ..., k-1) from Z/pZ and generates the following formula (hereinafter referred to as the distribution formula):
W _i =s+a ₁ x _i +a ₂ x _i ² +...+a _k-1 x _i ^k-1 (modp) (1)
4. The dealer substitutes each server ID for x _i in the above formula (1), calculates the variance value W _i , and distributes (x _i , W _i ) to each server.
[Decryption]
1. Let W _i (i=1, 2, ..., k) be the share used for decryption, and let x _i (i=1, 2, ..., k) be the server ID corresponding to that share.
2 The restorer collects k (x _i , W _i ), substitutes x _i and W _i into the variance formula, and solves k simultaneous equations to obtain s. When restoring s, it is convenient to use the Lagrange interpolation formula.

The additive secret sharing scheme is as follows: The case where n=k will be explained below.
[Additive secret sharing method]
[Dispersion]
1. The dealer generates k-1 random numbers S ₁ to S _k-1 .
2. The dealer calculates the following for the secret information s:

Sk=s-S ₁ -...-S _k-1
3. The dealer selects identifiers x _i (i=1, 2, . . . , k) for k servers and distributes S _i to the servers x _i as distribution values.
[Decryption]
1. The restorer collects k S _{i s} , calculates s = S 1 + ... + Sk s, and restores the secret information s.

When n=k+1, the dealer distributes S _i and S _i+1 to the server x _i , where Sk+1 is regarded as S1 for convenience.

However, a problem with secret sharing schemes is that one piece of secret information becomes n shares, which increases the memory capacity (in other words, the server capacity). To address this issue, a ramp secret sharing scheme, as shown in Non-Patent Document 1, is known, in which the secret information is divided into 1/L and used as the coefficients of the sharing formula. This allows the size of the shares to be reduced, thereby reducing the memory capacity. A technique called asymmetric secret sharing, as shown in Patent No. 6893708, has also been proposed. Asymmetric secret sharing schemes reduce the memory capacity (number of servers) by reducing the number of shares stored, rather than the size of the shares. Below, we will show an asymmetric secret sharing scheme for the Shamir scheme (asymmetric secret sharing schemes can also be applied to additive secret sharing schemes).
(Non-Patent Document 1)
Hirosuke Yamamoto. "(k, L, n) Threshold Secret Sharing System." Transactions of the Institute of Electronics and Communication Engineers, vol. J68-A, no. 9, pp. 945-952 (1985)
[Asymmetric Secret Sharing Scheme]
Of the n servers constituting the cloud system, t (i.e., a natural number) servers (t<k) are selected and designated as key servers. These key servers do not store shares, but only have keys for generating pseudorandom numbers. Servers other than the key servers are called data servers, and these store shares sent from users (i.e., communication terminals) who are dealers. Furthermore, for r (i.e., a natural number) users to whom secret information is shared, each user y is assigned an ID[y] (y = 1, ..., r) for user identification, and each of the m pieces of secret information s ₁ , ..., s _m held by user y is assigned a dID[s _i ] (i = 1, ..., m) for data identification. Furthermore, Enc(a, b) represents the process of encrypting a using key b. Below, we will explain the case where user y acts as the dealer and performs asymmetric secret sharing.

[Dispersion]
1. User y sends his ID[y] to key servers x ₁ , . . . , x _t .
2. The key server that receives ID[y] generates Eid(y, j) using its own encryption device and key _j (j=1, . . . , t) according to equation (2) and sends it to user y.
Eid (y, j) = Enc (ID [y], key _j ) (j = 1, ..., t) (2)

3. User y receives this and generates a pseudo-random number q _ij using the data identifier dID[s _i ] (i=1, . . . , m) relating to his/her own confidential information according to equation (3).
q _ij = Enc(dID[s _i ], Eid(y, j)) (3)
4. First, the user y determines the k-1-t-th order partial vector A(i) k-1-t = [a _it + ₁ , ..., a _ik-1 ] ^T in the coefficient vector A(i) = [s i , a i1, ..., a _ik-1 ] T of the k-1-th order distribution formula in formula (1) for each i using true random numbers. Then, the user y determines the following partial vector A(i) k-1 _-t = [a _it+1 , ..., a ik-1] ^T calculated from the t-th order pseudorandom number sequence Q = [q _i1 , ..., q _it ] ^T generated in step (3) and the ID sequence of the key server:

 

Using the above, the remaining partial vector A(i) _t =[a _i1 , . . . , a _it ] ^T is calculated for each i using the following equation (4).

 

Here, if S=[s _i , . . . , s _i ] ^T in the above formula, then
A(i) _k-1 =X'- ¹ (Q-S) (5)
This allows the user to determine all of the coefficient vectors A(i)=[s _i , a _i1 , . . . , a _ik-1 ] ^T of the k-1th order dispersion equation.
5. In addition, the user calculates the distribution values W _it+1 , ..., W _in for the data servers x _t+1 , ..., x _n using the coefficient matrix generated in step (4) using a procedure similar to the (k, n) threshold secret sharing scheme (see Shamir's method [distribution] 4 above).
6. User y sends the generated variance values W _1j , ..., W _mj (j=t+1, ..., n) to each data server.
[Restore]
1. A user who restores secret information s _i selects k arbitrary servers from n servers x ₁ , . . . , x _n and sends the ID [y] of user y and the data identifier dID[s _i ] of secret information s _i to the selected servers.
2. Among the key servers, the key server that receives (ID[y], dID[s _i ]) uses its own key _j and encryption device to generate Eid(y, j) using equation (2), and generates a pseudo-random number q _ij using equation (3) and sends it to the user.
3. Among the data servers, the data server that receives (ID[y], dID[s _i ]) sends the shared information W _ij corresponding to this ID information to the user.
4. The user who receives the shares and pseudo-random numbers generated by the server uses them to restore the secret information s _i in the same way as in the (k, n) threshold secret sharing scheme.

In the asymmetric secret sharing scheme, for example, when t=k-1, t key servers generate t=k-1 q _ij (j=1, ..., t) using their own keys as shares, and calculate the coefficients of a _ij (j=1, ..., k-1) that satisfy equation (1) using these shares and secret information. When t<k-1, first, k-1-t a _ij (j=1, ..., k-1-t) are determined from true random numbers, and the remaining coefficients that satisfy equation (1) are found to calculate all a _ij . If the owner manages the key _j held by the key server, a physical server called a key server is not required, so the number of physical servers can be n-t instead of n, thereby reducing memory capacity (number of servers). In this case, the secret information cannot be restored without shares generated from the key managed by the owner.

Research into quantum computers has progressed in recent years, and it is said that once quantum computers are realized, cryptography that currently only has computational security will be easily analyzed. Incidentally, computational security means security that can be solved if the attacker has greater computational power than expected, while security that cannot be solved even if the attacker has infinite computational power due to insufficient information is called information-theoretic security.

For example, in the asymmetric secret sharing scheme, the key server generates a pseudorandom number _q1j for one piece of secret information s1 using a cryptographic device, and then calculates and stores the shares W1 _,t+1 , ..., W1 _,n to be stored by the data server. While the Shamir scheme and ramp secret sharing scheme are known to have information-theoretic security (although the security of ramp secret sharing schemes gradually deteriorates depending on the number of shares collected), the asymmetric secret sharing scheme does not have information-theoretic security, but rather has computational security that depends on the cryptographic device that generates _qij . Therefore, the asymmetric secret sharing scheme is at risk of being analyzed by a quantum computer. For example, when n = k = 2, based on _q1 expressed by equation (6) generated by the key server for secret information _s1 , _W1 to be sent to the data server is calculated via equation (7) as shown in equation (8). For simplicity, notations such as j and (modp) are omitted. The following equation (6) is obtained from equation (4). When n = k = 2, equation (4) becomes q _i1 = s ₁ + x ₁ a ₁ , which can be transformed to a ₁ = to obtain equation (7). Also, since the data server ID in equation (8) is x ₂ , it is calculated using the obtained a ₁ as in 5 of the asymmetric secret sharing method. Similarly, by transforming this to a ₁ =, another equation of equation (7) can be obtained.
q ₁ = s ₁ + a ₁ x ₁ (6)
a ₁ = (q ₁ - _{s 1} )/x ₁ = (W ₁ - s ₁ )/x ₂ (7)
W ₁ = s ₁ + a ₁ x ₂ (8)
The values of _{q1 and a1} in equations (6) and (7) are known only to the dealer, but the attacker knows _W1 in equation (8) transmitted to the data server. Consider the case where secret information _s1 , which corresponds to a known plaintext attack, is made public. In this case, the attacker can determine _a1 from equation (7) ( _W1 and _x2 are known) and know the value of _q1 from equation (6). For example, if dID[ _s1 ] is public information, _q1 is the encrypted value of dID[ _s1 ], and if multiple pieces of secret information _s2 , ..., _sm are made public, the key _j used for encryption may be identified by analysis using a quantum computer or the like. If the key is identified, qm _{+ 1} for the subsequent secret information sm+1 will be leaked. Therefore, even if sm ₊₁ is not disclosed, the secret information sm+1 will be leaked from the transmitted Wm _{+1 and} the identified qm ₊₁ .

In contrast, in conventional secret sharing schemes, _a1 is determined as a true random number. Therefore, even if secret information _s1 is made public, a different true random number is used for the next secret information _s2 . This prevents the key from being analyzed, and the security of sm ₊₁ is maintained even if _s2 , ..., _sm are made public.

Therefore, it is necessary to make it more difficult to analyze secret information by improving the security of asymmetric secret sharing schemes.

The disclosed technology aims to provide an asymmetric secret sharing device, a secret information recovery device, an asymmetric secret sharing program, and a secret information recovery program that can make analyzing secret information more difficult than conventional technology.

A first aspect of the technology disclosed herein is an asymmetric secret sharing device for a system in which one piece of secret information is distributed into n shared values, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, and the secret information can be restored by collecting k of the shared values, but not by collecting k-1 or fewer of the shared values. The device is characterized by having: a generation unit that obtains one or more true random numbers as first secret information, and generates t (<k) shared values for each true random number from a first key; and a calculation unit that calculates n-t shared values from the t shared values and the first secret information.

The second aspect is an asymmetric secret sharing device for a system in which n is an integer equal to or greater than 2, k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n shared values, and the secret information can be restored by collecting k of the shared values, but cannot be restored by collecting k-1 or fewer shared values, and is characterized by having a first concealment unit that conceals a true random number as first secret information, and a second concealment unit that uses the first secret information to conceal second secret information in a form different from the first secret information.

The third aspect is a secret information restoration device for the system of the first aspect, characterized in that it has a first restoration unit that restores first secret information, and a second restoration unit that uses the restored first secret information to restore the second secret information of the second aspect.

The fourth aspect is a secret information recovery device for a system in which n is an integer equal to or greater than 2, k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n shares, and the secret information can be recovered by collecting k of the shares, but cannot be recovered by collecting k-1 or fewer shares, and is characterized by having a recovery unit that recovers the t shares and n-t shares generated from the key of the first aspect by sequentially changing the combination.

A fifth aspect is an asymmetric secret sharing apparatus for a system in which n is an integer greater than or equal to 2, k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is shared into n shares, and the secret information can be restored by collecting k of the shares, but not by collecting k-1 or fewer of the shares. The asymmetric secret sharing apparatus has a first calculation unit that calculates t (<k) shares from a key, and a second calculation unit that calculates n-t shares from the calculated t shares and the secret information. The secret sharing apparatus further comprises a true random number generation unit that generates true random numbers using a natural phenomenon that cannot be controlled by humans, and at least one of the t shares and the n-t shares is calculated further using the true random numbers.

In a sixth aspect of the asymmetric secret sharing program, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n shares, and the secret information can be restored by collecting k of the shares, but not by collecting k-1 or fewer. The asymmetric secret sharing program causes the computer of the asymmetric secret sharing device in this system to function as a generation unit that obtains one or more true random numbers as first secret information and generates t (<k) shares for each true random number from a first key, and a calculation unit that calculates n-t shares from the t shares and the first secret information.

The seventh aspect of the asymmetric secret sharing program is an asymmetric secret sharing program in which n is an integer greater than or equal to 2, k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but cannot be restored by collecting k-1 or fewer of the distribution values. The program causes the computer of the asymmetric secret sharing device in the system to function as a first concealment unit that conceals a true random number as first secret information, and a second concealment unit that uses the first secret information to conceal second secret information in a form different from the first secret information.

The secret information restoration program of the eighth aspect causes the computer of the secret information restoration device in the system of the first aspect to function as a first restoration unit that restores first secret information, and as a second restoration unit that restores second secret information of the second aspect using the restored first secret information.

The secret information recovery program of the ninth aspect, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, distributes one piece of secret information into n shares, and allows the secret information to be recovered by collecting k shares, but not by collecting k-1 or fewer shares. In this system, the program causes a computer of a secret information recovery device to function as a recovery unit that recovers the t shares and n-t shares generated from the key of the first aspect by sequentially changing their combinations.

In a tenth aspect of the asymmetric secret sharing program, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n shares, and the secret information can be restored by collecting k of the shares, but not by collecting k-1 or fewer. The asymmetric secret sharing program causes the computer of the asymmetric secret sharing device in this system to function as a generation unit that generates t (<k) shares from a key, and a calculation unit that calculates n-t shares from the calculated t shares and the secret information. The asymmetric secret sharing device further includes a true random number generation unit that generates true random numbers using a natural phenomenon that cannot be controlled by humans, and at least one of the t shares and the n-t shares is further calculated using the true random numbers.

The technology disclosed herein improves the security of asymmetric secret sharing schemes, making it difficult to analyze secret information.

1 is a block diagram of a distribution and decryption system 10 according to a first embodiment. FIG. 1 is a block diagram of the owner 12R1. 10 is a flowchart of a distribution program 26P1 according to the first embodiment. FIG. 10 is a diagram illustrating processing of a distribution unit 22A according to the first embodiment. 10 is a flowchart of a restoration program 26P2 according to the first embodiment. FIG. 10 is a diagram illustrating processing of a restoration unit 22B according to the first embodiment. 10 is a flowchart of a distribution program 26P1 according to the second embodiment. 10 is a flowchart of a restoration program 26P2 according to the second embodiment. 13 is a flowchart of a restoration program 26P2 according to the fourth embodiment.

An embodiment of the present invention will now be described in detail with reference to the accompanying drawings.
First Embodiment
A method for converting shares calculated by a computationally secure cryptosystem into shares with information-theoretic security will be described below. First, for simplicity, an outline of this embodiment will be described assuming n=k=2.
[Dispersion]
1. The owner generates a non-zero true random number (true random number) _r1 as first secret information, and performs asymmetric secret sharing of the true random number _r1 .
2. The owner performs asymmetric secret sharing of the second secret information _s1 using _q1 + _{r1 ,} which is the sum of _r1 and a pseudo-random number q1 generated from the key _key2j , as a share value.
[Restore]
1. The restorer restores the first secret information _r1 .
2. The restorer restores the second secret information _s1 using _q1 + _r1 , which is the pseudorandom number _q1 generated from the key _key2j plus _r1 , as the distribution.

In the above, the true random number _r1 is the first secret information, and the owner's secret information _s1 is the second secret information, and sharing and recovery are performed in two stages: _r1 and _s1 . First, in [Sharing]1, which shares _r1 , if _a1 in asymmetric secret sharing is expressed as _ar1 , _q1 as _qr1 , and _W1 as _Wr1 , then equation (7) can be written as follows:
ar ₁ = (qr ₁ - _{r 1} )/x ₁ = (Wr ₁ - _{r 1} )/x ₂ (9)
Here, since the first secret information _r1 is a true random number, _ar1 is a pseudo-random number _qr1 concealed by the true random number _r1 , and _ar1 itself can be regarded as a true random number like the Vernam cipher, and no information regarding _qr1 is given. In other words, although _Wr1 , _x1 , and _x2 are known to the attacker, the attacker can guess _ar1 for all values of _r1 , and therefore cannot narrow down the value of _ar1 , nor can he narrow down the value related to _qr1 . In other words, it has information-theoretic security.

Therefore, _Wr1 in equation (8) calculated using _ar1 and _r1 can also be considered a true random number, so an attacker cannot infer the first secret information _r1 or _qr1 from the transmitted _Wr1 , and it can be said that information-theoretic security is established. From another perspective, if the true random number _r1 is used as a coefficient of a first-order term instead of a constant term, then the following is obtained.
qr ₁ = a ₀ + r ₁ x ₁ (10)
a ₀ = qr ₁ - _{r 1} x ₁ (11)
Wr ₁ = a ₀ + r ₁ x ₂ (12)
Equations (10) and (12) are in the form of conventional secret sharing that conceals the secret information _a0 expressed in equation (11). The secret information _a0 includes the pseudo-random number _qr1 from equation (11) and is a value concealed using _the true random number _r1x1 . Furthermore, equations (11) and (12) give the following, and if _a0 is considered to be a shared value, this is a form in which the secret information _qr1 is directly concealed using equations (11) and (13) ( _x2 is considered to be _x1 - _x2 ).
Wr ₁ = qr ₁ - _{r 1} (x ₁ - _{x 2} ) (13)
Therefore, it can be said that information-theoretic security is established in [share]1, as in conventional secret sharing, and information about _qr1 is not given (the first secret information may be used as a coefficient of a term of first order or higher, rather than as a constant term). Also, since Wr and _s1 are unrelated, the following holds even if Wr1 and _s1 are known _in [share]1. Note that H(x) represents the amount of information or entropy about x,

 

represents the conditional amount of information about x on the assumption that information y is known. Therefore, equation (14) means that the amount of information about _qr1 does not change even if _Wr1 and _s1 are known. In other words, even if an attacker knows _Wr1, which can be obtained from [variance]1, it is not useful for analyzing _qr1 , which means that the system has information-theoretic security.

 

Next, in [Sharing] 2, which distributes _s1 , _q1 calculated from the key _key2j is kept secret using first secret information _r1 , which is a true random number, and similarly to the Vernam cipher, this does not provide any information about _q1 . That is, the distribution values in [Sharing] 2 are expressed as in equations (15) and (17) via equation (16).
q ₁ + r ₁ = s ₁ + a ₁ x ₁ (15)
a ₁ = {(q ₁ + r ₁ )-s ₁ }/x ₁ (16)
W ₁ = s ₁ + a ₁ x ₂ (17)
Here, since the first secret information _r1 is a true random number, _a1 is a pseudo-random number _q1 concealed by the true random number _r1 , and can be considered a true random number like the Vernam cipher. Therefore, it can be said that equations (15) and (17) calculated using _a1 have information-theoretic security similar to conventional secret sharing. In other words, an attacker cannot infer the second secret information _s1 or _q1 from the transmitted _W1 , and all _s1 or _q1 can be assumed.

Here, if the second secret information _s1 , ..., _sm is made public, _a1 , ..., am will be leaked from equation (17), but the first secret information _r1 , ..., _rm will not be leaked, so _q1 , ..., _qm will not be known. Also, from equation (15), it can be said that _q1 + _r1 is known, but _q1 is unknown. Therefore, equation (18) holds, and it can _be said that [distribution]2 also has information-theoretic security.

 

From the above, it can be said that the proposed method is information-theoretically secure even if the information W ₁ , ..., W _m of the communication path and all data servers is known to an attacker, and furthermore, even if the secret information s ₁ , ..., s _m is made public, the pseudo-random numbers cannot be analyzed, and the next secret information s _m+1 is as secure as conventional secret sharing.

Next, we will explain the specific details of when an owner manages keys for a fictitious key server.

Figure 1 shows a block diagram of a distribution and decryption system 10 according to a first embodiment. In the distribution and decryption system 10, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but cannot be restored by collecting k-1 or fewer.

The distribution and decryption system 10 comprises r (i.e., a natural number) owners 12R1 to 12Rr and n-t data servers 14Kt+1 to 14Kn. The owners 12R1 to 12Rr and the data servers 14Kt+1 to 14Kn are connected to each other via a network 16 (e.g., the Internet) so that they can communicate with each other.

User y is called the owner.

Data servers 14Kt+1 to 14Kn each have a storage device 14M that stores their own ID. For example, the storage device 14M of data server 14Kt+1 stores the ID xt+1, and also has a storage device that stores the distribution values sent from the owner.

Owners 12R1 to 12Rr are examples of the "asymmetric secret sharing device" and "secret information recovery device" of the technology disclosed herein. Note that in the technology disclosed herein, owners 12R1 to 12Rr have the functions of the "asymmetric secret sharing device" of the technology disclosed herein, and the sharing and decryption system 10 may also include a recovery device (an example of a "secret information recovery device") separate from owners 12R1 to 12Rr.

Figure 2 is a block diagram of owner 12R1. Note that the configurations of the other owners 12R2 to 12Rr are similar to that of owner 12R1, so their explanations will be omitted.

Owner 12R1 is composed of a computer. Owner 12R1 is a communications terminal. Specifically, Owner 12R1 includes a CPU (Central Processing Unit) 22, RAM (Random Access Memory) 24, a storage device 26, a true random number generator 28, and a communications device 30. The CPU 22, RAM 24, storage device 26, true random number generator 28, and communications device 30 are interconnected via a bus 32 so that they can communicate with each other.

The CPU 22 includes a distribution unit 22A and a restoration unit 22B.

The storage device 26 includes a secret information storage area 26M1 that stores the data identifier dID[S _i ] of the secret information S _i . The storage device 26 includes key storage areas 26M2 and 26M3 that store keys key _1j and key _2j (j = 1, ..., t) managed by the fictitious key servers 14K1 to 14Kt. The storage device 26 includes a program storage area 26MP that stores a distribution program 26P1 and a restoration program 26P2. The storage device 26 includes an ID storage area 26M4 that stores the IDs (x ₁ , ..., x _t , x _t+1 , x _t+2 , ..., xn) of the key servers 14K1 to 14Kt and the data servers 14Kt+1 to 14Kn. However, it is not necessary to store all IDs, and it is acceptable to store only the IDs necessary for distribution value calculation, including the data servers. Furthermore, according to this proposal, each time secret information is generated, the shared values are stored in the data server, and the shared values are called up as needed to restore the secret information. Furthermore, the storage area for data identifiers in 26M1 does not need to be stored if the method for constructing data identifiers is fixed. For example, if secret information is generated periodically, data identifiers can be generated from a fixed date and time. Furthermore, when generating key storage areas 26M2 and 26M3 that store keys _key1j and _key2j from a single key, the owner only needs to store the key, so this storage unit is not essential.

Sharing program 26P1 is an example of an "asymmetric secret sharing program" in the technology of the present disclosure. Reconstruction program 26P2 is an example of a "secret information reconstruction program" in the technology of the present disclosure.

The CPU 22 functions as the distribution unit 22A and the restoration unit 22B by reading and executing the distribution program 26P1 and the restoration program 26P2 from the program storage area 26MP to the RAM 24.

The communication device 30 sends and receives data via the network 16.

The owner 12R1 secretly holds keys _key1j and _key2j (j = 1, ..., t) managed by the key servers 14K1 to 14Kt, and uses them as key Eid(y, j) to encrypt dID[s _i ]. _Key1j and _key2j may be generated from a single key _keyj . Furthermore, although the shares Wr1 and W1 obtained in [shares] ₁ and ₂ may be sent separately, they are sent simultaneously to reduce the number of communications. Furthermore, when t > 1, it is desirable to conceal the t pseudo-random numbers generated by the key server with t true random numbers. However, as will be described later, there is no problem if the generated true random number is one and concealed with the same true random number. Therefore, for ease of understanding, the number of true random numbers concealing the pseudo-random numbers generated by the key server is assumed to be one.

If the pseudo-random numbers generated by the key server are to be kept secret using different true random numbers, this can be done as shown in the second embodiment. The rest is the same as the asymmetric secret sharing scheme.

<Dispersion>
Next, the distribution program 26P1 will be described with reference to Figures 3A and 3B. Figure 3A is a flowchart of the distribution program 26P1 according to the first embodiment, and Figure 3B is a diagram showing the processing of the distribution unit 22A according to the first embodiment. The CPU 22 executes the distribution program 26P1 to perform distributed processing.

[Variance 1]
In step 42, the sharing unit 22A obtains a true random number r _i as first secret information for its own secret information s _i from the true random number generation device 28.

In step 44, the sharing unit 22A generates pseudo-random numbers qr _ij (j=1, ..., t) using the data identifier dID[s _i ] (i=1, ..., m) related to its own secret information s _i as follows: Hereafter, qr _ij is used as t sharing values.
qr _ij = Enc(dID[s _i ], key _1j ) (19)
The key key1,j is an example of a "first key" in the technology of the present disclosure. The process of step 44 is an example of a process of a "generation unit" in the technology of the present disclosure.

In step 46, the sharing unit 22A sets the secret information s _i shown in the asymmetric secret sharing scheme as a true random number r _i , and the pseudo-random numbers (t shared values) qr _ij as q _ij , and performs processes 4 and 5 of the asymmetric secret sharing scheme [Sharing] to calculate n-t shared values Wr _i,t+1 , ..., Wr _i,n from the t shared values qr _ij and the first secret information r _i .

The processing of step 46 is an example of the processing of the "calculation unit" of the technology disclosed herein.

In this way, in distribution 1, the distribution unit 22A directly uses the pseudo-random numbers qr _ij to conceal the true random numbers (first secret information).

The processing of distribution 1 is an example of the processing of the "first concealment unit" of the technology disclosed herein. Distribution unit 22A of distribution 1 is an example of the "generation unit" and "calculation unit" of the technology disclosed herein.

[Dispersion 2]
In step 48, the sharing unit 22A uses the data identifier dID[s _i ] (i = 1, ..., m) to generate t pseudo-random numbers q _ij from the key key _2,j according to the following equation (20). Thereafter, q _ij is also used as the t shares. However, the t shares are in the form of q _ij + _ri, which are concealed by the true random number _ri of [share 1].
q _ij = Enc(dID[s _i ], key _2j ) (20)
key2,j is an example of a "second key" in the technique of the present disclosure.

In step 50, the sharing unit 22A sets its own secret information (i.e., the second secret information) as s _i , sets the key server's share value as q _ij + r _i , and performs processes 4 and 5 of the asymmetric secret sharing scheme [Sharing] to calculate n-t share values W _i,t+1 , ..., W _i,n from the t share values q _ij and the second secret information s _i .

In this way, in distribution 2, the sharing unit 22A does not directly use the pseudo-random numbers q _ij but uses true random numbers to conceal the shared values and conceal the secret information. This is a difference from distribution 1.

In step 52, the distribution unit 22A transmits dID[s _i ], the calculated distribution values W _i,t+1 , ..., W _i,n, and the distribution values Wr _i,t+1 , ..., Wr _i,n to the data servers x _t+1 , ..., x _n , thereby completing the execution of the distribution program 26P1.

The data server associates dID[s _i ], Wri _,t+1 , ..., Wri _,n with Wi _,t+1 , ..., Wi _,n and stores them.

The processing of distribution 2 is an example of the processing of the "second concealment unit" of the technology disclosed herein. Distribution unit 22A of distribution 2 is an example of the "second concealment unit" of the technology disclosed herein.

As described above, the distribution unit 22A is an example of the "first concealment unit" (specifically, the "generation unit" and "calculation unit") and "second concealment unit" of the technology disclosed herein.

<Restoration>
Next, the restoration program 26P2 will be described with reference to Figures 4A and 4B. Figure 4A is a flowchart of the restoration program 26P2 according to the first embodiment, and Figure 4B is a diagram showing the processing of the restoration unit 22B according to the first embodiment. The restoration processing is performed by the CPU 22 executing the restoration program 26P2.

[Restoration 1]
In step 62, the restoration unit 22B receives the associated and stored shared values Wr i,t ₊₁ , ..., Wr i, _n and W i _,t+1 , ..., W i,n from an owner who wants to restore _secret information s i by sending dID[s _i ] to n-t data servers x t+ ₁ , ... _{, xn} .

In step 66, the restoration unit 22B calculates qr _ij from equation (19) using the key key _1j managed by itself, and restores the first secret information r _i by combining it with Wr _i.t+1 , . . . , Wr _i,n .

[Restoration 2]
In step 68, the restoration unit 22B calculates q _ij from equation (20) using the key key _2j that it manages, and restores the secret information s _i by combining the shared values generated by the key server as q _ij +r _i with W _i,t+1 , ..., W _i,n .

A more detailed explanation follows.

When n = k = 2, there is one key server, so information-theoretic security can be achieved with one true random number, as mentioned above.

When n = k = 3, the number of key servers is t < k, so one or two can be selected. When t = 1 in [Share] 1, one pseudo-random number qr _i1 is generated by the key server, and Wr _i2 and Wr _i3 shown below are calculated by process 4 of asymmetric secret sharing using an additional true random number r ₂ corresponding to A(i) _k-1-t in asymmetric secret sharing [Share] 4, and sent to data servers x2 and x3. Here, the relationship between qr _i1 , Wr _i2 , and Wr _i3 is as follows, and if r ₁ and ar ₂ are swapped as described above, the form becomes the same as conventional secret sharing, and it can be said that information-theoretic security is established.

 

If t=2, two pseudo-random numbers qr _i1 and qr _i2 are generated by the key server, and Wr _i3 in equation (26) is calculated via ar ₁ and ar ₂ in the process 4 of asymmetric secret sharing, and sent to the data server x3 (the additional true random number r2 is not used).

 

In this case, the only true random number is _r1 , but since one true random number remains, information-theoretic security is maintained. Also, since there is only one data server, processing to delete any more true random numbers is not possible, and information-theoretic security is maintained in the same way as when t = 1.

Next, in the case of [distribution 2] where t=2, the pseudo-random numbers q ₁ and q ₂ generated by the key server are set to q ₁ +r ₁ and q ₂ +r _1, respectively, to obtain the following relationship.

 

Since the attacker only knows Wr _i3 (, W _i3 ), it can be said that there is no problem even if there is only one true random number (a ₁ and a ₂ in equations (27) to (29) are obtained by replacing qr ₁ and qr ₂ in equations (24) and (25) with q ₁ + r ₁ and q ₂ + r ₁ ). Next, even if t = 1 in [Distribution 2], an additional random number is added and qr _i1 in equation (21) becomes q ₁ + r ₁ , but it can also be said that there is no problem.

In addition, in [Sharing 2], t pseudo-random numbers q _ij generated using key _2j are concealed by first secret information r _i , which is a true random number. However, true random number r _i may be generated as t shares without addition with q _ij and used directly. In this case, the same number of true random numbers as the key servers are required to change the value of the shares. For example, even if q ₁ +r ₁ is replaced with r ₁ and q ₂ +r ₁ is replaced with r ₂ in equations (27) to (29), the formula will be the same as conventional secret sharing and no problems will arise. Also, r ₁ and r ₂ may be used instead of a ₁ and a ₂ , and in this case, ordinary secret sharing can be used instead of asymmetric secret sharing. Note that the concealment of secret information is achieved by the secret sharing itself.

From the above, it can be said that the method proposed by the technology disclosed herein allows n, k, and t to be set arbitrarily, and can achieve security equivalent to information-theoretic security, just like when n = k = 2.

Second Embodiment
Next, a second embodiment will be described. The configuration of the second embodiment is the same as that of the first embodiment, so the description thereof will be omitted. The operation of the second embodiment will be described below.

In addition to the processing in the first embodiment, the following methods can be used to make the asymmetric secret sharing scheme information-theoretically secure.

When calculating shares using formula (1) in the Shamir scheme, publicly known x _i, which is the server ID, is substituted into formula (1) to obtain the corresponding share W _i . Generally, if the publicly known x _i is unknown, it is not possible to recover the shares even if k shares are collected. Therefore, by doing the following, the asymmetric secret sharing scheme can be made information-theoretically secure even if the second secret information s1 is known. The following outline will be given assuming n=k=2 for simplicity.

[Dispersion]
The owner obtains a true random number _r1 that is not 0, _x1 , or _x2 , and performs asymmetric secret sharing of the true random number _r1 .

The owner asymmetrically shares secret information _s1 by dividing _r1 into _x2 . Hereinafter, _r1 = x2'.
[Restore]
The restorer restores x2'.

The restorer restores the secret information _s1 using the restored x2' as _x2 .

In the above, the true random number _r1 is also the first secret information, and the owner's secret information _s1 is the second secret information, and distribution and restoration are performed in two stages, _r1 and _s1 . As in the first embodiment, it is clear that information-theoretic security can be achieved for the first secret information _r1 . Therefore, unless _r1 = x2' is known, equation (1) cannot be solved, and since a solution exists for the second secret information _s1 for all x2', it can be said that information-theoretic security is achieved. Furthermore, even if the second secret information s1 is inferred or made public, _a1 x2' can be known from equation (8), but x2' cannot. Therefore, since _a1 is unknown, _q1 cannot be known, and equation (17) holds, ensuring information-theoretic security.

Furthermore, in the above, only _x2 is defined as the first secret information x2', but _x1 may also be defined as the first secret information _x1 ', or both _x1 ' and _x2 ' may be defined as the first secret information. A detailed algorithm is shown below. In the first embodiment, although multiple first secret information can be selected, only _r1 is defined for the second secret information _s1 . In this embodiment, all server IDs _x1 ', ..., _xn ' can be selected as the first secret information. However, since the secret information cannot be known even if only one server ID is unknown, the first secret information may be a single server ID, as in the first embodiment. However, in this embodiment, to differentiate from the first embodiment, the number of first secret information in [Sharing] 1 is set to n-t, which is the same number as the number of data servers. Therefore, asymmetric secret sharing is repeated using n-t true random numbers as the first secret information. However, when t=k-1, the number of data servers is 1, so the number of first secret information is 1, which is the same as in the first embodiment. Other settings are the same as those in the first embodiment.

Next, distribution program 26P1 will be described with reference to Figure 5 (see also Figure 3B). Figure 5 is a flowchart of distribution program 26P1 according to the second embodiment.

[Variance 1]
In step 72, the sharing unit 22A obtains from the true random number generation device 28 true random numbers r _{i,h (h=t+1, . . . , n) that do not match 0 or the server ID for its own secret information s i .}

In step 74, the sharing unit 22A generates pseudo-random numbers qr _ihj (j=1, ..., t) using the data identifier dID[r _i,h ] for r _i,h as follows: As described above, the pseudo-random numbers qr _ihj are used as t sharing values for each piece of first secret information r i,h.
qr _ihj = Enc(dID[r _i,h ], key _1j ) (30)
In step 76, the sharing unit 22A sets the first secret information to r _i,h (h = t + 1, ..., n) and qr _ihj to q _ij , and repeats the processes from step 4 onwards of the asymmetric secret sharing method to calculate the sharing values Wr _i,h,t+1 , ..., Wr _i,h,n (h = t + 1, ..., n) to be sent to the data servers x _t+1 , ..., x _n .

[Dispersion 2]
In step 78, the sharing unit 22A generates a pseudo-random number qij using a data identifier dID[s _i ] (i=1, . . . , m) related to the second secret information s _i .
q _ij = Enc(dID[s _i ], key _2j ) (31)
The key Key _2i is an example of the "second key" of the technology of the present disclosure.

In step 80, the sharing unit 22A uses the ID of the data server x _h (h=t+1, ..., n) as the true random number r _i,h , i.e., the true random number r _i,h is used as a variable in the sharing formula (1), and performs processes 4 and 5 of the asymmetric secret sharing method to _calculate n-t shared values W _i,t+1 , ..., W _i,n from the t shared values q _ij and the second secret information s i.

This differs from distribution 1 in that a true random number r _i,h is used as the server ID.

In step 82, the distribution unit 22A transmits dID[s _i ], Wri _{,h,t+1, ..., Wri,h,n} , and Wi _{,t+1, ...} , Wi, _n to the data servers x _{t+ 1} , ..., x _n .

The data server associates and stores them.

Next, the restoration program 26P2 will be described with reference to Figure 6 (see also Figure 4B). Figure 6 is a flowchart of the restoration program 26P2 in the second embodiment.

[Restoration 1]
In step 92, the restoration unit 22B of the owner who wants to restore the secret information s _i sends dID[s _i ] to n-t data servers x _t+1 , ..., x _n , and in step 94 receives the associated and stored shared values Wr _i,h,t+1 , ..., Wr _i,h,n and W _i,t+1 , ..., W _i,n .

In step 96, the restoration unit 22B obtains qr _ihj from equation (30) using the key key _1j that it manages, and combines it with Wr _i,h,t+1 , ..., Wr _i,h,n to restore the first secret information r _i,h (h = t+1, ..., n).
[Restoration 2]
In step 98, the restoration unit 22B obtains q _ij from equation (31) using the key key _2j that it manages, and restores the second secret information s _i by combining it with W _i,t+1 , ..., W i, _n , with the ID of the data server x _h (h = t+1, ..., n) as r i _, h.

In the above, only the data server ID was kept secret, but the key server ID may also be kept secret.

Also, if all server IDs are determined using true random numbers, the true random numbers do not need to be 0 or the same value.

Third Embodiment
Next, a third embodiment will be described. The configuration of the third embodiment is the same as that of the first embodiment, so the description thereof will be omitted. The operation of the third embodiment will be described below.

This embodiment demonstrates a method that remains secure even if secret information is made public in a different way than in the second embodiment. For simplicity, the following overview will be given assuming n = k = 2.

In the asymmetric secret sharing scheme, the owner performs encryption using fixed keys _key1j and _key2j (j = 1, ..., t) and calculates qr _ij and q _ij . If some qr _ij and q _ij can be inferred, there is a possibility that keys _key1j and _key2j may be analyzed. Therefore, a method for improving security by changing the key _key2j in [share]2 each time will be described below. As in the first embodiment, an overview will be given assuming n = k = 2.

[Dispersion]
The owner generates a true random number _r1 and asymmetrically shares the first secret information _r1 with the sharing unit 22A.
The 2 sharing unit 22A calculates q _ij using key _2j +r ₁ as a new key key _2j , and performs asymmetric secret sharing of the second secret information s ₁ .

In this way, the sharing unit 22A uses the true random number _r1 as the key _key2j for generating pseudo-random numbers to generate t shares, and calculates n-t shares from the t shares and the secret information.

The third embodiment differs from share 1 in that a true random number _r1 is used as a key _key2j for generating pseudo-random numbers.

[Restore]
1. The restoration unit 22B restores the first secret information _r1 .
2. The restoration unit 22B calculates q _ij using r ₁ +key _2j as a new key _2j , and restores the second secret information s ₁ .

In the above, the key _key2j used to generate _qij changes each time depending on the true random number _rj , so even if _qij can be analyzed from previously transmitted data, etc., and the _key2j used to generate _qij can be analyzed, it becomes meaningless. When first secret information _rj is generated for _each piece of secret information sj and _key2j is changed, the detailed algorithm is the same as in the first embodiment except that _key2j is set to _r1 + _key2j . When _key2j is changed each time, even if the key is determined from one set of dID[ _sj ] and _qij , it will not be used next time, so it can be said that security equivalent to information-theoretic security is achieved. If several sets of dID[ _sj ] and _qij are required for analysis, _key2j can be changed for each of multiple _sj within that range. In this case, process 1 of [distribution] [recovery] is performed each time _key2j is changed. Therefore, in this case, the number of times asymmetric secret sharing is performed and the number of shares stored in the data server are fewer than in the first embodiment. However, in the first and second embodiments, asymmetric secret sharing of the first secret does not have to be performed every time, but can be performed for multiple _sj . Also, in this embodiment, if asymmetric secret sharing of the first secret is performed every time, it will be almost the same as the first embodiment. Also, if the first secret is updated once every few times, [Share 1] and [Restore 1] can be performed at that time. Therefore, detailed algorithms will be omitted.

Furthermore, if two true random numbers r _1j and r _2j are used as the first secret information, and key _1j is set to key _1j +r _1j and key _2j is set to key _2j +r _1j , then even if key _1j is analyzed, it will be useless.

Furthermore, the first secret information can be used as an update key without being added to key _1j and key _2j .

<Fourth embodiment>
Next, a fourth embodiment will be described. The configuration of the fourth embodiment is the same as that of the first embodiment except that the owner is provided with a display device (not shown), so a description thereof will be omitted. The operation of the fourth embodiment will be described below.

In the first embodiment, it was shown that even if the shares stored in the data server are leaked, the secret information is protected with the same security as information-theoretic security. In this embodiment, a method is shown that can verify if the data server has been tampered with by an attacker in asymmetric secret sharing. First, an overview will be given assuming n = 4, k = 3, t = 2, and the number of data servers u = n - t = 2. Also, let x ₁ and x ₂ be the IDs of the key servers, and x ₃ and x ₄ be the IDs of the data servers. If k = 3, the secret can be restored if all three shares are collected. Therefore, the shares generated from the two key server keys held by the owner are restored by changing the data server shares one by one, and if the results match, it is determined that the data server has not been tampered with.

[Dispersion]
The secret sharing unit 22A asymmetrically shares the true random number _r1 with n=4, k=3, t=2, and u=2.
The 2 sharing unit 22A performs asymmetric secret sharing of the second secret information _s1 using _q1 + _r1 , which is the sum of _{r1 and} the pseudo-random number q1 generated from the key _2j , as a sharing value.

[Restore]
1-1. The restoration unit 22B restores secret information using the server's shared values of x ₁ , x ₂ , and x ₃ to r ₁ '.
1-2. The restoration unit 22B restores the secret information restored using the server's shared values of x ₁ , x ₂ , and x ₄ to r ₁ ″.
1-3. The restoration unit 22B determines that there is no tampering if r ₁ '=r _{1 '} ', and terminates the process if r ₁ '≠r1 ''.
2-1. The restoration unit 22B restores secret information using the server's shared values of x ₁ , x ₂ , and x ₃ to s 1 '.
2-2. The restoration unit 22B restores the secret information restored using the server's shared values of x ₁ , x ₂ , and x ₄ to s ₁ ″.
2-3. The restoration unit 22B determines that there is no tampering if s ₁ '=s ₁ '' and determines that there is tampering if s ₁ '≠s ₁ ''.

In the above [Distribution] 1, the key servers x ₁ and x ₂ generate the following pseudo-random numbers q ₁ and q ₂ , and the data servers x ₃ and x ₄ calculate and store W ₃ and W ₄ .

 

a ₁ and a ₂ are calculated from q ₁ and q ₂ generated by t=2 key servers as in equations (24) and (25), and can be regarded as true random numbers since they contain r ₁ .

Therefore, _W1 and _W2 calculated from _r1 , _a1 , and _a2 can also be considered to be true random numbers and do not provide information about _q1 and _q2 . Furthermore, since k = 3, an attacker cannot find _r1 by solving _W3 and _W4 , which they can know. Furthermore, the constant term _r1 can be deleted by subtracting _W4 from _W3 , but since _a1 and _a2 contain _r1 as described above, information-theoretic security is satisfied.

In contrast, in [Recovery] 1, _r1 is recovered twice by changing the combination of data servers. If the results match, it is determined that there has been no tampering; if they do not match, it is determined that there has been tampering. Generally, the shared value is the y-coordinate at the coordinate _x in equation (1), and equation (1) forms a two-dimensional curve. In the above asymmetric secret sharing, k = 3, so the owner finds a curve passing through three points _r1 , _q1 , and _q2 ( _r1 is the y-coordinate when the x-coordinate is 0), and stores the y-coordinates of _{x3 and x4} on that curve as _W3 and _W4 on the data server. However, an attacker cannot know the curve because he only knows two points, W3 and _W4 . Therefore, even if an attacker tampers with _W3 to _W3 ', he does not know the curve passing through _q1 , _q2 , and _W3 ', and therefore cannot correctly determine _W4 ' on the tampered curve. Therefore, _W3 and _W4 are combined with _q1 and _q2 in order to perform restoration, and if the restoration results match, it means that the curves passing through _q1 , _q2 , _W3 and _q1 , _q2 , _W4 match, and there is no tampering. However, if the above calculation is performed on modp, there is a 1/p probability that _W4 ' will coincidentally match a false curve. However, if p is set to a sufficiently large value, 1/p becomes a negligible probability, and security is maintained.

It is clear from the first embodiment that the process performed in [Distribution][Recovery] 2 has the same security as that in 1. Furthermore, if the recovery results match, it can be said that the recovered second secret information _s1 has not been tampered with, just like in [Distribution][Recovery] 1.

Next, the restoration program 26P2 will be explained with reference to Figure 7 (see also Figure 4B). The distribution program is a value that allows the n, k, and t settings to be tamper-detectable, and the same processing as in the first embodiment can be performed on these settings. A setting that allows tamper detection requires the number of data servers u to be 2 or more, and is a setting that cannot be restored from a data server, so 1 < u = n - t < k (where t < k). Therefore, since there are no n or t that satisfy this equation when k = 2, the minimum settings are k = 3, n - t = 2, and so t = 2 and n = 4. Figure 7 is a flowchart of the restoration program 26P2 of the fourth embodiment.

For simplicity, let t = k-1. If t < k-1, the variance values of the data servers are verified while changing the combination. Other assumptions are the same as in the first embodiment, so they will be omitted.

[Restoration 1]
In step 102, the restoration unit 22B sends dID[s _i ] to u data servers x _n−u+1 , . . . , x _n .

In step 104, the restoration unit 22B receives the associated and stored variance values Wr _{i, n-u+1} , ..., Wr i,n and W _{i,n-u+1, ..., Wi,n from} u data servers _{x n-u+1} , ..., x _n .

In step 106, the restoration unit 22B obtains k-1 qrij (j=1, ..., k-1) from Equation 19 using the key _key1j managed by itself, and sequentially combines _Wri.nu+1 , ..., Wri _,n one by one to restore the secret information ri _,nu+1 , ..., ri _,n .

In step 108, the restoration unit 22B determines whether or not there is a match among r _i,n−u+1 , . . . , r _i,n .

If there is a match among r _i,n−u+1 , . . . , r _{i,n ,} the restoration unit 22B sets the match among r _{i,n−u+1 ,} .
[Restoration 2]
In step 112, the restoration unit 22B obtains q _ij (j=1, ..., k-1) from equation 20 using the key key _2j , and sequentially combines it with W _i,n-u+1 , ..., W _i,n one by one to restore the secret information s _i,n-u+1 , ..., s _i,n .

In step 114, the restoration unit 22B determines whether or not there is a match among s _i,n−u+1 , . . . , s _i,n .

If there is a match among s _i,n−u+1 , . . . , s _{i ,n} , the restoration unit 22B adopts the match among s _i,n−u+1 , .

If step 108 or step 114 returns a negative result, the display device displays a message indicating that tampering has occurred.

In the above, the tampering check in [Restoration 1] can be omitted. This is because if the results of [Restoration 1] do not match, it is likely that the results of [Restoration 2] will also not match, so it is sufficient to check [Restoration 2] alone. Accordingly, [Distribution 1] and [Restoration 1] may be the same as in the first embodiment.

If a similar verification is performed for the second and third embodiments, it is possible to verify whether the restored results have been tampered with.
Security can also be improved by increasing n and k. For example, if n = 6, k = 4, and t = 3, the number of data servers is 3. Here, the probability that three distributed values from the data servers will be tampered with and accidentally match is 1/ ^p2 , improving security.

<Other embodiments>
It is clear that the above four embodiments can be implemented in combination. For example, the first to third embodiments can simultaneously conceal shares for the second secret, a server ID, and a pseudo-random number generation key using different first secret information, and one of these can be used as the fourth embodiment to detect tampering. Furthermore, although the second secret information in the above embodiments is s _i , various other values may also be used as the second secret information.

(Non-Patent Document 2)
Keiichi Iwamura and Ahmad Akmal Aminuddin Mohd Kamal, “Communication-Efficient Secure Computation of Encrypted Inputs Using (k,n) Threshold Secret Sharing”, IEEE Access, May 2023.
For example, if _r1 ( _s1 +1) used in the secure computation shown in Non-Patent Document 2 is used as secret information, the restored value can be used directly in the secure computation. Also, the second secret information _s1 may be sent as _r1 + _s1 using the first secret information r1, as in the Vernam cipher. Furthermore, the sending side may send a pseudo-random number _qr1j using the first secret information r1, concealing _r1 + _qr1j as in the Vernam cipher, and the receiving side may obtain _qr1j from the shared key _key1j to extract the first secret information _r1 , and use _r1 to send the second secret information _s1 as in the first to fourth embodiments. However, if the second secret information _s1 is sent in the form of the Vernam cipher, like the first secret information, it becomes _r1 + _s1 , and the true random number is lost by the following calculation.
(r ₁ +qr ₁ )+(r ₁ +s ₁ )=qr ₁ +s ₁
Therefore, the first secret information and the second secret information need to be concealed in different ways. In the first embodiment, the first secret information is used to conceal the shares, in the second embodiment it is used as a server ID, and in the third embodiment it is used for key update. Since they are concealed in different ways, no problems arise. That is, the essence of the present invention is to communicate a true random number as the first secret information while concealing it, and to conceal the second secret information in a different way from the first secret information using the first secret information. However, asymmetric secret sharing is used for one or both of them.

Furthermore, although the keys held by the owner are designated as key _1j and key _2j , encryption may be performed using the same key key _j . In this case, to change the encryption result, the data may be changed by adding or concatenating a predetermined value to the encrypted data identifier. Furthermore, in the first embodiment, if the shares for the second secret information are directly used as the first secret information, key _2j becomes unnecessary, and key _j may be used directly as key _1j .

Furthermore, in the first embodiment, when n = k = 2, the number of shares stored in the data server is two, and no reduction in memory capacity is achieved compared to conventional secret sharing schemes. However, for example, if n = k = 3 and t = k-1, the number of data servers is one and the number of shares stored is two. In conventional secret sharing schemes, three shares are stored, so the total memory capacity is 2/3. Therefore, in the first to third embodiments, if n and k are increased, the total memory capacity is 2/n compared to conventional secret sharing schemes, and the memory reduction rate can be increased.

On the other hand, an advantage of asymmetric secret sharing schemes is that, in addition to reducing memory capacity, it also makes it easier for the owner to manage shares. That is, conventional secret sharing schemes require n data servers, but if k of these servers are attacked by an attacker without the owner's knowledge and shares are leaked, there is a risk that the attacker will learn the secret information. In contrast, asymmetric secret sharing schemes allow the owner to generate up to k-1 shares from a key, the number of data servers can be kept to k-1 (a minimum of 1). Therefore, even if an attacker attacks up to k-1 data servers without the owner's knowledge, the secret information will not be leaked unless there are shares generated by the owner. Therefore, the secret information will not be leaked without the owner's knowledge.
From the above, if t = k-1, a single cloud data server is sufficient, and if the owner performs distribution and restoration using a smartphone or PC (i.e., a personal computer (PC)) that has the function of generating true random numbers, data management with the above characteristics can be achieved with just one smartphone or PC, even if the amount of secret information is enormous. Furthermore, in conventional asymmetric secret sharing schemes, if an attacker can infer the shares generated from the key from the transmitted information, the secret information can be leaked using a quantum computer or the like. In contrast, in the present invention, the security of the transmitted information can be made information-theoretically secure, so an attacker cannot know the shares generated by the owner even with a quantum computer, and it can be said that security is greatly improved.
Furthermore, in conventional secret sharing schemes, even when the minimum value k is 2, a separate encryption mechanism such as the Vernam cipher is required to securely transmit two shares, making them unsuitable for communication. In contrast, asymmetric secret sharing schemes can be used for communication because they require only one share when t = k-1. That is, if n = k = 2, keys _key1j and _key2j are shared between the sender and receiver, and the sender generates a true random number and simultaneously transmits one share each for the first secret and the second secret, cryptographic communication that achieves information-theoretic security in a single communication can be achieved. Furthermore, as shown in the fourth embodiment, if two different shares for the same secret are transmitted when n = 4, k = 3, and t = 2, it is possible to verify whether tampering has occurred on the communication channel using verifiable secret sharing.

Furthermore, if the IoT device performs distributed processing with n = k = 2 and sends Wr _i,2 and W _i,2 to the receiving terminal, and the receiving terminal performs the restoration processing using the shared keys key _1j and key _2j , then the IoT device can perform information-theoretically secure communication with very light processing. Therefore, the proposed method can also be used for communication.

Furthermore, if the secret information is a password (i.e., PW) shared by the sender and receiver, identity authentication can be achieved by the sender sending the PW as secret information to the receiver. However, this alone results in the same information being sent every time, so if a new true random number is sent as additional first secret information and the value obtained by applying this true random number to the PW is sent as the second secret information, identity authentication can be achieved using different information each time. The additional true random number can also be sent by the receiver, and the sender can restore it, apply it to the PW, and send back the value as the second secret information.

Also, the owner and restorer may be the same person, but if the owner allows another restorer to restore the secret information, the owner may tell the restorer the combination of pseudo-random or true random numbers generated for the second secret information. In this case, it is necessary to update the shares stored on the data server, for example by changing the first secret information, to prevent a second restoration from being performed.

The CPU 22 is an example of a "processor" in the technology of this disclosure. In addition to the CPU 22, other examples of processors include dedicated electrical circuits, such as FPGAs (Field-Programmable Gate Arrays), PLDs (Programmable Logic Devices), or ASICs (Application Specific Integrated Circuits), which are processors with a circuit configuration designed specifically to perform specific processing.

The hardware resource that executes the distributed processing and restoration processing may be composed of one of these various processors, or may be composed of a combination of two or more processors of the same or different types (for example, a combination of multiple FPGAs, or a combination of a CPU and an FPGA). Also, the hardware resource that executes the distributed processing and restoration processing may be a single processor.

As an example of a system configured with a single processor, first, one processor is configured with a combination of one or more CPUs and software, and this processor functions as a hardware resource that executes distributed processing and restoration processing. Second, there is a system that uses a processor that realizes the functions of an entire system, including multiple hardware resources that execute distributed processing and restoration processing, on a single IC chip, as typified by SoCs (System-on-a-chip). In this way, distributed processing and restoration processing are realized using one or more of the various processors listed above as hardware resources.

Furthermore, the hardware structure of these various processors can be, more specifically, an electrical circuit that combines circuit elements such as semiconductor devices. Furthermore, the distributed processing and restoration processing described above are merely examples. Therefore, it goes without saying that unnecessary steps can be deleted, new steps can be added, or the processing order can be rearranged, as long as it does not deviate from the spirit of the invention.

Storage device 26 is a non-transitory storage medium. An example of storage device 26 is a hard disk drive (HDD). Note that an HDD is merely an example, and other types of storage devices such as a solid state drive (SSD) may also be used.

The above-described written content and illustrations are a detailed explanation of the parts related to the technology of the present disclosure and are merely an example of the technology of the present disclosure. For example, the above explanation of the configuration, functions, actions, and effects is an explanation of an example of the configuration, functions, actions, and effects of the parts related to the technology of the present disclosure. Therefore, it goes without saying that unnecessary parts may be deleted, new elements may be added, or substitutions may be made to the above-described written content and illustrations, as long as they do not deviate from the spirit of the technology of the present disclosure. Furthermore, in order to avoid confusion and to facilitate understanding of the parts related to the technology of the present disclosure, the above-described written content and illustrations omit explanations of common technical knowledge that do not require particular explanation to enable the implementation of the technology of the present disclosure.

All publications, patent applications, and technical standards mentioned in this specification are incorporated by reference herein to the same extent as if each individual publication, patent application, and technical standard was specifically and individually indicated to be incorporated by reference.

<Additional Notes>
In light of the above disclosure, the following remarks are proposed:
(Appendix 1)
A system is provided with a secret sharing device and a secret information recovery device, where n is an integer greater than or equal to 2 and k is an integer having a minimum value of 2 and a maximum value of n, where one piece of secret information is distributed into n shared values, and the secret information can be recovered by collecting k of the shared values, but the secret information cannot be recovered by collecting k-1 or fewer shared values. The secret sharing device in this system is provided with a processor, which acquires one or more true random numbers as first secret information, generates t (<k) shared values for each true random number from a first key, and executes a process of calculating n-t shared values from the t shared values and the first secret information.
(Appendix 2)
A system comprising a secret sharing device and a secret information recovery device, where n is an integer greater than or equal to 2 and k is an integer having a minimum value of 2 and a maximum value of n, where one piece of secret information is distributed into n distribution values, and the secret information can be recovered by collecting k of the distribution values, but the secret information cannot be recovered by collecting k-1 or fewer of the distribution values, comprises a processor, and the processor conceals a true random number as first secret information, and uses the first secret information to perform a process of concealing second secret information in a form different from the first secret information.
(Appendix 3)
The secret information recovery device in the system described in claim 1 includes a processor, and the processor recovers first secret information and performs a process of recovering second secret information described in Appendix 2 using the recovered first secret information.
(Appendix 4)
A secret information recovery device in a system in which n is an integer greater than or equal to 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distributed values, and the secret information can be recovered by collecting k of the distributed values, but cannot be recovered by collecting k-1 or fewer distributed values, includes a processor, and the processor executes a process of recovering the secret information by sequentially changing the combinations of t distributed values and n-t distributed values generated from the key described in Appendix 1.
(Appendix 5)
A secret sharing apparatus for a system in which one piece of secret information is distributed into n shared values, where n is an integer greater than or equal to 2 and k is an integer with a minimum value of 2 and a maximum value of n, and the secret information can be restored by collecting k of the shared values but cannot be restored by collecting k-1 or fewer shared values, comprises a processor, which calculates t (<k) shared values from a key and executes a process of calculating n-t shared values from the calculated t shared values and the secret information, and the secret sharing apparatus further comprises a true random number generation unit which generates true random numbers using a natural phenomenon that cannot be controlled by humans, and the processor calculates at least one of the t shared values and the n-t shared values using the true random numbers.

Claims (18)

An asymmetric secret sharing apparatus for a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values,
a generation unit that acquires one or more true random numbers as first secret information and generates t (<k) shares for each true random number from a first key;
a calculation unit that calculates n−t shared values from the t shared values and first secret information;
1. An asymmetric secret sharing device comprising: An asymmetric secret sharing apparatus for a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values,
a first concealment unit that conceals the true random number as first secret information;
a second concealment unit that conceals second secret information using the first secret information in a form different from that of the first secret information;
An asymmetric secret sharing device comprising: the first concealment unit includes a generation unit and a calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second secret information generating unit secretly generates t shared values from all or some of the t pseudo-random numbers generated from the second key using the true random numbers, or generates t shared values directly from the t true random numbers, and calculates n-t shared values from the t shared values and the second secret information;
3. The asymmetric secret sharing device according to claim 2. the first concealment unit includes the generation unit and calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second secret unit generates t shares by using a second key, and calculates n-t shares from the t shares and the second secret by using the first secret as a variable of a sharing formula;
3. The asymmetric secret sharing device according to claim 2. the first concealment unit includes the generation unit and calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second concealing unit generates t shares by using the true random number as a second key for generating pseudo-random numbers, and calculates n-t shares from the t shares and secret information;
3. The asymmetric secret sharing device according to claim 2. The asymmetric secret sharing device described in claim 2, characterized in that the first concealment unit or the second concealment unit obtains one or more true random numbers and conceals pseudo-random numbers generated from a key. A secret information recovery device in the system according to claim 1,
a first restoration unit that restores the first secret information;
a second restoration unit that restores the second secret information according to any one of claims 3 to 6 using the restored first secret information;
A secret information recovery device comprising: A secret information recovery device for a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distributed values, and the secret information can be recovered by collecting k of the distributed values, but the secret information cannot be recovered by collecting k-1 or fewer distributed values,
6. A secret information recovery device comprising: a recovery unit that recovers secret information by sequentially changing the combination of t shares and n−t shares generated from the key according to claim 1. An asymmetric secret sharing apparatus for a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values,
a first calculation unit for calculating t (<k) shares from the key;
a second calculation unit that calculates n−t shared values from the calculated t shared values and secret information;
and
The secret sharing apparatus further comprises a true random number generation unit that generates true random numbers using natural phenomena that cannot be controlled by humans,
At least one of the t variance values and the n-t variance values is calculated further using the true random numbers.
Asymmetric secret sharing device. A computer of an asymmetric secret sharing device in a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values, is
An asymmetric secret sharing program for functioning as: a generation unit that acquires one or more true random numbers as first secret information, and generates t (<k) shares for each true random number from a first key; and a calculation unit that calculates n-t shares from the t shares and the first secret information. A computer of an asymmetric secret sharing device in a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values, is
An asymmetric secret sharing program for causing a first concealment unit to conceal a true random number as first secret information, and a second concealment unit to conceal second secret information in a form different from that of the first secret information by using the first secret information. the first concealment unit includes a generation unit and a calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second secret information generating unit secretly generates t shared values from all or some of the t pseudo-random numbers generated from the second key using the true random numbers, or generates t shared values directly from the t true random numbers, and calculates n-t shared values from the t shared values and the second secret information;
The asymmetric secret sharing program according to claim 11. the first concealment unit includes the generation unit and calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second secret unit generates t shares by using a second key, and calculates n-t shares from the t shares and the second secret by using the first secret as a variable of a sharing formula;
The asymmetric secret sharing program according to claim 11. the first concealment unit includes the generation unit and calculation unit according to claim 1, and generates the t shared values, and calculates n-t shared values from the t shared values and the first secret information, thereby concealing the true random numbers as the first secret information;
the second concealing unit generates t shares by using the true random number as a second key for generating pseudo-random numbers, and calculates n-t shares from the t shares and secret information;
The asymmetric secret sharing program according to claim 11. The asymmetric secret sharing program described in claim 11, characterized in that the first or second concealment unit obtains one or more true random numbers and conceals pseudo-random numbers generated from a key. The computer of the secret information recovery device in the system according to claim 1 is
A secret information restoration program for causing a computer to function as: a first restoration unit that restores first secret information; and a second restoration unit that restores second secret information according to any one of claims 3 to 6 using the restored first secret information. A computer of a secret information recovery device in a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distributed values, and the secret information can be recovered by collecting k of the distributed values, but the secret information cannot be recovered by collecting k-1 or fewer distributed values, is
A secret information recovery program for causing a recovery unit to function as a recovery unit that recovers secret information by sequentially changing the combination of t shares and n-t shares generated from the key according to any one of claims 1, 3 to 5. A computer of an asymmetric secret sharing device in a system in which n is an integer equal to or greater than 2, k is an integer having a minimum value of 2 and a maximum value of n, one piece of secret information is distributed into n distribution values, and the secret information can be restored by collecting k of the distribution values, but the secret information cannot be restored by collecting k-1 or fewer distribution values, is
an asymmetric secret sharing program for causing a generating unit to generate t (<k) shares from a key; and a calculating unit to calculate n-t shares from the calculated t shares and secret information, the program comprising:
The asymmetric secret sharing apparatus further comprises a true random number generation unit that generates true random numbers using natural phenomena that cannot be controlled by humans,
At least one of the t variance values and the n-t variance values is calculated further using the true random numbers.
Asymmetric secret sharing program.