Babbitt column | How is full homomorphic encryption solved?

After reading a paper, if you understand it, many people think that the case is a piece of cake, but when I wrote this case, I found that the paper understood, and more cases or implementations were needed to further deepen or consolidate. Because only through the specific implementation steps, some of the details in the paper can be found, which in turn can promote the understanding of the paper.

The integer homomorphic encryption scheme has two very classic papers, one is "Fully Homomorphic Encryption over the Integers" hereinafter referred to as the DGHV program, and the other is Gentry's "Computing Arbitrary Functions of Encrypted Data" referred to as CAFED paper. The beginner is suitable to read the CAFED paper first. This is not to say that the paper is simple, just because the article is written in a very popular way. (In a strict sense, this article is not a real paper, it is an article written for the magazine, a little science. Nature), there is a good metaphor example "Glovebox" throughout the paper, Gentry's writing is very well written, and some background explanations have been made, and these explanations are exactly what the DGHV paper did not say. Of course, it is not so easy to completely read CAFED papers at the beginning. At this time, you can start reading the DGHV paper. This paper is not a big deal for me, because in some places, even reading a hundred articles is not necessarily understandable, and this article is very suitable for deep digging, some interesting places, such as the setting of noise parameters.

Another paper is the fully homomorphic classic "Fully homomorphic encryption using ideal lattices". If you are not familiar with the grid, you can read the first third of this article because of the detailed definition of homomorphism, hierarchy. Full homomorphism, permissive circuits, enhanced decryption circuits, bootstrable, re-encryption principles, and how to achieve full homomorphism through recursion, especially the process of recursive full homomorphism, is worthy of repeated understanding in the paper. The rest of the course is Gentry's doctoral thesis, which can also be read in stages.

1. Fully homomorphic encryption scheme

• Ding Wei Li Dawei: The old tree sprouts, can 30 years of cryptography experience bring live water to the blockchain?
• Chasing up and killing! Google Trends data shows that investors always want to buy after rising
• Babbitt's exclusive approach to the low-key legend, see how the real Gavin Wood "nothing"

As for the formal definition of what is a full homomorphism, I will not say it, please refer to the paper.

The full homomorphic encryption is in one sentence: it can perform arbitrary function operations on the encrypted data, and the result of the operation is decrypted corresponding to the result of doing the same operation on the plaintext. The meaning of a little crossing, from the ciphertext space to the plaintext space, but when crossing, it is to be blindfolded. In addition, the above sentence can not be said to be reversed. For example, the result of the operation is encrypted corresponding to the encryption result of the same operation on the plaintext. This is wrong, because the encryption is not deterministic, and each encryption is introduced. Random numbers, the result of each encryption is different, the same plaintext corresponds to several ciphertexts. The decryption is ok.

The homomorphism has such a good nature, what kind of encryption scheme can meet the requirements? Look down:

Enc(m): m+2r+pq

Dec(c): (c mod p) mod 2=(c – pדc/p”) mod 2 = Lsb(c) XOR Lsb(“c/p”)

The above encryption scheme is obviously correct. The modulo p operation eliminates pq, the modulo 2 operation eliminates 2r, and finally the plaintext m is left. This formula looks very simple, but it is very eye-catching and needs to be seen.

The p in the formula is a positive odd number, q is a large positive integer (no requirement is odd, it is much larger than p), p and q are determined during the key generation phase, and p is considered to be the key. And r is a small integer (can be a negative number) randomly selected when encrypting. The plaintext m∈ {0,1} encrypts the "bit" and the resulting ciphertext is an integer.

The plaintext space of the above scheme is {0, 1}, and the ciphertext space is a set of integers.

In addition to encryption and decryption, a very important algorithm in the homomorphic encryption scheme is: Evaluate, which is used to perform operations f (c1, c2) for a given function f and ciphertext c1, c2, …, ct, etc. ,…,ct). Here is the corresponding integer addition, subtraction, multiplication of the ciphertext.

The above scheme can be regarded as a symmetric encryption scheme. Let's consider the public key encryption scheme. In fact, see pq as a public key is OK. Since q is public, if pq is treated as a public key, the private key p is immediately known (p=pq/q). How to do it? Looking at the above encryption algorithm, when encrypting plaintext 0, the ciphertext is 2r+pq, so we can make a set {x _i ;x _i =2r _i +pq _i }, and the public key pk is this set {x _i }, randomly select a subset S from {x _i } during encryption, and encrypt it as follows:

Enc(m): m+2r+sum(S); where sum(S) represents the summation of x _i in S.

Since sum(S) is the sum of some 0 encrypted ciphertexts, it does not affect the decryption, and the entire decryption process does not change.

This program is safe, which is what we call the DGHV solution. Its security relies on a difficult problem "approximate GCD problem." Just give you some x _i , you can't find p (because the integer homomorphism is hot, approximating GCD has become a point of research).

For the convenience of explanation, we still adopt the scheme of pq as the public key (although it is not safe, it does not affect the description process). So encryption and decryption are still in accordance with the formula at the beginning, now pq is the public key, p is the private key, and q is the public parameter. Repeat our encryption and decryption algorithm again:

Enc(m): m+2r+pq

Dec(c): (c mod p) mod 2=(c – pדc/p”) mod 2 = Lsb(c) XOR Lsb(“c/p”)

In addition, it is hereby agreed that a real modulus p is: a mod p = a – "a/p" *p, "a" represents the nearest integer, that is, there is a unique integer at (a-1/2, a+1/2 In the middle, so the range of a mod p becomes (-p/2, p/2) (this is in mind). This is different from the range of the modulo p we usually say, the usual modulo p range is [0] , p-1], that is because the modulus formula is rounded down: a mod p = a –floor(a/p)*p.

Lsb is the least significant bit, because it is a modulo 2 operation, so the result is the lowest bit of this binary number .

2, terrible noise

Since the public key pq is public, it can be obtained by subtracting the public key after knowing the ciphertext c:

C-pq= m+2r

The plaintext m cannot be identified due to the interference of r. We call m+2r noise. In addition, when decrypting, only when c mod p=m+2r <p/2, it can be decrypted correctly by performing modulo 2 operation:

(m+2r)mod 2= m.

If the noise is greater than p/2, c mod p is no longer equal to m+2r, and the decryption may not recover the plaintext correctly. So noise is the key to decryption. And the noise will grow in ciphertext calculations. Let's take a look at the momentum of growth:

Let c1 = m1 + 2r1 + pq1; c2 = m2 + 2r2 + pq2; where c1 is the encryption of ciphertext m1 and c2 is the encryption of ciphertext m2.

密文加 and multiplication:

C1+c2=(m1+m2)+2(r1+r2)+p(q1+q2)

C1*c2=( m1+2r1)(m2+2r2)+p(pq1q2+m1q2+m2q1+2r1q2+2r2q1)

(c1+c2) mod p= (m1+m2)+2(r1+r2)

C1*c2 ​​mod p=( m1+2r1)(m2+2r2)

It can be seen from the above that the noise of the sum of the ciphertexts is the sum of the noises of the respective ciphertexts; and the noise of the ciphertext product is the product of the noises. Therefore, the main source of noise is multiplication, and the noise is amplified very quickly in multiplication.

For example: let p=11, q=5, m1=0, m2=1, then randomly select r1=1 and r2= – 4 respectively, there are:

C1=Enc(m1)=m1+2r1+pq=0+2*(-1)+11*5=53; c1 mod p= -2, Dec(c1)=0.

C2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58; c2 mod p= 3, Dec(1)=1.

Since c1 mod p and c2 mod p are both in the range (-p/2, p/2), the decryption is correct. C1 and c2 are called fresh ciphertexts, which are ciphertexts generated directly from plaintext. In fresh ciphertext, the noise is within a reasonable range.

Let's take a look at c1*c2:

c*=c1*c2=53*58=3074; c* mod p=5, Dec(c*)=1≠m1*m2=0, decryption error, the cause of the error is the product of noise (c1 mod p)* (c2 mod p)= -6 is not in the range (-p/2, p/2).

It seems that the ciphertext operation will cause an increase in noise. When the noise is out of range, the decryption will fail, which means that the ciphertext operation cannot be infinite (that is, the circuit depth of the Evaluate function function is limited. We will see it later when we talk about the circuit). Here we only get a homomorphic scheme (Somewhat homomorphism scheme) where the noise range cannot exceed p/2, and it seems that it is not feasible to achieve full homomorphism with this scheme. What we need is a fully homomorphic scheme, that is, Evaluate can run arbitrary function functions instead of a certain type of function (this is called a homomorphic scheme). It is estimated that many heroes have come here to feel that there is no drama, so they find another way, so a breakthrough will pass by. So let's analyze the crux of the problem below.

3, Bootstappable : a blunt idea

Noise hinders our goal, so how to eliminate the noise of this enemy? An intuitive method is to decrypt the ciphertext. After the ciphertext is decrypted, the noise is gone. However, to decrypt the private key, it is unrealistic to obtain the private key to eliminate the noise. So what if you encrypt the key?

Let us first look at the Evaluate algorithm. In the Evaluate algorithm, the operation of the function f of the ciphertext can be performed, where f is any function belonging to the set of permitted functions (for a brief explanation here, the set of permitted functions is also called a permitted circuit, for example, there are two function functions f1 and f2, Run Evaluate(pk, f1, c1, c2,…,cn) and Evaluate(pk, f1, c1,c2,…,cn) to perform f1 and f2 operations on ciphertext respectively. If the result of f1 operation is decrypted It happens that f1 is the result of the corresponding plaintext operation (the homomorphism is true), then f1 belongs to the permitted functions. If the result of the f2 operation is not equal to the result of f2 for the corresponding plaintext operation, then f2 is not a permitted function. Imagine that if the Dec decryption algorithm is also in the set of permitted functions, the Evaluate algorithm can perform the Dec decryption function. If we input s* (which is the ciphertext obtained by encrypting the private key s with pk2), and for the ciphertext c* (which is the ciphertext re-encrypted with pk2 to c, the original ciphertext c is encrypted with pk1. ), then execute

Evaluate(pk2, Dec, s*,c*);

The result is a new ciphertext. The ciphertext is a ciphertext encrypted in plain text under pk2. Is it a bit like magic, just like a person wearing a suit, now you don’t see this person changing clothes? The magician just applied a magic, this person immediately changed to a sportswear, the person is still the original person, but the packaging has changed. This is one of the most important features of Gentry's thinking: homomorphic decryption.

So what is the relationship between homomorphic decryption and noise reduction?

When the ciphertext operation, the noise will be quickly amplified. If we do a homomorphic decryption on the ciphertext after the operation, is it equivalent to getting a fresh ciphertext, and the noise of the fresh ciphertext is the smallest, so The purpose of noise reduction. (In fact, the ciphertext obtained after the homomorphic decryption is slightly louder than the fresh ciphertext.) This technique is called: re-encryption technology, which provides us with a way to reduce noise.

Next, you will definitely think: before each ciphertext operation, as long as the ciphertext is re-encrypted to reduce the noise, and then the ciphertext operation, then the noise is always within the controllable range, and the decryption of the operation result will not Failed. The arithmetic circuit can recursively repeat this process, and the purpose of infinite ciphertext operation can be achieved. However, reducing noise is not the ultimate goal. The noise is reduced in order to be able to perform the next operation. Therefore, the decryption circuit is added with a gate circuit (this gate circuit can be a basic circuit such as an adder gate circuit or a multiplication gate circuit). ". Figure:

Enhanced circuit

Since re-encryption requires a public key to encrypt the private key and ciphertext before each execution, a public key sequence {pk1, pk2,…, pki} is required to perform multiple re-encryption, and there is also a corresponding public key sequence. Encrypted private key chain {sk1*, sk2*, …, sk(i-1)*} (where ski* is the ciphertext obtained by encrypting ski with pk(i+1)). How is this process carried out?

Each layer of the arithmetic circuit corresponds to a pair of public and private keys. The first layer corresponds to pk1 and sk1, and the second layer corresponds to pk2 and sk2. For example, the initial public key is pk1, and the corresponding private key is sk1. When the first layer of the circuit is re-encrypted, the public key pk2 of the second layer circuit is used to encrypt sk1 to obtain sk1* (the public key is for all layers) Publicly), and encrypting the ciphertext with pk2; then inputting the decryption circuit, the decryption circuit will output a ciphertext after running, and the ciphertext is the result of encrypting the plaintext with pk2. Similarly, when the second layer of the circuit is re-encrypted, the layer key sk2 is encrypted with pk3 to obtain sk2*, and the output ciphertext from the first layer circuit is encrypted; then the decryption circuit is input, and the decryption circuit outputs A ciphertext that is the result of encrypting plaintext with pk3. Go on like this.

In this case, the number of public and private keys is linearly dependent on the depth of the circuit. If the encrypted private key information is leaked and does not affect the security of the key itself, this is called circular security. If the fully homomorphic encryption scheme is circular security, then there is no need for so many public and private keys. All circuit layers share a public key and an encrypted private key. The advantage is that we do not need to determine the circuit depth of the function of the function before the operation in order to determine the number of keys, which is much more convenient. It is still difficult to prove that the previous scheme is circular security, but it can be considered that it will not bring an attack.

If the decryption circuit is in the set of permitted functions executed by Evaluate, the encryption scheme is said to be Bootstrappable. From the above solution, we can see that there is no special way around the bend, that is, when the problem is solved, the problem can not be solved, and the conditions for creation must be solved. By creating the condition of the homomorphic execution of the decryption circuit, the noise is reduced to achieve an infinite number of ciphertext operations.

Well, it seems that the whole homomorphism has been realized here (there is a feeling that communism is realized immediately). However, there is still a question: Can the Evaluate circuit be able to run the decryption circuit? In other words: Is the decryption circuit in the set of permitted functions that Evaluate executes? Some people may say: One algorithm calls another algorithm, what can't be done? This is to talk about the complexity of the circuit.

4, circuit complexity

In the previous scheme, we saw that it is encrypted by "bit" (ie m∈ {0,1}). After encryption, it is an integer. The ciphertext is very bloated. So why is the plaintext not encrypted by integer? ? For example, take the plain text m∈Z. I think the reason is this: Everyone who studies the whole homomorphism has thought about it, but did not find a solution to encrypt the plaintext by integer. It's not that there is no such plan, it is estimated that it has not been found yet.

Some people will ask: Why should the full homomorphic scheme be described by circuits?

First of all, what do we call a program that is fully homomorphic? If a scheme can perform arbitrary functions on ciphertext, and the ciphertext obtained from the operation is compact, and the Evaluate algorithm (ie, operation) is effective, then we call the scheme completely homomorphic. Can be described as follows:

The above formula is too important. I feel that as long as the above formula is kept in mind, the concept of full homomorphism is in my heart. “Compact” is not mentioned here, there are explanations in the paper, and it is also well understood. Correctness is of course a must. So how do you measure the effectiveness of Evaluate? The most intuitive method can be measured by complexity. Obviously the complexity of Evaluate depends on the function f being operated. So how is the complexity of f measured? Of course, the most straightforward method is to measure the time of f on the Turing machine. But what is the function f? I think it should be a variety of function functions. If you want to describe it with functions, it may be difficult to say a word, but if you measure the size of the boolean circuit (the number of gates), then f can be dismantled. Into some simple Boolean circuits: for example, "and" circuits, "or" circuits, "non" circuits. These circuits can be combined into any circuit, that is, a circuit that can represent any function.

Similarly, we can also choose to use the AND circuit and the XOR circuit, because the two circuits are fully functional, that is, the combination of the two circuits can also express the circuit of any function (and use these two circuits to describe more Intuitive, their direct arithmetic operations are multiplication and addition). Obviously the AND circuit and the XOR circuit belong to the set of permitted functions (why? Because the AND circuit corresponds to the multiplication of two binary bits, and the XOR corresponds to the addition of two binary bits. The above homomorphism scheme can certainly perform this correctly. Two operations, because it is a multiplication or an addition, since they can be executed correctly, they belong to the set of permitted functions). Since the AND circuit and the XOR circuit are complete, any function can be combined with the two circuits, that is, the homomorphic scheme can perform arbitrary functions on the ciphertext, which is not the legendary all-in-one. State definition! The problem with any feature is solved, but one thing is missing: it must be correct. After you have sneaked into the ciphertext, what do you feel if the result is not the same as the result of the plaintext?

So can the above homomorphic scheme guarantee the correctness of the calculation? As we have seen above, due to the existence of noise, the program can only do a limited number of operations, which means that only the function functions in the set of permitted functions are guaranteed to be correct. Otherwise, you can't guarantee it. Now you know the permitted functions. What's in the collection? How can we guarantee that the operation of doing arbitrary functions on ciphertext is correct? As mentioned earlier, you can reduce the noise through heavy encryption technology! How to do it? Very simple: connect a decryption circuit to the AND circuit, and connect a decryption circuit to the XOR circuit. Before entering the AND circuit or XOR circuit, let any ciphertext enter the decryption circuit for re-encryption, and then come out from the decryption circuit. The ciphertext is a ciphertext similar to the fresh ciphertext. The noise is reduced before entering, and then the new ciphertext is entered into the AND circuit or the XOR circuit, so that we can correctly calculate the ciphertext for any function. Now! The AND circuit or the XOR circuit that is connected to the decryption circuit is called an enhancement circuit.

To sum up: any function function is used, first expressed by the enhanced AND circuit and the enhanced XOR circuit, so that the ciphertext can be calculated for any function. Because it is enhanced, we are no longer afraid of noise. Can be infinitely calculated. OK, the blue image of the full homomorphism is finally realized on paper.

But there is still a problem (there are so many problems, no wonder people say that science is caused by problems, now I understand), is the decryption circuit in the set of permitted functions? Some people may say that there is no decryption circuit in the scheme, Evaluate should be able to run it. In addition, some people say that it is not enough to represent the decryption circuit as an enhancement circuit according to the above method. Don't forget, the enhanced circuit contains the decryption circuit, so this is equivalent to the cause. The AND circuit, XOR circuit, and decryption circuit can all be regarded as "original circuits" (the name is taken by myself), that is, they are the cornerstones of any function function, and it is enough to contain them in the set of permitted functions.

We have explained the reason why the AND circuit and the XOR circuit belong to the set of permitted functions. The only thing missing is that the decryption circuit is not confirmed in the set of permitted functions. Let's analyze and analyze the decryption circuit.

5, the depth of the decryption circuit

One of the above said that it is half right. In fact, we can express the decryption circuit with the AND circuit and the XOR circuit to calculate the depth of the circuit (the depth of the circuit is the logarithm of the number of operations, for example, the depth is d, and the number of calculations is log d) Then, compare it with the maximum depth allowed by the functional circuits in the permitted functions, and know if the decryption circuit belongs to the set of permitted functions.

First, analyze the circuit depth allowed by the set of permitted functions. Since any function f in the set of permitted functions can be represented by an AND circuit and an XOR circuit, the AND circuit and the XOR circuit can be regarded as multiplying and adding the input binary bits, so the depth of the f circuit can be used as an input bit. The symmetry polynomial is measured (measured by polynomial because the polynomial happens to be the multiplication and addition of arguments), and since multiplication is the main source of noise, the number of multiplications in polynomial can be used as the main measure of circuit depth . Have:

c* = f ( c1, c2, …, cn ) = f ( m1+2r1+pq, m2+2r2+pq, …, mn+2rn+pq )

= f ( m1+2r1, m2+2r2, …, mn+2rn ) +p(…)

The noise of ciphertext c* is: c* mod p = f ( m1+2r1, m2+2r2, …, mn+2rn ). To correctly decrypt c*, there must be: f ( m1+2r1, m2+2r2, … , mn+2rn )< p/2, where mi+2ri is the noise of ciphertext ci. Let m+2ri = xi, and xi < B, B is the upper bound of the cipher ci noise, then:

f ( x1, x2, …, xn ) < p/2.

Our goal is to measure the number of operations d of f, so we can use the elementary symmetric polynomial to express f, with:

f ( x1, x2, …, xn ) = x1x2…xd + x1x3…xd + ……; where d<=n

Each of f ( x1, x2, …, xn ) selects d arguments from n arguments ( x1, x2, …, xn ), so there are C(n, d) terms (C means combination Operation), obtained by C(n, d) < n ^d :

f ( x1, x2, …, xn ) < B ^d n ^d < p/2 => d < log p / log Bn , that is, the maximum number of operations of f is log p / log Bn .

Let's take a look at the number of operations of the decryption circuit:

Dec(c): (c mod p) mod 2=(c – p·“c/p”) mod 2 = Lsb(c) XOR Lsb(“c/p”)

Carefully look at the formula of the decryption circuit and find that the main source of its complexity is c/p, so we mainly look at the number of operations required for c/p. c/p=c·p ^-1 , p ^-1 is a decimal. To ensure the accuracy of c· p ^-1 after rounding, p ^-1 takes the log c bit. For example, the results of 12345678 × 0.111111 and 12345678 × 0.11111111 are different after rounding. So how is the number of times the two numbers are multiplied? Have the following conclusions:

Multiplying two t-bits is equivalent to adding t: the output bit is a 2nd degree polynomial about the input bit

Adding "t" can apply "3-for-2 trick": 3 numbers are added to get two numbers added, and the output bit is a polynomial with a maximum of 2 times on the input bit.

Where a1b1+a1c1+b1c1 is a carry, note that it is also a symmetric polynomial.

Then t number of applications of this technique after log _{3 / 2} t additions to get two numbers, the number of output bits is 2 ^{log 3 / 2 t} = t ^{log 3/2 2} = t ^1.71 .

Look at the two t-digit additions:

Therefore, the number of output bits is up to t times, because the number of additions of the above 3 digits is up to 3 times.

The combination is: multiply two t-digits up to 2t ^1.71 t=2t ^2.71 , while c·p ^-1 has the number of c in log c, p ^-1 takes log c, and because of log c > log p (because p<c), so the number of c· p ^-1 is at least 2 (log p) ^2.71 , and the number of operations up to f is log p / log Bn, so the depth of the decryption circuit is greater than Evaluate The depth of the functional circuit is allowed to run, so if Evaluate runs the decryption circuit, it will produce incorrect results. We say that Evaluate cannot run the decryption circuit, in other words, the decryption circuit is not in the set of permitted functions.

The conclusion should be known, it is a bad news. The decryption circuit is not in the set of permitted functions. The consequence is that you cannot perform arbitrary functions on the ciphertext! Lost with the full homomorphism.

How to do it? The ancients said: The soldiers will block, and the water will cover the earth. The decryption circuit is deep, and it is not finished by lightening it. It is a bit difficult to say that it is easy to do. I think the trick is to compress and decrypt the circuit.

6, compression and decryption circuit

How to lighten the circuit? An intuitive way is to take some work for others, so the original task size will be smaller.

Or first take a closer look at where the problem lies:

c× p ^-1

This is a product. How do you want to turn it into a shallower arithmetic circuit? The most intuitive way is to turn the product into a sum, that is, put c·p ^-1 →∑zi. c is ciphertext, we can't take it, the only place that can be processed is p ^-1 , which means that p ^-1 should be converted into a form of sum: p ^-1 →∑yi, know that p is The private key can't be publicized, so you can hide p in ∑yi, and this kind of hiding will not be possible to leak p, so you have to have a trapdoor. This trapdoor is Sparse Subset Sum Prob (SSSP). Is to give a string of integers x1, x2, …, xn, there is a subset S of {1, …, n}, so that ∑si * xi = 0 (where i ∈ S), let you ask this S is not OK. This problem is said to be difficult, as if it has not been well studied. With this trapdoor you can construct:

Take y1, y2,…, yn ∈[0, 2), there exists a sparse subset S, such that ∑si · yi ≈ 1/p mod 2 (i∈S) (because it is a real number, it is approximately equal to 1/p , there is an error, this error does not affect the result of the rounding). Let zi←c· yi mod 2, zi retain a certain degree of precision, thus: ∑si · zi ≈ c/p mod 2. Therefore, "c/p" in the decryption circuit can be replaced with "∑si * zi". The decryption circuit becomes:

Lsb(c) XOR Lsb ("∑si·zi").

In this transformed scheme, the public key adds a vector {yi} in addition to the original public key pk. The ciphertext has a vector {zi} in addition to the original c. This extra zi can be seen as being calculated in advance to reduce the burden on the decryption circuit. This method is called post-process. The private key has changed from the original sk to {si}. It can be seen that the public key becomes larger and the ciphertext becomes larger. The price is to exchange for a shallower circuit. So is the circuit lighter? Let's analyze it below:

Mainly analyze the number of polynomials of ∑si·zi, and then compare it with the maximum number of times that we can analyze before f.

Suppose the accuracy of zi is n bits (we consider binary representations), the integer bits only consider the lowest bit, because Lsb ("∑si·zi") is the right and the first, and then the least significant bit. As follows:

If the above t numbers are added by "3-for-2 trick", the circuit depth will not meet the requirements. So you have to find another way.

There is a concept to say: HammingWeight, Hamming weight is the number of "1" in the vector. Since we are binary addition, the result of adding each column above can be regarded as the Hamming weight of the column . So how does Haiming's weight ask? There is a theorem that is very useful, namely:

For any binary vector <a1, a2, …, at> whose Hamming weight is W, and its binary representation is: wn, … w1w0, then wi can be expressed as arguments a1, a2, … One of the times of at is 2 ⁱ polynomial . This polynomial is very good, that is, the symmetric polynomial e ₂ ⁱ (a1, a2, …, at), there are ready-made algorithms.

Ok, we can apply this theorem to those columns above. For the lowest column, the Hamming weight, the lowest bit of the Hamming weight is e ₂ ⁰ (a1, -n, a2, -n …, at, -n) mod 2, which is the sum of the column, this Hamming The penultimate bit of the weight is e ₂ ¹ (a1, -n, a2, -n ……, at, -n) mod 2, and the carry-up to the penultimate column is denoted as Cn, -(n-1), Go on

Finally get:

Then there are:

b=“∑si * zi ”= (b0 + b-1 ) mod 2 (because it is rounded, so only care about the 0th column, rounding is to take the nearest integer, so it is related to b-1, if b- 1 is 1 and you have to go in)

Don't forget our current task: to calculate the number of polynomials of ai, j for the circuit of "∑si * zi". It can be seen as one at the beginning:

A1,0 · a1,-1 …… a1,-(n-1) a1,-n deg=1 · deg=1… deg=1 deg=1

A2,0 · a2,-1 …… a2,-(n-1) a2,-n deg=1 · deg=1… deg=1 deg=1

A3,0 · a3,-1 …… a3,-(n-1) a3,-n deg=1 · deg=1… deg=1 deg=1

…… …………

At,0 · at,-1 …… at,-(n-1) at,-n deg=1 · deg=1… deg=1 deg=1

Then the last column is calculated, and after the carry to the previous columns, it becomes the following form:

e ₂ ⁿ ( ) e ₂ ^n-1 ( ) e ₂ ¹ ( )

Deg=1 · deg=1…… deg=1 deg=1

Deg=1 · deg=1…… deg=1 deg=1

Deg=1 · deg=1…… deg=1 deg=1

……………………

Deg=1 · deg=1…… deg=1 deg=1

The number of times each column is about ai, j has changed, for example, the number of penultimate columns is 4, and then goes on:

Since the final result is (b0 + b-1 ) mod 2, we only care about the number of the first two columns (ie, column 0 and column 1). Since the result of each column calculation is e ₂ ⁰ (…), it is a symmetric polynomial with a number of times for the input term. For column 0, since the highest number of times is 2 ⁿ , the highest number of times e ₂ ⁰ (…) is 2 ⁿ . For the first column, since the highest number of times is 2 ^n-1 , the highest number of times the result e ₂ ⁰ (…) is 2 ^n-1 . Therefore, the circuit for calculating "∑si * zi " has a polynomial of 2 ⁿ for ai, j (don't forget that n is the precision of zi). Recall that the highest number of polynomials we can calculate for f is: log p / log Bn (note that ⁿ in 2 ^{n and n} in this equation are not an n). How to compare it, we must determine the parameters, according to the parameters in the DGHV scheme, λ is the safety parameter, take ||p|| ～λ ² , ||r||～λ, so p~2 ^λ2 , B~2 ^λ , then log p / log Bn ~ λ. In order for Evaluate to run the "∑si * zi" circuit, the accuracy of zi should be λλ. Now you know why zi precision in DGHV papers is to take that number.

So far we know that the decryption circuit is compressed and can be correctly calculated by Evaluate, so that the decryption circuit enters the set of permitted functions, so the program can perform arbitrary functions on the ciphertext, knowing what it means. The full homomorphism is achieved. It’s not easy to make a positive result.

Next, we summarize the implementation steps, in fact, the above already.

7, the implementation steps

There are actually two basic things in the function f: the AND enhanced circuit and the XOR enhanced circuit are as follows:

Any function function such as f1 can be represented by the combination of the above two enhancement circuits, for example:

So the basic steps for each calculation are as follows:

1) Encrypt the input plaintext m Enc(m) to obtain ciphertext (c, z), c is ciphertext, z is a vector <z1, z2, …> also called extended ciphertext.

2) Re-encrypt the input ciphertext. The ciphertext entered is (c,z). It is re-encrypted each time before the ciphertext operation. Since the plaintext space is {0, 1}, the encryption must be encrypted in bits by ciphertext. The process of re-encryption is the process of decryption, but the object is performed on the encrypted ciphertext and the encrypted private key. So there is: c'=Enc(Lsb(c)), and the resulting c' is an integer. Originally, each bit of z was also encrypted, but there is a way to improve efficiency, that is, not encrypting z, and thinking that each of z is its own encryption. In addition, the private key is s=<s1, s2, …> is a vector of 0 and 1, and the encryption of each bit of the private key is recorded as sk'=<Enc(s1), Enc(s2), …>= <s1', s2', …>, the resulting si' is also an integer. Then run ∑si·zi, the algorithm that runs it, as described above, writes the binary representation of each zi as a row of the matrix, thus getting a matrix:

A1,0 · a1,-1 …… a1,-(n-1) a1,-n

A2,0 · a2,-1 …… a2,-(n-1) a2,-n

A3,0 · a3,-1 …… a3,-(n-1) a3,-n

…… …………

At,0 · at,-1 …… at,-(n-1) at,-n

Then multiply each bit of the ith row of the above matrix with si' to get an integer matrix (each element in the matrix is ​​an integer):

Then the Hamming code is obtained for the last column (the lowest bit). According to the theorem described above, the lowest bit of the Hamming code is e ₂ ⁰ (b1, -n, b2, -n ……, bt, -n), and the rest e ₂ ¹ (b1, -(n-1), b2, -(n-1) …, bt, -(n-1)), …, all enter as the carry to the corresponding bit. Calculated in turn, the result of column 1 is b-1 = e ₂ ⁰ (b1, -1, b2, -1 …, bt, -1, …), and the result in column 0 is b0 = e ₂ ⁰ (b1,0, b2,0 ……,bt,0,…)

3) Calculate b = (b0 + b-1), where b is the result of the corresponding Lsb ("∑si* zi") ciphertext operation.

4) According to c'=Enc(Lsb(c)) which has been obtained above, the final re-encryption result of ciphertext c is:

c* = c'+ b

Do you know what this c* and c have to do with it? c* is the "rebirth" of c, and the noise is lower than the original.

5) Then enter c* into the gate. The gates are generally binary, requiring two inputs, and the other input is calculated in the same way.

6) Perform gate operations, such as adding or multiplying, and outputting the results. There are two cases: The first one: This result is the final result, then after re-encrypting once, the ciphertext is returned to the user, and the user decrypts to get the correct operation result. Second: This result is not the final result, then continue to input to the next level of circuit, still need to first re-encrypt.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!