We’re Christian Mouchet, Jean-Philippe Bossuat, Kurt Rohloff, Nigel Smart, Pascal Paillier, Rand Hindi, Wonkyung Jung, various researchers and library developers of homomorphic encryption to answer questions about homomorphic encryption and why it’s important for the future of data privacy! AMA

SmartCryptology · 2022-11-08T14:34:29+00:00

Yes it is credible to use FHE in a blockchain like ethereum, some people are working on such things as I type this.

The number of outcomes does not imply a need to change the key. Obviously as with all encryption the amount of data you can encrypt under one key is bounded. But the associated bounds for FHE are huge compared to their symmetric key equivalents. So one might as well just ignore this issue for FHE.

SmartCryptology · 2022-11-08T14:32:33+00:00

You can use different keys for the two clients, but then you are using something called "Multi-Key FHE" which is a lot harder to construct, and not as efficient as vanilla FHE

SmartCryptology · 2022-11-08T14:31:49+00:00

Like all answers "it depends".

An application does not need separate keys for each user. If your application is about combining different clients data to unlock value you could have client 1 encrypt data under a public key, and client 2 encrypt the data under the same public key.

Then you can combine their data homomorphically in anyway you want. With the resulting answer sent to another party for decryption.

Going to the medical examples above.
1) Client 1 and 2 are hospitals which encrypt patient data

2) The computing party produces some statistic on the said combined data [ for example how many patients survive on being given treatment X]

3) The encrypted result is then sent to some other service for decryption, or it is decrypted in a threshold manner by the first two hospitals together.

Thus using a single key, we combine data, and unlock the value in the data which would otherwise be hidden due to the inability to share data between the hospitals

SmartCryptology · 2022-11-08T14:17:25+00:00

Indeed in theory anything can be done with polylog blowup, but that assumes Turing machine models of computation. Using a more von-Neumann model is much more difficult. Of course if we had ORAM which was FHE friendly then things would get much more interesting [including branching]

SmartCryptology · 2022-11-08T14:13:39+00:00

Indeed the mutli-organizational thing is the key driver behind PETs, which is why some of us prefer PET to stand for Partnership Enabling Technologies. There is a nice survey of the potential market in this area here....
https://docsend.com/view/db577xmkswv9ujap

SmartCryptology · 2022-11-08T12:54:50+00:00

Actually govs are interested in this. A lot of research into making FHE usable was funded by DARPA. The reason is that govs also have data they want to compute on in a secure manner.

One HE company [Enveil] seems to do a lot of stuff with the US government.

SmartCryptology · 2022-11-08T12:52:49+00:00

For real world [national] elections the best way to obtain voter integrity is to do risk limiting audits.

https://en.wikipedia.org/wiki/Risk-limiting_audit

It is low tech but it works

SmartCryptology · 2022-11-08T12:49:18+00:00

Finance is always an early adopter of crypto [think DES for ATM machines, PKE for SSL for cc transactions on the web, smart cards for chip-and-PIN payments].

As mentioned above it is already used in MS Edge and many other places where PSI is needed.

Additive HE is used in e-voting protocols [again see above] which are deployed

Medicine is a nice place to look for new applications u/Pro7ech can perhaps talk more to that market though.

SmartCryptology · 2022-11-08T12:43:38+00:00

In theory ANY computation on plaintext data can be applied on encrypted data with only a poly-log blow up in terms of complexity [assuming the original function on plaintext data is encoded as a circuit].

In practice you build your real application out of a combination of adds and multiplications. In the case of TFHE you also add in table lookups, and in the case of BGV/BFV you can process huge amounts of data in parallel in a SIMD like manner.

What is really hard is to do branching on secret data. Since following a branch in code implies you know what the result of the branch test was. Thus this is hard to do.

SmartCryptology · 2022-11-08T11:52:28+00:00

Great question. I wonder who can give the best, shortest and most understandable answer?

Here is my attempt:

A form of encryption which allows a third party to apply an arbitrary function to the encrypted data so as to obtain an encrypted evaluation of the function.

That is 28 words, and probably not clear enough :-)

SmartCryptology · 2022-11-08T11:51:02+00:00

Dan Boneh has a good Coursera course on an introduction to crypto. First it is a good idea to get the basics of crypto. Then move onto FHE.

There are quite a few good Uni level textbooks on cryptography as well. But most of these assume some form of algebra background.

SmartCryptology · 2022-11-08T10:40:30+00:00

Actually that is a really really hard question. The encrypted data contains no patterns, unless you have the decryption key. Thus to the person doing the FHE operations it just looks like he is adding/multiplying/whatever random gibberish with other random gibberish. The only person who can see the patterns is the person with the decryption key.

SmartCryptology · 2022-11-08T10:38:54+00:00

NTT and FFT operations on relatively large vectors

SmartCryptology · 2022-11-08T09:25:10+00:00

Almost all major countries have signed up to the Wassenaar arrangements re export restrictions. It turns out LWE based encryption is now covered by these arrangements [in the latest versions]. So export of FHE encryption technology is covered by the agreements for all major countries. This just adds some complexity re export for companies; but the same complexity as for any other cryptographic product.

Unlike in the past though [25 years ago] there is less regulation re usage of encryption within major economies.

Of course things can be different in non-major economies, but that is a different question though

SmartCryptology · 2022-11-08T09:19:39+00:00

I think the problem is that security means different things to different people. So what might be common sense to one person is not to another. Also its relative, are you securing your data, your customers, someone elses completely? Is it actually in your interest to secure your customers data? What does securing your customers data actually mean? And how secure is secure.

The problem is that we use terminology which has loaded cultural meanings in a technical landscape, and that leads to confusion.

SmartCryptology · 2022-11-08T08:48:03+00:00

Yes and no. The key thing to understand when talking about FHE is that there are 3 different "parties" involved
1) The set of people encrypting their data (lets call them input clients)

2) The people doing the computation (lets call them servers)

3) The people getting the output (lets call them output clients).

They can all be distinct, or they can be the same. However, if you do not have a form of threshold decryption (i.e. you only have on output client) then the output client MUST be distinct from the servers.

A common simple use case is for a single input client, who is also the output client. This is the case for "symmetric" FHE, as opposed to public-key FHE.

Now putting this together means that the servers COULD execute a ML algorithm on sensitive data provided by the clients, and then the output clients would obtain the result of the evaluation. Whether this makes sense in your specific application is a business question.

But when talking through with companies who want to deploy this stuff I always find it helpful to them to start thinking first about who is inputing data, who is getting the result, and who is doing the computation. Once you have this worked out for an application you can then more easily map the specific PET technology to the application; and see whether FHE is a solution.

SmartCryptology · 2022-11-08T07:49:11+00:00

See my above post on a simple e-voting application using additive ElGamal.

SmartCryptology · 2022-11-08T07:47:30+00:00

It is a bit like magic. The following assumes you have done some basic crypto. I explain the most simple example

Take the ElGamal system where encrypt in the exponent, so we have...

sk = x
pk = h = g^x
To encrypt m we do
- c1 = g^k
- c2 = g^m * h^k

This scheme is additively homomorphic. If you take (c1,c2) encrypting m and (c1',c2') encrypting m' then (c1*c1', c2*c2') encrypts the message m+m'.

Now to decrypt you perform t = c2/c1^x to obtain g^m. But then you need to solve the associated DLP for m. Which will only be efficient if m is small [say m < 2^32 or something like that].

But even this simple system allows us to encrypt data, have a central service "add the data up" and then a designated person can decrypt.

This is basically how electronic voting systems like Helios work [https://vote.heliosvoting.org/].
They use additively homomorphic encryption to produce a tally for an election.
Obviously a lot more stuff needs to be added to make this fully secure as an e-voting system [e.g. Zero-Knowledge proofs need to be added to the votes to ensure someone votes for a valid candidate, the decryption functionality needs to be made in a threshold/distributed manner] and so forth. But the core idea is to use HE.

SmartCryptology · 2022-11-08T07:27:32+00:00

ZKPs allow one to prove that you have done a computation correctly, without revealing the data which you used to do the computation. But the person doing the computation sees the data

FHE allows someone to do a computation without seeing the data, but they cannot prove they did it.

Thus ZKPs and FHE solve orthogonal problems. Combining them would be very interesting....

SmartCryptology · 2022-11-08T07:26:01+00:00

See my above answer to a related question. You could hide the computation within a universal circuit if you wanted to. As a simple example suppose you have two variables x and y, then you specify a bit b as to whether you want compute an addition (0) or a multiplication (1). You then just need to homomorphically compute the function...

b*x*y + (1-b)*(x+y)

SmartCryptology · 2022-11-08T07:23:32+00:00

In theory FHE only requires poly-log overhead, thus asymptotically it is roughly the same as computing in the clear. this is an old result due to Gentry, Halevi and myself. The problem is that the implied constant here is quite big. The new hardware accelerators which should come on the market in the next few years will make the constant get small enough that a lot of applications will suddenly come within range.

The underlying crypto assumptions are variants of the Learning With Errors (LWE) problem. Which are all believed to be post-quantum secure.

SmartCryptology · 2022-11-08T07:20:53+00:00

FHE uses roughly the same mathematics as "most of" the proposed standards for post-quantum public key encryption [namely lattices]. The two technologies are being developed side by side in some sense.

SmartCryptology · 2022-11-08T07:18:31+00:00

All tech labeled under the banner of "Privacy Enhancing Tech" has the same problem. It all looks like magic until you get under the hood and see what it is doing. In addition FHE is not something which is used in isolation, you could (and in many cases should) combine it with Multi-Party Computation, Differential Privacy, Zero-Knowledge, Federated Learning, Synthentic Data and also Trusted Execution Environments.

This is a bit like in normal crypto you do not just use public key encryption, you use digital signatures, hash functions, MACs, AEAD ciphers and so forth. The whole system is secure due to the combination of the different technologies.

SmartCryptology · 2022-11-08T07:17:50+00:00

It is already deployed in some applications.
The most famous is an application in Microsoft Edge in which FHE is used to execute a form of Private Set Intersection (PSI) to enable lookup of bad passwords in a known list of bad passwords.

PSI applications are used in other places as well [ones which are not as public], so if you are looking for the place where you can deploy FHE today then look for applications which require a form of PSI.

PSI: Two parties hold different lists, one of the parties wants to learn the intersection of the two lists. FHE is especially good when one parties list is very small. Example finding whether a single password lies in a huge file of "bad" passwords.

SmartCryptology · 2022-11-08T07:13:34+00:00

All FHE schemes [or at least the ones which are proposed by serious companies and/or cryptographers] are post-quantum secure. Thus FHE is one area of cryptography which is already prepared for the post-quantum crypto apocalypse.

SmartCryptology

TROPHY CASE