Hello everyone,

So far I have already seen several Fully Homomorphic Encryption (FHE) schemes where the plaintext is from the space Z_q, where q is a prime number, and the ciphertext is, of course, from a larger space, somewhat like Z_q^n where n is some parameter of the scheme. Two of such schemes I have already broken, and one of them is the FHE scheme described in that paper eprint.iacr.org/2015/468.

From the first look, the idea to keep the ciphertext space in some size limits (e.g., in some finite field with characteristic q) is very attractive. If it would be possible, then there is no need for bootstrapping, the size of the ciphertext is then bound, and computations in such a scheme would become very practical.

However, in this short note I will show how I broke this particular FHE scheme, and then later I will show that any FHE scheme whose plaintext is modulus prime q seems to be not a good design.

In this paper the plaintext v is a value from Z_q, where q is prime. The ciphertext C=Enc(v) is a vector of n+1 integers each from Z_q. The scheme defines a complicated method for addition and multiplication. While reading the paper, I started to think that it has a high nonlinearity, and it was not easy to understand how it works, and why, but then when we came to the formulae on page 7, just before Section 3.6, we then realize that dk’s are actually the secret values that are used for decryption, and they are secret, but always the same for the same key.

It is also known that if we collect many (say, k) ciphertexts Ci i=1..k, and try to use Gaussian elimination on the matrix M with n+1 columns and k rows, where M[i][j] = Ci[j], then we always get a matrix of rank l<n - this is also a property of that scheme, where l is another parameter, and it was mentioned about this in the paper as well.

So how we can do the attack is that we collect l ciphertexts C1…Cl, for known plaintexts v1…vl, then perform Gaussian elimination on [M|V]=>[M’|V’], and choose the secret dk[1..n+1] as follows: dk[i]=V’[i] for i=1..l, and dk[i]=0, for i=l+1..n+1. And it works.

I have discussed this attack with the author of the paper and he acknowledged that it works, after we have tried a small challenge. The challenge scenario was even tougher, as follows:

The author chose the scheme parameters n, l, q, generated the secret key, chose a secret plaintext value v from Z_q, and derived the corresponding ciphertext C=Enc(v). Then the author also did some steps for me (thank you!) and also computed C1=C^{q-1}, C2=C1^2, C3=C1^3…C_{l+1}=C1^{l+1}. So, I received from the author the following challenge:
q=10007, l=2, n=5.
C vector = 1944, 5434, 4001, 4543, 4169, 3632,
C1 vector = 8384, 7222, 8386, 3244, 4688, 3169,
C2 vector = 7613, 2064, 1930, 832, 4883, 3111,
C3 vector = 5114, 8006, 8411, 3139, 1120, 7148,

I.e., I was about to decrypt C=Enc(v) just from only one single ciphertext C, since C1..C3 are directly derived from C without secret values. According to the Fermat’s theorem, C1 must be Enc(1), and thus C2 and C3 as well. Therefore, I constructed the matrix [M|V] =
8384, 7222, 8386, 3244, 4688, 3169, | 1
7613, 2064, 1930, 832, 4883, 3111, | 1
5114, 8006, 8411, 3139, 1120, 7148, | 1

And after Gaussian elimination we get:
1 0 0 4616 9868 1205 | 847
0 1 0 6474 8662 3242 | 6621
0 0 1 7669 3441 8871 | 6025

And, therefore, we take dk[] as follows: dk[] ={847, 6621, 6025, 0, 0, 0}

Then we take the original ciphertext C, and multiply it by dk[] and thus derive the plaintext v as
v = 7931 – and it was correct…

Now, what I actually wanted to talk about in this post is a more general problem.

Assume we create a FHE scheme where the plaintext is from Z_q, where q is prime. Then, an adversary can derive an encryption of any plaintext value without even knowing the secret key, or even the encryption scheme. Let’s take any ciphertext C that is =Enc(v), for some unknown v. We can get an encryption of 1 by raising C to the power q-1, i.e., C1=C^{q-1}=Enc(1), simply because of the plaintext v^{q-1} must be congruent to 1 in modulo q. Thus, to derive an encryption of any plaintext value x we then need to add C1 to itself x times.

As I understand it, homomorphic encryption can be very useful if the key and data owner could export his own data in an encrypted form to some remote storage and computation cloud such that it is able to perform requested computation on the owner’s data, without having to decrypt the data. For a certain scenario, let us assume that we have a remote database with salaries (encrypted by an FHE scheme), and at some time later the payroll system/manager requests a salary record for… for me, for example. In this situation, I could change my own salary record to another desired encrypted value, applying the Fermat’s theorem as described above…

Therefore, in the scenario described above, it seems to me that any FHE scheme whose plaintext space is in modulo prime q cannot be really useful.

What do you think?

/Alexander