What is the shortest ciphertext size output by FHE?

Assume we use batching and modulus switching techniques to reduce the size of ciphertext in fully homomorphic encryption (FHE).

Question: What is the shortest ciphertext bit-size output by the most efficient fully homomorphic encryption?

Remark: I'm aware that there're different FHE schemes. I'd like to see what is the shortest ciphertext we can get (even using the above techniques) from an efficient FHE that outputs the shortest ciphertext.

• The schemes aren't just different, they have different capabilities. Only capable of addition, or multiplication, or Turing complete, etc. It's it the latter that you are interested in? – Natanael Feb 18 '19 at 13:46
• @Natanael The question is in context to FHE. Only capable of addition would be a partially homomorphic encryption (PHE). – AleksanderRas Feb 18 '19 at 13:59
• @AleksanderRas thanks for your comments. I hope that answers your question "Natanael'. – Ay. Feb 18 '19 at 14:02
• This question is too broad. You are asking reviewing and comparing all FHE schemes. – kelalaka Feb 18 '19 at 17:03
• @kelalaka You might be right! However, there might be some FHE schemes well-known for their output compactness, etc. In other words, I'm not asking anyone to do the review for me, instead, I'm asking if anyone is aware of such a scheme based on his\her experience (or literature review). – Ay. Feb 18 '19 at 17:46

1 Answer

It depends on whether you want to encrypt a single bit, or many bits.

If you want to encrypt a single bit, I think (disclaimer: I might be missing other schemes) that the shortest ciphertexts are achieved by the TLWE-based FHE of this paper (see also this paper on which it is based). According to their claim, the ciphertext expansion is "only" 10000 bits (i.e., encrypting one bit requires 10000 bits). This is because they can simply work with LWE-like ciphertexts, and then transform them when needed into a GSW ciphertext (which supports fully homomorphic operations).

If, however, you want to encrypt multiple bits, then any FHE scheme can achieve optimal rate of $$1+o(1)$$ using a standard hybrid encryption: an encryption of an $$n$$ bit plaintext $$m_1, \cdots, m_n$$ is $$(\mathsf{FHE}(K), \mathsf{SymEnc}_K(m_1, \cdots m_n))$$, where $$\mathsf{SymEnc}_K$$ is a secret-key encryption scheme with secret key $$K$$. To evaluate a function homomorphically on this ciphertext, simply homomorphically apply first the following circuit $$C$$ to $$\mathsf{FHE}(K)$$: $$C$$ has $$E = \mathsf{SymEnc}_K(m_1, \cdots m_n)$$ hardcoded in its description, and on input $$K$$, it outputs $$\mathsf{SymDec}_K(E)$$. Hence, this steps gives you $$\mathsf{FHE}(C(K)) = \mathsf{FHE}(\mathsf{SymDec}_K(E)) = \mathsf{FHE}(m_1, \cdots m_n)$$, from which you can then evaluate any function of your choice. The ciphertext size is then $$n + O(\lambda)$$, where $$\lambda$$ is a security parameter, assuming $$\mathsf{SymEnc}_K$$ has rate $$1+o(1)$$ (which is the case with every modern symmetric encryption scheme, e.g. AES).