When an encryption scheme is said to be homomorphic, what that means is that if you perform some mathematical operation on the ciphertext, you affect the plaintext in a useful way once it's decrypted.

While this sounds neat, there are three major problems with current homomorphic encryption designs:

1. Performance: Homomorphic encryption is unbearably slow.
2. Distinguishability: There is an underlying algebraic structure to ciphertexts encrypted with homomorphic schemes, unlike non-homomorphic encryption schemes, which produce ciphertext that look like random noise.
3. Integrity: Homomorphic encryption is not impervious to chosen-ciphertext attacks.

While research into solving the performance and distinguishability problems of homomorphic encryption schemes is ongoing, there has been very little attention given towards preventing chosen-ciphertext attacks.

If you're interested in homomorphic encryption because you want to be able to search encrypted database fields in a web application you're developing, see the linked article instead.

Chosen-Ciphertext Attacks Against Databases Employing Homomorphic Encryption

Let's assume you have an application that encrypts sensitive information before sending it to a third-party service provider, using homomorphic encryption. We're going to treat this feature as a black box, rather than a specific implementation.

The app possesses the only private key capable of decrypting messages, but because it's using a homomorphic scheme, the database software used by the service provider can modify the ciphertext by performing calculations on its contents before sending it back. There may be any number of systems that can perform mathematical operations on the ciphertext, but this is abstracted away from the app through a simple API gateway.

What's to stop an attacker who has successfully compromised the service provider from...

• Replaying an older valid ciphertext message, thus hiding updates from the app?
• Performing their own calculations on the message before sending it back, thus feeding the app invalid data?
• If present, exploiting higher-level protocols with targeted modifications?
  • e.g. instead of multiplying, using XOR to create an erroneous ciphertext and triggering fallback code that reissues the request can be used to create an error oracle side-channel attack that may enable an attacker to steal plaintext contents without the private key

Generally, these sort of attacks are outright written out of the threat model of such systems, which is concerning since homomorphic encryption schemes usually come up in discussions about preventing data breaches caused by SQL injection. The typical real world use-case for a homomorphic cryptosystem places chosen-ciphertext attacks directly in the capability of attackers. We can do better than that.

Of course, that begs the question: Is it possible to have ciphertext integrity in a system intended for ciphertext modification? My hope is that the answer to this question is clearly, "Yes."

Securing Homomorphic Encryption with Append-Only Cryptographic Ledgers

Previously, we assumed that the ciphertext for each message was shipped from the app to the service provider, modifications were made, and then it was shipped back and decrypted.

We're going to make an addendum to this protocol in order to make it resistant to active attacks, using only tools that are already available to developers in 2017.

1. When the app sends ciphertext to the server, it also publishes a digital signature of the ciphertext that can be publicly verified.
2. Every time an amendment is made to this ciphertext by the service provider (or their backend computers), the following information is pushed into a ledger (which may or may not be a blockchain, but must be cryptographically secure):
   1. The operation being performed (e.g. "add 17").
   2. The timestamp of the operation.
   3. A hash of the resultant ciphertext.
   4. A digital signature of all of the above.
3. When the service provider returns the modified ciphertext, it also includes a list of ledger hashes for the modifications performed on the ciphertext since the last check-in.
4. The app can then verify each operation by querying the ledger for the modifications performed. A modification can be rejected if:
   • If the operation does not produce the expected ciphertext
   • The timestamp does not make sense (e.g. before previous changes)
   • The hash does not match this stage of the ciphertext
   • The digital signature is invalid, or
   • The digital signature is valid, but not associated with a trusted public key
5. The app may resubmit a signature for the most recent ciphertext, thereby resetting the list of unconfirmed changes to step 1.
   • This design assumes that the app stores the most recent ciphertext locally, so that the service provider can't perform multiple modifications from the same starting point.
   • If step 4 partly fails, the app may include a corrected ciphertext that possesses the outcome of all verified changes but no invalid changes.

This limits the attack surface significantly, by introducing automatic change auditing into the protocol. However, it still allows for ciphertext malleability to be useful without opening the door to practical chosen-ciphertext attacks.

Limitations of This Approach

My design does not guarantee availability. A powerful attacker may be able to perform denial-of-service attacks and replay attacks.

My design does not magically make the underlying ciphertext indistinguishable from random noise, but it does work with any homomorphic scheme by treating that step as a black box. If a better homomorphic encryption scheme is developed and deployed, you can use it with this design.

The use of digital signatures does not guarantee that none of the nodes authorized to perform ciphertext modifications are malicious. It can, however, make them accountable.

Committing data to a public blockchain (i.e. a cryptocurrency) is strongly discouraged. A Merkle tree for each app that cross-signs its Merkle root onto a public ledger is more appropriate. Chronicle is also an appropriate solution.