WO2021129470A1 - Polynomial-based system and method for fully homomorphic encryption of binary data - Google Patents

Abstract

A polynomial-based system and method for fully homomorphic encryption of binary data The system comprises a splitting and combining unit, an encryption and decryption unit, a number system conversion unit, a logic operation unit, and a control unit. The present invention enables encryption and decryption to be directly performed on a binary value, and supports execution of various operations and processing on a binary ciphertext. In the invention, binary data remains in the form of a ciphertext during transmission, storage and operation, and thus a user can keep a cipher key and provide encrypted data to a cloud application which can perform normal data processing and obtain a correct processing result, thereby greatly extending the scope of applications and application scenarios.

Description

Binary data encryption system and method based on polynomial complete homomorphism Technical field

The invention relates to a technology in the field of information security, in particular to a system and method for binary data encryption and decryption and ciphertext operation processing based on a polynomial fully homomorphic encryption technology based on coefficient mapping transformation.

Background technique

When users use cloud applications to process their own important data, it is easy to cause user data leakage due to factors such as hacker attacks or application administrators. The fundamental reason is that cloud applications can only perform data operations and processing on unencrypted plaintext data. In contrast, fully homomorphic encryption technology can completely protect data privacy without affecting data operations. At the bottom of the computer and communication system, whether it is storage or transmission, all data is expressed in binary form.

Summary of the invention

Aiming at the above-mentioned shortcomings in the prior art, the present invention proposes a binary data encryption system and method based on a polynomial complete homomorphism, which can directly encrypt and decrypt binary values, and supports various operations and processing of binary ciphertexts. The data is always kept in ciphertext state during transmission, storage and calculation, so that once the user keeps the key by himself, only the encrypted data is delivered to the cloud application, and the cloud application can still process the data normally and get the correct processing As a result, the scope of adaptation and application scenarios have been greatly expanded.

The present invention is realized through the following technical solutions:

The present invention relates to a binary data encryption system based on polynomial complete homomorphism, including: a split and merge unit, an encryption and decryption unit, a binary conversion unit, a logic operation unit and a control unit, wherein: the split and merge unit ① receives all plaintext or All ciphertexts are split into single-byte component plaintexts or component ciphertexts or ②Receive single-byte component plaintexts or component ciphertexts and merge them into corresponding all plaintexts or all ciphertexts; the binary/decimal ciphertext is received by the binary conversion unit And output the ten/binary ciphertext; the logic operation unit executes the logic operation on the input single or a pair of ciphertexts according to the instructions of the control unit. The control unit is combined with the split and merge unit, the encryption unit, the binary conversion unit and the logic operation unit. Transmit encryption parameters; the encryption and decryption unit performs fully homomorphic encryption/decryption according to the input single-byte plaintext/ciphertext and the encryption parameters from the control unit, and outputs single-byte ciphertext/plaintext.

The logical operation includes: AND operation (AND), OR operation (OR), exclusive OR operation (XOR), NOT operation (NOT) or a combination thereof.

The described system is further provided with a shift unit connected to the control unit, which realizes a left shift by n bits (<<n) or a right shift by n bits (>>n) by receiving a shift instruction from the control unit.

Description of the drawings

Figure 1 is a schematic diagram of a binary number encryption, ciphertext operation, and decryption process;

Figure 2 is a schematic diagram of the exclusive OR operation process;

Figure 3 is a schematic diagram of the AND operation flow;

Figure 4 is a schematic diagram of the OR operation process;

Figure 5 is a schematic diagram of a non-operation flow;

Figure 6 is a schematic diagram of a left shift operation flow;

Figure 7 is a schematic diagram of the right shift operation flow.

Detailed ways

This embodiment takes a binary number as an example. The binary plaintext is: ₂ P=([a _i ·f(x _i )]·y _i ), i∈I=[0,7], where: the operator [] is Rounding operation is to take the nearest integer, [a _i ·f(x _i )] ∈ Z; f() is the function key part, which is the same for each component; x _i is the self of function f() Variable and x _i ∈ R; a _i is a polynomial coefficient and a _i ∈ R; y _i is a polynomial key part and y _i ∈ Z, each component y _i takes a different value, where R is the real number domain and Z is the integer domain .

The ciphertext corresponding to the above binary plaintext is ₂ C=(A,X), A={a _i |i∈I=[0,7]}, X={x _i |i∈I=[0,7]} ; The key is K=(f,Y), Y={y _i |i∈I=[0,7]}, each component of the ciphertext expression represents a binary number, so: [a _i ·f(x _i )]·y _i mod2∈{0,1}, in order to save the space occupied by the ciphertext, the function argument is set to an integer, that is, x _i ∈Z.

As shown in Figure 1, this embodiment relates to a binary encryption method, and the specific steps are as follows:

1) Split the input plaintext P into byte sequences according to 8 bits and one byte: P = (P ₁ ,P ₂ ,...,P _n ), where P _i =(b _i0 ,b _i1 ,... _{., b i7), b ij} = {0,1}, i∈ [1, n], j∈ [0,7], i.e. P _i either byte consists of 8-bit binary variable b _ij;

于是第i个明文部分第j位二进制数的值b _ij＝a _ij·f(x _ij)·y _jmod2； 2) a sequence of bytes, byte by byte encrypted encryption function calls: byte _{P i = (b i0, b} i1, ..., b i7) as input, for each component b _ij, the function key Randomly generate integer x _ij and random integer m _{j in the} domain, and calculate the key coefficient

Therefore, the value of the j-th binary number of the i-th plaintext part is b _ij = a _ij · f(x _ij ) · y _j mod2;

3) Repeat Step 2) down through all the bytes in the byte sequence P _i, to give the component the ciphertext _{C i = (C i0, C} i1, ... C i7), where _{C i = (A i, X} i _{), a i = {a ij} | j = [0,7]}, X i = {x ij | j = [0,7]}; further iterate across all bytes of plaintext P, the ciphertext C = get all (C ₁ , C ₂ ,..., C _n ), the ciphertext C _i of each component is arranged in the same order as the plaintext P.

This embodiment relates to the above-mentioned encryption and decryption method, that is, according to the binary ciphertext C=(C ₁ , C ₂ ,..., C _n ), the ciphertext is split into a sequence of multiple components according to the order in the ciphertext, verbatim section call sequence for decryption function decrypts components: component of either byte ciphertext _{C i = (a i, X} i), a i = {a ij | j = [0,7]}, X i = { x _ij |j=[0,7]}, call the key K, and decrypt it bit by bit, that is, the j-th bit of the _{component ciphertext C i is b ij} =a _ij ·f(x _ij )·y _j mod2, repeat Decryption obtains the component plaintext P _i = (b _i0 , b _i1 ,..., b _i7 ), and then obtains all the combined plain text P = (P ₁ , P ₂ ,..., P _n ).

This embodiment relates to a homomorphic number conversion method, and the specific steps include:

i) The component ciphertext converted from decimal to binary, including:

i-0) Set a reasonable homomorphic comparison operation accuracy, for the ciphertext greater than or equal to 2, the comparison result greater than 0 can be correctly returned, for the ciphertext less than 0, the comparison result less than 0 is correctly returned, and for 0 and 1 it is returned. Incomparable results;

i-1) Take a ciphertext C with a value between 0 and 255, which is the decimal value range of one byte, as input;

i-2) Set the loop variable i=7, calculate the input ciphertext C minus the ciphertext C128 corresponding to 27=128, get the bad ciphertext C7, and compare whether C7 is greater than 0;

i-3) When C7>0, then the i+1th bit of the binary ciphertext is the ciphertext form of 1, and replace C with C7, the loop variable i decreases by 1, and when i>0, it returns to the i-th- 2) Step; otherwise, the ciphertext form where the i+1 bit of the binary ciphertext is 0, C remains unchanged, and the loop variable i decreases by 1. When i>0, return to step i-2);

i-4) The loop variable i=0, the current ciphertext C is assigned to the 0th bit of the binary ciphertext through conversion. The conversion method is: set y ₁ '=β ₁ ·f(x ₁ ')· y ₁ ,y ₂ '=β ₂ ·f(x ₂ ')·y ₁ , then the current ciphertext is:

This embodiment relates to a homomorphic logic calculation method, and the specific steps include:

①Single-byte binary ciphertext exclusive OR operation A XOR B=C, ciphertext C _A ＝(A _A ,X _A ), ciphertext C _B ＝(A _B ,X _B ), by bit by bit of A and B Perform a homomorphic addition operation, that is, calculate the sum of b _Aj = a _Aj · f(x _Aj ) · z _j , b _Bj = a _Bj · f(x _Bj ) · z _j , and get b _Cj = [a _Aj · f( x _Aj )+a _Bj ·f(x _Bj )]·z _j =[a _Cj ·f(x _Cj )]·z _j , where the addition operation is the same as the ciphertext in the real number form, and the coefficients a _Cj and The argument x _{Cj is} calculated based on the operation support function G; by traversing all the bits of CA and CB, that is, the operation index j changes from 0 to 7, and the final result ciphertext C _C = (b _C0 ,b _C1 ,... .,b _C7 ), the ciphertext that realizes the result of the exclusive OR operation.

Preferably, for any multi-byte case, it can be known from the nature of the XOR operation that as long as the operation is performed byte by byte, and the results are combined in the original order, the final result can be obtained.

②Single-byte binary ciphertext and operation A AND B, the specific steps include:

1) According to the binary ciphertexts A and B, first calculate C=A XOR B in binary;

2) Convert the binary ciphertext A, B, C to decimal and calculate D=(A+B-C)/2;

3) Convert the decimal ciphertext D to binary, and get the final result D=A AND B.

Preferably, for any multi-byte case, it can be known from the nature of the AND operation that the final result can be obtained by performing the operation byte by byte and then combining the results in the original order.

③Single-byte binary ciphertext or operation A OR B, the specific steps include:

1) According to the binary ciphertexts A and B, first calculate C=A XOR B in binary;

2) Convert the binary ciphertext A, B, C to decimal and calculate D=(A+B+C)/2;

3) Convert the decimal ciphertext D to binary to get the final result D=A OR B.

Preferably, for any multi-byte case, it can be known from the nature of the OR operation that the final result can be obtained by performing the operation byte by byte and then combining the results in the original order.

④Single-byte binary ciphertext non-operation NOT A, the specific steps include:

4.1) According to the binary single-byte ciphertext A, first use the binary method to encrypt 255 to obtain the unit ciphertext E, and the value of each ciphertext of the unit ciphertext E is 1;

4.2) Calculate F=A XOR E, that is, F=NOT A.

Preferably, for any multi-byte case, it can be known from the nature of non-operation that the final result can be obtained by performing the operation byte by byte and then combining the results in the original order.

This embodiment relates to a method for calculating homomorphic displacement of a single-byte binary ciphertext, and the specific steps include left shift and right shift:

①Left shift by n bits: Convert binary ciphertext A to decimal ciphertext B, calculate C=B·2 ⁿ , then convert decimal ciphertext C to binary ciphertext D, which is the result ciphertext of A left shift by n bits .

②Right shift n bits: Convert binary ciphertext A to decimal ciphertext B, calculate C=[B÷2 ⁿ ], that is, after homomorphic rounding operation, then convert decimal ciphertext C to binary ciphertext D, namely The ciphertext of the result of shifting A to the left by n bits.

When a protected java program is run on a server that cannot ensure security, the result of the operation is obtained. Users do not want the results of the program calculations to be illegally stolen by possible attackers by monitoring server memory, nor do they want this java program to be copied by the attacker and use reverse engineering to analyze the program logic and data processing flow. Install an encrypted virtual machine on the insecure device, and execute the encrypted java program to obtain the encrypted running result. In this scenario, since the compiled form of the java program is binary, and the input and output data are also binary, the above-mentioned binary ciphertext processing method and system are needed to process. In this embodiment, the above encryption/decryption and fully homomorphic operations are implemented in the hardware environment of a notebook computer, a CPU Intel i5-7200U octa-core 2.5GHz, and a memory of 8GB through golang version 1.12.5, and the obtained private key size: <1KB , The time taken to load the private key is: 1ms, the dictionary size is: 45MB, and the speaking time to load the dictionary is: 227ms.

In this embodiment, the size of the binary ciphertext obtained by encrypting an integer based on the above method: <1KB, the time taken to obtain the binary ciphertext from the encrypted data: <1ns; the time taken to decrypt the binary ciphertext to obtain the original data: <1ns.

On this basis, the time taken for decimal addition operation: 30ms, the time taken for binary conversion to decimal: 1280ms, the time taken for decimal conversion to binary: 715ms.

On this basis, the logic calculation method is carried out. The specific steps include the time spent by the XOR operation: 265ms, the size of the result ciphertext is unchanged; the time spent by the AND operation: 4812ms, the size of the result ciphertext is unchanged; the time spent by the OR operation: 4819ms, As a result, the size of the ciphertext remains unchanged.

The above-mentioned specific implementations can be locally adjusted in different ways by those skilled in the art without departing from the principle and purpose of the present invention. The protection scope of the present invention is subject to the claims and is not limited by the above-mentioned specific implementations. All implementation schemes within the scope are bound by the present invention.

Claims (7)

A binary data encryption system based on polynomial complete homomorphism, which is characterized in that it includes: a split and merge unit, an encryption and decryption unit, a binary conversion unit, a logic operation unit, and a control unit, wherein: the split and merge unit ① receives all plaintext Or all ciphertexts are divided into single-byte component plaintext or component ciphertext or ②Receive single-byte component plaintext or component ciphertext and merge into corresponding all plaintext or all ciphertext; the binary conversion unit receives the binary/decimal ciphertext The text and output ten/binary ciphertext; the logical operation unit performs logical operations on the input single or a pair of ciphertexts according to the control unit instructions, and the control unit is separately combined with the splitting and merging unit, the encryption unit, the binary conversion unit and the logical operation unit And transmit encryption parameters; the encryption and decryption unit performs fully homomorphic encryption/decryption according to the input single-byte plaintext/ciphertext and the encryption parameters from the control unit, and outputs single-byte ciphertext/plaintext. The binary data encryption system according to claim 1, characterized in that it is further provided with a shift unit connected to the control unit, and shifts to the left by n bits (<<n) or shifts to the right by receiving a shift instruction from the control unit n bits (>>n). An encryption method based on the system of claim 1 or 2, comprising the following steps: 1) Split the input plaintext P into byte sequences according to 8 bits and one byte: P = (P ₁ ,P ₂ ,...,P _n ), where P _i =(b _i0 ,b _i1 ,... _{., b i7), b ij} = {0,1}, i∈ [1, n], j∈ [0,7], i.e. P _i either byte consists of 8-bit binary variable b _ij; 2) a sequence of bytes, byte by byte encrypted encryption function calls: byte _{P i = (b i0, b} i1, ..., b i7) as input, for each component b _ij, the function key Randomly generate integer x _ij and random integer m _{j in the} domain, and calculate the key coefficient

Therefore, the value of the j-th binary number of the i-th plaintext part b _ij = a _ij · f(x _ij ) · y _j mod 2; 3) Repeat Step 2) down through all the bytes in the byte sequence P _i, to give the component the ciphertext _{C i = (C i0, C} i1, ... C i7), where _{C i = (A i, X} i _{), a i = {a ij} | j = [0,7]}, X i = {x ij | j = [0,7]}; further iterate across all bytes of plaintext P, the ciphertext C = get all (C ₁ , C ₂ ,..., C _n ), the ciphertext C _i of each component is arranged in the same order as the plaintext P. A decryption method based on the encryption method of claim 3, characterized in that, according to the binary ciphertext C=(C ₁ , C ₂ ,..., C _n ), the ciphertext is split into multiple For the sequence composed of components, the component sequence is decrypted by calling the decryption function byte by byte: for any byte component ciphertext C _i =(A _i ,X _i ), A _i ={a _ij |j=[0,7 _{]}, X i = {x} ij | j = [0,7]}, calling key K, decrypt bitwise, i.e., the component of the ciphertext C _i j bits _{b ij = a ij · f (} x ij )·Y _j mod 2, repeat decryption to obtain the component plaintext P _i = (b _i0 ,b _i1 ,...,b _i7 ), and then obtain all the combined plaintext P=(P ₁ ,P ₂ ,..., P _n ). A homomorphic number conversion method based on the method of claim 3 or 4, wherein the conversion of decimal number to binary component ciphertext specifically includes: 1) Take a ciphertext C with a value between 0 and 255, which is the decimal value range of one byte, as input; 2) Set the loop variable i=7, calculate the input ciphertext C minus the ciphertext C128 corresponding to 27=128, get the bad ciphertext C7, and compare whether C7 is greater than 0; 3) When C7>0, then the i+1 bit of the binary ciphertext is the ciphertext form of 1, and replace C with C7, the loop variable i is reduced by 1, and when i>0, go back to step 2; otherwise , The ciphertext form where the i+1 bit of the binary ciphertext is 0, C remains unchanged, and the loop variable i decreases by 1. When i>0, return to step 2; 4) The loop variable i=0, the current ciphertext C is assigned to the 0th bit of the binary ciphertext through conversion. The conversion method is: set y ₁ '=β ₁ ·f(x ₁ ')·y ₁ ,y ₂ '=β ₂ ·f(x ₂ ')·y ₁ , then the current ciphertext is: C=a ₁ ·f(x ₁ )·y ₁ '+a ₂ ·f(x ₂ )·y ₂ ' =a ₁ ·β ₁ ·f(x ₁ )·f(x ₁ ')·y ₁ +a ₂ ·β ₂ ·f(x ₂ )·f(x ₂ ')·y ₁ =a ₃ ·f(x ₃ )·y ₁ . A homomorphic logic calculation method based on the method of claim 3 or 4, characterized in that it comprises: single-byte binary ciphertext exclusive OR operation, single-byte binary ciphertext AND operation, single-byte binary ciphertext or Operation and single-byte binary ciphertext non-operation, where: ① single byte ciphertext binary exclusive OR operation A XOR B = C, the ciphertext _{C A = (A A, X} A), the ciphertext _{C B = (A B, X} B), by A and B bit by bit Perform a homomorphic addition operation, that is, calculate the sum of b _Aj = a _Aj · f(x _Aj ) · z _j , b _Bj = a _Bj · f(x _Bj ) · z _j , and get b _Cj = [a _Aj · f( x _Aj )+a _Bj ·f(x _Bj )]·z _j =[a _Cj ·f(x _Cj )]·z _j , where the addition operation is the same as the ciphertext in the real number form, and the coefficients a _Cj and The independent variable x _{Cj is} calculated based on the operation support function G; by traversing all the bits of CA and CB, that is, the operation index j changes from 0 to 7, and the final result ciphertext C _C = (b _C0 ,b _C1 ,... .,b _C7 ), the ciphertext that realizes the result of the XOR operation; ②Single-byte binary ciphertext and operation A AND B, according to binary ciphertext A and B, first calculate C=A XOR B in binary; then convert binary ciphertext A, B, C to decimal and calculate D= (A+BC)/2; Finally, the decimal ciphertext D is converted to binary, and the final result D=A AND B is obtained; ③Single-byte binary ciphertext or operation A OR B, according to binary ciphertext A and B, first calculate C=A XOR B in binary; then convert binary ciphertext A, B, C to decimal and calculate D= (A+B+C)/2; Finally, the decimal ciphertext D is converted to binary, and the final result D=A OR B is obtained; ④Single-byte binary ciphertext non-operation NOT A, according to the binary single-byte ciphertext A, first use the binary method to encrypt 255 to obtain the unit ciphertext E, and the value of each bit of the unit ciphertext E is 1; Then calculate F=A XOR E, that is, F=NOT A. A homomorphic logic calculation method based on the method of claim 3 or 4, characterized in that, for homomorphic shifting of single-byte binary ciphertext, the specific steps include shifting left and shifting right, wherein: ①Left shift by n bits: Convert binary ciphertext A to decimal ciphertext B, calculate C=B·2 ⁿ , then convert decimal ciphertext C to binary ciphertext D, which is the result ciphertext of A left shift by n bits ； ②Right shift n bits: Convert binary ciphertext A to decimal ciphertext B, calculate C=[B÷2 ⁿ ], that is, after homomorphic rounding operation, then convert decimal ciphertext C to binary ciphertext D, namely The ciphertext of the result of shifting A to the left by n bits.

Images