Swift Homomorphic Encryption

https://www.swift.org/blog/announcing-swift-homomorphic-encryption/

by yAak • 2 years ago

322 122 2 years ago

This must be the first real world use case of HE. It has generally been considered too slow to do anything useful but this is an excellent use case.

MBCook3• 2 years ago

I tried to look homomorphic encryption up casually earlier this year. I saw references that it was being used, but I don’t think they said where.

This is one topic I have a very hard time with, I just don’t know enough math to really grok it.

It just seems crazy a system could operate on encrypted data (which is effectively random noise from the server’s point of view) and return a result that is correctly calculated and encrypted for the client, despite never understanding the data at any point.

I sort of understand the theory (at a very simple level) but my brain doesn’t want to agree.

oblvious-earth• 2 years ago

Maybe it’s the fact it can be done with multiple operators and strong encryption that is hard to grok, but at least here is a very simple example of a limited partially homomorphic encryption:

You have a 7-bit character representation (e.g. ASCII) and your encryption is to add 1 mod 128. E.g. 0 -> 1, 1 -> 2, ... 126 -> 127, 127 -> 0.

As it turns out, all your operations can be represented as adding or subtracting constants. You can now encrypt your data (+1), send it to a remote server, send all the adding and subtracting operations, pull back the processed data, decrypt the data (-1).

Of course, this example is neither useful encryption nor generally useful operation, but can be useful for grokking why it might be possible.

kmeisthax• 2 years ago

Let's say I want you to add two numbers, but I don't want you to know what those numbers are, nor what the result is. What I can do is multiply both numbers by some other number you don't know. I then give you the premultiplied numbers, you add them, and give back a premultiplied answer. I can then divide out the number to get the true result.

What we've done here is this:

(a * key) + (b * key) = (c * key)

The rules of elementary algebra allow us to divide out the key on both sides because of a few useful symmetries that addition and multiplication have. Namely, these two equations are always the same number:

(a + b) * key = (a * key) + (b * key)

This is known as the distributive property. Normally, we talk about it applying to numbers being added and multiplied, but there are plenty of other mathematical structures and pairs of operations that do this, too. In the language of abstract algebra, we call any number system and pair of operations that distribute like this a "field", of which addition and multiplication over real[0] numbers is just one of.

A simple example of a field that isn't the normal number system you're used to is a 'finite field'. To visualize these, imagine a number circle instead of a line. We get a finite field by chopping off the number line at some prime[1] number that we decide is the highest in the loop. But this is still a field: addition and multiplication keep distributing.

It turns out cryptography loves using finite fields, so a lot of these identities hold in various cryptosystems. If I encrypt some data with RSA, which is just a pair of finite field exponents, multiplying that encrypted data will multiply the result when I decrypt it later on. In normal crypto, this is an attack we have to defend against, but in homomorphic crypto we want to deliberately design systems that allow manipulation of encrypted data like this in ways we approve of.

[0] Also complex numbers.

[1] Yes, it has to be prime and I'm unable to find a compact explanation as to why, I assume all the symmetries of algebra we're used to stop working if it's not.

osaariki• 2 years ago

Edge's Password Monitor feature uses homomorphic encryption to match passwords against a database of leaks without revealing anything about those passwords: https://www.microsoft.com/en-us/research/blog/password-monit... So not the first, but definitely cool to see more adoption!

dagmx• 2 years ago

I believe Safari does the same as well, so not even technically the first at Apple if I’m correct?

cedws• 2 years ago

This is nicer than the k-anonymity algorithm that Have I Been Pwned uses, but probably an order of magnitude more expensive to run.

7e• 2 years ago

A TEE would be a cheaper and more straightforward solution, though.

saagarjha4• 2 years ago

They also mean if you break the TEE then your privacy guarantees are lost. This, of course, has happened many times.

nightpool4• 2 years ago

Second: Google Recaptcha Enterprise can use Homomorphic Encryption to check whether your password has been compromised (searching the set of all breached passwords without disclosing which individual password you want to check)

Now, in practice, HaveIBeenPwned does the exact same thing with a k-anonymity scheme based off of MD5 collisions, which is wayyyy easier in practice and what most people actually deploy, but the Google thing is cool too.

glenngillen• 2 years ago

I believe Cipherstash is using HE to do what they do: https://cipherstash.com

kmdupree• 2 years ago

it says on their webpage that they aren't using HE

tedunangst3• 2 years ago

I feel like phone number lookup is the textbook example of homomorphic encryption not actually working because there's so few keys you can simply enumerate them.

willseth• 2 years ago

The novelty is that the server processing the phone number can perform the lookup without actually knowing the phone number or whether it matched.

colmmacc3• 2 years ago

I think here the query exposes who called who, which isn't as enumerable. By encrypting the query homomorphically on the client, the answering service has no knowledge of what number the lookup is for, and so Apple can't build a database of who calls you.

tedunangst3• 2 years ago

It includes both numbers? That wasn't clear. It sounded like they're just looking up the calling number for fancy caller id. How does the recipient affect the query?

Dylan16807• 2 years ago

Are you thinking of hashing?

As far as I'm aware homomorphic encryption can keep even a single bit safe, but maybe I missed something.

scosman• 2 years ago

add a seed.

silasdavis• 2 years ago

I'm not sure what enumeration attack you have in mind, but if you were to encrypt the same value many times you would not get the same ciphertext under most schemes.

gumby• 2 years ago

The name is hilarious because HME is anything but speedy -- by many orders of magnitude.

I think the real fix is secure enclaves, and those have proven to be difficult as well.

Someone• 2 years ago

I think the real fix is secure enclaves

FTA: “Live Caller ID Lookup uses homomorphic encryption to send an encrypted query to a server that can provide information about a phone number without the server knowing the specific phone number in the request”

So, this would require a distributed Secure Enclave or one of them on Apple’s server communicating with one on an Apple device (likely, certainly over time, with lots of different Apple devices fo lots of different iCloud accounts)

dllthomas3• 2 years ago

I don't see why it would? IIUC, the promise of homomorphic encryption is that I can encrypt my database of contacts and send it to an untrusted server, later send the encrypted query to that untrusted server, and get back an encrypted response, without the server being able to tell anything that couldn't be told from the wire (some bounds on how much data, timing of communication, that sort of thing) or provide an incorrect answer.

shortstuffsushi• 2 years ago

I think Swift in this case is just referring to the programming language, Swift, and not a characteristic of the encryption library itself

dllthomas3• 2 years ago

Right, but that doesn't make it not funny.

layer8• 2 years ago

I didn’t look at domain at first and ended up being quite disappointed. :)

ganyu• 2 years ago

At least 10^4 times slower than raw code, i think

That makes HE anything but Swift (

bawolff3• 2 years ago

Its like high-temperature super conductors, its all relative.

karulont5• 2 years ago

There was a recent paper that also uses Swift in the name:

“Cheddar: A Swift Fully Homomorphic Encryption Library for CUDA GPUs” - https://arxiv.org/pdf/2407.13055

We were a little worried, but quickly discovered that they used Swift as an adjective not as a programming language.

[Disclosure: I work on the team responsible for the feature]

golol• 2 years ago

I find homomorphic encryption fascinating as it can in some sense move a simulation into an inaccessible parallel universe.

Jerrrrrrry• 2 years ago

move a simulation into an inaccessible parallel universe.

more like, "move a computation into an progressed, but still unknown, state"

tiffanyh• 2 years ago

This is hugely significant (long-term), that won't be felt immediately.

This is a massive announcement for AI and use cases related to PII.

tombert• 2 years ago

I wrote some basic homomorphic encryption code for a hackathon like 8 years ago. When I interviewed for a BigTechCo [1] about a year later, the topic came up, and when I tried explaining what homomorphic encryption was to one of the interviewers, he told me that I misunderstood, because it was "impossible" to update encrypted data without decrypting it. I politely tried saying "actually no, that's what makes homomorphic encryption super cool", and we went back and forth; eventually I kind of gave up because I was trying to make a good impression.

I did actually get that job, but I found out that that interviewer actually said "no", I believe because he thought I was wrong about that.

[1] My usual disclaimer: It's not hard to find my work history, I don't hide it, but I politely ask that you do not post it here directly.

jancsika• 2 years ago

Digression-- this is a good example where the mumbo jumbo that anarchists buzz on about applies in a very obvious way.

You were literate in that domain. The interviewer wasn't. In a conversation among equals you'd just continue talking until the interviewer yielded (or revealed their narcissism). The other interviewers would then stand educated. You see this process happen all the time on (healthy) FOSS mailing lists.

Instead, you had to weigh the benefit of sharing your knowledge against the risk of getting in a pissing contest with someone who had some unspecified (but real!) amount of power over your hiring.

That's the problem with a power imbalance, and it generally makes humans feel shitty. It's also insidious-- in this case you still don't know if the interviewer said "no" because they misunderstood homomorphic encryption.

Plus it's a BigTechCo, so we know they understand why freely sharing knowledge is important-- hell, if we didn't do it, nearly none of them would have a business model!

ChadNauseam2• 2 years ago

In my experience this comes up a lot less often when people are paid to be empirically right, and the most annoying arguments occur when no one has an interest in being right and instead wants to defend their status. e.g. try telling a guy with his date nearby that he's wrong about something irrelevant like how state alcohol minimum markups work. An even more common scenario is when someone is passionate about a political topic and they publicly say something incorrect, and now would look like a fool if they admitted they were wrong. Sometimes I worry that a post-money future would become entirely dominated by status considerations and there would be no domain where people are actually incentivized to be right. Do you know if there's any anarchist thought related to this topic?

lcnPylGDnU4H9OF• 2 years ago

the mumbo jumbo that anarchists buzz on about

I enjoy exposing myself to new-to-me opinions. Do you know a decent anarchist blog/vlog to dip my toes into this area?

saagarjha4• 2 years ago

In a conversation among equals you'd just continue talking until the interviewer yielded (or revealed their narcissism). The other interviewers would then stand educated. You see this process happen all the time on (healthy) FOSS mailing lists.

Yeah, what actually happens is that both parties think they are right and keep yapping until someone "yields" by being so fed up that they don't want to argue anymore. Everyone else watching learns nothing.

bawolff3• 2 years ago

You see this process happen all the time on (healthy) FOSS mailing lists.

In a FOSS mailing list, someone would hopefully just link to wikipedia.

No amount of arguing is going to resolve a duspute about definitions of terms.

hansvm3• 2 years ago

I had the same experience with Python's walrus operator [0] in a BigTechCo interview. After few times of the interviewer insisting I had no idea what I was talking about, I wrote it a different way. I can't imagine trying explaining something actually complicated in that environment.

It didn't hold me back from the job either. I like to believe the interviewer looked it up later, but I never poked into my hiring packet.

[0] It was useful at the time to have a prefix sum primitive. Ignoring annotations, something like this:

    def scan(f, items, x):
        return [x := f(x, item) for item in items]

hot_gril4• 2 years ago

This is pretty bad. We learned in school how RSA works, which can be easily extended to show HME multiplication at least. I can't remember it off the top of my head, but I know it's possible.

hot_gril4• 2 years ago

(And if I didn't learn RSA in school, I wouldn't take a strong stand on how it works)

refulgentis• 2 years ago

Something similar happened to me at my first(!) tech interview, with Apple's [REDACTED] team.

There was ~3 minutes left in the interview, and they asked me a difficult l33t code concurrency question that was trivially answerable if you knew a specific, but lesser known, function in Apple's concurrency library. [1]

I said as much, TL;DR: "hmm I could do full leetcode that requires X, Y, and Z, and I might not have enough time to finish it, but there is a one-liner via a new API y'all got that I could do quick"

They said go ahead and write it, I did, then they insisted I was making up the function -- slapping the table and getting loud the second time they said it. Paired interviewer put a hand on their arm.

Looking back, that was not only a stark warning about the arbitrariness of interviews, but also that going from dropout waiter => founder => sold, then to Google, wasn't going to be all sunshine and moonbeams just because people were smart and worked in tech too. People are people, everywhere. (fwiw, Apple rejected w/"not a college grad, no bigco experience, come back in 3 years if you can hack it somewhere else". Took Google, stayed 7 years)

[1] https://developer.apple.com/documentation/dispatch/3191903-d...

tomlue• 2 years ago

This happened to me in a grant application. We had written a web application that did a homomorphic encryption based calculation of molecular weight to demonstrate that HE could be used to build federated learning models for chemical libraries.

Our reviewers told us that machine learning on encrypted data was impossible. We had the citations and the working model to refute them. Very frustrating.

hot_gril4• 2 years ago

What was the end result? I was almost roped into a project like this, encrypted ML for biology applications. It was definitely possible, but it seemed too slow to be worthwhile. Other federated learning projects shut down because it was wayy more efficient on a single cluster, and that was without the HE tax. I also have no idea if you can practically do HE matrix operations on a TPU or GPU or CPU SIMD at least; presumably that's something the research would cover.

Then again I didn't test very much because they also wanted it to be the proof of work for a blockchain, a possibility that I didn't discount but also figured it'd be extremely hard and I wasn't the guy to do it.

77pt77• 2 years ago

he told me that I misunderstood, because it was "impossible" to update encrypted data without decrypting it. I politely tried saying "actually no, that's what makes homomorphic encryption super cool", and we went back and forth; eventually I kind of gave up because I was trying to make a good impression.

The moment you have to explain yourself you've already lost.

No argument you make will change their mind.

They are just stupid and that will never change.

And never forget, these people have power over you.

hot_gril4• 2 years ago

It's not stupid to intuitively doubt HME and ask for an explanation if you've never heard of it before, but to argue that it's impossible without knowing anything about it, yeah.

ReptileMan• 2 years ago

What is the processing that the server does on the encrypted phone number? I am not sure I understand. I always thought that this type of encryption was (roughly and imprecisely) - you send some encrypted blob to the server, it does some side effect free number crunching on the blob and returns the output blob. You decrypt the blob and everyone is happy.

But to return information if some number is spam it has to be either plaintext or hashed condition somewhere outside of the phone?

dboreham• 2 years ago

The "side effect free number crunching" in this case is: is <encrypted_phone_number> in <set_of_encrypted_bad_numbers>

You're on the right track with the idea of hashing -- I find it helpful to explain any fancy encryption scheme beginning with "if it were just hashing", then extend to "well this is a very fancy kind of hash", and <poof> now I kind of understand what's going on. Or at least it's no longer magic.

saagarjha4• 2 years ago

I don't think the set of bad numbers needs to be encrypted.

fboemer3• 2 years ago

https://news.ycombinator.com/item?id=41115179 give some intuition. The server database is stored in plaintext, but the server response will be encrypted under the client's key.

[Disclosure: I work on the team responsible for the feature]

nmadden4• 2 years ago

The thing that I always want to know with FHE: the gold standard of modern encryption is IND-CCA security. FHE by definition cannot meet that standard (being able to change a ciphertext to have predictable effects on the plaintext is the definition of a chosen ciphertext attack). So how close do modern FHE schemes get? ie how much security am I sacrificing to get the FHE goodness?

GTP2• 2 years ago

Is the used scheme fully homomorphic encryption or just homomorphic wrt a specific operation? Because they only mention "homomorphic" without the "fully".

fboemer3• 2 years ago

Swift Homomorphic Encryption implements the Brakerski-Fan-Vercauteren (BFV) HE scheme (https://eprint.iacr.org/2012/078, https://eprint.iacr.org/2012/144) (without bootstrapping). This is a leveled HE scheme, which supports a limited number of encrypted adds and multiplies (among other operations).

[Disclosure: I work on the team responsible for the feature]

nmadden4• 2 years ago

With respect to IND-CCA, it doesn’t matter. Neither is compatible.

hansvm3• 2 years ago

You can't attain IND-CCA2 (adaptively choosing cyphertexts based on previous decryptions). You can attain IND-CCA1 (after a decryption oracle, you're done fiddling with the system).

nmadden4• 2 years ago

Right, but IND-CCA1 is kind of a toy security goal though. A sort theoretical consolation prize if you can’t achieve the real thing. And AFAICT, no actually implemented schemes do obtain even CCA1?

tpurves• 2 years ago

Anyone interested in FHE should also be checking out https://www.zama.ai they've made a ton of progress recently in making FHE practical.

lsh1236• 2 years ago

If we assume that server is “evil” then the server can store both PIR encrypted and plain text phone number in the same row in the database and when this row is read, simply log plain text phone number. What do I miss here? We can send PIR request and trust server not to do the above; or we can send plain text phone number and trust server not to log it — what’s the difference?

jayd162• 2 years ago

The server never gets the plaintext at all. It only ever receives encrypted data that it cannot read.

vlovich1237• 2 years ago

I think OP is talking about the set of “spam phone numbers” stored on the server and looking at side channels based on what data is looked up by processing the query.

vlovich1237• 2 years ago

It’s a lot more complicated because the phone numbers themselves are stored encrypted and there’s not a 1:1 mapping between encrypted representation and the mapping. So processing the query is actually blinding the evil server afaik.

lsh1236• 2 years ago

Evil server stores BOTH encrypted and plain text phone number in the same db row

karulont5• 2 years ago

A very simple PIR scheme on top of homomorphic encryption that supports multiplying with a plaintext and homomorphic addition, would look like this:

The client one-hot-encodes the query: Enc(0), Enc(1), Enc(0). The server has 3 values: x, y, z. Now the server computes: Enc(0) * x + Enc(1) * y + Enc(0) * z == Enc(y). Client can decrypt Enc(y) and get the value y. Server received three ciphertexts, but does not know which one of them was encryption of zero or one, because the multiplications and additions that the server did, never leak the underlying value.

This gives some intuition on how PIR works, actual schemes are more efficient.

[Disclosure: I work on the team responsible for the feature]

lsh1236• 2 years ago

Does the server reads specific rows from spam numbers DB or the whole database?

motohagiography3• 2 years ago

great to see this becoming part of mainstream tools. the question I have is, when a weakness is published in FHE, is it more like a hash function you can do some transformations on, but there is no 'decryption' to recover plaintext again- or is it more like a symmetric cipher, where all your old ciphertexts can be cracked, but now your FHE data sets are no longer considered secure or private and need to be re-generated from their plaintexts with the updated version?

what is the failure mode of FHE and how does it recover?

j2kun3• 2 years ago

It is more like a symmetric cipher. Once you have a key you can decrypt everything encrypted with that key

motohagiography3• 2 years ago

the risk in this is that FHE is proposed as a privacy protecting tech, and it will "squeeze a lot of toothpaste out of the tube" in private data sharing, where a weakness will be a rug pull under all the data subjects whose data was shared under the aegis of being "encrypted."

It's important to understand this failure mode, imo.

attilakun• 2 years ago

Is there a good primer that explains the math basis of this?

j2kun3• 2 years ago

https://www.jeremykun.com/2024/05/04/fhe-overview/

yalogin• 2 years ago

FHE is cool but I wonder how many use cases it actually fits. Don’t get me wrong, it gives better security guarantees for the end user but do they really care if the organization makes a promise about a secure execution environment in the cloud?

Also from an engineering point of view, using FHE requires a refactoring of flows and an inflexible commitment to all processing downstream. Without laws mandating it, do organizations have enough motivation to do that?

nightpool4• 2 years ago

but do they really care if the organization makes a promise about a secure execution environment in the cloud?

Uh... demonstrably yes? No "secure execution environment" is secure against a government wiretap order. FHE is.

chipsrafferty2• 2 years ago

Unless the operating system for iPhones is open source and one can verify which version they have installed, users can't really be sure that Apple is doing this. They could just say they are doing things to protect user's privacy, and then not, and sell their data.

bobbylarrybobby• 2 years ago

I assume companies like it because it lets them compute on servers they don't trust. The corollary is they don't need to secure HE servers as much because any data the servers lose isn't valuable. And the corollary to that is that companies can have much more flexible compute infra, sending HE requests to arbitrary machines instead of only those that are known to be highly secure.

kybernetikos• 2 years ago

I think the main thing that throws it into question is when you get the software that sends the data to the service and the service from the same people (in this case apple). You're already trusting them with your data, and a fancy HE scheme doesn't change that. They can update their software and start sending everything in plain text and you wouldn't even realise they'd done it.

FHE is plausibly most useful when you trust the source of the client code but want to use the compute resource of an organisation you don't want to have to trust.

oulipo• 2 years ago

How does it compare to the FHE from https://zama.ai ?

rhindi• 2 years ago

They use BFV, which is an FHE scheme allowing a limited number of fast additions and multiplications (enough for their use case).

Zama uses TFHE, which allows any operation (eg comparisons) with unlimited depth.

So if you only need add/mul, BFV, BGV and CKKS are good options. For anything else, you better use TFHE

jayavanth• 2 years ago

I was curious about that choice as well. I guess they also just wanted to operate on integers and not floats

menkalinan• 2 years ago

I don't quite understand how the server can match the ciphertext with a value without knowing the key. How does the server determine that the ciphertext corresponds to the specific value? If the server constructs this ciphertext-value database, how does it know what algorithm to use to create ciphertext from a value and store on its side?

karulont5• 2 years ago

Check my comment here for some intuition: https://news.ycombinator.com/item?id=41115179

Basically the server does not know, it just computes with every possible value. And the result turns out to be what the client was interested in.

Swift Homomorphic Encryption

Related Stories