CN108418810A - Secret sharing method based on Hadamard matrix - Google Patents

Abstract

The invention relates to the technical field of information hiding, in particular to a secret sharing method based on a Hadamard matrix, which comprises the following steps: s1, generating key parameters, generating a Hadamard matrix H with a specified dimension by an administrator according to the key parameters, and constructing a block association matrix U according to the Hadamard matrix H; s2, the administrator generates corresponding secret sharing for each member according to the block association matrix U; and S3, reconstructing the secret S by the member according to the secret sharing value and the group association matrix U. The invention is suitable for secret sharing and privacy protection of multi-party members in a distributed computing environment, and the secret sharing method based on the Hadamard matrix is simple and effective. An administrator can generate a Hadamard matrix with a designated dimension according to the secret space and the user scale, then a group association matrix is generated, secret sharing and secret reconstruction are finally achieved, calculation and storage efficiency is high, and the method has a wide application prospect.

Description

A Secret Sharing Method Based on Hadamard Matrix

technical field

The invention relates to the technical field of information hiding, in particular to a Hadamard matrix-based secret sharing scheme and its safety proof.

Background technique

With the continuous evolution and development of network technology and computing models, distributed computing represented by cloud computing plays an irreplaceable important role in information technology and has become a basic computing technology. Distributed computing technology needs to solve the problems of information sharing and information privacy protection among untrustworthy multi-party members during collaborative computing. The secret sharing scheme solves the problems of information sharing and privacy protection in a distributed computing environment. The secret sharing scheme is a basic protocol, originally proposed by Shamir and Blakley independently to solve key distribution, and can also be applied to general information sharing and privacy protection. The basic idea of secret sharing is to protect the privacy of information. Its initial application scenario is: the administrator has the key of a core information system and is worried about the loss of the key, so the administrator shares the key with multiple members, but every No member can obtain the key individually. The secret sharing scheme can not only solve the problem of dishonesty of a single member, but also solve the problem of the loss of a single secret sharing and damage the security of the key itself. Therefore, keys are shared among members of a group. Secret sharing schemes play a pivotal role in cryptography and distributed computing, such as multi-party secure computing, threshold cryptography, access control, attribute-based encryption mechanism, attribute-based signature mechanism, general forgetful transmission protocol, image hiding and digital watermarking Wait.

The administrator has the key s, and distributes shared values _{s 1} , s ₂ , ..., s _n to n members P 1 , P ₂ , ..., P _n . Note that the threshold for key recovery is r and r>2. When the number of members is greater than or equal to the threshold r, this group of members can easily recover the key s; otherwise, each member cannot obtain the key s. Figure 1 depicts the secret sharing scheme when r>2. Of course, the recoverability of secret sharing schemes can be represented by many more generalized forms, such as monotonic functions and access structures.

At present, the industry and academia have given a variety of secret sharing schemes. According to the principle of secret sharing schemes, they can be divided into secret sharing schemes based on Lagrange interpolation polynomials, secret sharing schemes based on linear space theory on finite fields, and modular operation-based secret sharing schemes. Secret sharing scheme, etc. Shamir first proposed the (r,n)-type threshold secret sharing scheme (A.Shamir, How to share a secret, Commun.ACM, vol.22, no.11, pp.612–613, 1979.), the scheme Reconstructing the key s using at least r shared secret values requires Lagrange interpolation polynomials to perform complex calculations. Blakley proposed a secret sharing scheme based on linear space theory (G.R.Blakley, Safeguarding cryptographic keys, in Proc.AFIPS 1979National Computer Conference.AFIPS,1979,pp.313–317.), which requires Computing the intersection of linear subspaces, the elements in the intersection are generally not unique, which brings interference to key reconstruction. Asmuth-Bloom proposed a secret sharing scheme based on modular operations (C.Asmuth and J.Bloom, A modular approach to key safeguarding, IEEETrans.Information Theory, vol.29, no.2, pp.208–210, 1983 .), the scheme has high computational efficiency in the secret sharing stage, but the key reconstruction calculation and secret sharing storage bring huge calculation and storage costs.

Contents of the invention

The object of the present invention is to establish a secret sharing scheme with low computation and storage complexity. The secret sharing scheme based on Hadamard matrix generates a Hadamard matrix H of specified dimension according to the secret space and the number of members, calculates the corresponding block correlation matrix U from the Hadamard matrix, and uses the row vector of the block correlation matrix U to distribute secrets to each member Shared value; in the key reconstruction stage, the secret s is reconstructed according to the block matrix and the member's secret shared value. This solution can be widely used in computing and storage devices, especially for lightweight computing and storage devices, such as smart terminals and sensors in the Internet of Things.

The present invention is achieved through the following technical solutions:

A method for sharing secrets based on Hadamard matrix, comprising the following steps:

S1, generating key parameters, the administrator generates a Hadamard matrix H of specified dimensions according to the key parameters, and then constructs a block association matrix U according to the Hadamard matrix H;

S2. The administrator generates a corresponding secret share for each member according to the block association matrix U;

S3. The member reconstructs the secret s according to the secret sharing value and the block association matrix U.

Preferably, the key parameters include the number of members and the scale of secret values.

Preferably, S1 specifically includes the following steps:

S11. The administrator determines the secret parameter n′ according to the size of the secret space q and the number of members n

S12. The administrator converts the secret s∈F _q into binary form

S13, construct n' order Hadamard matrix H _n' ;

S14. Calculating the n'-1 order block correlation matrix U;

Among them, s _j represents the value of the jth bit of the secret s, which takes the value of 0 or 1, and the value range of the secret s F _q ={0,1,2,…,q-1} is a finite field, and q is Prime number.

Furthermore, n' described in S11 is determined in the following manner:

Further, the generating method of the matrix U in S14 includes the following steps:

S141. Calculate the matrix according to the Hadamard matrix H _n' of order n'

S142, the matrix Remove the elements of the first row and the first column to generate n′-1 order block association matrix U;

Wherein J _n' is a matrix of all 1s of order n', n'=4m, and m is a positive integer.

Preferably, the construction method of the Hadamard matrix is recursive construction or Paley construction.

Preferably, the secret sharing described in S2 includes the following steps:

S21. The administrator takes the ith row vector U _i of the block matrix U, and sets U _i =(u _i,1 ,u _i,2 ,…,u _i,n′-1 ) to generate a secret sharing value

S22. When u _i,j =1, the administrator sends the jth bit of the key s to the member P _i as a vector The jth element of s _i,j =s _j ; when u _i,j =0, the administrator randomly selects s _i,j ∈{0,1} as the vector The jth element of .

Preferably, the secret reconstruction described in S3 includes the following steps:

S31. Each member P _i who wishes to reconstruct the secret s submits their own block vector U _i private key and secret sharing vector

S32. Each member contributes key bits corresponding to its private key;

S33. When , the member group can reconstruct the secret s;

Where w is the number of members who want to reconstruct the secret.

The beneficial effects of the present invention are:

The invention is suitable for secret sharing and privacy protection of multi-party members in a distributed computing environment, and the secret sharing method based on Hadamard matrix is simple and effective. Administrators can generate a Hadamard matrix of specified dimensions according to the secret space and user scale, and then generate a block association matrix, and finally realize secret sharing and secret reconstruction. The calculation and storage efficiency is high, and it has broad application prospects.

Description of drawings

Figure 1 is a schematic diagram of secret sharing and secret reconstruction.

Fig. 2 is a flowchart of the Hadamard matrix-based secret sharing method of the present invention.

Fig. 3 is an example diagram of the secret sharing stage based on Hadamard matrix in the present invention.

Fig. 4 is an example diagram of the secret reconstruction stage based on Hadamard matrix in the present invention.

Detailed ways

In order to better understand the present invention, the present invention will be further described below in conjunction with the examples and accompanying drawings, and the following examples are only to illustrate the present invention rather than limit it.

Currently, existing secret sharing schemes have high computational or storage complexity for secret sharing and secret reconstruction. How to construct a secret sharing scheme with low computational and storage complexity has become an important research content. The secret sharing scheme based on Hadamard matrix is based on Hadamard matrix, constructs block correlation matrix, realizes secret sharing and secret reconstruction according to block correlation matrix. The secret sharing scheme based on Hadamard matrix has a simple construction method, low computation and storage complexity, and can be widely used in lightweight computing and storage devices.

In the secret sharing scheme based on Hadamard matrix, the key owner first converts the secret s∈F _q into binary form And generate n′order Hadamard matrix H _n' , where n is the number of members, q specifies the secret scale, s _j takes the value of 0 or 1, is a positive integer. The key owner determines the secret parameter n′ according to the size of the secret space and the number of members; in the secret sharing stage, the administrator constructs the n′-order Hadamard matrix H _n′ to calculate the n′-1-order block group matrix U, according to n′ -1-order block matrix distributes the secret sharing value; in the secret reconstruction stage, each member reconstructs the secret s based on the block matrix U. As shown in Figure 2, the specific steps are as follows:

(1) Parameter generation stage

Given a secret s∈[0,q-1] and members P ₁ ,P ₂ ,…,P _n-1 , compute The administrator generates Hadamard matrix H n' of order n _' , then calculates block matrix U of order n'-1, and sends the ith row vector U _i of block matrix U to member _Pi as its private key. Here, the parameters n and s should be relatively balanced, that is,

Given n′order Hadamard matrix H _n′ , calculate the matrix And remove the n'-1 order block matrix U generated by its first row and first column elements, where J _n' is an n' order full 1 matrix, n'=4m, and m is a positive integer. Denote U _i as the i-th row vector of block matrix U, and there are |U _i |=2m-1 and |U _i ∩U _j |=m-1.

The construction of Hadamard matrix is usually constructed by recursive construction or Paley construction (Ron M. Roth, Introduction to coding theory. Cambridge University Press 2006, ISBN978-0-521-84504-5, pp.I-XI, 1-566. ). The matrix H of order n is called Hadamard matrix, if HH ^T =nI, where H ^T is the transpose matrix of matrix H, n is the dimension of the matrix, and I is the identity matrix. It can be proved that the dimension n of Hadamard matrix H is a multiple of 1, 2 or 4. The dimensions of Hadamard matrices have strict restrictions. In practical applications, we only focus on Hadamard matrices with dimensions greater than 2. At this time, the dimension n>2 satisfies n≡0(mod 4), that is, there exists a positive integer m such that n=4m.

The recursive construction method can construct a Hadamard matrix whose dimension is a power of 2: easy to verify is a Hadamard matrix of order 2; at the same time, if H _n is a Hadamard matrix of order n, then is a Hadamard matrix of order 2n. Therefore, Hadamard matrices of any power of 2 can be constructed on the basis of Hadamard matrices of order 2. For the sake of simple construction, the dimension n' of the Hadamard matrix in the parameter generation process can be selected as a power of 2, so the recursive construction can solve the construction of the Hadamard matrix.

The Paley construction gives a more general Hadamard matrix construction method: this method is based on the quadratic residue problem over finite fields, where the sum of the number of finite field elements and 1 is a multiple of 4.

(2) Secret sharing stage

The administrator distributes secret sharing values to members _Pi according to the block matrix U. The administrator takes the i-th row vector U _i of the block matrix U, and sets U _i =(u _i,1 ,u _i,2 ,…,u _i,n′-1 ) to generate a secret sharing value as follows:

When u _i,j = 1, the administrator sends the jth bit of key s to member P _i as a vector The jth element of , that is, s _i,j = s _j ;

When u _i,j =0, the administrator randomly selects si _,j ∈{0,1} as the vector The jth element of .

Figure 3 shows the secret sharing process based on Hadamard matrix H. In the secret sharing phase, the member _Pi gives the private key U _i = (0,1,0,0,1,1,0), the administrator sends the secret bits s ₂ , s ₃ , s ₆ to the member _Pi , The other bits λ _i are randomly assigned 0 or 1.

(3) Secret reconstruction stage

as a group member When it is desired to reconstruct the secret s, each member submits its own block vector private key and secret sharing vector The reconstruction algorithm computes the key s'. Assuming that the number of members is w, each member can uniquely recover the key s if and only if

Figure 4 shows the secret reconstruction process based on Hadamard matrix H. When the secret is reconstructed, the corresponding secret bits whose private key bit is 1 are recovered according to the member's private key, as shown in Figure 4, the secret bits s ₂ , s ₃ , and s ₆ are recovered. When a group of members jointly reconstructs the key, each member can contribute the key bits corresponding to its private key, and the member group can reconstruct the key if and only if In this secret sharing mechanism, the threshold r≤2m+1, where n'=4m. That is to say, any member greater than or equal to 2m+1 must be able to successfully reconstruct the key s; when hour, Where E[·] represents the expected value of the random variable. That is, when Any u members can reconstruct the entire key s in the desired sense.

The invention is suitable for secret sharing and privacy protection of multi-party members in a distributed computing environment, and the secret sharing method based on Hadamard matrix is simple and effective. Administrators can generate a Hadamard matrix of specified dimensions according to the secret space and user scale, and then generate a block association matrix, and finally realize secret sharing and secret reconstruction. The calculation and storage efficiency is high, and it has broad application prospects.

The above-mentioned embodiments are only descriptions of the preferred embodiments of the present invention, and are not intended to limit the scope of the present invention. Without departing from the design spirit of the present invention, those skilled in the art may make various modifications to the technical solutions of the present invention. and improvements, all should fall within the scope of protection determined by the claims of the present invention.

Claims (8)

1. a kind of secret sharing method based on Hadamard matrixes, which is characterized in that include the following steps：

S1, key parameter being generated, administrator generates the Hadamard matrix Hs for specifying dimension according to key parameter, further according to Hadamard matrix Hs construct district's groups incidence matrix U；

S2, administrator are that each member generates corresponding secret sharing according to district's groups incidence matrix U；

S3, member are according to Secret Shares and district's groups incidence matrix U reconstruct secrets s.

2. a kind of secret sharing method based on Hadamard matrixes according to claim 1, it is characterised in that：It is described close Key parameter includes membership, secret value scale.

3. a kind of secret sharing method based on Hadamard matrixes according to claim 1, which is characterized in that S1 is specific Include the following steps：

S11, administrator determine secret parameter n ' according to secret Space Scale q and number of members n

S12, administrator are by secret s ∈ F_qIt is converted into binary form

S13, construction n ' rank Hadamard matrix Hs_n′；

S14, -1 rank district's groups incidence matrix U of n ' are calculated；

Wherein, s_jThe value of j-th of bit of secret s is represented, value is 0 or 1, the value range F of secret s_q=0,1,2 ..., q- 1 } it is finite field, q is prime number.

4. a kind of secret sharing method based on Hadamard matrixes according to claim 3, which is characterized in that S11 institutes N ' is stated to be determined according to following manner：

5. a kind of secret sharing method based on Hadamard matrixes according to claim 3, which is characterized in that S14 institutes The generating mode for stating matrix U includes the following steps：

S141, according to n ' rank Hadamard matrix Hs_n′, calculating matrix

S142, by matrixRemove i.e. -1 rank district's groups incidence matrix U of generation n ' of first element of first trip；

Wherein J_n′It is n ' rank all 1's matrixes, n '=4m, m are positive integers.

6. a kind of secret sharing method based on Hadamard matrixes according to claim 1, it is characterised in that：It is described The building method of Hadamard matrixes is that recurrence Construction or Paley are constructed.

7. a kind of secret sharing method based on Hadamard matrixes according to claim 1, which is characterized in that described in S2 Secret sharing include the following steps：

S21, administrator are by i-th of row vector U of district's groups matrix U_iIf U_i=(u_i,1,u_i,2,…,u_i,n′-1), generate secret sharing Value

S22, work as u_i,jWhen=1, j-th of bit of key s is sent to member P by administrator_iAs vectorJ-th of element, That is s_i,j=s_j；Work as u_i,jWhen=0, administrator randomly chooses s_i,j∈ { 0,1 } is as vectorJ-th of element.

8. a kind of secret sharing method based on Hadamard matrixes according to claim 1, which is characterized in that described in S3 Secret reconstruct include the following steps：

S31, wish to reconstruct each member P of secret s_iSubmit respective district's groups vector U_iPrivate key and secret sharing vector

S32, each member contribute the corresponding key bit of its private key；

S33, whenWhen, member's group can reconstruct secret s；

Wherein w is to wish to reconstruct secret membership.