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?

It's extremely unlikely that this chip supports fully homomorphic encryption. It's far more likely that they're using some extremely limited form and the marketing department blew it up. — CodesInChaos, Sep 14 '12 at 12:56
My guess is that they use some kind of obfuscation, where data doesn't appear in its natural form, but isn't strongly encrypted either. Somewhat similar to whitebox crypto, where the key never appears explicitly, but can still be extracted by a sophisticated attacker. — CodesInChaos, Sep 15 '12 at 09:20
Homomorphic encryption is not the only technique available for performing computation on encrypted data. Multi-party computation protocols is another technique which is quite practical in [real life](http://eprint.iacr.org/2008/068). — mikeazo, Sep 17 '12 at 15:00

score 9 · Answer 1 · answered Sep 14 '12 at 21:14

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.

score 6 · Answer 2 · edited Apr 13 '17 at 12:48

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:

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

score 3 · Answer 3 · edited Apr 24 '22 at 11:02

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:

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.

@Mok-KongShen Do you have any clear statements about what this IntegrityGuard chip actually does? From that marketing text, it could as well be a simple obfuscated chip. You can't use it as an example of working homomorphic encryption, unless you can show that it actually uses homomorphic encryption. — CodesInChaos, Sep 14 '12 at 18:39
No, I don't know what's actually going on there. It is claimed that computations are done on encrpyted data instead of in plaintext form and that's considered a distinguishing feature of the chip in comparison to others of its genre. — Mok-Kong Shen, Sep 14 '12 at 20:21

score 1 · Answer 4 · answered Sep 15 '12 at 21:00

1

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.

answered Sep 15 '12 at 21:00

David Wachtfogel

5,512
21
35

One reads however from http://www.infineon.com/cms/en/product/promopages/CCS/integrityGuard/index.html the fairly definite assertion "fully encrypted data path leaving no plaintext on the chip - incl. calculation with encrypted numbers in the CPU itself". – Mok-Kong Shen Sep 16 '12 at 08:45
[addendum] Being surprised in hearing the lecture I mentioned earlier, I asked the lecturer how the chip could manage to compute with encrypted data and obtained from him an answer in a similar sense. As said, I have written an email and hope soon to be able to get a definite clarification. [OT] While not relevant to our theme being discussed, a very recent paper by M. Bond et al. entitled "Chip and Skim: cloning EMV cards with the pre-play attack" may be of some interest: http://www.cl.cam.ac.uk/~rja14/Papers/unattack.pdf – Mok-Kong Shen Sep 16 '12 at 09:03
1

"In the CPU itself" most likely refers to the CPU registers and not the ALU itself. – David Wachtfogel Sep 16 '12 at 09:13
You may be interested in what I just posted. (I wrote this comment so that you would be alerted via your inbox, since the thread is almost 2 months old now.) – Mok-Kong Shen Nov 08 '12 at 20:33

score -1 · Answer 5 · answered Nov 08 '12 at 18:46

-1

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?

answered Nov 08 '12 at 18:46

Mok-Kong Shen

1,199
1
10
14

That has *nothing* to do with homomorphic encryption. Encrypting data on-chip does *not* mean that it is encrypted with a fully homomorphic encryption algorithm, and does *not* mean that fully homomorphic encryption is practical. They are probably encrypting using standard non-homomorphic cryptosystems (e.g., AES) or partially homomorphic cryptosystems (which are well-known). – D.W. Nov 08 '12 at 23:00
@D.W.: Could one achieve purposes of arithmetic operations through processing AES-encrypted data without having to decrypt them in the processors? – Mok-Kong Shen Nov 11 '12 at 16:41
@D.W.: I highly doubt the answer to the question in my previous comment could be positive. Thus there remains only the other probability you suggested. But that is unlikely, since I had asked the development team in their lecture in Deutsches Museum whether they could perform all 4 arithmetic operations on encrypted data and the answer they gave was "yes". BTW, after receiving the cited email, I wrote Mr. Janke again on 8th October, asking about the homomorphic encryption issue and requesting also patent informations, but till now without reply (on 8th November another email was sent to him). – Mok-Kong Shen Nov 13 '12 at 13:52
It seems unlikely that my said email would get a reply, 4 weeks being elapsed by now. (BTW, the Infinion team was one of the 4 finalists competing for the "Deutscher Zukunftspreis 2012", see http://www.deutscher-zukunftspreis.de/aktuelles.) – Mok-Kong Shen Dec 07 '12 at 15:27

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

5 Answers5

Linked