5 ms·
A High-Level Technical Overview of Homomorphic Encryption
- monero-xmr 2y ago[flagged]
- gigatexal 2y agoAgain my math ignorance screws me, I wish I had more acumen here to grasp it all but this did catch my eye: “ In one example FHE scheme with lightweight keys, a ciphertext encrypting a single integer is on the order of 25 KB, and the special keys are about 0.5 GB.”
- kragen 2y agofor those wondering about the and/xor thing, well, of course a nand b is just 1 xor (a and b), but you can do enormously better than that! it turns out there's a very pretty formulation of boolean combinational logic (i can't bring myself to say 'circuits') called zhegalkin polynomials, in which arbitrary boolean functions are just polynomials in gf(2). i wrote a simple implementation of them in http://canonical.org/~kragen/sw/dev3/zhegalkin.py http://canonical.org/~kragen/sw/dev3/zhegalkin.py.
- oulipo 2y agoVery nice! Check also the amazing work by https://www.zama.ai/ https://www.zama.ai/
- noam_k 2y agoAmazing summary, Jeremy! One nitpick is regarding the double-CRT: you are referring to the RNS encoding, when the original paper[0] uses the term to talk about how polynomials are stored for fast computation. It's a nice philosophical view of decomposing the polynomial Φm(X) into products X − ζi the same way that the integer modulus Q is decomposed into primes. So it's more like one CRT on the coefficients, and another implemented as a DFT. [0] https://eprint.iacr.org/2012/099 https://eprint.iacr.org/2012/099
- j2kun 2y agoThis may be some nuance I'm not quite getting still. You're saying that even if you use the coefficient encoding, one would still have reason to store polynomials in the CRT domain. I agree that would be more performant, but it seems not useful because then your element-wise products only ever correspond to convolutions (as I mention in the article). As far as I can tell, everyone does Double-CRT with RNS encoding, but I may be mistaken.
- dataexp 2y agoI wonder is there is some restricted kind of homomorphic encryption so that the encryption is tailored to be used for certain kind of programs. For example if the program is to compute the average of a list of numbers then some simple encryption could be done just to compute the average and nothing more. Is there some related concept to this idea of the encryption restricted to a concrete computation?
- ngneer 2y agoI think there are special cases, like Yao's millionaire problem, where you compute a simple predicate to compare two numbers. I do not know whether such a notion will save you much, though. Because as soon as you can compute a simple instruction like SUBLEQ you have a Turing complete scheme.
- lowdanie 2y agoOne related concept is “partially homomorphic encryption” (https://en.wikipedia.org/wiki/Homomorphic_encryption#Partially_homomorphic_cryptosystems https://en.wikipedia.org/wiki/Homomorphic_encryption#Partial...). These are encryption schemes that are homomorphic under one operation such as addition or multiplication. For example, you could use an additively homomorphic scheme to compute a sum of encrypted values. This could then be converted into an average assuming you knew the number of values.
- aildours 2y agoYou're looking for functional encryption (https://en.wikipedia.org/wiki/Functional_encryption https://en.wikipedia.org/wiki/Functional_encryption). It lets you compute exactly an encryption of a pre-specified function of the input message and nothing else.
- j2kun 2y agoI think functional encryption is even less well developed than FHE. Most problems can't be expressed in functional encryption, and the security model is really iffy.
- j2kun 2y ago
- vouaobrasil 2y agoI believe that homomorphic encryption is one of those technologies that is too dangerous to develop. It is one step to a path where any person on earth will eventually have access to enormous amounts of computation. Is that a good thing? Well, it means one can do high-powered AI research on chemical and biological weapons or advanced malware by using high-powered compute clusters that they may not otherwise have access to. Moreoever, it will be impossible to detect since the computations themselves are encrypted.
- ramchip 2y agoHow does FHE lead to people getting access to more computation?
- pas 2y ago(as far as I understand) it makes trustless compute farms possible im theory
- vouaobrasil 2y agoWell, more people can buy time on an FHE computer and compute whatever they want on it, like a program that can find even more dangerous viruses, and no one will be able to detect what they are doing because their computations are encrypted. In other words, the data that could give them away is transformed under a homomorphism that disguises that data with encryption so that the nature of the computations is not evident.
- smoothgrammer 2y agoYou should reread. It is very obvious why that won't be a problem if you sit back and think about it.
- vouaobrasil 2y agoOkay, I await your explanation.
- dosran 2y agoI've been following Jeremy's blog for some years now and although I don't always understand everything, I appreciate it for being a relatively accessible look into the research that's going on. > you can implement ciphertext-ciphertext multiplication: x.y = ((x^2 + y^2) - (x^2 - y^2))/4 However this one part confused me - the RHS seems to simplify to y^2 / 2. Is there a mistake here or is this specific to the polynomial fields being worked in? (Or am I being dumb?)
- HappyPanacea 2y agoIt is a mistake, it should be x.y = ((x + y)^2 - (x - y)^2)/4.
- j2kun 2y agoThanks, fixed!
- H8crilA 2y agoHow does multiplication work in LWE? Let's say in the non-trippy variant, the "leveled homomorphic encryption".
- photonthug 2y agoI’ve been trying to puzzle out the market for this kind of technology. Making truly private data actually useful while retaining the privacy would of course be incredible and the use cases are obvious. But the people that have big data generally are not interested in privacy at all. Academic interest in fhe is understandable since it’s fascinating, but why does industry care? Is this just hedging their bets for if/when the future brings stronger data regulation?
- hackpelican 2y agoMy undergraduate thesis project attempted to use homomorphic encryption to create a voting system where any party could verify the final tally count while keeping ballot secrecy.
- drdaeman 2y agoJust like the other industries - are politicians generally interested in changing the status quo that works for them nicely already? Based on the history of use of auditable voting systems use in real-world elections, it feels like barely anyone cares.
- hackpelican 2y agoYeah probably not. Many established players in the game already and either way, adding fancy technology isn’t going to help the general public feel more trust in the system.
- lagniappe 2y agoafaik ring signatures can do this also.
- noman-land 2y agoPeople are (very) slowly realizing that plastering their data all over third party clouds is dangerous for their own privacy and safety. Hopefully we can make data breaches existentially costly for companies so they stop fucking around and take privacy seriously. People want FHE, they just don't know it. It solves so many problems and when it works really well, it will become a selling point for customers. Companies that don't take data privacy seriously will rot.
- jijji 2y agowhat are potential benefits and use cases of writing a program using FHE if the program is literally a million times slower than a similar program without FHE?
- djcooley 2y agoThere are chip startups trying to address this exact issue. For example, Cornami: https://cornami.com https://cornami.com. There is also a lot of research into lowering the power/compute penalty of FHE. See ISSCC 2023: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10067522 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1006752....
- j2kun 2y agoMentioned in the article: because doing it without FHE is risky or illegal due to data privacy laws or IP protection or similar.
- hundredwatt 2y ago> Much of the FHE industry is focused right now on the subset of applications where legal hurdles make the two available options “slow, but compliant” and “fast, but incurs prison time.” Anyone have any examples of these applications?
- alexey-salmin 2y ago> For example, it is not be possible to write an FHE program that uses fewer instructions than the program’s worst-case input. Doing so would reveal information that the input is not the worst-case, which contradicts the security of the cryptography. Instead, an FHE program must eagerly compute all branches of if-statements, and then use a select statement to decide which result should be used. What exactly is "select statement"? Curious to know how to select a value without giving away what this value equals to (even in encrypting form). Otherwise I assume it would give away as much as seeing which branch was taken.
- j2kun 2y agoCf. https://llvm.org/docs/LangRef.html#select-instruction https://llvm.org/docs/LangRef.html#select-instruction No branching, and the hard part in FHE is to evaluate this when the bit is encrypted. The results are the same type, so all you see after the op is that the result is a ciphertext.
- sn9 2y agoUnrelated, but have you heard of Distributed Computing Through Combinatorial Topology? Seems up your alley. Distributed Computing Through Combinatorial Topology: https://www.amazon.com/Distributed-Computing-Through-Combinatorial-Topology/dp/0124045782 https://www.amazon.com/Distributed-Computing-Through-Combina...
- j2kun 2y agoThis seems up my alley, but I suspect the techniques in that book aren't used, since I have spent a lot of time chasing down applications of computational topology only to find they weren't as useful as advertised. Are you aware of anyone who uses these methods? Would be good for my book Practical Math
- sn9 2y agoI've only skimmed my way through it, but it seems like the bulk of the research started in 2000 so it would be fairly new. It might still be just academic research at this point, but it at least seems to show some pretty interesting abstractions with which to analyze systems. It came out in 2013, so if it is used in industry after that point, the book wouldn't say and you'd have to go hunting for whitepapers that cite the research probably.