IBM's homomorphic encryption library

IBM has released a new GPL-licensed encryption library called HElib which boasts the property of being fully homomorphic. This means that the encrypted message can be manipulated (subject to certain constraints), and the transformations applied to it will propagate correctly to the plaintext message. For example, given a number n and its encrypted "ciphertext" E(n), a homomorphic encryption scheme might allow you to multiply by a constant, and decrypting 42 * E(n) would give you 42 * n.

Exactly which operations preserve this property varies with the encryption scheme used. Schemes which are partially homomorphic preserve the homomorphic property only for addition or for multiplication, but not both. A fully homomorphic scheme preserves computation for both addition and multiplication, which is considerably more powerful. Such a system also preserves the useful algebraic properties of a ring:

• The associative property of addition: (a + b) + c = a + (b + c)
• The commutative property of addition: a + b = b + a
• The associative property of multiplication: (a * b) * c = a * (b * c)
• The distributive property: a * (b + c) = (a * b) + (a * c)

In short, with a fully homomorphic encryption scheme, you can perform a wide variety of computations on a file without decrypting it first. Consequently, untrusted programs can operate on encrypted data without risking the disclosure of its information. Remote servers could adjust financial documents without knowing their contents (for example, crediting an account, or computing sales tax on a purchase), voting machines could track totals without disclosing what the intermediate counts are, sensitive databases can be recklessly stored on public web sites, and so on (well, perhaps not that final example). There are several well-known cryptosystems which are partially homomorphic; for example, RSA encryption is homomorphic over multiplication only. But only recently have there been practical systems that are fully homomorphic.

The downside is that the few known fully homomorphic systems are considerably slower than are partially homomorphic schemes. The very first was described in 2009 by Craig Gentry. It used lattice-based cryptography, but it was not particularly practical, because the complexity of the operations needed scaled exponentially with the degree of attack-resistance desired. Just as importantly, the tendency is for ciphertext in a homomorphic encryption scheme to get longer (often drastically longer) every time additional operations are applied to it. Thus, the scheme was inefficient in space as well as in time. Gentry's original method also involved setting up an initial lattice that is "somewhat" homomorphic (meaning that it is very limited in the functions that it can be used to evaluate), then "bootstrapping" it by iteratively improving it. Subsequent advances allowed faster computation of Gentry's original method, eliminating bootstrap stages and replacing some of the lattice-based operations with integer math.

HElib implements Brakerski-Gentry-Vaikuntanathan (BGV) encryption, first published in 2011 by Zvika Brakerski, Gentry, and Vinod Vaikuntanathan. It too is a derivative of Gentry's work, building on several intermediate schemes devised during the years in between. HElib also incorporates a number of speed optimizations, including single instruction, multiple data (SIMD) operations to parallelize some encryption steps, and other methods for keeping the ciphertext as compact as possible (thus making it faster to process). For a bit of real-world comparison, one commenter on the Hacker News coverage of the release looked at the results described in one of the optimization papers and estimated that computing AES-128 rounds was about 10 billion times slower in the homomorphic system than when using the straightforward mathematical approach.

HElib is written in C++ using the NTL mathematical library. Currently, one does need to have a good understanding of homomorphic encryption to make much use of HElib—one does not simply pipe a text file to it and drag the result into a spreadsheet cell. So its importance is more about the impact that will be felt in the long term than it is about the prospect of drag-and-drop homomorphic encryption for the average user.

In the future, homomorphic storage might make sense in databases or in a number of different places where a form of "write only" access is desirable. An example is the voting-machine scenario mentioned above. The voting machine's tally for each candidate can be encrypted, so no intruder can read the result. But each voter's ballot can add an encrypted 1 to their selection and an encrypted 0 to each of the others. The voter could theoretically decrypt his or her ballot and verify its contents, but no one else can; the count in the machine is still incremented correctly, without ever needing to be in possession of the ballot in plaintext form. The same approach could be applied to secure event logging, message routing, or any number of other tasks.

Even if practical applications remain years away, it is a big win that HElib is being made available to the public under the GPL, rather than debuting in a proprietary tool. For decades, homomorphic encryption was not even known to be possible; now there is considerable work still remaining in order to develop a practical tool (as well as scrutiny by other cryptographers to analyze the scheme for overlooked weaknesses)—but there is also working code where before there was not.