2
$\begingroup$

If my key size is as large as the data I'm encoding, is it trivial to devise a theoretically secure homomorphic encryption scheme for integers (or else any finite/infinite group with order) that supports $+$ as an operation on encrypted data? Plus points if your scheme is computationally inexpensive or easy to understand.

Formally, $e(k,a+b)$ can be computed quickly from $e(k,a)$ and $e(k,b)$ where $k$ is the key. Theoretically secure means it should be impossible to determine any $a_i$, given a large number of samples $e(k,a_i)$ unless $k$ is known. Also $e(k,a)$ shouldn't be constructible for known $a$ unless you know $k$

I tried coming up with an example, which I couldn't but it does appear quite doable.

A use case for this could be say secure online voting, wherein the vote count is a small data value but it would be good if the votes can be added in by servers who themselves don't have access to the vote count.

$\endgroup$
  • $\begingroup$ @fgrieu Sorry I meant group, not field. $\endgroup$ – ghosts_in_the_code Mar 6 at 7:03
  • $\begingroup$ @fgrieu I can remove the voting bit if it's causing confusion, it's not the focus of the post. $\endgroup$ – ghosts_in_the_code Mar 6 at 7:07
  • $\begingroup$ @fgrieu Okay, I completely see your point on comparison operations, I've edited the post accordingly. $\endgroup$ – ghosts_in_the_code Mar 6 at 7:11
  • $\begingroup$ Your notation suggests that encryption $e$ is deterministic, as would be $e(k,a)=k\oplus a$ in OTP. Problem is, deterministic encryption, and that $e$, is not theoretically secure. Plus, with deterministic encryption and $e(k,a+b)$ being computable from $e(k,a)$ and $e(k,b)$ without knowledge of $k$, knowledge of $a$ and $e(k,a)$ allows to get the ciphertext for all multiples of $a$, and decipher these. Since theoretically secure encryption of infinite sets is impossible, get the ciphertext for 1 and you can decipher everything. $\endgroup$ – fgrieu Mar 6 at 8:06
  • $\begingroup$ @fgrieu Not sure I follow, but if the set of possible inputs is finite (for all practical purposes it anyway is), then is it possible? $\endgroup$ – ghosts_in_the_code Mar 6 at 8:36
4
$\begingroup$

For encryption by a determinisitic function as suggested by the question's notation $e(k,a)$, "perfect security" as asked is not possible, because the homomorphic property allows to decipher many ciphertexts. In particular, if we know the encryption of $1$, we can use it to find the encryption of $2=1+1$, thus decipher the unique ciphertext for $2$, and that extends to every positive integer. Notice that One Time Pad encryption is not a deterministic function either (encrypting the same plaintext multiple times usually yields different results).


Here is a trivial scheme that is homomorphic and information-theoretically secure, in the sense that a ciphertext leaks nothing about the value it conveys, even to an arbitrarily powerful adversary.

  • Plaintext consists of $b$-bit bitstring, assimilated to integers in range $[-2^{b-1},2^{b-1})$ per two's complement. Everything is big-endian.
  • Key is a One Time Pad of $2^k\,b$ bits, enough for $2^k$ encryptions.
  • For encryption, it is consumed $b$ bits from the OTP/key, and these are added modulo $2^b$ with the plaintext. The ciphertext consists of that, followed with the encoding over $k$ bits of how many ciphertext(s) where produced previously.
  • Addition of two ciphertexts is the addition modulo $2^b$ of their first $b$ bits, followed by the concatenation of what remains.
  • Decryption takes the ciphertext, extracts the first $b$ bits as an integer, and from this repeatedly subtract modulo $2^b$ the $b$-bit integer at position $i\,b$ in the OTP/key, for each integer $i$ of $k$ bits parsed from the rest.

That matches all the question's explicit goals. Notice however that (as pointed by Ella Rose's comments)

  • Whether a ciphertext was generated by encryption (and then when in sequence) or homomorphically generated (and then how) is in clear in that ciphertext, and distinguishible from random, contrary to e.g. Paillier encryption where ciphertexts are computationally indistinguishable from random.
  • The homomorphic property creates a link between plaintexts when one is obtained homomorphically from another, and we correspondingly loose the information-theoretic property that leaking a plaintext leaks nothing about any other.

Extensions:

  • The limit of $2^k$ encryptions can be waived with a more complex encoding scheme for $i$, and of course an arbitrary-length key/OTP.
  • For some use cases, what follows the encrypted count can be compacted. For example, when adding vote counts, it makes sense to forbid adding the same encrypted count multiple times. That allows to use a bitmap of fixed size for what follows the encrypted count, and combine disjoint bitmaps with bitwise-OR. Regular bitmaps can be further compacted.
$\endgroup$
  • $\begingroup$ There is an issue with this scheme: The ciphertext output from $c_0 + c_1$ is not indistinguishable from random, at least for anyone who knows the plaintexts for $c_0, c_1$. E.g., given a public set of $c_0, c_1, c_2, \dots$, anyone can attempt to compute $c_x = c_i + c_j + c_k + \oplus$, but the plaintext value of $c_x$ can be determined by anyone who knows the set by looking at the indicator bits tagged onto the end of $c_x$. This appears to make it not usable for at least one thing symmetric H.E would be potentially useful for (making public-key encryption). $\endgroup$ – Ella Rose Mar 6 at 15:57
  • $\begingroup$ @Ella Rose: I understand that ciphertext $c_x$ is not indistinguishable from random, and leaks if it was generated by encryption (and then when) or homomorphically (and then the indices $i$ for the $c_i$ from which it was computed, and some of the order of that). I added a note about it (end of paragraph after the 5 bullet points). But I fail to get how "the plaintext value of $c_x$ can be determined" (other than by leak of a plaintext component), or how my (edited) "information-theoretically secure, in the sense that a ciphertext leaks nothing about the value it conveys" is violated. $\endgroup$ – fgrieu Mar 6 at 17:06
  • $\begingroup$ My comment used the assumption that the plaintext values of the ciphertexts are known ("at least for anyone who knows the plaintexts"). As I'm sure you already know, Information-theoretic security means an adversary can learn nothing more about the plaintext than they already know when given a ciphertext, not that an adversary can know nothing about the plaintext in general. It's not disallowed to consider a known-plaintext scenario (and I believe that the known-plaintext scenario is a requirement for symmetric homomorphic encryption based PKE, though I don't have/know of proof of that) $\endgroup$ – Ella Rose Mar 6 at 17:13
  • $\begingroup$ @Ella Rose. Agreed, and thats why I changed ciphertexts leak nothing about the values they convey to "a ciphertext leaks nothing about the value it conveys". And I added two bullet points (before Extensions) that hopefully address your useful comments. $\endgroup$ – fgrieu Mar 6 at 17:35
1
$\begingroup$

In principle, you could define the OTP over any group, where encryption of a group element $m$ is done by sampling a uniform group element $k$ and compute the ciphertext as $c = m + k$. Here $+$ is the group operation. However, your design implies that the key is used multiple times to encrypt different messages which is insecure.

An attack against this scheme could be, the attacker asks for encryption of the identity element, let's call it $0$ for simplicity. This results in the ciphertext being $k$, which can be used to decrypt other ciphertexts.

$\endgroup$
  • $\begingroup$ Proposing an example system that is insecure is not a proof that all systems are insecure. $\endgroup$ – fgrieu Mar 6 at 11:19
  • $\begingroup$ @fgrieu True and that's not the intent of the answer. However, the problem statement strongly suggests a construction as I did. If the scope of the question was broader as you showed in your answer then it's fine for me ;-) $\endgroup$ – Marc Ilunga Mar 6 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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