CN108768622A - The safely outsourced calculating encryption method of matrix determinant in a kind of cloud computing - Google Patents

Abstract

The invention discloses a secure outsourcing calculation encryption method of matrix determinant in cloud computing, and proposes a brand-new encryption method of matrix determinant outsourcing calculation by using identity transformation of matrix determinant and related properties of block matrix, The security of each data element in the matrix and the verifiability of the operation results are guaranteed; the present invention is composed of a key module, an encryption module, a calculation module, a verification module and a decryption module, wherein the key module, the encryption module, the verification module and The decryption module is set on the user's local client, the calculation module is set on the cloud server, and complex calculations are performed on the cloud server, which reduces the time complexity of the algorithm and greatly improves the efficiency of the algorithm.

Description

A secure outsourcing calculation encryption method of matrix determinant in cloud computing

technical field

The invention relates to the field of cloud computing security, in particular to a secure outsourcing calculation encryption method of a matrix determinant in cloud computing.

Background technique

As a basic calculation problem, matrix calculation has a wide range of applications in large-scale engineering calculations, astrophysics research, economic trend analysis, meteorological environment prediction, graphics and image processing and other fields. To some extent, matrix operations, especially large-scale matrix operations, directly affect the development of national industrial infrastructure and national defense. However, for large matrices, its operation is a very time-consuming task, often requiring an extremely expensive price.

The emergence of cloud computing has brought good news to all of these. As a commercial service model, cloud computing essentially outsources its own sufficient equipment resources. Customers use entrusted computing to reduce consumption that cannot be solved locally. Time tasks are entrusted to cloud service providers with capabilities, and cloud service providers perform related tasks on behalf of users, and charge a certain fee according to the number of times of use or the size of occupied resources.

But while cloud computing brings many conveniences to users, it also has huge security risks. As more and more sensitive data is uploaded to the commercial cloud platform through outsourcing, the cloud also deprives users of direct control over the data while receiving user data, thus creating security issues for private data. The security outsourcing calculation of the matrix is applied in this context. It solves the problem that the user's private data and calculation results are easily leaked or maliciously attacked, and at the same time avoids the impact of the complicated encryption process on the calculation efficiency. The security and efficiency of the encryption scheme are improved.

Currently, there are mainly two encryption methods for matrix determinant secure outsourcing calculation in cloud computing: (1) According to the identity property of matrix determinant, a row (column) in the matrix is decomposed into the form of the sum of n elements, The other elements in the matrix remain unchanged, and outsourced encryption calculations are performed on the n matrix determinants respectively. There are two main problems in this solution. On the one hand, the cloud server needs to calculate n matrix determinants, which increases the calculation cost. On the other hand, the user cannot verify the correctness of the calculation results returned by the cloud server. (2) Use the encryption method to encrypt the same matrix twice, and then send the encrypted matrix to the cloud server for calculation respectively, and compare the consistency of the results returned by the cloud server twice. If the results returned by the two times are equal, it is considered that the cloud server The calculation result is credible, otherwise the cloud server will reject the calculation result. Although this solution reduces the calculation cost of the cloud server to a certain extent, if the cloud server multiplies the two returned results by the same coefficient, the wrong calculation result can still be verified by the user and accepted by the user as the correct result. The calculation method proposed in this paper uses the consistency comparison between the calculation results of the cloud server and the relevant elements in the user encryption matrix to verify the correctness of the results returned by the cloud server, which ensures the correctness of the calculation results and the efficiency of the cloud server.

Contents of the invention

The purpose of the present invention is to provide a secure outsourcing calculation encryption method of matrix determinant in cloud computing, which ensures the security of each data element in the matrix and the verifiability of calculation results, and greatly improves the efficiency of the algorithm.

The present invention adopts following technical scheme:

A secure outsourcing calculation encryption method of a matrix determinant in cloud computing, comprising the following steps in sequence:

A: The local client reads the data entered by the user and forms a matrix A: Among them, matrix A is a square matrix of order n, and n is a positive integer;

B: The local client preprocesses matrix A to generate encrypted matrix A ₁ ″:

B1, a set of random keys k, α, β, P, Q, M, N and {π ₁ , π ₂ , π ₃ } are generated by the key module, where k is any non-zero random number, α is a non-zero Zero random vector, α=[α ₁ α ₂ … α _n ] _1×n , β is a zero vector, Both P and Q are sets of random numbers containing n+1 elements, P={p ₁ ,p ₂ ,…,p _n+1 }, Q={q ₁ ,q ₂ ,…,q _n+1 }, M and N are two n+1-order random single-position permutation matrices, and each row and column has only one non-zero element 1; {π ₁ , π ₂ , π ₃ } are n+1-element random permutation functions, Among them, x ₁ ,x ₂ ,x ₃ ,…x _n+1 ∈{1,2,…,n+1}, and any two numbers in x ₁ ,x ₂ ,x ₃ ,…x _n+1 are not equal; y ₁ ,y ₂ ,y ₃ ,…y _n+1 ∈{1,2,…,n+1}, and any two of y ₁ ,y ₂ ,y3,…y _n+1 The numbers are not equal; z ₁ ,z ₂ ,z ₃ ,…z _n+1 ∈{1,2,…,n+1}, and any of z ₁ ,z ₂ ,z ₃ ,…z _n+1 Neither number is equal;

B2. Construct a new matrix A ₁ of order n+1, and encrypt the matrix A input by the user according to the key k, α and β generated in step B1 to obtain a new matrix

B3, perform identity transformation on matrix A ₁ , according to the random permutation function {π ₁ , π ₂ , π ₃ } and random number sets P and Q in step B1, perform the following transformation on matrix A ₁ to obtain matrix A ₁ ′: Wherein, i and j are 1,2,3,...,n+1 respectively; if π ₁ (i)=π ₂ (i), then let p _i =0; if π ₂ (j)=π ₃ (j ), then let q _j =0;

B4. Perform random permutation on matrix A ₁ ′, and perform random permutation on matrix A ₁ ′ according to key M and N to obtain A ₁ ″: A ₁ ″=MA ₁ ′N;

B5, the local client sends the encryption matrix A ₁ ″ to the cloud server;

C: The cloud server calculates the encryption matrix A ₁ ″:

The cloud server executes the LU decomposition algorithm, decomposes the encryption matrix A ₁ " into a lower triangular matrix L and an upper triangular matrix U, and then returns the calculation results L and U to the local client;

D: The local client receives the calculation results L and U returned by the cloud server and performs verification and decryption on the returned calculation results L and U in turn:

D1, verification of the local client: the verification module of the local client verifies whether the value a″ on the main diagonal of the i-th row in the encrypted matrix A ₁ ″ _{i, i} is the same as that of the i element before the i-th row of the lower triangular matrix L and the upper triangular The sum of the products of the first i elements in the i column of matrix U is equal; if Then execute step D2, otherwise refuse to receive the result returned by the cloud server;

D2. The local client uses the decryption module to decrypt the returned calculation results L and U, and restores the value of the determinant of the input matrix A:

The present invention utilizes the identity transformation of the matrix determinant and the related properties of the block matrix to propose a brand-new encryption method for outsourcing calculation of the matrix determinant; compared with the existing encryption method, the present invention ensures that each The security of data elements and the verifiability of operation results; the present invention is composed of a key module, an encryption module, a calculation module, a verification module and a decryption module, wherein the key module, encryption module, verification module and decryption module are set locally on the user The client and the calculation module are set on the cloud server, and complex calculations are performed on the cloud server, which reduces the time complexity of the algorithm and greatly improves the efficiency of the algorithm.

Description of drawings

Fig. 1 is a schematic flow chart of the present invention.

Detailed ways

Below in conjunction with accompanying drawing and embodiment the present invention is described in detail:

As shown in Fig. 1, a kind of matrix determinant safe outsourcing computing encryption method in cloud computing according to the present invention comprises key module, encryption module, calculation module, verification module and decryption module, wherein key module, encryption module The verification module and the decryption module are set on the user's local client, and the calculation module is set on the cloud server, which includes the following steps in turn:

A: The local client reads the data entered by the user and forms a matrix A:

Matrix A is a square matrix of order n; where n is a positive integer;

B: The local client preprocesses matrix A to generate encrypted matrix A ₁ ″:

Step B includes the following specific steps:

B1: A set of random keys are generated by the key module, k, α, β, P, Q, M, N and {π ₁ ,π ₂ ,π ₃ }, where k is any non-zero random number, and α is Non-zero random vector, α=[α ₁ α ₂ …α _n ] _1×n , β is a zero vector, Both P and Q are sets of random numbers containing n+1 elements, P={p ₁ ,p ₂ ,…,p _n+1 }, Q={q ₁ ,q ₂ ,…,q _n+1 }, M and N are two n+1-order random single-position permutation matrices, and each row and column has only one non-zero element 1; {π ₁ , π ₂ , π ₃ } are n+1-element random permutation functions, Among them, x ₁ ,x ₂ ,x ₃ ,…x _n+1 ∈{1,2,…n+1}, and any two numbers in x ₁ ,x ₂ ,x ₃ ,…x _n+1 The values are not equal; y ₁ ,y ₂ ,y ₃ ,…y _n+1 ∈{1,2,…n+1}, and any two of y ₁ ,y ₂ ,y ₃ ,…y _n+1 The values of the numbers are not equal; z ₁ ,z ₂ ,z ₃ ,…z _n+1 ∈{1,2,…n+1}, and z ₁ ,z ₂ ,z ₃ ,…z _n+1 The values of any two numbers are not equal.

B2: Construct a new matrix A of order n+1. ₁ : Encrypt matrix A according to the key k, α and β generated in step B1 to obtain a new matrix

B3: Perform identity transformation on matrix A ₁ : according to the random permutation function {π ₁ , π ₂ , π ₃ } and random number sets P and Q in step B1, perform the following transformation on matrix A ₁ to obtain matrix A ₁ ′: Wherein, i and j are 1,2,3,...,n+1 respectively; if π ₁ (i)=π ₂ (i), then let p _i =0; if π ₂ (j)=π ₃ (j ), then let q _j =0;

B4: Perform random permutation on matrix A ₁ ′, and perform random permutation on matrix A ₁ ′ according to key M and N to obtain A ₁ ″: A ₁ ″=MA ₁ ′N;

B5: The local client sends the encryption matrix A ₁ ″ to the cloud server;

C: The cloud server calculates the encryption matrix A ₁ ″:

Step C includes the following specific steps:

C1: The cloud server executes the LU decomposition algorithm to decompose the encryption matrix A ₁ ″ into a lower triangular matrix L and an upper triangular matrix U;

C2: The cloud server returns the calculation results L and U to the local client;

D: The local client receives the calculation results L and U returned by the cloud server and performs verification and decryption on the returned calculation results L and U in turn:

D1: The local client verifies the calculation results L and U: the verification module of the local client judges whether the value a″ _i,i on the main diagonal of the i-th row in the encryption matrix A ₁ ″ is consistent with the i-th value of the lower triangular matrix L The sum of the product of the first i elements of the row and the first i elements of the i column of the upper triangular matrix U equal; if Then execute step D2, where l _i,j is the element corresponding to row i and column j of the lower triangular matrix L, u _i,j is the element corresponding to row i and column j of the upper triangular matrix U, otherwise the local client refuses to receive The calculation results L and U returned by the cloud server, and then return to step C1 to re-decompose the encryption matrix A ₁ ";

D2: The local client uses the decryption module to decrypt the returned calculation results L and U, and restores the value of the determinant of the input matrix A:

which is,

Claims (1)

1. the safely outsourced calculating encryption method of matrix determinant in a kind of cloud computing, which is characterized in that include following step successively Suddenly：

A：Local client reads data input by user and composition matrix A：Wherein, square Battle array A is n rank square formations, and n is positive integer；

B：Local client pre-processes matrix A, generates scrambled matrix A "₁：

B1 generates one group of random key k, α, β, P, Q, M, N and { π by cipher key module₁,π₂,π₃, wherein k be arbitrary non-zero with Machine number, α are non-zero random vector, α=[α₁ α₂ … α_n]_1×n, β is null vector,P and Q is containing n+1 member The set of random numbers of element, P={ p₁,p₂,…,p_n+1, Q={ q₁,q₂,…,q_n+1, M and N are that two random units of n+1 ranks are set Matrix is changed, and often only there are one nonzero elements 1 for row and each column；{π₁,π₂,π₃Be n+1 members random permutation function, Wherein, x₁,x₂, x₃,…x_n+1∈ 1,2 ... n+1 } and x₁,x₂,x₃,…x_n+1In any two number it is unequal；y₁,y₂,y₃,…y_n+1∈{1, 2 ... n+1 } and y₁,y₂,y₃,…y_n+1In any two number it is unequal；z₁,z₂,z₃,…z_n+1∈ 1,2 ... n+1 } and z₁, z₂,z₃,…z_n+1In any two number it is unequal；

B2 constructs the new matrix A of n+1 ranks₁, place is encrypted to user's input matrix A according to the key k, α and β that are generated in step B1 Reason, obtains new matrix

B3, to matrix A₁Identical transformation is carried out, according to the random permutation function { π in step B1₁,π₂,π₃And set of random numbers P And Q, to matrix A₁Carry out such as down conversion obtain matrix A '₁： Wherein, i and j is respectively 1,2,3 ..., n+1；If π₁(i)=π₂(i), then p is enabled_i=0；If π₂(j)=π₃(j), then q is enabled_j=0；

B4, to matrix A '₁Carry out random permutation, according to key M and N to matrix A '₁It carries out random permutation and obtains A "₁：A″₁=MA '₁N；

B5, local client is by scrambled matrix A "₁It is sent to cloud server；

C：Cloud server is to scrambled matrix A "₁It is calculated：

Cloud server executes LU decomposition algorithms, by scrambled matrix A "₁Resolve into a lower triangular matrix L and upper three angular moment Battle array U, then result of calculation L and U are back to local client；

D：Local client receive cloud server return result of calculation L and U and to the result of calculation L and U of return successively Carry out verification and decryption processing：

D1, the verification of local client：The authentication module verification scrambled matrix A " of local client₁In on the i-th row leading diagonal Value a "_i,iThe sum of products phase of i element before whether being arranged with upper triangular matrix U i-th with i element before the i-th rows of lower triangular matrix L Deng；IfStep D2 is executed, the result that cloud server returns otherwise is rejected；

D2, local client are decrypted the result of calculation L and U of return using deciphering module, restore input matrix A Determinant value：