Homomorphic encryption is the idea to arrange computation in such a way that, if fed encrypted input data, it will produce an encrypted result, and even if an attacker observes every bit manipulation the machine does, they will not be able to gain any information about the unencrypted input or result data.

Ideally, we would simply write a program, which a compiler would transform into homomorphically encrypted code for us. To date, there is no practical scheme for doing this, and there are reasons to believe that there may never be a way to do this in general. But there are some subtle details. Let me explain.

There is a somewhat simple scheme for homomorphic encryption which works, but there is a catch. First you need to blow up the input data exponentially, so that enough variants are produced, and the attacker is confronted with the problem that he cannot tell which of these are real data and which are just garbage.

But that's not enough! When running the program, the machine will also need to compute every possible conditional branch! Whenever there's an `if` in our program, the required computational effort doubles!

This cost explosion makes it completely impractical for almost all forms of data processing, like for example database applications, or even most patterns of communication, let aside any computationally more intensive workloads or, well, basically anything we use computers for today!

However, it may be feasible, perhaps, even if just barely so, for some cryptographical applications operating on tiny chunks of data. You'd still have to pay a hefty price for the blow-up, but it could be done. I mean, I fail to come up with ideas here, but maybe someone among you is able to imagine a scenario where this could be useful today, of course, given the limitations I mentioned.

So, it's pretty much theory, interesting as a subject for research, but not very useful. So what is cutting edge today? Here is a cool blog post by **Jeremy Kun** about the latest FHE compiler from google labs (of course, FHE means full homomorphic encryption):

https://jeremykun.com/2023/02/13/googles-fully-homomorphic-encryption-compiler-a-primer/

They implemented a compiler which takes a subset of C++ and generates logic gates. As to be expected, the subset of C++ is severly limited, here's how Jeremy puts it:

> A few limitations result from this circuit-based approach, which will be woven throughout the rest of this tutorial. First is that all loops must be fully unrolled and have statically-known bounds. Second, constructs like pointers, and dynamic memory allocation are not supported. Third, all control flow is multiplexed, meaning that all branches of all if statements are evaluated, and only then is one chosen. Finally, there are important practical considerations related to the bit-width of the types used and the expansion of cleartexts into ciphertexts that impact the performance of the resulting program.

Typically we'd expect a general purpose language to be _Turing complete, at least in theory. Some languages don't quite achieve that kind of generality and are only _primitive recursive_. SQL is such an example, it does not have unbounded while loops with which one could search for an object satisfying any given mathematical constraint. The Ackermann function is an example which is not primitive recursive.

The latter sounds a bit like what Jeremy describes, but his fragment of C++ is much more restrictive: We have to bound the number of operations by a constant before even looking at the data! A primitive recursive program may escalate its computation time quite considerably based on its input.

Okay, that's all theory, in practice, every program running on a physical machine is bounded, because it only has a limited amount of memory, and because we, its operators, won't have arbitrary amounts of patience before aborting what is obviously a crashed program. In fact, our limits on what we see as feasible are so tight, that the afforementioned exponential blow up still makes FHE wholly unattractive.

But wait, why does this research compiler produce logic gates instead of assembly code?

Well, that's the cool thing about this research. Assembly could be used, but logic gates have an essential advantage: There are well-known and rather effective optimization techniques for logic gates! And the speedup gained in this context really is impressive. The article doesn't go into too much detail, but if you search for optimizers for logic circuits you should find lots of fun literature about this stuff!

Still, by far not sufficient to make any of this practical, but interesting nonetheless!

#homomorphicEncryption #FHE

N. Samardzic et al., "CraterLake: a hardware accelerator for efficient unbounded computation on encrypted data"¹

Fully Homomorphic Encryption (FHE) enables offloading computation to untrusted servers with cryptographic privacy. Despite its attractive security, FHE is not yet widely adopted due to its prohibitive overheads, about 10,000X over unencrypted computation. Recent FHE accelerators have made strides to bridge this performance gap. Unfortunately, prior accelerators only work well for simple programs, but become inefficient for complex programs, which bring additional costs and challenges.
We present CraterLake, the first FHE accelerator that enables FHE programs of unbounded size (i.e., unbounded multiplicative depth). Such computations require very large ciphertexts (tens of MBs each) and different algorithms that prior work does not support well. To tackle this challenge, CraterLake introduces a new hardware architecture that efficiently scales to very large cipher-texts, novel functional units to accelerate key kernels, and new algorithms and compiler techniques to reduce data movement.
We evaluate CraterLake on deep FHE programs, including deep neural networks like ResNet and LSTMs, where prior work takes minutes to hours per inference on a CPU. CraterLake outperforms a CPU by gmean 4,600X and the best prior FHE accelerator by 11.2X under similar area and power budgets. These speeds enable realtime performance on unbounded FHE programs for the first time.

#ResearchPapers #HomomorphicEncryption #HardwareAcceleration
__
¹ https://dl.acm.org/doi/10.1145/3470496.3527393

Three days to submit your work and present during the http://FHE.org conference 2023 in Tokyo.

Read the official Call for Presentations here: https://fhe.org/conferences/conference-2023/call-for-presentations

#fhe #realworldcrypto #homomorphicencryption

@alcinnz just a minor fix to your archives: #Belenios implements the #HeliosC protocol (aka. #Helios with Credentials). #CHVote is an other protocol. Both protocols rely on #HomomorphicEncryption.

@alcinnz #HomomorphicEncryption is used in some online #voting protocols like #CHVote https://chvote2.gitlab.io/
or #HeliosC https://hal.inria.fr/hal-02066930/ whose main implementation is in #Belenios
https://www.belenios.org/
but one can found some part reimplemented by others:
- https://github.com/yvesago/borvo
- and my own https://hackage.haskell.org/package/hjugement-protocol

Note however that to enable voting methods based upon comparisons (instead of counting), #Belenios is now experimenting with #mixnets:
https://www.belenios.org/mixnet.html