I'm surprised the "capitalizing a 32 character string" example is actually one second faster than adding two 32bit integers. Still super slow, but I'm curious why. I'd assume that if the string_cap.cc example takes 256 wires, wouldn't add.cc take 64 wires?

Short answer: string cap has more parallelism in the circuit. Depth is more important than total number of gates, and optimizers can decrease depth pretty well.

Thanks (and Dylan18607). So to continue assuming, the number of wires specified is just the input/output, and the add.cc has more intermediate "wires"?

It's more like: to implement add you need a ripple carry adder. You can't evaluate bit 6 until you've evaluated bits 1-5. So there's a nested dependence that makes the circuit deep. String cap, on the other hand, can be implemented in parallel by looking at pairs of characters independently. So that makes it into a parallel band of small circuits, which we can evaluate in parallelism. Also I think the capitalization routing affects fewer bits of a char (it's just toggling one bit in each char, IIRC).

It's faster to carry six glasses at once than having to carry them to some point one by one.

That makes perfect sense, thank you! I also didn't know until today that capitalization in ascii is just the 6th bit. I thought it would have been doing 32 subtract operations. (I'll be honest I haven't written my own uppercase function since school haha)

Since it encrypts one bit at a time, does capitalizing even have to touch the 224 bits that don't change?

> wouldn't add.cc take 64 wires?

Plus another hundred intermediate wires. And it's doing more complicated operations, however much that matters.

No idea lol! Though it says it works on all 32 bytes in parallel regardless of input size. I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise? They state it should take the same duration regardless of the length of the input string or how much needs to be capitalized (all branches are executed even though many are discarded)

> I imagine ignoring the bits that don't change would be some sort of security vulnerability? You could probably work out some timing attack or entropy reduction otherwise?

Nah. The bits are hardcoded into the circuit to not change. That's part of the program, and the program is public information. Only bit 6 of each byte might change, and everyone knows it.

Whoa, I never knew about the ascii 6th bit trick, I've never really considered capitalization wasn't some random offset. So that does make this circuit simpler than I thought it was, and there's the parallelism aspect. It's not so surprising now that it's faster than the add.

I feel it's already at the edge of being useful in practice. Compute and memory are cheap, and we're wasting a lot of it - so even with overhead this big, simple calculations wrapped in FHE wouldn't be prohibitively expensive - and may just be useful enough to create new types of software systems.

7 seconds to add two numbers; that's roughly, what, 10 orders of magnitude slower than without FHE? I'm not sure compute is that cheap.

It would be interesting to see a whole new generation of writing apps with hyper optimized code. We suddenly go back to the 1950s(?) in relative compute power for apps behind FHE.

Not sure what could be done with it at 7s though hah.

An order of magnitude order of magnitude

It’s orders of magnitude all the way down

If all you need to do is handle a symmetric key exchange that you then use for everything else, that might be enough.

This is tempting to believe, but unfortunately the dream is to be able to run applications on someone else's servers without them knowing what you're doing. That's when I lost interest in FHE. If you want to use it, you have to use it everywhere, and it's just too slow.

Hopefully I'm wrong about that.

I probably should have added: the backends used in the post are 3-ish years old and missing some of the latest features. We're working on integrating newer backends and taking advantage of the new techniques! The performance story is better than it seems from my article. Plus this doesn't have any hardware acceleration, another big topic on my agenda :)

Hey no need to justify it here, this is really cool! The first few runs are always slow and ready for optimization. I am very optimistic for what this tech may do for medical records and similar industries.

Yeah I’ve always wondered if FHE would benefit from asic level acceleration, or at least FPGA

If you are going to do an asic (w/o data going to memory IO) then why not use regular encryption with codec on the SoC itself (like DRM content). that works just fine. IMO the main value here would be trust between unknown parties over untrusted medium.

The typical perceived use case is FHE in cloud providers providing highly sensitive compute in a multi tenant platform. In something like that full on hardware acceleration is key

just noticed the response..

Not really, even in those cases you need to understand that bits in memory (ie.. everything past (&including) the SoC's IO pins would never see the data unencrypted. any decryption is handled within working cache on soc with secure context (typically on a secure OS vm). I dont see why a bunch of compute code wont work there. in fact you could go a step further and encrypt compute instructions too. then assuming you know what you are doing and dont crash the compute node will have no idea what ops you are actually doing on what data.

btw thats how DRM works (sans the last part).

Great article btw

Binary TFHE (the scheme the Google compiler uses) is fairly slow and has very large public keys (like 100MB). However the advantage is that binary computation is very flexible and well understood. Additionally, TFHE supports fast (~10ms) bootstrapping, which allows you to perform an arbitrary amount of computation.

If you can live with the limitations of other schemes FHE can be much faster. On a single core of an M1 Macbook Air, multiplying 2 BFV encrypted 4096-bit values takes 4ms and adding them takes only 15us. Additionally, key sizes aren't horrendous (<500kB). One downside with this scheme are that bootstrapping takes minutes so it isn't really practical. This limits the amount of computation you can do before you exceed your noise budget and the ciphertext decrypts to garbage. The other downside is that arithmetic circuits make some computations far more difficult (e.g. comparisons).