3
$\begingroup$

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}_{sk}: \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, \cdot)$?

$\endgroup$
5
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Jun 15, 2018 at 9:42
  • $\begingroup$ @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. $\endgroup$
    – Blanco
    Commented Jun 16, 2018 at 7:01
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jun 18, 2018 at 8:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – tylo
    Commented Jul 13, 2018 at 14:55
  • $\begingroup$ 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|$. $\endgroup$
    – Blanco
    Commented Jul 16, 2018 at 12:25

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Blanco
    Commented Jun 13, 2018 at 7:57
1
$\begingroup$

If you have the $k_{sk}$, this means that you already know the size of plaintext which is encrypted exactly in every point since you are the designer.

If the evaluator has a function to extract the size of the plaintext while it is encrypted then there is a problem; apply this

get the size, substruct 1, get size, substruct 1,...

When the size decreased the Evaluator get information from the ciphertext that you don't want.

$\endgroup$
1
  • $\begingroup$ @TeamBright $k_{sk}$, in your case. let me correct. $\endgroup$
    – kelalaka
    Commented Nov 12, 2018 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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