What's the State of the Art of Homomorphic Encryption?

Question

I get the impression from some internet resources I have skimmed that homomorphic encryption is yet computationally very inefficient. However, an Infineon press release from 2010 says that the CPUs of chip cards can do computations in encrypted form. Are there then no more practical hinderances to homomorphic encryptions today, since common CPUs are certainly more powerful than those on chip cards?

Answer 1

Not sure how to read between the lines on the press document, but I'm seeing here that it is by no means dead, and I'm seeing a lot of hot topics on it with respect to Cloud Security - which makes at least some level of sense on a macroscopic view, although the part of me that actually used to implement security solutions says "don't believe it till you see it".

My take on what I'm seeing in Google is that it is still very much in the world of university research - lots of math still to be done and lots of computational analysis. It'll be a while before we see companies invest big-time in anything hardware related or anything significant in software implementations - by which I mean a very solid, tested, certified peice of software usable for large scale computing (vs. something in a lab for verification purposes).

It sounds like value of the capability is high enough that funding for research is still available.

Addition based on commentary:

With more digging, I'm seeing things like:

• http://www.faqs.org/patents/app/20120039473
• http://people.csail.mit.edu/joanne/vahlis-slides.pptx
• http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5622064&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F5619950%2F5621989%2F05622064.pdf%3Farnumber%3D5622064

Which makes me stick with my initial assertion - with papers of this type being published in this time frame, the nature how exactly this mathematics can best be implemented is still undergoing some level of evolution. I'm willing to agree "there are no practical hindrances" in the sense of "we simply haven't found a way to do this with technology in a time efficient way" - but I would argue that at this phase of the game, I don't see anyone in the industry making making money selling such a solution - so even if we figured out how to do the math efficiently, I don't see it being used yet in implementation. I'm not saying it's not coming, but it isn't there yet, and there's probably still come implementation hurdles ahead - likely to be fixable with time and money, which will increase in availability as soon as industry works its way through some driving use cases and proves the solutions can scale.

Answer 2

There are two types of homomorphic encryption.

Partially homomorphic encryption is about computing one type of operation over encrypted values. For instance, you know E(m₁) and E(m₂), and, without knowing the private key, you can compute E(m₁*m₂). Several efficient algorithms which allow for that are known, especially ElGamal (which allows you to multiply encrypted messages) and the Paillier cryptosystem (which allows you to add encrypted messages). Partially homomorphic encryption is useful for some protocols, e.g. electronic voting (the idea is that you can tally together encrypted votes, and decrypt the result at the end). Partially homomorphic encryption works well and has done so for at least a decade.

Fully homomorphic encryption is about computing two types of operations over encrypted values: from E(m₁) and E(m₂), you can compute E(m₁*m₂) and E(m₁+m₂). Fully homomorphic encryption allows for arbitrary computations; ultimately, you could provide encrypted inputs to a biiig computer, which will run the computation and provide the encrypted result, without needing to trust that big computer. The idea is that the state of a transistor in a virtual circuit can be encrypted, and the additions/multiplications are sufficient to emulate state changes based on inputs to the transistor. The big computer would have to run a virtual CPU, with a few homomorphic operations for each transistor in the virtual CPU and for each clock cycle. Needless to say, this looks expensive.

Unfortunately, the best known fully homomorphic encryption algorithms (derived from Gentry's work in 2009) are awfully slow and inefficient, making it not worth the effort (i.e. the whole Amazon S3 cloud could not compute homomorphically faster than what a single smartcard could do without the encryption). The research area is not dead, far from it; but it is very new and has not yet produced anything practical.

Answer 3

No. Fully homomorphic cryptography is not practical today -- not on a desktop computer, and not on a chip-card. See, e.g., the following question on our sister site, Crypto.SE: What is the most practical fully homomorphic cryptosystem?. (Excerpt: "none of them are practical ... yet".) The press release you are reading probably got distorted by the publication relations folks. Hey, it happens.

It is possible to do partially homomorphic cryptography in a reasonably efficient way, but that's a lot more restricted in its applications and does not have the power or usefulness of fully homomorphic cryptography.

For more information about this topic, see the following questions:

• In what ways does Full or Partial Homomorphic Encryption benefit the cloud?

• What Partial Homomorphic Encryption implementations exist and how do I leverage them?

• Is there difference between Algebraic Homomorphic Encryption and Fully Homomorphic Encryption Schemes?

Use the search bar on the upper-right of this site, and on Crypto.SE, to find more information about homomorphic cryptography.

Answer 4

I'm afraid this press release from Infineon is misleading. Infineon have published a Common Criteria Evaluation Security Target document for the SLE 78 chip (available for download here). From reading this document one can infer that though data is encrypted in memory, on the bus and in registers, it is in fact decrypted when used for computations (e.g. by the ALU).

Fully homomorphic encryption is definitely not computational feasible on a chip card at this time.

Answer 5

In his answer (and a comment) David Wachtfogel was of the opinion that a phrase involved in the press release of Infinion, namely "in the CPU itself", most likely refers to the CPU registers and not the ALU itself. If this is indeed the case, the seeming paradox could be explained. I like however to report that I have written an email to Mr. Janke, a team member of Infinion developing the chip, and obtained the following in his response:

Aus den Zertifizerungsreports bzw. den Security Targets können Sie entnehmen (Quelle: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Reporte06/0640b_pdf.pdf?__blob=publicationFile):

• "The TOE provides full on-chip encryption covering the complete core, busses, memories and cryptographic co-processors leaving no plaintext on the chip." [Der Begriff "core" beinhaltet auch die CPU inklusive der ALU, vgl. Abbildung auf Seite 16.]

• "No data in plain are handled anywhere on the TOE and thus also the two CPUs compute entirely masked and in addition dynamic mask changes are applied." [Hier wird deutlich, dass die CPU's mit verschlüsselten Daten arbeiten, wobei die Schlüssel sich dynamisch verhalten.]

These paragraphs evidently very firmly claimed the opposite. So what do experts consider to be the case in reality?