Intel to Build Silicon for Fully Homomorphic Encryption | Hacker News Reader

Intel to Build Silicon for Fully Homomorphic Encryption

anandtech.com

169 pointszdw83 comments

> The press release states that the target is to reduce processing time by five orders of magnitude

Not sure if that's 2^5 or 10^5. A 100,000x speed up just might make FHE into the realm of feasible for some applications (not the silly big-data, AI buzzword soup BS the article is pushing though). Pretty exciting.

I've always felt that crypto is magic,FHE especially so. Would be cool to see it remotely in the realm of practicality.

More than 2^5 has already been demonstrated with GPU implementations, so they definitely do mean 10^5.

10^5 speed up will get them to 10x slower than plaintext processing of deep neural networks. See page 15 of DARPA's BAA:

https://beta.sam.gov/api/prod/opps/v3/opportunities/resource...

For simple computing like logistic regression, they aim to be as fast as plaintext.

Based on the image used at the top of the article, it is almost certainly 10^5.

What would the implications of FHE be for the average consumer?

Even with a 100000x speed up, that probably puts it more in the territory of cool demo than actual production use, except for very specialized usecases (the overhead for current FHE methods is utterly insane).

In principle, the main use case is cloud based algorithm as a service. If google has some service it wants to sell to users but it doesn't want to reveal how it works and the users dont trust google with their private data they can use FHE. The user data is encrypted so google can't extract anything from it to do evil with. The proprietary software stays on google servers so nobody can steal the algorithm. Everyone wins (except of course the progress that would be made if the algorithm was open).

FHE is a really unique primitive, i expect when demos become practical people will come up with new interesting use cases.

There's also some applications to identity-based/attribute-based encryption and multi-party computation, although i doubt that's coming to average consumer any time soon

We already have AMD's Secure Encrypted Virtualization (SEV). If you trust AMD, you can have a secure VM running on that CPU that's totally opaque to the person who owns the CPU. So even if the KGB could own the CPU, and the USA's president could use a VM on it in full confidence the KGB wouldn't know what calculations he's using it for. What's more it runs existing software, at full speed.

Well, that's the theory anyway. In practice, researchers say modifying the encrypted memory, then running the program and seeing what happens next reveals something, enough to get them root in fact. [0] But even so, it's a deficiency that can be fixed, so if we aren't there yet we will be one day.

The difference between SEV and FHE is where with SEV you have to trust AMD, but with FHE you don't have to trust Intel. China could have designed and made this FHE chips, and you should be fine. But on the downside FHE is very, very slow (and this won't really close that gap), and expands the data hugely and of course doesn't run conventional software.

To me it looks like that sorts of applications people are discussing here, such as database servers, will be done by SEV because of the shear amount data and processing they have to deal with. The article talks about speeding things up, but the primary bottle neck for those applications is MIPS/Watt. Speeding up FHE by throwing a huge GPU at it doesn't sole the MIPS/Watt problem. However, there are applications that tend to involve primary secrets - things like handling passwords, PIN's, PIN Pads, perhaps even gab.com's OAuth2 bearer tokens that involve tiny amounts of highly sensitive data. Perhaps FHE could be useful in dealing with them.

[0] https://arxiv.org/pdf/1712.05090.pdf

What is an average consumer?

It lets you do operations on encrypted data. By volume are data centers the average consumer? It seems fairly clear what the benefit would be to them, they can process all kinds of sensitive data that would otherwise be off limits for various reasons.

Have you seen Intel's underground facility for national security issues. Why do people trust on-chip cryptography? https://cryptome.org/2013-info/11/intel-ug-lab/intel-ug-lab....

Homomorphic encryption (HE) is NOT what people would understand as "on-chip cryptography", i.e., secure enclaves. HE is a form of encryption that allows arithmetic operations on encrypted numbers without any access to the decryption key. Secure enclaves on the other hand do decrypt data on-chip and are thus vulnerable to side channel attacks.

You can use HE to implement things like encrypted database lookups that don't reveal what is being queried (even to the database server) and the security of the encrypted query does not depend on any hardware properties of the server providing the service.

While noting that "database lookup" is a painful scenario for HE because you have to read through the entire thing just to find a single row.

Wouldn't a normal db btree index work just fine? Scans certainly seem problematic though

A tree would require the ability to have control flow based on data, or using data as an index. You can't do that while keeping the data secret.

Just to select a single row you have to do something like sum(row_meets_criteria() * row). With row_meets_criteria returning 0 or 1.

for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.

The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.

But then you are not using FHE, but something with much weaker security properties.

If every query didn’t walk the entire dataset then the server could figure out what was queried based on what data was loaded and what data was not loaded.

Can't it already figure that out based on the query? E.g. I'm asking for the value at key `7`. So my query asks for the encrypted value for whatever `7` gets encrypted to. The db/algo already knows I'm asking for `qasfdj`, and that its returning `zsqwer`.

It doesn't matter whether it walks the dataset or not, it gets to know those two values. So may as well build an index on the keys?

Most FHE schemes introduce some randomness into the request that differs on every request so that the executor can’t make that sort of association. So if you want the value at key ‘7’ you instead send a request like (7, nonce) but encrypted in a way so that different nonces will make the encrypted bytes of the request look totally different.

If the FHE program then bundles the nonce back into the response you get a brand new request/response on every query, even if you’re just querying the same key over and over.

Couldn't ORAM help with that? https://en.m.wikipedia.org/wiki/Oblivious_RAM

Regardless, this is pretty far afield of FHE...

Maybe, but you’d have to bundle the ORAM translation layer inside of the encryption. Conditional logic inside of FHE is extremely expensive in computation time, so this might be infeasibly slow.

Does that matter if the indexes, the data, and the query are all encrypted?

Possibly? It could leak data in a lot of ways. For instance you might see that a particular IP is accessing particular rows.

Or you might see that certain rows are accessed together. For instance if rows represent users, you could look at the "shape" of accesses and try to match that to the shape of a social network you know from elsewhere. As an unrealistic reduced example: Maybe you know that Alice is friends with Bob and Charlie and Dennis. Bob is friends with Charlie. Now you see that W has 3 friends X, Y, Z, of which X and Z are friends with each other. Then W might be Alice, the X and Z might be Bob and Charlie (but we don't know which is which), and the Y Dennis.

    . ABCD
    A  xxx
    B x x
    C xx
    D x

    . XYZW
    X   xx
    Y    x
    Z x  x
    W xxxx

Fair. I suppose it really depends what the motivating use cases are for this kind of thing— in my head, the killer app would be a mail server where I decrypt (from GPG) my email in my local client, and then re-encrypt (with HE) and prepare indexing information which is sent to a cloud service for long-term archival. The cloud service allows me to search on and retrieve my email without ever seeing the contents or knowing any of the metadata other than when you uploaded them and the message lengths (and even that could be scrambled up a bunch by adding arbitrary padding and periodically re-uploading old messages). In this scenario there isn't really the "known from elsewhere" info— knowing that certain groups of messages are returned together in response to sets of queries is unlikely to be meaningful if you don't have anything else to map that info to.

And thinking about it further, the client could do other shenanigans to further protect the user, like arranging for every query to return 20% "false" results that are filtered out before display, or storing duplicate instances in the database so that the server thinks query X leads to result A and query Y leads to result B, without knowing the A and B are in fact the same thing.

> In this scenario there isn't really the "known from elsewhere" info— knowing that certain groups of messages are returned together in response to sets of queries is unlikely to be meaningful if you don't have anything else to map that info to.

If the service knows the upload date of the message (presumably same as send date), and does this for a lot of users to cross correlate, that's actually quite a bit to go on to figure out who you are talking to.

Either (a) the index is encrypted in such a way the db engine cannot make branches based on it, in which vase its useless. Or (b) the db-engine can take branches based on the index, in which case the index can't have been encrypted very good if the db engine can read it.

Remember, in fully homomorphic encryption, the algorithm is the party you are trying to hide data from.

The point would be that the index would serve to route "scrambled search term X" to "scrambled record Y", and the degree to which that scheme could protect the privacy of users would be a function of how much redundancy was inserted into the system at various points, all of which could be tunable on the client side (dummy record entries, dummy index entries, dummy queries, whatever).

Never been inside, but pretty sure JFS-1 is a datacenter, not an underground secret fab. The NSA does have their own wafer fab at ft. Mead, they have done many talks on it.

Anyone have a link to a good talk about this?

That looks like a data center.

Interesting, I was aware of IBM's work in this field and certainly an area they have been a bit more focused upon:

https://www.ibm.com/security/services/homomorphic-encryption https://www.ibm.com/blogs/research/2020/06/ibm-releases-full... https://www.ibm.com/blogs/research/2020/12/fhe-progress-mile...

So the whole aspect of IBM not being involved does seem (too me at least, curious.

I would imagine that IBM have their own private hardware for it, or at the very least wants to make it themselves. IBM still have their own chip designers and still make quite a large selection of rather custom kinds of chips and processors.

Very true, but they also do not own any chip Fab nowadays, having shifted that to Global Foundaries iirc. Which is one area that Intel still have in house. But given how much research IBM has done, I do wonder how many patents they hold in the FME feild.

Can someone better versed in this area give a decent sense of how this works and whether this is feasible? Also, as the article mentions, given an unencrypted dataset similar to the original, couldn’t you figure out important elements of the underlying data by brute force reverse engineering of the resulting algorithm?

The hitch is the explosive increase in the size of the data. From the article:

> Encryption methods to enable FHE can increase the size of the data by 100-1000x

Note that the DARPA program does nothing about this. DPRIVE is about making the computation go faster. The input+output dataset size explosion is a much harder problem; there's no real silver bullet anywhere on the horizon. This stuff is not viable for "big data" type computation, or anything involving a database.

Personally I'm skeptical that it will ever save customers any money. What it might do is allow a sale to go through in a situation where the vendor won't trust the customer with a copy of the algorithm they're selling, and the customer won't trust the vendor with a copy of the data. So instead of "nobody buys nothing", a sale is made and the telecoms make mad bank from all that bloaty FHE-ified data flying around.

Note that input+output size explosion is one of the major barriers to post-quantum encryption (PQCrypto) being competitive with RSA+ECC. This is understandable: FHE and PQCrypto use lattice-based cryptosystems.

FHE is pretty well established at this point. It can guarantee that someone observing the computation has no ability to tell what data they are acting on or what result they are outputting.

But, this is notably assuming that the program is not itself outputting leaky information. For example, if I use FHE to encrypt a program that takes my name and date of birth as input and then output "Taek is over the age of 21", the program itself has revealed data about me.

You can't reverse engineer the FHE itself. But if the encrypted program is outputting information that could be used in reverse engineering, FHE is not going to protect you. Similar to how Tor isn't going to protect you if you go and log into Facebook using your real account information.

The whole point of FHE is that the output (at the cloud server) is encrypted so that you can send it back to a client for decryption. Assuming an attacker isn’t in control of the client, there is nothing that would leak.

So, just as I can store an encrypted file in the Cloud and nobody can tell what it is, we can have a computation happen in the Cloud where nobody can determine what it is?

Exactly. And the magic is that now you can securely compute aggregations of data you've stored without having to download all of your data.

Say you have some field in all of your encrypted, cloud-stored records and want to find the sum of all of them. With traditional encryption you'd either have to trust the cloud with your decryption key or download all of the records for local processing, which could be very slow. With homomorphic encryption you can instead have a cloud service do that computation without any visibility to the actual values and only have to download a single ciphertext containing the result.

Yes. But not only the data, also the algorithm isn’t visible to the computer doing the computing...

You may be thinking of Indistinguishability Obfuscation. Current FHE algorithms (e.g. those undergoing standardization: https://homomorphicencryption.org/) don't provide IO. The compute provider knows the exact graph that is being computed, but, in the most secure scenario, they don't get to know the inputs and outputs of each node in the graph. The node operation (which can be only addition or multiplication) must be known to the compute provider so they can perform the correct mathematical transforms on the encrypted data.

Unfortunately you can't even make the FHE produce unencrypted output at all currently, doing so would give you you secure obfuscation -- but AFAIK all candidates for that seem to be badly broken.

If you need unencrypted output, you don't want FHE, you want functional encryption. But it's much younger and there's still a lot of research to be done in the field before prime time.

What output are you talking about? In FHE, you need the private key to decrypt any output. The "program" cannot output anything without access to some decryption oracle.

Working and secure crypto is based on the fact that you get different ciphers for the same massages. So if you run „21“ through you encryption you get „xy“ as your first cipher. If another user puts in „21“ and runs it through encryption the output should be now something like „ae“. That’s not the case with FTH you always get the same result. That’s bullshit. Because if data leaks you can reverse engineer the ciphers without having a private key. If your encrypted data can be decrypted without the private key. Your encryption ist just nonsense.

This is not how homomorphic encryptions works. The schemes in use are not deterministic.

I think the point is that the program is useless unless it outputs _something_. And when it does, it can leak. This isn't a mind blowing concept.

The inputs are encrypted, the processing is encrypted, the outputs are encrypted. Once the execution service has produced an encrypted result it is sent back to the requester, who decrypts the returned result with their decryption key, which has never left their control.

Interestingly they measure anticipated speedup compared to a CPU, not a GPU:

> Intel’s Data Platforms Group will come together to create a dedicated ASIC to reduce the computational overhead of FHE over existing CPU-based methods. The press release states that the target is to reduce processing time by five orders of magnitude from current methods, reducing compute times from days to minutes.

AFAIK, a modern GPU already provides up to 3 orders of magnitude speedup compared to a CPU [1].

[1] - https://ieeexplore.ieee.org/document/9185077

CPU is currently a rather natural baseline as the various GPU implementations are still somewhat preliminary. I'm not quite an expert on the implementation challenges around FHE (I work on compilers targeting FHE), but my understanding is that the access patterns of the core operation, the number theoretic transform (NTT, a DFT in a finite field), are not particularly GPU friendly. Dedicated hardware is expected to comparatively very well here.

Definitely agreed that CPU is a natural baseline. But there are promising results for implementing NTT on GPUs. Here is something recent https://eprint.iacr.org/2021/124

Nothing will beat an ASIC for NTT though.

Why would anyone trust Intel with encrypted data? They have basically proven they are working with the U.S. government who clearly doesn't care about your privacy.

Remote clients are the only ones with the encryption/decryption keys. The compute provider (Intel in this case) only has public keys. If the remote client is using trusted open source software, I wish the compute provider the best of luck in extracting any information from what they are processing.

This might be important. Practical FHE would be a big deal. But this is to TRY to make it practical, and that is not the same thing. I wish them luck.

I didn't fully understand the implications. Why is there so much focus on privacy protection? Isn't by far the biggest application of this technology in security? (Presumably, ensuring that no one steals money out of my bank account is much more important than hiding my porn preferences from the advertisers.)

AFAIK FHE offers little security benefits compared to more standard cryptography when it comes to securing bank accounts. It can hide things (which is the first application of cryptography, hence the crypto prefix − ancient greek for hidden), but it doesn't give you certification like asymmetric cryptography, quite the opposite actually, because by definition FHE schemes are perfectly malleable.

Ah thanks! I incorrectly assumed that if so much effort is spent on this, it must be because it helps protect something valuable (directly by preventing bank or credit hacking, or indirectly by helping secure trade secrets behind encryption, etc.).

Is it quantum safe?

They are quantum resistant; as far as we know.

https://crypto.stackexchange.com/a/27589

One of the main drawbacks of FHE is that it usually leaks some details of your data. E.g., if you do a multiplication of two (encrypted) values, an attacker can memorize the input and output. Since for most useful applications (eg ML) your computations must be deterministic, an attacker can build up a table of calculations. Once this is filled a bit, he can use that with some heuristics to estimate the data.

The problem here is that it can be very difficult to prove that an application using FHE is really secure against leaking information.

I guess Intel will just do some marketing a la "it's encrypted, thus is safe" BS that semi- or non-technical managers will buy to put a checkmark on their security checklists.

This is inaccurate. Any encryption that cryptographers will accept will be semantically secure at a minimum (which FHE is). Briefly, to quote Gentry's paper which first showed the existence of FHE: this means given a ciphertext c that encrypts either m0 or m1, it is hard for an adversary to decide which, even if it is allowed to choose m0 and m1.

This rules out deterministic encryption, which is not sufficient for the reasons you mention (and is why, for example, you shouldn't use textbook RSA).

Also it's actually easier to prove that FHE applications are secure than it is to prove a lot of other things. FHE is designed around commonly used hardness assumptions, such as the Learning With Errors problem. As long as you're encrypting your information correctly there's really nothing Intel can do to leak your information short of disproving open conjectures in computer science. At the very least, they probably won't fumble their way into doing so

I'm confused who is the attacker in this scenario? The entity doing the computation? If the party doing the computation can only see the encrypted inputs and outputs, and the ciphertexts are not deterministic, how would they create a table out of that?

The threat model for FHE is that the attacker is the entity doing the computation

Principally yes, but it also aims to protect against evesdroppers for example. Many usecases want to keep the algorithm being invoked secret (by having it run on a computer the requester does not have access to)

Anyways, the reason i asked is because the grandparent said "attacker can memorize the input and output", which is not something the entity doing the computation can do, as they only see the encrypted text, and encrypted values never repeat (or only with negligible probability) even if the plaintext they are encrypting are the same.

The end user entity on the other hand, could try (in theory, not practically) every single value, memorize it, and recreate the secret function. So if the attacker in this scenario is the entity encrypting/decrypting the data, some of the grandparent's post makes more sense.

Doesn’t that threat model defeat the purpose of the algorithm leaks?

Yes it's encrypted, but the unit of encryption is individual values. If you multiply two arrays of values, they the computer/attacker can't tell exactly what each value is but could observe that, say, elements 7 and 12 are the same. Thus leaking some information about the data set.

FHE is semantically secure against chosen plaintext attacks. (The gentry latice scheme paper claims it is semantically secure against chosen plaintext attacks [1])

If i understand that correctly, it means that when you encrypt a value, you always get a different value, even if the plaintext is the same.

So how would the attacker observe that value 7 and 12 are the same without decrypting the value?

[1] https://www.google.com/url?sa=t&source=web&rct=j&url=https:/...

P.s. are you maybe confusing FHE with deterministic encryption or order-preserving-encryption which is sometimes used in "encrypted" (scare quotes because they're pretty bad) db products that still want to allow queries on encrypted data. That's a totally different thing with much much weaker security garuntees.

Honestly, I don't understand how you can get downvoted for this answer. The GP should be downvoted in oblivion, because it obviously doesn't know what it's talking about, yet you are the greyed one…

If people don't believe the parent post and would like to see a visual “proof” of it, here is the (abbreviated) ciphertext for same value (`true`) encrypted by [TFHE](https://github.com/tfhe/tfhe), note how these aren't the same:

{ coefficients: [-224220402, 1267713220, 372943361, 263858338, -370546283, -605917751, -1924979310, -1572775794, 1846572795, -468768480, -290510339, -915978400, -1364310315, 809081884, -1495989601, -331539817, -1453231071, 404566454, 495420049, -879411073, 830751792, -517575314, 1556751889, 443973073, 1944290005, 674176195, -2141487034, -317403947, -460501881, -530948496, -1701307365, -1131020764, -951177975, 185735343, -607301526, -1413023671, -927580822, -1519370777, -867508577, 1783197541, -1563558893, 1077184331, 1711379115, 1493923712, 1553459001, -1181497038, 2076454627, 2090667603, -1811778643, -1964586812, -1514194032, 1847333213, -29937879, 1408366270, -246399878, -2100573013, 143332974, 355615400, -1746332080, 1803753774, 1010929751, -178538162, 2019489654, -1762380579, 1676883032, 855666812, 2078455615, 1070127391, -310916718, 1972027124, 1145751265, 1391734199, …], b: -362940425, current_variance: 0.0000000009313225746154785 }

{ coefficients: [-297806840, -994586634, 304850282, 863793687, 1840210042, -1105546555, -1110462781, 858561202, 1572862702, -1414807433, 925868178, -2022139768, 1977503124, -1355884545, 252233845, -607580470, -1640661899, 184197878, 175367248, -1883040938, -1452285303, 2135910408, 1848643984, 277669753, 1205220991, -1010438927, 344717140, -616704798, 617000592, -706461456, -1674056437, -1108542319, 1209547087, -1275731206, -1050202170, 1804450949, -212790115, 1603633119, 1581631548, 891985869, -767711288, 1662132229, -488697271, 1729020643, 68369628, 594815617, -697565685, -1119636178, -1069556471, 668091191, 2058655289, -965364559, -428300746, 1288771675, -1291673545, -1936980021, 1344393745, -566147990, -2017181358, -876369855, 1202714564, 279954504, 1954812679, -121935512, 1508624251, 1746889815, 10036320, -694130814, 1749036054, -350031511, 856310504, -486108325, 447226889, -108777191, 1323665880, 819541960, 441166350, -934866202, 837730330, 281902593, -1870154550, 963192542, 649262920, -2012432624, 1553637232, 627237492, 616166507, 781074188, 44864017, -1911286875, -1429302424, -1054092570, -1620457762, 641734226, 1629006914, 1365659737, 360668934, -874923908, …], b: 27536240, current_variance: 0.0000000009313225746154785 }

That's partially what random filler values are for.

Also, aren't there FHE algorithms or potential constructs for encrypting blocks of data using the index as part of a shared secret?

Would it be possible to add random low order bits to prevent that? E.g instead of doing 7 * 9 you do 7.00024378 * 9.00003891

FHE involves adding random noise pretty constantly (FHE kind of works by adding noise at every step, and regulary does a magic encrypted re-encryption step where during evaluation the intermediate values are reencrypted without ever revealing the original value, to get rid of the excess noise).

Anyways, FHE is secure against (non-adaptive) chosen plaintext attacks. That among other things means that if E is the encryption function, E(7) != E(7), and if you have E(x) and E(y) you cant tell if x and y are related to each other unless you have access to the decryption function.

> Once this is filled a bit, he can use that with some heuristics to estimate the data.

how many inputs do you need before the heuristics start letting you guess than a function with 128 bits of input is a 64 bit multiply?

and if the input is 8192 bits?

i feel like you're reporting some theoretical ("needs 2^1024 ciphertexts!") attack as though it is a practical concern.

Isn’t this the whole problem in homomorphic encryption? We already have cryptographic systems for which encryption is a homomorphism, such as RSA. I thought that the whole problem was finding ways to do it that don’t leak any data, basically.

FHE leaks information indeed. It's proven to not be secure against a chosen ciphertext attack.

It's not that straightforward. There's two types of chosen ciphertext attacks: IND-CCA1 (non-adaptive) and IND-CCA2 (adaptive).

There are in fact FHE schemes for the former such as https://www.iacr.org/archive/pkc2017/101750203/101750203.pdf

The problem comes in the adaptive case. In the distinguishing game, an adaptive adversary can have the decryption oracle decrypt any ciphertext after it receives its challenge ciphertext (besides the challenge itself, as that would be trivially defeatable). However, if the adversary receives Enc(m), they can just compute Enc(m+m) and ask the oracle to decrypt it, thus winning the game.

No FHE scheme will be IND-CCA2 secure by definition, but that doesn't mean that they "leak information" in the applications FHE is being proposed for. As long as you're not decrypting arbitrary ciphertexts for the server you just uploaded your sensitive encrypted information to, you can have your delegated computation, as a treat.

Well this is unfortunate, i can't help but feel that many of the usecases for FHE are much less likely to have decryption oracles than traditional encryption would.

I'm also not sure if i would say "leak information" is the right word to describe a chosen ciphertext attack.

This needs to happen in order to have secure, distributed/p2p computational shared overlay networks.

I'm not sure i see the relavance. I would consider Zk-Snark's much more relavant to that domain. And well, doing something about targeted DoS attacks somehow.

I see we have all caught on to Apple's "Silicon" buzzword.

This is a form of technology which is designed to harm computer users.

?? By allowing us to use computationao services without leaking data to them?

Yes, by taking control away from them.

Its a pretty generic technology. It has good and bad uses

Reply on news.ycombinator.com