[HN Gopher] A High-Level Technical Overview of Homomorphic Encry...
___________________________________________________________________
A High-Level Technical Overview of Homomorphic Encryption
Author : ggeorgovassilis
Score : 176 points
Date : 2024-05-05 06:02 UTC (1 days ago)
(HTM) web link (www.jeremykun.com)
(TXT) w3m dump (www.jeremykun.com)
| gigatexal wrote:
| Again 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 wrote:
| for 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.
| oulipo wrote:
| Very nice! Check also the amazing work by https://www.zama.ai/
| noam_k wrote:
| Amazing 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 Phm(X) into
| products X - zi 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
| dataexp wrote:
| I 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 wrote:
| I 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 wrote:
| One related concept is "partially homomorphic encryption" (http
| s://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 wrote:
| You're looking for 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 wrote:
| I 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 wrote:
| This is basically what people do with problems like Private
| Information Retrieval and Private Set Intersection. They use
| some lightly applied FHE as a subroutine, but otherwise hand-
| develop a cryptographic protocol for the specific program at
| hand.
|
| As it turns out, these applications are much more widely used
| than FHE.
| vouaobrasil wrote:
| I 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 wrote:
| How does FHE lead to people getting access to more computation?
| pas wrote:
| (as far as I understand) it makes trustless compute farms
| possible im theory
| vouaobrasil wrote:
| Well, 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 wrote:
| You should reread. It is very obvious why that won't be a
| problem if you sit back and think about it.
| vouaobrasil wrote:
| Okay, I await your explanation.
| AnimalMuppet wrote:
| The existence of homomorphic encryption doesn't give me
| any more money to buy compute time on servers, nor does
| it make compute servers any cheaper. Those are completely
| orthogonal. So, it may make it so that people with money
| can do nasty things on servers undetected, but it
| absolutely does not make it so everyone on earth can.
| Nevermark wrote:
| And to top that off, the ratio in costs for regular vs.
| homomorphic computing, is far greater than the ratio of
| costs for using other's servers, which might be monitored
| for "safe" or "legal" code, vs. just buying and managing
| your own private servers.
|
| So if the problem is simply to hide a computation, that
| is already "solved".
|
| Homomorphic computing enables hiding in plain sight, but
| that's not necessary to simply hide.
| j2kun wrote:
| I think there's a case to be made that FHE will empower
| "laundering" responsibility for using cloud resources for evil
| purposes. But I don't think that will have much to do with
| high-power computation.
| dosran wrote:
| I'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 wrote:
| It is a mistake, it should be x.y = ((x + y)^2 - (x - y)^2)/4.
| j2kun wrote:
| Thanks, fixed!
| H8crilA wrote:
| How does multiplication work in LWE? Let's say in the non-trippy
| variant, the "leveled homomorphic encryption".
| photonthug wrote:
| I'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 wrote:
| My 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 wrote:
| Just 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.
| lagniappe wrote:
| afaik ring signatures can do this also.
| noman-land wrote:
| People 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.
| azeemba wrote:
| I think the AI-model-as-a-service is actually a great use case.
|
| You want to use their AI model but you don't trust them to not
| train on your data so you don't want to send your data to them.
| They don't trust you enough to send you their models.
|
| So you encrypt your data, they compute on your data and send
| you the encrypted result back.
|
| The only problem is that you have turned an expensive
| computation into a exponentially more expensive computation
| jijji wrote:
| what 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 wrote:
| There are chip startups trying to address this exact issue. For
| example, Cornami: 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/sta
| mp/stamp.jsp?arnumber=1006752....
| j2kun wrote:
| Mentioned in the article: because doing it without FHE is risky
| or illegal due to data privacy laws or IP protection or
| similar.
| hundredwatt wrote:
| > 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 wrote:
| > 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 wrote:
| Cf. 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 wrote:
| Unrelated, 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-
| Combina...
| adolgert wrote:
| A select statement, in this case, looks like a ternary in C, "y
| = (x > 0) ? 1 : 0". In FHE with integers, it's evaluated by
| making a large polynomial all x <= 0 become 0 and all x>0
| become 1. Once you have y, you evaluate both halves of the if-
| then but multiply one result by y and the other by (1-y). Then
| add them.
___________________________________________________________________
(page generated 2024-05-06 23:01 UTC)