5
$\begingroup$

Homomorphic cryptography is a kind of cryptography that allows you to do special math operations on the ciphertext, and the maths performed are identical to the obvious ones. For example, one person can combine two cached numbers, and decode the result, the sum will be two numbers.

  • What is the purpose of Homomorphic encryption?
$\endgroup$

closed as too broad by Hilder Vítor Lima Pereira, otus, e-sushi Sep 23 '18 at 4:28

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

9
$\begingroup$

In addition to the other answers: A secure secret-key homomorphic encryption scheme can be used to create a public-key encryption scheme.

If we consider encryption to be control of read and write abilities on data, then it's easy to see how this is the case.

With normal secret-key encryption:

  • only the key holder(s) can create ciphertexts (write permissions)*
  • only the key holder(s) can decrypt ciphertexts (read permissions)

With normal public-key encryption:

  • anyone with the public key (which is anyone, as it is public) can create ciphertexts
  • only the private key holder can decrypt ciphertexts.

With homomorphic secret-key encryption:

  • the key holder can create ciphertexts
  • anyone can manipulate ciphertexts (another form of write permission)
  • only the key holder can decrypt ciphertexts

This overlaps with the above definition for public-key encryption. While someone without the secret key cannot create a ciphertext for a given plaintext directly, they can do so if they are given pre-existing ciphertexts with known plaintext by the key holder.

An example

Assume the existence of a secure, secret-key, partially homomorphic encryption algorithm that supports integer addition on ciphertexts.

For the sake of simplicity, we will also assume that noise levels and resultant corruption of plaintext are not an issue (this is a real issue that many homomorphic encryption schemes suffer from).

A private key is simply a secret key $d$ for the secret-key encryption algorithm.

  • The nature of which is unspecified in this example, it would depend on the concrete scheme being used whether $d$ is a scalar, vector, etc.

A public key $\mathbf{e}$ of is a vector of encryptions of $1$ of length $n$ created using the private key with the symmetric encryption algorithm.

The public key operation generates a vector $\mathbf{r}$ such that $$m = \sum_{i=0}^{n}r_i$$ (secret splitting of $m$ into $n$ shares) and computes $$c \leftarrow \mathbf{er}$$

The inner product of $\mathbf{e}$ and $\mathbf{r}$.

The private key operation applies the decryption procedure from the secret-key cryptosystem to $c$ to recover $$1 * r_0 + 1 * r_1 + 1 * r_2 + \dots + 1 * r_n$$

Which is of course simply equal to $$m = r_0 + r_1 + r_2 + \dots + r_n$$

There are other possible public-key operations, e.g. based on subset-sum problems and/or LWE.

* Only the user with the secret key can create meaningful ciphertexts; An arbitrary block of bits of correct size is a valid ciphertext, but picking such a block of bits arbitrarily is unlikely to yield a meaningful plaintext with overwhelming probability

$\endgroup$
  • 1
    $\begingroup$ I have trouble with "someone without the secret key cannot create a ciphertext for a given plaintext directly". That does not seem to hold for Paillier; in that cryptosystem, anyone (with the public key) can change any plaintext to a corresponding ciphertext, just like in standard public-key encryption. $\endgroup$ – fgrieu Sep 16 '18 at 6:08
  • 1
    $\begingroup$ @fgrieu I'm not sure I understand the trouble, but I think it stems from: The quotation is from the section on secret-key (symmetric) homomorphic encryption. Of course if you have the public key for an asymmetric cryptosystem you have write permissions (as noted in the section on public-key encryption). $\endgroup$ – Ella Rose Sep 16 '18 at 12:39
  • 1
    $\begingroup$ you guessed it, because of the previous "This overlaps with the above definition for public-key encryption", I missed that the next sentence was about homomorphic secret-key encryption. Makes perfect sense now. $\endgroup$ – fgrieu Sep 16 '18 at 14:28
6
$\begingroup$

Homomorphic encryption lets you encrypt data, do operations/calculations with it such that when you decrypt the result, it's as if the same operations were done on the plaintext instead of the cyphertext.

The use of this is that untrusted parties can do computation on sensitive data.

This lets you use the computing power of people you might not trust with your data, like using publically available cloud computing services on your personal financial data.

Another usage case if it ever gets more applicable is in video games.

Some type of games (specifically real-time strategy games) is programmed such that every player needs to know about every other player's data due to being a deterministic simulation. Homomorphic encryption would allow deterministic simulation without players being able to cheat and get info about what other players are doing.

$\endgroup$
  • 3
    $\begingroup$ The "use computing power of people you might not trust" thing is largely theoretical. Problem is, encryption and decryption of the data tends to be a more expensive than the calculation itself would be, and the computing power needed by the untrusted party a lot more expensive. $\endgroup$ – fgrieu Sep 15 '18 at 18:26
5
$\begingroup$

First, I just copy-paste the introduction of homomorphic encryption from Wikipedia here

Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext. The purpose of homomorphic encryption is to allow computation on encrypted data.

For its applications (which demonstrate its purpose), Gentry said the following for its strong version fully homomorphic encryption in his famous thesis:

Fully homomorphic encryption has numerous applications. For example, it enables private queries to a search engine – the user submits an encrypted query and the search engine computes a succinct encrypted answer without ever looking at the query in the clear. It also enables searching on encrypted data – a user stores encrypted files on a remote file server and can later have the server retrieve only files that (when decrypted) satisfy some boolean constraint, even though the server cannot decrypt the files on its own. More broadly, fully homomorphic encryption improves the efficiency of secure multiparty computation.

Finally, homomorphic encryption is only part of secure voting systems. See here: Homomorphic encryption used for e-voting?

$\endgroup$

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