I want to pre-compute the result for all possible ciphertext of a homomorphic encryption. Is it acheivable?
Is there a fully homomorphic encryption scheme that has the same size of plaintext space and ciphertext space?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ I doubt that any exist. Else, how could we have semantic security? Also, the ciphertext space for modern public-key ciphers is so large you could never pre-compute results for all possible ciphertexts. Perhaps it would be better if you described the problem you are trying to solve and let us help you figure out a solution. Right now you are describing a possible solution to some unknown (to us) problem. $\endgroup$– mikeazoApr 23, 2014 at 12:50
-
$\begingroup$ @mikeazo How about this scheme $\endgroup$– Jan LeoApr 23, 2014 at 14:10
-
$\begingroup$ That one still does not have equal size plaintext/ciphertext spaces (I'm assuming you're referring to section 6). The plaintext space is binary polynomials of degree less than N. The ciphertext space is non-binary polynomials of degree less than N. If you think about it, you could not have a semantically secure public-key cipher where the plaintext and ciphertext spaces are the same size. Non-semantically secure public-key homomorphic ciphers are of little interest. $\endgroup$– mikeazoApr 23, 2014 at 14:17
-
$\begingroup$ @mikeazo sorry I just read this paper. At first glimpse of section 3, I found the size of the ciphertext is p. Can I get a small ciphertext space by reducing the size of the plaintext space? $\endgroup$– Jan LeoApr 23, 2014 at 14:49
-
$\begingroup$ The size of the ciphertext space is often a function of the security parameter. If you shrink the ciphertext space too small, the cryptosystem becomes insecure. $\endgroup$– mikeazoApr 23, 2014 at 14:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Is there a fully homomorphic encryption scheme that has the same size of plaintext space and ciphertext space?
As far as I know, none have this property and it makes sense when you think about it.
IF the plaintext and ciphertext spaces are the same size, you cannot achieve semantic security. A good example of this is RSA. In order to achieve semantic security in RSA, we shrink the plaintext space so that we can add random padding.
Semantic security is very important, especially when we are talking public key encryption. W/O it, an attacker can simply use the public key to encrypt guesses of ciphertexts and then compare with the ciphertext of interest to figure out the plaintext. FHE applications would be especially vulnerable to these sorts of attacks as we are likely not encrypting random values, but are encrypting values with some meaning (salaries, votes, etc) so that we can compute on these values.
I want to pre-compute the result for all possible ciphertext of a homomorphic encryption. Is it achievable?
I am not exactly sure what you mean here, but I doubt it is achievable. The ciphertext spaces in modern public-key systems are huge ($2^{2048}$ for 2048 bit RSA for example). Precomputing all of that would take more storage space than you can even dream about having. For a comparison, the estimated number of atoms in the observable universe is $10^{82}\approx 2^{272}$. So even if you could store one pre-computation per atom, it would take more atoms than what we can even observe in the universe to store your table.
Now, for this example I used RSA. FHE ciphers today have larger ciphertext space than even RSA.
-
$\begingroup$ Sorry, I am still confused about this scheme. It always performs (mod p) in the Encryption. Doesn't it mean that the size of the ciphertext is p? $\endgroup$– Jan LeoApr 23, 2014 at 17:08
-
$\begingroup$ @JianLiu, you are right. I am not super familiar with the SV system. Ciphertexts are an integer modulo p. Plaintexts are either a single bit or (if you follow section 6) a binary polynomial of degree $N-1$. So to know how the plaintext and ciphertext spaces compare you need to know how $p$ and $N$ compare. To get an idea of how these compare, look at the table in Section 7. They have (for one instance) $N=2^8$ (since $n=8$ and $N=2^n$) while $p\approx 2^{4096}$ (a 4096 bit prime). $\endgroup$– mikeazoApr 23, 2014 at 17:44
-
$\begingroup$ @JianLiu so even in the SV scheme, the plaintext space and the ciphertext space have very different sizes. $\endgroup$– mikeazoApr 23, 2014 at 17:47
-
$\begingroup$ Can I modify a FHE scheme into symmetric so that it needn't to be semantically secure. That's to say, I want to construct a Fully Homomrophic Encryption (or Hash) scheme, which is deterministic, symmetric and with the same size of plaintext space and ciphertext space. Is that achievable? $\endgroup$– Jan LeoJul 25, 2014 at 20:59