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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityI 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?
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.