2
$\begingroup$

An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can reduce your uncertainty about the plaintext.

Fully homomorphic encryption is, roughly, an encryption scheme where $\text{Encr}(T(x)) = T(\text{Encr}(x))$ for arbitrary transformations of the ciphertext and plaintext (this is not entirely accurate but that's not important for this question).

Is it theoretically possible to have an information-theoretically secure FHE scheme? That is, is it possible to encrypt a plaintext $x$, have an external party do computations on them in a fully homomorphic way, without them being able to gain ANY information about the plaintext even with infinite? computing power?

Improve this question
$\endgroup$
6
  • $\begingroup$ The idea is to have an encryption scheme which preserves certain structure. In your example, the ciphertext exposes $E(T(x))$. To know whether this is meaningful we're going to need precise definitions. What does $E$ guarantee, what are the domain/range. $\endgroup$
    – Ariel
    Nov 13, 2018 at 13:15
  • $\begingroup$ @Ariel, I don't think we need this at all. Someone with knowledge of fully homomorphic encryption (not me) just has to know whether it is possible to have an information-theoretically secure FHE scheme, or at least, whether it is currently known to be possible or not. (btw, I haven't given any "example"). $\endgroup$
    – user600670
    Nov 13, 2018 at 18:54
  • $\begingroup$ What kind of encryption? Public-key encryption or symmetric-key encryption? $\endgroup$
    – D.W. ♦
    Nov 13, 2018 at 23:02
  • $\begingroup$ @D.W., you tell me? I'm just asking for one example of an information-theoretically secure FHE scheme, whether it is public or symmetric key. $\endgroup$
    – user600670
    Nov 14, 2018 at 12:14
  • $\begingroup$ The answer might depend on your specific definition of what properties you want it to have. For example: Do you want $T(\text{Enc}(x))$ to be indistinguishable from $\text{Enc}(T(x))$? Or is it OK if the adversary can learn which transformations $T$ were applied, as long as $x$ or $T(x)$ remain secret? $\endgroup$
    – D.W. ♦
    Nov 17, 2018 at 0:22

1 Answer 1

Reset to default
1
$\begingroup$

You said you don't need to conceal the set of transformations that have been applied. In that case a simple scheme is

$$T(\text{Enc}(x)) = \langle T, \text{Enc}(x)\rangle,$$

where $\text{Enc}$ is information-theoretically secure encryption (e.g., the one-time pad). In other words, you simply list in the cipher text which transformations should be applied to $x$ after it is decrypted.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't understand? why are you suggesting that the transformations should be applied AFTER $x$ is decrypted? The point of FHE is that the transformations are applied while it is still encrypted. It's not clear to me either why we can just use the one time pad, because this seems to break the homomorphic nature of the encryption? I'm not sure. $\endgroup$
    – user600670
    Nov 18, 2018 at 7:43
  • $\begingroup$ @user600670, this meets the definitions you have provided. If it isn't what you are looking for, then you will probably need to reflect on how to formalize your requirements more accurately. $\endgroup$
    – D.W. ♦
    Nov 18, 2018 at 19:52
  • $\begingroup$ What definitions? there is a standard definition of FHE and I haven't given it really (I've only informally hinted at it). The nature of FHE is such that a transformation is applied to encrypted data, so that party B can perform a computation on data without knowing what the data is. (I didn't make this up). $\endgroup$
    – user600670
    Nov 19, 2018 at 11:12
  • $\begingroup$ Perhaps I should have said that it appears to meet all of the requirements stated in the question (and in your comment). Again, if it isn't what you're looking for, I suggest you spend time thinking how to identify more precisely what your requirements are, then edit the question to articulate your requirements or criteria more clearly. $\endgroup$
    – D.W. ♦
    Nov 19, 2018 at 20:10
  • $\begingroup$ I'm quite baffled by your response. Let's say that $T$ is the transformation that "adds $5$ to $x$". My question was: can we let someone do this transformation on $Enc(x)$ without them knowing the value of $x$ (only knowing $Enc(x)$). That is, if $x=5$, then they should do the computation on $Enc(x)$, which results in the output $y$. It must hold that $Dec(y)=10$, but the one doing the computation must not be able to know this. Instead, you provided me with a scheme that requires the original party (who knows $x$) to do the computation himself. This has nothing to do with what I asked. $\endgroup$
    – user600670
    Nov 20, 2018 at 10:40

Your Answer

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

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