Intel joins DARPA in search of encryption 'holy grail' | Hacker News Reader

Intel joins DARPA in search of encryption 'holy grail'

zdnet.com

58 pointsBender46 comments

For the naive like myself, if FHE permits an untrusted computer to perform operations on encrypted data, without being able to read the unencrypted data, what operations could be performed? (multiply/add?) Is it still capable of conditional logic? If so, how could this be done without unveiling some of the information?

Edit: And what's even a good use case for it?

Since conditional logic can be implemented as and/or logic gates, FHE should still apply to them and should be quite general purpose. But I’m not an expert, and I think it would depend on the design of specific FHE schemes.

I think there's a bunch of confusion between conditional logic in the sense of being able to solve a problem that can be specified with conditional logic, and the sense of having the performance implications of a normal program that has data-dependent branches.

I think FHE is nowhere close to practical performance, conditional branches or not.

> conditional logic

Conditional logic can be expressed in terms of arithmetic:

  if c then t else f = c*t + (1-c)*f

You can also do boolean logic:

  NOT y = 1 - y
  x AND y = x * y
  x OR y = (x + y) - (x * y)

(Where 1 indicates truth and 0 falsity.)

What you can't do, however, is conditional execution, as this would leak information. Which doesn't limit the capabilities of the system in principle, but does in practice because this harms performance. E.G. ‘select count(*) from users where name = bob’ will be much slower with HFE than with a traditional database because there will be no possibility of using precalculated indices.

Ah yes, I was thinking it was possible to execute both computations and take the one you need. 'Conditional execution' was more what I meant.

You can think of FHE as just "you can compute arbitrary polynomials over ciphertexts". You can't exactly get conditional execution using polynomials. Most people instead think of FHE computation as "arithmetic circuits".

Also, some schemes offer extra stuff for free. BFV (https://eprint.iacr.org/2012/078) for example lets you compute Frobenius endomorphisms very cheaply. That is, given ciphertext c, you can compute c^q without having to do log(q) many squarings, where q is the characteristic of your ring.

Can you think of a practical use for something like this? Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret?

> Perhaps there's a need to keep an algorithm secret, but also the client wishes to keep their inputs secret?

That is basically the problem statement that FHE is trying to solve.

Yup that's the idea. I give an example in another comment https://news.ycombinator.com/item?id=26421172

FHE was pursued by Japanese telcos pre-2000s.

Imagine a central exchange building, serving few million customers in a region, each connecting from VT110 over ISDN line, handling imagined Internet thing pre-Internet. Something like “Tanaka-san is making a golf course reservation using easy to learn SQL language”.

FHE-based database fits the bill there; there’s a risk that equipment technicians might get hold of a key. FHE can offer protections all-around.

Performances and privacy of logic is irrelevant; it’s responsibilities of service providers to account for technical implications. Code to run is supplied. Customers are not required to/expected to write it.

Researchers doing FHE works today would be fully aware of Internet, but models in some papers to explain it might still carry that Transatlantic accent.

> Code to run is supplied. Customers are not required to/expected to write it.

Do I have this right: FHE is useful for running queries across a dataset without revealing what the queries are nor the result? If so, would write operations even be possible?

I do research on FHE. On a high level querying works by evaluating an equivalence function between the encrypted query key and keys in the database such that the result is 1 if the key matches and 0 otherwise. You can then multiply this with the values and sum all of them together to get just the row that matches.

For write operations you could do a similar trick to select a new version of each value based on the query key matching. You are in effect writing all rows, but using the old value when you don't want to change it.

Now, due to some quirks of FHE you can only do this write operation a limited number of times before you have to perform a more expensive operation called bootstrapping to "refresh" ciphertexts. I find bootstrapping to be the coolest part of homomorphic encryption: you encrypt the secret key itself with homomorphic encryption and then use it to decrypt inside FHE. The result is still encrypted but closer to a freshly encrypted ciphertext.

Are there any good papers (with code even) you know of demonstrating these kind of practical applications?

So in essence you're performing encrypted operations on a remote and potentially untrusted encrypted database, but these operations are very expensive? So when would this be valuable?

When it matures to be less expensive, or the hardware handles it fast enough to not be a problem.

But always orders of magnitude slower than what a vanilla CPU can do locally. The value would entail that operations on a remote server are necessary to the function. Maybe a remote database that can be accessed from multiple devices with the same key but still permitting simultaneous read/write operations? The database could be compromised without any data stolen.

Sometimes the benefit from FHE can be larger than the speed gains. Doubt facebook would use this (for scaling and privacy reasons) but if the CIA needed to not have to trust a cloud provider for something of a smaller scale? 100% worth it.

> The value would entail that operations on a remote server are necessary to the function

Yes, not every organization has the compute power necessary, or even prefer to not handle it at all in house. If you only manage keys locally, that's a significantly smaller attack surface.

> 100% worth it

I'm not sure the value proposition is clear cut. In terms of security, while the server data itself is secure, and the nature of the transactions are inscrutable, there's now reason to share a single key between multiple users, and only one of those users needs to be compromised. The key could be generated and stored in some super secure silicon with a small attack surface, but if the data needs to be available to multiple users, you're back to duplicating and distributing the key, and social engineering remains the best attack vector. A benefit could be gained with multiple users with multiple keys and limited sharing to reduce vulnerability, like sharing sensitive documents between between select individuals. But that's a pretty niche use case.

I don’t know, but write to 0-initialized variable is a bitwise add against 0b0, so if you random-initialize a variable, then add a value, query variable, then subtract the known initial random state from response, you end up with the value == response - initial_random(key).

If you could add/multiply cryptographically securely, such that the current_variable - initial_random = delta != data is meaningless to third parties without the key, that will be a secure write to a secure database.

Dynamic allocation is probably not possible.

Yes, multiply and add, or any set of operations necessary to create an arbitrary Boolean function, which then would have encrypted input and output.

From that you get "Turing completeness" because, for any computation you want to do, you can unwind it into a static Boolean circuit that computes (some appropriately sized version of) it. Note that this means you're limited to primitive recursive functions i.e. all loops must be compile-time bounded.

The use case is stuff like, "add up my numbers without knowing what the numbers are or their sum is". I think there are also end-to-end auditable voting systems that preserve privacy.

From my understanding, FHE can represent Boolean circuits, so you don't write an "FHE application"; you can send an encrypted input into an encrypted Boolean circuit and get an encrypted result.

Since FHE operations are Boolean circuits, we can consider basic stuff like "AND" or "NOT" - but all the inputs, outputs and the operation itself are encrypted, so the owner of the server won't even know if someone called an AND gate, a NOT gate, or something else.

Which means that if primitive Boolean operations are supported, you can chain them to create a general purpose, Turing complete computer.

However if you were a nefarious actor looking at the order and frequency at which various primitives were called, then you could be able to discern a call graph (or at least, a statistical "heatmap"), and you might figure something about the nature of the program, and therefore be able to glean some kind of understanding of the information passing through it, however abstract.

However since FHE can represent boolean circuits, we're not just limited to primitives. A futuristic compiler could create a single boolean circuit to represent a complex application - however for something like a blog or eCommerce store, that would result in inordinate amount of cyphertext to represent the code, and undoubtedly be very slow to run.

I think more likely is the compiler would optimise layers or stacks of black-boxes that are not simply boolean primitives. Your plaintext code (in the language of you choosing) would have every branch of the call stack from input, processing, and output analysed n-levels deep optimising for a balance of runtime and obfuscation.

In such a case, the nefarious actor would see a blob of cypher going into a blob of other cypher to generate a blob of cypher as input into the next blob of cypher. Maybe there are parallel cypher blobs, but their internals are completely hidden. An inside actor might have intimate knowledge of how long each blob takes to execute for various inputs, so assuming that knowledge is shared we're back at good old timing attacks - which would probably become irrelevant on the next compiler pass anyway.

Use-cases I can think of are any kind of transactional situation where various actors have competing interests, where it may be in one or more actor's best interests to game the system. Anything peer-to-peer is a good example.

Gaming seems trite, but in the early days, gaming was full of client side cheats. The current model for multiplayer gaming to avoid cheating is centralised - every client has to interface with a central server that then has to figure out which moves were legal in the game's rules - peer-to-peer is fraught with cheaters since they can analyse and change the code client-side. Realtime FHE would allow game developers to come back to peer-to-peer gaming, since it would be mathematically improbable that a peer is cheating.

Escrow is another peer-to-peer type activity, where it would be useful to have a trusted middleman. Maybe provenance for digital / physical goods (that's a bit of a stretch). But essentially, right now, a lot of development effort is expended to make sure individuals in a system can't gain an advantage on the client side - if we didn't have to trust a user's computer to do the right thing, then the client/server trust barrier collapses.

Can someone explain how FHE can make data useable e.g. for a database application without also leaking lots of information? Like when I select count(*) from data where name = 'Bob' and SSN = 123, can't I use that to find out Bob's social security number with little effort despite FHE?

The database server won't have any idea what the query is, and doesn't know how to create encrypted queries either.

It also won't know the size of the result, only seeing a fixed-size buffer.

I think what OP meant is that this logically implies every query must touch all the data (or else you could infer information from data access patterns) at which point is it really a database anymore as we know it?

If that's the question, then the answer is "if you make it usable for a database application then it's not FHE, sorry"

Interesting, so FHE is essentially useless for cloud applications? What would be a good use case where FHE can be applied?

Many types of processing on small data sets are fine. Or lots of small data sets in parallel.

You could run statistics on data or do a grid-based simulation.

Running a neural net would be almost trivial.

General purpose code is extremely difficult to adapt, since it loves to branch based on data.

Neural nets are a very convincing use case. Thanks!

No offense but just "running a neural net" is rarely trivial

What do you mean? I'm not talking about design or tuning or anything, just shoving raw data through.

All you have to do is multiply each weight and add up each node.

Pure bulk arithmetic is both simple and a perfect match for FHE.

“Trivial” is relative, and in the context of this forum post and the audience that is reading it, running a basic neural net is unlikely a large hurdle for most here.

Hell, I’m not an ML practitioner and I almost never use python, and yet it took me maybe a day or two learn enough about covnet training to detect my dog on a home security camera.

Probably good for batch jobs? Updating billing information, device location registry, etc., for 10k users each day or each hour etc.

"Cloud applications" cover a big range.

If you mean is it useless as a replacement for the mysql backend of your php app, the answer is yes.

I'm confused what your plan of attack is.

Because simply querying the database a billion times and replacing SSN with 1, 2 etc. is never going to work in any reasonably secure environment. Queries are logged and people will know if you're trying to brute force a table.

The whole point of homomorphic encryption is that you don’t trust the server doing the computation.

Is it ? I thought the whole point was that your data remains encrypted during computation.

Especially for data lakes where the act of manipulating data can sometimes involve moving actual files around a distributed cluster in a potentially insecure environment e.g. cloud.

For practical applications you can do better if you allow some information leakage or multiple rounds of communication. People play various tricks. What kind of leakage is acceptable depends on the application.

You're right. This isn't a good use case for FHE. Instead, FHE is really useful when the query itself is private, and the data is not private.

One example is a private OCSP. Every time you open a TLS-secured webpage, your browser has to check whether or not the TLS certificate has been revoked (I'm leaving out some complications but bear with me). In order to do that, you browser has to contact the certificate authority (CA) and ask "has anyone revoked this cert?". But in doing that, the browser is revealing your browsing patterns to the CA!

It would be nice, instead, to use Private Information Retrieval to ask the CA "please process this encrypted query and return the result". Then the CA knows nothing about your browsing patterns, and you still get your data. Well, (computational) Private Information Retrieval is super inefficient today, and the best asymptotic solution we have is based on FHE (https://eprint.iacr.org/2017/1142). So getting efficient FHE would hopefully make something like this a lot more reasonable for moderately sized databases.

For the record, this is only a toy example. We actually have really good solutions for private OCSP that don't require FHE. We can side-step the difficult of Private Information Retrieval in this case because OCSP databases are small enough for anyone to download. If this interests you, check out CRLite https://blog.mozilla.org/security/2020/01/09/crlite-part-1-a...

- Does -my time/location- match any time/location where we know corona case was. - Does -my dna- match known predistortions for diseases

that kind of thing.

They could potentially extend SGX type mechanism to execute more complex data operators within an enclave and give out only results that are at least k-anonymous or allow decrypted results only if it is explicitly allowed when enclave is created. And of course all this has to be implemented in an isolated hardware so that classic chip timing/race attacks cannot steal secrets like it is possible from within the enclaves with SGX today.

I am worried that Intel will present a new encryption tech that turns out to be 5 years old /s

Wonderful for e2e hosted guest VMs.

I would like to see adiabatic physical computing to reduce power consumption too.

Don't create information that needs to be hidden. you wouldn't even need encryption after that

I take it you publish your credit card number for the world to see?

Valid point

Reply on news.ycombinator.com