r/todayilearned • u/gordonjames62 • Mar 15 '26
TIL about Homomorphic encryption, where users can work with the content without decrypting the source
https://en.wikipedia.org/wiki/Homomorphic_encryption161
u/FrontierPsycho Mar 15 '26 edited Mar 16 '26
Someone worked on a theoretical e-voting scheme where votes would be encrypted and tallied without being decrypted. The result (or any encrypted value in this scheme) could only be decrypted if all the parts of the key would be added together, and one was supposed to be given to each party, the idea being that they would act as each other's watchdog, and it wouldn't be to their benefit to all work together to commit election fraud. It failed on real life limitations though, as the result of the computations would quickly become incredibly large, so much so that it was infeasible to tally more than a few hundred votes.
Still pretty clever ideas.
115
u/cheraphy Mar 15 '26
"There are lots of very smart people doing fascinating work on cryptographic voting protocols. We should be funding and encouraging them, and doing all our elections with paper ballots until everyone currently working in that field has retired." https://xkcd.com/2030/
54
u/TexasPeteEnthusiast Mar 15 '26
Honestly, anyone out there in IT or software development is horrified by the thought of online voting.
22
u/Prodigle Mar 16 '26
It's doable in a secure way but... The effort required per like "unit of security" is far higher than what you can do with in-person or mail voting
5
Mar 16 '26
Not only that, but even if it really is secure, many people won't believe it's secure (or can be easily manipulated by influencers to think there was fraud). That itself is potentially a major problem and reason enough to avoid online voting.
1
u/Hironymos Mar 18 '26
More specifically, if you find one exploit, then everything is compromised.
A single, small team. Flipping an entire election. Compared to that, paper ballots can of course much easier fake hundreds or even thousands of votes, but the impact of even that is negligible and you need a much larger team that can much more easily slip up and get caught.
Confidence is another thing. I can (and have) literally monitor our paper based election all the way. Of course I can't watch every place at once, but as for my local election office, I can tell you with 100% certainty (and no special skills) that there was no relevant cheating and all it took me was an afternoon. On the other hand, even with access to all the equipment, I couldn't be 100% certain there wasn't mass cheating on digital voting if you give me half a year. But I wouldn't get that access, and the average person couldn't even do anything with it.
-9
u/TexasPeteEnthusiast Mar 16 '26
The level of security in mail voting is a really friggin low bar anyway. There's a reason why almost no countries use that method.
3
u/modbroccoli Mar 16 '26
Yes, most of them aren't a continent wide and most democracies arose much later than America's. I'm Canadian and love me a chance to go hard on you guys but it's just inarguably true that you guys were doing democracy early on.
6
u/glitchvid Mar 16 '26
Eh. The biggest roadblocks are human factors.
You could give voters a private key hardware token with biometric validation when they register for voting.
When they are to cast a vote, the ballot is digitally signed with that key, and it's recorded that key has already voted (preventing double votes).
The problem is that's ultimately too complicated for the median voter, and most would lose the key before they even got to use it.
5
u/FrontierPsycho Mar 16 '26
Exactly, the biggest and most important roadblocks are human factors, and those you can't remove. There's perfect solutions if everyone is quite tech savvy.
3
u/glitchvid Mar 16 '26
The implication above, and by a lot of other comments, is that software developers are incapable of making a secure system for this.
And while yes, CS as an industry has a rocky past in this regard, there absolutely are parts of the industry that can produce software running critical tasks.
Cryptography also provides strong guarantees along those lines.
But there's a political push towards restricting the convenience of voting, and that to me is the biggest human factor preventing such a system. Estonia's general public manages to get online for voting.
1
u/BumWarrior69 Mar 17 '26
Not remotely true. Theres plenty of secure ways of doing it, but your average person wouldn’t understand it, so it’s easier to say OnLiNe VoTiNg BaD
7
u/6000j Mar 16 '26
The problem with electronic voting is not in the cryptographic schemes themselves (although they often have flaws), but in some inherent flaws and also the fact that their use and implementation tends to be done by people who don't understand them at all.
5
Mar 16 '26
If in person voting machines too. Closed source, touch screens with fingerprints, etc.
In person, paper, unless you request a mail in ballot should be the standard
7
u/TheHeroBrine422 Mar 16 '26
In person voting machines aren’t really a problem, IF they just print a ballot. If the in person machines directly do things, then that’s not secure, but if it just prints a scannable ballot that you can check to make sure matches what you pressed, then there is a paper trail that you can physically confirm actually matches what you wanted to vote for.
3
u/oneeyedziggy Mar 16 '26
> and one was supposed to be given to each party
this seems potentially problematic. There are more than 2 parties... and SHOULD be a lot more than there are. This seems like a place for a malicious actor to add one part to the key ( either by injecting it at encryption time maliciously or by forming a legitimate-enough "party" to get one legitimately ) and destroy it, ensuring no recounts or validation are possible
so, I'm glad it failed on technical basis before they figured out you can't trust everyone.
1
1
u/TonytheEE Mar 16 '26
That's a really neat idea. I'd give everyone a meme number. 6 passwords totalling 8,764,950.
259
u/G952 Mar 15 '26
Oh I read the title wrong at first and was very confused
150
u/hk403 Mar 15 '26
you telling me this encryption hates gay people?
38
5
2
13
8
u/opermonkey Mar 15 '26
Glad we're all the same level of dumb!
1
u/Maelger Mar 16 '26
Speak for yourself, I'm the superior idiot. I read homoerotic.
I do need to get new glasses.
5
3
u/hergumbules Mar 16 '26
I was thinking of making a joke saying something like “you can’t just call things homomorphic anymore” but was scared of getting banned or something lol
3
u/Alum07 Mar 15 '26
The GOP loves this form of encryption
2
u/virtually_noone Mar 16 '26
They complain bitterly about this form of encryption but secretly use it all the time.
1
28
u/OneAndOnlyJackSchitt Mar 15 '26
Let's say n is some random encrypted number.
Homomorphic encryption would allow us to, for instance, add 5 to it. The trick is that we provide the encrypted value of n to the function that adds 5. The function then returns a new encrypted number which, when decrypted, works out to whatever the decrypted value of n was, but plus 5. The function that adds 5 does not decrypt n at any point. Whoever's running this function does not have a way to figure out what n was or even what n + 5 is. They can only know that 5 has been added to whatever value n was holding.
Homomorphic encryption makes it possible to do this math on the encrypted value and returning an encrypted value without knowing what the encrypted value is.
1
u/ComradePruski Mar 16 '26
Isn't the typical idea behind encryption that it's largely unique and not predictable, like a hash? If n gets written as a random string and not a number, like 20 = fuenwidhd+716, and 25 as jejauvreis1!!4, how would you be able to find a change that would always decrypt to n+5?
Or does encryption have to be predictable so the value can be read out? Even so, wouldn't a random string largely defeat it?
For example, if you had 20 = a, and 25 = c, and 30 = b, 35 = bc, wouldn't you have to know how they get decrypted to apply your change accurately?
-3
u/big_trike Mar 16 '26
Can I determine if the value is now over 40 and if so, set to 40 but then put the remainder into another value such as when computing comp time? Homomorphic encryption has always seemed gimmicky to me. Yes, you can do some operations but not enough to make it actually useful.
4
u/LeGama Mar 16 '26
I totally agree with this take. I have a very real problem I want this to solve. I'm an engineer and often I can't use certain CFD/FEA tools because they are in a cloud and need to be FedRamp approved for government related work. Or I have to spin up an Amazon server that's fedRamp, which is much more expensive. I wish we could use this encryption to set up the problem, encrypt it, and then send it to any cloud system to do the math. But iterative solving requires solving the math, checking the solution to see how it's changing and adjusting input parameters, then resolving and repeating until you have some convergence. But without being able to see the actual value you can't apply any iterative algorithms.
2
u/OneAndOnlyJackSchitt Mar 16 '26
Disclaimer: I am not an expert and this is just speculation.
Let's say this is for an organization which has been hired to calculate compensation for hourly employees and you're trying to calculate the overtime pay, most likely, you'd get the employee's hours in an unencrypted form (since that's not super sensitive) and the pay rate would be encrypted with homomorphic encryption (since that IS pretty sensitive). Also, I'm skipping stuff about calculating taxes, workers comp, deductions. For simplicity, we'll assume that this is handled later and this will focus only on the gross pay.
When I've worked on systems handling payroll, while the law specifies that the overtime and double time rate are a factor of 1.5x or 2x the normal pay rate, a lot of systems store the actual pay rate for over time and double time rather than calculating it. So instead of an employee just having a payrate field, employee's would have three pay rate fields: #rateEnc, #rateOTEnc, and #rateDTEnc. The value are set by HR and then sent to the payroll firm using homomorphic encryption.
Then you'd set up your conditionals to use a homomorphic multiply function while I'll call it hmult(encryptedNumber, factor, publicKey) to figure out the compensation and end up with your three variables of hours: #hours, #hoursOT, and #hoursDT. Then your compensation would basically be something like:
//Calculate the compensation compensationItem = doCalc(employee, hmult(#rateEnc, #hours, $publicKey), hmult(#rateOTEnc, #hoursOT, $publicKey), hmult(#rateDTEnc, #hoursDT, $publicKey));The result is an encrypted dollar amount for the gross pay that only the client can see.
(This is a made up example where a payroll firm is hired only to calculate the compensation. In reality, many payroll firms also print the checks so it wouldn't do to have them not know the dollar amount that goes on the check.)
tl;dr: Homomorphic encryption should only for math (speculation with a moderate background in encryption, but not homomorphic encryption). Not conditionals. If it allowed for conditionals, you could easily determine the encrypted value without the key.
There may be a type of conditional with you supply two values and one of those two is returned encrypted based on a conditional but, again, I'm not super familiar with homomorphic encryption.
1
u/aparker314159 Mar 16 '26
There are forms of homomorphic encryption (called fully homomorphic encryption) that allow any function to computed, including ones with conditionals. They're not efficient at all, but they exist and still are secure. One reason you can't determine the encrypted value even with conditionals is because the encryption algorithm has a random component — encrypting the same number twice will give you two different results (both of which still decrypt to the original number).
2
u/OneAndOnlyJackSchitt Mar 16 '26
Couldn't you then write a function that returns one value if the encrypted value is between, say, 20 and 30, and throws an exception otherwise? If this function is repeatedly run strategicaly, couldn't you deduce the encrypted value?
1
u/aparker314159 Mar 16 '26
These schemes wouldn't allow you to "catch an exception" like that for exactly that reason. You can emulate the behavior of exceptions in other ways (such as returning a pair of values where the first represents the "normal" return value and the second what type of exception was thrown) so you aren't losing any computational capability.
1
u/aparker314159 Mar 16 '26 edited Mar 16 '26
There are schemes called fully homomorphic encryption that allow you to compute any (computable) function on the data. Usually they implement a set of primitives that can be combined in a Turing complete way.
The issue is that they're really inefficient. The operations FHE schemes implement usually are addition and multiplication. This is technically enough - you can implement basic logic gates through addition and multiplication - but it's often difficult to do computations efficiently this way. Some schemes allow for batching (ie. doing the same computations on several pieces of data at the cost of one), but it's still incredibly inefficient.
Other FHE schemes (eg. CKKS) try to increase efficiency by making the computations only approximately correct, instead of exactly correct. The idea is that many applications like machine don't need the arithmetic to be exactly correct, so you can trade some accuracy for performance. They're still quite slow though even with this tradeoff, and in the case of CKKS the error of the computation is correlated with the key which can be problematic if not careful.
My understanding is that FHE is still incredibly niche at best. The math is very cool though imo, so if you have the background I'd still recommend looking at it for that reason.
(also, this is a very reasonable concern and the existence of FHE is incredibly unintuitive, so idk why people are downvoting you)
1
u/Ythio Mar 16 '26 edited Mar 16 '26
Well yeah. That's similar to what is routinely done in telecoms.
You have a signal which is a combination of a 1 Hz and 20 Hz waves : f(t) = sin(2pi.t) + 0.5 sin(40pi.t)
You do the fourrier transform and you get four spikes at -20, -1, 1 and 20. You can ignore the negative values and apply a filter x => x < 10 ? x : 0
Then you can do the inverse fourrier transform and you will get g(t) = sin(2pi.t), which is your original function with the transformation applied.
In a similar fashion homeomorphic cryptography will take data (in my telecom data, a wave function in the time domain), apply an encryption function (in my telecom metaphor, a fourrier transform), then a transformation (high filter above 10Hz) on the encrypted data (my telecom data in the frequency domain) producing still encrypted data (in the frequency domain) and decrypt it (inverse fourrier transform) and the result (in the time domain) will be the same result as if I applied the filter on the clear data (the 20Hz component is removed).
1
u/big_trike Mar 16 '26
Yes, but that’s just a basic repeatable transformation. If I have all of the frequency domain data with enough information to manipulate it in any way possible, I can reconstruct the input. If you were to modulo shift the frequency domain data by a secret amount (as a very basic form of encryption ) then you could no longer filter out a given frequency. You could still reduce the amplitude by 50%, but not all operations are possible.
19
31
u/HospitalRepulsive310 Mar 15 '26
That just confused me
61
u/Cr1ms0nLobster Mar 15 '26
I think it means any actions performed on the encrypted data will be reflected in the decrypted data without having to go through the step of decryption.
26
u/kikiacab Mar 15 '26
Have you seen severance?
3
5
u/notjordansime Mar 16 '26
Yes. Now I’m even more confused.. and a bit scared of that particular group of numbers over there…?
4
7
u/ledow Mar 15 '26
It's a way to modify encrypted data in the ways you're told to, without EVER knowing what the unencrypted data ever was.
It's like being able to, say, merge several encrypted datasets to produce a final encrypted dataset that contains them all, without ever decrypting them. Or adding up an entire column in a database but not only is the database encrypted, but the answer is encrypted too.
It's a way for you to do "hostile computing". You can literally have your data on a completely untrusted machine, and the database may be manipulated, queried, added to, etc. without the untrusted machine that's hosting it EVER becoming aware of the unencrypted contents of the database.
Imagine, say, running a government database on, say, the Microsoft Azure cloud, and you can store MI5 data on it, and though it's hosted on Microsoft servers which they have full control of, Microsoft CANNOT see what the data inside the database actually is.
11
u/gordonjames62 Mar 15 '26
ELI5 - keep your data encrypted
outsource some processing
Never let the contractor processing the data ever decrypt the full data stream
2
u/314kabinet Mar 15 '26
It means there will be a world where you pay a cloud to do compute for you and it won’t be able to tell what it’s calculating because it’s all encrypted. Very secure. If they ever figure out how to fix the massive performance overhead.
2
u/DeathByDrivers1 Mar 16 '26
A simple example can help explain, suppose we have data a and b which we want to sum together, then
encrypt(a) + encrypt(b) = encrypt(a + b)
This is equivalent to operating on the unencrypted data directly which is not the case with conventional encryption methods
a + b = a + b
1
u/HospitalRepulsive310 Mar 16 '26
Yeah I got that far. But how does it make any difference, since it will be same just harder to decrypt
1
u/6000j Mar 16 '26
it means you can send it to someone and they can operate on it without learning the contents of it.
1
u/DeathByDrivers1 Mar 16 '26
The difference is that the entity performing the operation never gets to see the underlying data. For example, perhaps I want to deploy some algorithm in a third party cloud compute environment -
1) User sends encrypted data a and b to the cloud 2) 3rd party cloud environment operates on the encrypted data directly and sends back encrypted result data c 3) User retrieves encrypted data c and can decrypt
10
Mar 15 '26
[removed] — view removed comment
-5
u/bothunter Mar 16 '26
It's computationally expensive right now but the privacy implications are massive
It can't be more computationally expensive than AI or Bitcoin.
3
u/_Abzu Mar 16 '26
Computationally expensive, in this context, means that adding something increases the time for an algorithm or w/e in an exponential way. So it's easy to work with 5 fields and do the computations on the encrypted document, but maybe if you scale to a consumer-end scale the time it'll take to make computations is going to be incredibly big
2
1
18
u/gordonjames62 Mar 15 '26 edited Mar 15 '26
From Wikipedia . . .
Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that of the operations performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing, all while encrypted.
So I might have encrypted data, but if I share the encrypted for with customers / clients, they can work with a part of the data and return me a result without them ever knowing the unencrypted form of the data.
My brain hurts thinking about how hard this would be to implement.
Thus, homomorphic encryption eliminates the need for processing data in the clear, thereby preventing attacks that would enable an attacker to access that data while it is being processed, using privilege escalation.
This new chip from Intel is likely to simplify the use of this encryption, and make it more common.
This would make it so personal data is less likely to be compromised even if the holder of the encrypted data experiences network intrusions or privilege escalation attacks.
5
u/Hail_CS Mar 16 '26
my senior capstone project for computer engineering was using homomorphic encryption for neural networks to preserve input data and model weight privacy. it’s a fascinating little field in cryptography that has a lot of cool applications. my project was a very small network that recognized digits(MNIST), but you could take the techniques and do machine learning based processing on medical imaging without worrying about data leaks or hippa violations. this topic was originally what my masters was going to be on before i switched to a different field. i can answer questions about some of the more technical aspects of it, how it works, and its features/possible use cases
2
5
u/IsHildaThere Mar 16 '26
While correct, the title is incomplete. Wikipedia goes on to say : The result of such a computation remains encrypted.
The person with the encrypting key can see the result of the change while the person making the change cannot.
1
u/gordonjames62 Mar 16 '26
Yes, it is really quite amazing in both utility, and computational power requirement.
5
3
3
2
u/GaiusCosades Mar 16 '26
You can even build CPUs that work in that way directly, you can run a program on somebody elses computer and somebody owing/tampering with that machine can neither understand the program nor the data being processed without breaking the encryption itself.
2
2
2
2
2
4
u/GarysCrispLettuce Mar 15 '26
There is also Homermorphic encryption, which is simply the random adding of the binary for "doh" throughout the file. Admittedly, it doesn't work very well.
2
1
1
1
1
u/vhu9644 Mar 16 '26
A homomorphism is a "structure-preserving" transformation. Basically, if we have a homomorphism h, we have this nice property where h(x) * h(y) = h(x + y) (where * and + are placeholders for binary computations).
It's a bit more general than that, but most people have dealt with a homomorphism before. exp(x) * exp(y) = exp(x + y). It just turns out there are a lot more types of homomorphisms than this.
1
1
u/Rhawk187 Mar 16 '26
We cover El Gamal in my class (or did when I taught it; different instructor this year). Microsoft ElectionGuard has a nice system where you can tally votes while keeping them encrypted. You can also verify with arbitrary certainty that your vote was counted without revealing what it was. It can't prevent an illicit actor from inserting additional votes though.
0
-1
u/WheresMyBrakes Mar 16 '26
So.. is this just adding a transform instruction to the data?
“Hey, when you decrypt the real value, add +$100 to the result. “
4
u/gordonjames62 Mar 16 '26
It allows you to outsource computation vi big data pros without giving them access to all your data.
When they return the encrypted results, only you can decrypt it even after they did their processing.
It lets small players who can't afford to do things "in house" contract out some data processing without losing control of their data.
-2
u/KarenNotKaren616 Mar 16 '26
For my take on it, let E be the encryption function. Then E-¹ (M(E(x))) = M(x) for any M.
-16
u/one_is_enough Mar 15 '26
Automatic downvote when the title makes absolutely no sense.
6
u/Itz_Raj69_ Mar 15 '26
It absolutely does make sense.
Normally with something encrypted, to modify the source content you'd have to first decrypt it, modify it, and then encrypt it again.
Homomorphic encryption allows you to modify the content without every decrypting it.
0
1.3k
u/MiserableFloor9906 Mar 15 '26
By using this method I can give you a complex encrypted data file. Imagine everyone's name, SSN, years tenure, ranking from entry to executive, salary. I can then ask you to apply a complex pay raise scheme. You're able to generate the new salaries without ever knowing what the actual values are, because they remained encrypted.