IBM completes successful field trials on Fully Homomorphic Encryption

[Pickles von Brine]

Quote

FHE is a type of encryption that allows direct mathematical operations on the encrypted data. Upon decryption, the results will be correct. For example, you might encrypt 2, 3, and 7 and send the three encrypted values to a third party. If you then ask the third party to add the first and second values, then multiply the result by the third value and return the result to you, you can then decrypt that result—and get 35.

You don't ever have to share a key with the third party doing the computation; the data remains encrypted with a key the third party never received. So, while the third party performed the operations you asked it to, it never knew the values of either the inputs or the output. You can also ask the third party to perform mathematical or logical operations of the encrypted data with non-encrypted data—for example, in pseudocode, FHE_decrypt(FHE_encrypt(2) * 5) equals 10.

Fully Homomorphic Encryption offers many possibilities that Secure Encrypted Virtualization does not, however. Since all mathematical and logical operations can be built from additive and multiplicative operations, this effectively means that any computation can be performed upon FHE encrypted data. This opens a dizzying array of possibilities: one might search a database without ever letting the database owner know what you searched for or what the result was. Two parties might discover the intersection set of their separately held datasets without either party revealing the actual contents of their data to the other.

Something rather interesting to be honest. The fact you can search a database that is encrpyted for data without actually knowing what that data is is... mind boggling. Some really smart folks over at IBM. Any of you get this stuff? My brain broke halfway through. 

Source

[Jurrunio]

9 minutes ago, Pickles - Lord of the Jar said:

Something rather interesting to be honest. The fact you can search a database that is encrpyted for data without actually knowing what that data is is... mind boggling. Some really smart folks over at IBM. Any of you get this stuff? My brain broke halfway through. 

Source

If request sent to the database is already encrypted, then since the database itself doesnt hold the solution to decryption, the owner cannot know what the request asked for.

[rcmaehl]

I can see the API flags now

 

EncryptData(https://server1/encrypt?=<data>&flags=NoHomo,SHA256)

[Bananasplit_00]

Sounds pretty cool at least, not sure how widely useful it is but hey its cool at least

[Kisai]

5 hours ago, Pickles - Lord of the Jar said:

Something rather interesting to be honest. The fact you can search a database that is encrpyted for data without actually knowing what that data is is... mind boggling. Some really smart folks over at IBM. Any of you get this stuff? My brain broke halfway through. 

Source

Well that has benefits for "not sharing" private information. Someone going select * from table doesn't end up with information you can't use, theoretically. 

 

It would probably be useful for PCI DSS and HIPAA, where you really don't want anyone to know what the data is before doing something with it. Let's say, theoretically, you need an algorithm run on someone's x-ray's, you could send the data, do what is needed, and the owner of the algorithm machine never sees it.

[nick name]

4 hours ago, rcmaehl said:

I can see the API flags now

 

EncryptData(https://server1/encrypt?=<data>&flags=NoHomo,SHA256)

Elegantly done.  Bravo.

[Trik'Stari]

So is this supposed to be more, or less secure than traditional encryption?

 

"For example, you might encrypt 2, 3, and 7 and send the three encrypted values to a third party. If you then ask the third party to add the first and second values, then multiply the result by the third value and return the result to you, you can then decrypt that result—and get 35."

 

It would seem to me, that if someone snooping were to simply get a hold of the instructions, and the final result, they can just work backwards to determine the original values of the encrypted data?

[Trik'Stari]

12 minutes ago, gabrielcarvfer said:

It is more secure. The important part is that the third party know the operations but can't work back the original and/or resulting value, unless it can break the cryptography itself.

If you know the operations and their order, and have the end result, you should be able to work backwards to figure it out.

 

I feel like you'd need to encrypt the operations and their order, and send them to the second party, for this to be secure.

 

X*Y=8

 

It could be 2*4, or 1*8, or 4*2. While yes, it is still somewhat obfuscated, it still seems less secure to me. Although I suppose adding more operations could potentially create more possible outcomes.

 

X*Y-B=8 for instance. I'm no math wiz, but I'm guessing that has far more possible answers?

 

[colonel_mortis]

By the formal models that are currently used to reason about the security of encryption protocols, homomorphic encryption is less secure (in a formal sense) than traditional non-homomorphic encryption, because by design you can't check whether the message has been tampered with - it's designed so that you can "tamper" with it. You're not going to see this in most existing conventional uses of encryption, for that reason and because it offers no benefits there.

 

One interesting application of this is in verifiable electronic voting. One possible scheme (off the top of my head) would be

• I encrypt my vote using homomorphic encryption, and submit that encrypted vote to the central server
• The central server combines my vote with the current total, and publishes the current total as well as all previous totals
• I can verify that my vote was counted by performing previous_total ⊕ my_vote, and checking that it matches current_total, but nobody else can tell what my actual vote was (except the holder of the encryption key)

 

The applications of homomorphic encryption are pretty niche, but it is a powerful tool for those applications.

[Pickles von Brine]

23 minutes ago, colonel_mortis said:

By the formal models that are currently used to reason about the security of encryption protocols, homomorphic encryption is less secure (in a formal sense) than traditional non-homomorphic encryption, because by design you can't check whether the message has been tampered with - it's designed so that you can "tamper" with it. You're not going to see this in most existing conventional uses of encryption, for that reason and because it offers no benefits there.

 

One interesting application of this is in verifiable electronic voting. One possible scheme (off the top of my head) would be

• I encrypt my vote using homomorphic encryption, and submit that encrypted vote to the central server
• The central server combines my vote with the current total, and publishes the current total as well as all previous totals
• I can verify that my vote was counted by performing previous_total ⊕ my_vote, and checking that it matches current_total, but nobody else can tell what my actual vote was (except the holder of the encryption key)

 

The applications of homomorphic encryption are pretty niche, but it is a powerful tool for those applications.

Interesting. Thanks for the insight!

[mr moose]

2 hours ago, VegetableStu said:

i'm having trouble trying to imagine the use of this ,_,

 

Storing passwords without actually storing passwords maybe?

 

@colonel_mortis  does this lead us to electronic voting or are we still miles from that actually being secure?

[colonel_mortis]

7 minutes ago, mr moose said:

 

@colonel_mortis  does this lead us to electronic voting or are we still miles from that actually being secure?

I don't think I'm really qualified to answer that (my understanding of it is extremely superficial), but if I had to answer I would say that electronic voting has gone ahead without this in some places, and without having looked at the specifics of this approach I expect that it still requires trust at some points in the chain (assuming that it's symmetric encryption, the encryption key would need to be stored in the voting machines, which have historically had shockingly poor security and requires trust at that first step of knowing that your vote has been encrypted correctly). Even if a system is provably secure, it's a whole other issue to actually convince the general public to use them (and proven security is limited to the design of the system rather than the actual implementation, which regularly results in vulnerabilities).

18 minutes ago, mr moose said:

Storing passwords without actually storing passwords maybe?

That problem is pretty well solved already - hashed passwords cannot be inverted to the original password, but can be used to check that the password you entered was correct (by hashing the input and making sure it matches). I don't think homomorphic encryption would allow improvements on that model - it's pretty much mathematically optimal for that use case as it is.

[Tech_Dreamer]

totally read that last part of the title wrong.

[The1Dickens]

17 hours ago, Trik'Stari said:

If you know the operations and their order, and have the end result,

But you don't know the results. It is also encrypted. Your equation will look like X+Y*Z=A

 

As they said:

18 hours ago, gabrielcarvfer said:

The important part is that the third party know the operations but can't work back the original and/or resulting value,

And the article says:

23 hours ago, Pickles - Lord of the Jar said:

Upon decryption, the results will be correct.

And

On 7/31/2020 at 9:14 AM, Pickles - Lord of the Jar said:

return the result to you, you can then decrypt that result—and get 35

 

[Kisai]

3 hours ago, VegetableStu said:

on the topic of potential uses in digital elections: is this prone to one-way ballot stuffing? o_o

There would need to be multiple stages to do electronic voting of any sort. Below is kinda a gross oversiplification, but basically the cryptographic aspects involve looking through databases for specific keys (such as the name and face in one database, name and tax return value in another)

 

Stage 1: Verifying the voter exists. So you need two forms of "ID", preferably the voter's state/federal tax return and their DMV or Passport. This has to be done in person to create the initial digital voter roll. If you have facial recognition, you can just have the voter use their camera phone and take a picture of themselves, and the backend process will check the DMV or Passport database, go "yup this person is entitled to vote digitally", and then the query the tax return database and ask the voter how much they earned that year on their tax return. If both align to the same person, then that person is entitled to vote electronically. If they didn't file a tax return, or have no passport/dmv, then they will need someone to vouch for them when they go vote in person. This is why paying taxes should automatically enroll people to vote and only an "opt out" should exist for people who do not vote for religious/personal reasons. Note no registration of address, that comes later.

 

Stage 2: 

Once verified for electronic voting. When an election is being held, your ISP gets involved. To determine you are voting for the right area. The ISP takes the place of the "utility bill" proving you live there. So if you are going to vote from your desktop, you must vote from your desktop that is actually connected to your billing address. The ISP will send (without the customer's info) a list of addresses (preferably the GPS coordinates, not the actual street addresses) that wish to electronically vote to the state voting server to determine which version of a ballot to obtain. When the user then hits stage 3, they will be presented with presumably the ballot that applies to where they physically reside.

 

Stage 3: The digital voter roll token and the digital ballot are presented to the voter. The voter picks whatever they want to vote for, including "intentionally spoil this ballot", each ballot is timestamped with a one-way hash, and the voter is "checked off" once they digitally seal the ballot with a key in a second database. Once sealed, the voter can not vote again* in this election, and the ballot is handed to the real time tabulator to count the "in" votes. Once polls close, then the ballots are unsealed and the key in the second database used to decrypt the ballot's and count them. If the "in" ballots don't match the "out" ballots then each key is used to look up the ballot and any ballots without matching keys are considered spoiled. If there are duplicate keys, then the timestamp's are checked against the actual time they were placed "in", and theoretically once you vote, you can't change your vote, but if there was a mistake made by the voter, it would be possible (eg the "do not hit reload".) Only the first vote counts.

 

Stage 4: The central tabulator then reports the results of the digital vote, and then uses it with the vote-in-person (eg traditional voting) results to determine if votes should be recounted.

 

So for example, let's say that the digital voting area Q has 300 people, had 100 votes for A and 100 votes for B and 0 votes for C, and the traditional voting results in 10 votes for A, 100 votes for B, and 2 votes for C. You count the total and check how many people were registered to vote (eg all digital votes were registered) and then look for either duplicate votes, or what would normally be called in the US, a provisional ballot. 

 

Considering that in most states, around 20% or more of the population might not even be registered, you still need to be able to count them if they do decide to turn up and vote.

https://ballotpedia.org/Voter_registration

 

Provisional ballots are usually the first to be thrown away in US elections, so you really want as few of those as possible. But how do you know someone didn't vote electronically, but then showed up somewhere else to vote provisionally?

 

* That's the entire problem behind voter fraud. You need a way to ensure that all votes count, but you can only do that if the "in-person" voting system uses the same database as the electronic one, which means what you are effectively doing is registering the voter at the time of voting, and since the reason they're there and not at home voting, is because of some issue with registering, that means someone needs to actually vouch that the person is who they say they are and where they live. The registration database will already tell the election official if they have already voted, just not who they voted for, and if that's the case, they should be refused to vote in person as well.

 

Because Americans are hesitant to adopt any kind of ID, you'll run into situations where people turned 18 that day, people who moved to the area that day and don't have anything saying who they are and where they live, and under most normal election circumstances, the people working the polls would just ask that they get their employer or landlord to vouch for them. However no system will be 100% perfect and it may very well mean that people who move a lot, or travel for work, might only be able to register to vote when they are home, and can only vote electronically when the election happens, making geographical checks difficult.

 

[Kisai]

9 minutes ago, gabrielcarvfer said:

 

 

TL;DR: Electronic voting is just as shit-show as paper voting, but way more complicated. AFAICR, the German supreme court blocked electronic voting due to the lack of transparency for layman people.

Yep, it's just unfortunate that there are way of improving the situation but it literately took a pandemic to reconsider.

 

Like to put it bluntly, if everyone has a cell phone, a text message to various numbers would register a vote, and the phone would receive a message back verifying who they voted for. That works in that situation because cell phones are required to be registered to a billing address. So the underlying process of that SMS vote would be that "one person at X address voted for Y", and unless you're keeping census records for addresses for use with voting, or require cell phone numbers to be present on tax documents, you have no way to know the maximum number of votes from that address. You also can't trust the tabulator or the ISP in that case to not tamper with it (eg making SMS unavailable to people known to vote a certain way against the carriers interests.)

 

 

[Sauron]

This is actually extremely cool

[Kisai]

4 minutes ago, gabrielcarvfer said:

There are more problems on that:

- Telcos don't actually check the source of calls or SMS messages, similarly to IP spoofing. Bunch of ministers, judges, prosecutors and congressmen had their messages stolen as "hackers" used this fact to get their two-factor authentication codes by abusing this flaw.

- SMS doesn't guarantee the delivery of the message. Not really adequate for voting.

- Tracing the vote back to the voter implies the voter has no privacy (unless it is encrypted by the voter key, which in real life would probably be generated by the election organizers and could be leaked).

When I worked for AT&T Wireless, there was literately a html web portal to send text messages. Nothing complicated. that's why SMS as 2FA is really a mistake. An election run on one would be a mistake as well. But as far as using it as "key" for a vote, I still think it could work. eg whatever electronic process is used to encrypt the ballot generates a number that you text to the vote tabulator, that, at the very least makes it so someone can't just "ballot stuff" by using a stolen database of phone numbers to spoof.

 

Like with the US, really the US has to get past the not having national ID cards debate. The US has one, it's called the passport. Using a passport, drivers license or SSN should never be used outside the purpose they were designed for (Passports for national border controls, drivers licenses for state permission to drive, and SSN's should never, ever have been used for anything but tax documents.) If everyone was issued a national photo ID card that was used primarily for all federal services (eg voting, tax payments, welfare/food-stamps, medicaid) that was kept in sync with the passport, that solves that. Then if you vote in person, tap the passport or national id card to the voter roll machine, the camera checks the photo, and the human double checks. Nothing stored at that point. The ballot is printed, you're checked off the roll for the election, and at that point the fraud concerns go into how the ballot is filled, stored and counted. If you want to vote electronically, tap the passport or id card to your phone, the phone queries the carrier database to check where you should be voting based on the billing address, the software queries the voter roll, and once you submit the electronic ballot, you can't vote again, electronically or in person in that election.

 

Like the processes are more simple, it's the lack of trust in these databases, and using the pandemic as cover to de-register people. Like why isn't everyone who pays taxes not automatically enrolled to begin with?

[Sauron]

23 hours ago, mr moose said:

 

@colonel_mortis  does this lead us to electronic voting or are we still miles from that actually being secure?

As far as I can tell this does nothing for e-voting, it's never been a problem with people knowing who you voted for - the system doesn't need to know, it just needs to count votes. Voter fraud safeguards don't typically depend on the electronic ballot in implementations we've seen so far so checking that you don't vote twice is also not the system's concern. The problem is the safety of the counting mechanism which is usually terrible, not to mention giving a single company control over vote counting sounds like a mess waiting to happen (most voting machines aren't even open source so they could literally do whatever they want).

On 8/1/2020 at 12:43 AM, colonel_mortis said:

One interesting application of this is in verifiable electronic voting. One possible scheme (off the top of my head) would be

• I encrypt my vote using homomorphic encryption, and submit that encrypted vote to the central server
• The central server combines my vote with the current total, and publishes the current total as well as all previous totals
• I can verify that my vote was counted by performing previous_total ⊕ my_vote, and checking that it matches current_total, but nobody else can tell what my actual vote was (except the holder of the encryption key)

There's a major problem I can see with that: for the operation to work I assume both numbers need to be encrypted with the same key or at least that you need access to both keys to decrypt the result of the operation. If that's the case then either you need access to the same keys the counters will use or you need to send them your vote to have it encrypted and perform the operation with the result you're given; both approaches completely defeat the purpose.

 

Unfortunately I'm afraid there's no way around it, for e-voting you need absolute trust in a centralized system and so far nobody has been able to provide a satisfactory solution.

 

 

This is probably more useful for databases where you can prevent people with physical access to the server or in possession of a database dump from reading any of the data. The client on your personal computer can decrypt the result of the query with your personal key rather than trusting the server.

[Sauron]

6 minutes ago, gabrielcarvfer said:

Even jailed people get to vote, which is completely absurd in my opinion.

Uhhh... why? You can go to jail for all sorts of reasons, that doesn't mean you're no longer a person who has a right to their say in how the country they live in is run. What, do you think thieves in prison will somehow be able to get theft legalized through voting or something? If that were a real issue why wouldn't it have happened already?

[mr moose]

6 minutes ago, Sauron said:

As far as I can tell this does nothing for e-voting, it's never been a problem with people knowing who you voted for - the system doesn't need to know, it just needs to count votes.

Still think of this every time I talk about e voting:

 

 

 

[Kisai]

20 minutes ago, gabrielcarvfer said:

No idea. Here everyone is automatically enrolled (in fact, we are obligated to vote, and not voting can give you a ton of problems, unless you justify and pay a fee). Every few years, we're required to go to an electoral notary's office to prove that we are alive, re-register fingerprint, confirm or move to another electoral zone (when you move to a different municipality), etc. Even jailed people get to vote, which is completely absurd in my opinion.

Jailed people should be permitted to vote, provided they are jailed for reasons that will not affect their voting. eg people in jail for drug crimes can vote, except on things that directly affect prison (say there was an abolish all prisons vote) because that would be voting to further their personal interests. Much the same reason politicians already in office should not be able to use information learned being in office to make financial decisions (eg stock trades for one.)

 

[colonel_mortis]

Please don't make this a debate about who should be allowed to vote.

[Jet_ski]

On 7/31/2020 at 12:14 PM, Pickles - Lord of the Jar said:

Something rather interesting to be honest. The fact you can search a database that is encrpyted for data without actually knowing what that data is is... mind boggling. Some really smart folks over at IBM. Any of you get this stuff? My brain broke halfway through. 

Source

In [abstract] algebra there are certain maps with special properties called homomorphisms. A homomorphism maps two spaces [of a particular mathematical structure] in a way that it doesn’t matter whether you apply scalar multiplication, addition, and element multiplication in the range space or in the image space.

 

For example suppose F(x)=2x was a homomorphism that maps the integers to the even numbers (this map is not a homomorphism because it fails the 3rd requirement but it’s simple enough to get the idea across). So for some integer x and scalar 6 we have: F(6x)=2(6x)=12x=6(2x)=6F(x) which means it doesn’t matter whether you multiply before or after you apply the map. Similarly F(x+y)=2x+2y=F(x)+F(y). However F(xy)=2xy != F(x)F(y)=2x2y=4xy and therefore this map is not a homomorphism. A lot of these maps are classified and understood.

 

 

As it relates to encryption, suppose F is a homomorphism map of some kind that encrypts your data. Since it is a homomorphism, the person who is looking at the encrypted data can perform those basic operations for you without seeing your data. And computer operations boil down to addition, multiplication, and scalar multiplication on some level.
 

The technical challenge here is to find all these homomorphisms and combine them with cryptography.

 

For example if you multiply two prime numbers like 7 and 11 you get 77, this number can only be only factored into the two prime numbers that gave you 77. This is true for any two prime numbers. For the RSA keys they use a pair of large enough prime numbers like 1607 and 1277, multiply and you get 2,052,139 which you use as the key for your encryption algorithm. For someone to use brute force to find those prime numbers and therefore break the RSA encryption, they will need a lot of time and computational resources (it'll take much longer than the 60 seconds before the RSA key refreshes). Now numbers ending in 9 have some divisibility properties which makes them easier to factor out so some encryption algorithms use twin primes (like 41 and 43 but much larger ones) which don't have any known patterns.

 

Anyway, if you are a government agency with data on AWS, you want to access it and use the server computing power to search the data without risking someone else gaining access to it. Multiple US agencies use AWS. So they could use these homomorphic encryptions to make it practically impossible for anyone to use brute force on their data. Most importantly, if an AWS server is compromised even with processor level chips that send data to some foreign government, they can't use any of it because even the CPUs that are processing your data don't know what they are doing!