There are many kinds of fully homomorphic encryption scheme by using boolean circuits. And the plaintext space $\mathcal{P} = \{ 0,1 \}$.

If there is a -bit FHE scheme, we can construct a FHE scheme which can encrypt all the messages. For a string $x \in \{ 0,1 \}^{*}$ and $x = x_{1} \Vert x_{2} \Vert \cdots \Vert x_{n}$, we can define $$\mathrm{Enc}_{pk} (x) = y = \mathrm{Enc}_{pk} (x_{1}) \Vert \mathrm{Enc}_{pk} (x_{2}) \Vert \cdots \Vert \mathrm{Enc}_{pk} (x_{n})$$ where $x_{i} \in \{ 0,1 \}$

However, if I want to define a FHE with $\mathcal{P} = \{ 0,1 \}^*$, there is a problem.

Naturally, $$\mathrm{Enc}_{pk}: \mathcal{P} \rightarrow \mathcal{C}$$ $$\mathrm{Dec}_{pk}: \mathcal{C} \rightarrow \mathcal{P} \text{ or } \bot$$ $$\mathrm{Eval}: \mathcal{B} \times \mathcal{C}^* \rightarrow \mathcal{C}$$ where $\mathcal{B}$ is the set of all the boolean circuits.

Given $C \in \mathcal{B}$ such that $C \colon \{ 0,1 \}^{n} \rightarrow \{ 0,1 \}^m$, if $c \leftarrow \mathrm{Eval} (C, c_{1}, c_{2}, \ldots, c_{l})$, we have $$|\mathrm{Dec}_{sk}\left( c_{1} \right)| + |\mathrm{Dec}_{sk}\left( c_{2} \right)| + \cdots + |\mathrm{Dec}_{sk}\left( c_{l} \right)| = n$$ and $$|\mathrm{Dec}_{sk}\left( c \right)| = m$$ But, how can we know the size of $|\mathrm{Dec}_{sk}\left( c_{i} \right)|$ when we ask the access to $\mathrm{Eval}(\cdot)$?

  • Most notions of security allows the adversary to learn the size of the plaintext if given a ciphertext. This includes semantic security and ind-cpa, ind-cca games – Florian Bourse Jun 15 at 9:42
  • @FlorianBourse Really? Do you know some bibliographies or papers about this? I didn't find it in my books and the papers I read. I just know that in the security games, it requires that the length of the test messages must be the same. – TeamBright Jun 16 at 7:01
  • this requirement is what I'm talking about. Even if the scheme is CPA secure, it doesn't mean that you can't distinguish encryptions of 2 messages of different length. And in practice, all schemes have this "weakness". If you look at the definitions of functional encryption (eprint.iacr.org/2010/543.pdf), you'll notice that they explicitely give a key that allows to check the length of the message. – Florian Bourse Jun 18 at 8:26
  • One of the first references on google is Introduction to Modern Cryptography, page 56: "The main reason for this is that it is impossible to support arbitrary-length messages while hiding all information about the plaintext length (cf. Exercise 3.2)". This is one of the very basics of cryptography and is probably in every introduction book. The argument here is information-theoretic: You would require keys of infinite length (e.g. a complete mapping from $\mathbb{Z}$ to $\mathbb{Z}$), otherwise something leaks. – tylo Jul 13 at 14:55
  • I know what you mean, and I also study the book. But I just think that the notions are not equivalence totally. Even if $\Pr [ Dec_{sk}(y) \rightarrow x, |x| \leq 2^{|y|}] = 1$ holds true, it cannot imply that there exists a PPT algorithm $F$ such that $F(y) = |x|$. – TeamBright Jul 16 at 12:25

I believe we have a more fundamental problem with we try to handle arbitrary length plaintexts.

Suppose that we have any encryption scheme $\mathbb{B}$ (not necessarily FHE, or even asymmetric) that tries to handle arbitrary length plaintexts. Suppose also we also had a $\mathbb{B}$ encrypted ciphertext, which we can see is 1000 bits long. We don't know the key, however, we can deduce that there are, at most $2^{1000}$ possible plaintexts that this might correspond to.

What does that deduction give us (given that we don't know the value of any of those $2^{1000}$ plaintexts? Well, it'd be a pretty good guess that the plaintext isn't more than 1 Gigabyte long, even if the decryption process could potentially have a plaintext which is longer than the ciphertext.

Because of this, there is a limit to the amount of length hiding we can do, if we try to handle unbounded plaintexts.

  • Yes, "there is a limit to the amount of length hiding we can do". But I want to focus something specific. What does the "limit" mean? For example, for every ciphertext $y$, there exists a PPT algorithm $A$ which tells the length of $\mathrm{Dec}_{sk}(y)$ correctly with a probability $p$. If $p=1$, perfect, we can define the evaluation algorithm. If $p=1−ε$, it may be OK. What if $p=1−1/poly$ or $1/poly$? The probability of the correctness of evaluation algorithm depends on $p$. Even if there is a "limit", I still don't know how to make $\mathrm{Eval}(⋅)$ well-defined. – TeamBright Jun 13 at 7:57

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.