9 ms·

Swift Homomorphic Encryption

322 points by yAak 2y ago

PROMISE_237 2y ago
[dead]
tedunangst 2y 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 2y 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.
- colmmacc 2y 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.
  - tedunangst 2y 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?
    - colmmacc 2y ago
      The lookup has to come from your phone, which implicitly discloses you. Encrypting the caller-id symmetrically or asymmetrically wouldn't get privacy, because the receiver would have the decryption key. Hashing it, even with a seed, would be dumb because it's enumerable as you pointed out. But encrypting the entire query does work, because it becomes on a homomorphic search on uniform looking data. So the receiver has no idea what you queried. That said, research on things like memory access side-channels is thin here. Like if I take a guess and try a query for my guess number, are there timings there that could be exploited because of cache effects? I have no idea, but a lot of PIR schemes have fallen to this.
      - tedunangst 2y ago
        Okay, I figure if Apple wanted, they could simply query every number and see which disk blocks get read. But now maybe I'm confused. They read the whole database on every query?
        colmmacc 2y ago
        My understanding of encrypted search in FHE is that there can be multiple copies of the same search key, and that search keys aren't simply in-place encrypted versions of themselves - as encrypted fields in a database are - but are mappings embedded in a higher dimensional space that is encrypted. That reads like sci-fi nonsense, but the "on the metal" result is that a search key will translate to a set of memory locations that are combined to determine the match, and a separate query for the same search key will translate to a different (but potentially overlapping) set of memory locations that produce the same result.
        MBCook 2y ago
        Do I have this right? If the server could actually decode things it would’ve gotten something that could be decrypted into let’s say 15 phone numbers. A little bit like if they were hashed, to simplify. So the answer the server returns isn’t who the phone number belongs to, it’s who those 15 phone numbers belong to. And then the client can decrypt it and just get the one that it cares about. But unlike if you were just doing hash buckets no one who saw the data going back-and-forth could actually understand any of it. Correct? Is this only really good for data to look up cases? I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds.
        fragmede 2y ago
        Theoretically it can, but the tech isn't quite there yet, so we don't know for sure.
        ElFitz 2y ago
        > I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds. Well yes. There was this: - https://news.ycombinator.com/item?id=21638639 https://news.ycombinator.com/item?id=21638639 - https://news.ycombinator.com/item?id=31933995 https://news.ycombinator.com/item?id=31933995 - https://azeemba.com/posts/homomorphic-encryption-with-images.html https://azeemba.com/posts/homomorphic-encryption-with-images... And quite a few more.
- Dylan16807 2y 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 2y ago
  add a seed.
- silasdavis 2y 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.
bluedevilzn 2y 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.
- MBCook 2y 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.
  - deleted 2y ago
    [deleted]
  - oblvious-earth 2y 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 2y 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.
gumby 2y 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 2y 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)
  - dllthomas 2y 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.
    - tempay 2y ago
      That's not the use case mentioned here. The example given is blocking known spam callers and displaying identity information on the incoming call screen. To do this without homomorphic encryption requires the entire DB to be sent to every client. Even if size wasn't an issue (which it is), it's hard to update it frequently. Homomorphic encryption means you can ask Apple "who is calling me" without Apple knowing who is calling you.
      - MBCook 2y ago
        Not really. You could do it the way the Have I Been Pwned database works. You hash your query and then send only the first X number of bits. The server returns all results that hash up to that same first X number of bits. The server doesn’t know exactly what number you were looking for, and you don’t have to download the entire database. But in this case the server WOULD be able to figure out the set of possible phone numbers you were asking about. Because of the complexity of passwords the search space would be a lot larger. So privacy wise this does seem better.
golol 2y ago
I find homomorphic encryption fascinating as it can in some sense move a simulation into an inaccessible parallel universe.
- Jerrrrrrry 2y ago
  > move a simulation into an inaccessible parallel universe. more like, "move a computation into an progressed, but still unknown, state"
tiffanyh 2y 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 2y 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 2y 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!
  - ChadNauseam 2y 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?
ReptileMan 2y 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 2y 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.
  - saagarjha 2y ago
    I don't think the set of bad numbers needs to be encrypted.
    - vlovich123 2y ago
      It does - otherwise you would know which numbers are queried to process the query, letting you narrow things down (ie huge side channel and thus not HE anymore).
      - saagarjha 2y ago
        How so? You can just query all the numbers and discard results you don't want.
        vlovich123 2y ago
        Sure, you can query the database all you want. The important property is that the server cannot observe the client querying the database - processing a query occurs in an encrypted space that it does not have the keys to. Similarly, one would expect that each query, even if it's for the same phone number, would be observed to be reading randomly from the database each time.
nmadden 2y 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?
- GTP 2y ago
  Is the used scheme fully homomorphic encryption or just homomorphic wrt a specific operation? Because they only mention "homomorphic" without the "fully".
  - fboemer 2y ago
    Swift Homomorphic Encryption implements the Brakerski-Fan-Vercauteren (BFV) HE scheme (https://eprint.iacr.org/2012/078 https://eprint.iacr.org/2012/078, https://eprint.iacr.org/2012/144 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]
    - Jommi 2y ago
      That’s awesome. I’m part of a cryptography group working on more applied uses of homomorphic encryption, is there a way to contact you?
  - nmadden 2y ago
    With respect to IND-CCA, it doesn’t matter. Neither is compatible.
- hansvm 2y 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).
joeisaveggie 2y ago
[flagged]
tpurves 2y ago
Anyone interested in FHE should also be checking out https://www.zama.ai https://www.zama.ai they've made a ton of progress recently in making FHE practical.
your-username 2y ago
[flagged]
idkdotcom 2y ago
[dead]
lsh123 2y 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?
- jayd16 2y ago
  The server never gets the plaintext at all. It only ever receives encrypted data that it cannot read.
  - vlovich123 2y 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.
    - lsh123 2y ago
      Exactly, plain text phone number in the same db row
      - vlovich123 2y ago
        Yeah but as I wrote elsewhere, the DB isn’t a KV store of plain text numbers and their encrypted representation. Instead the entire database would be encrypted and you’d do set containment operations in encrypted space which wouldn’t /couldn’t leak anything about your query (modulo unexpected side channels in the design). I don’t know how they do this efficiently and at scale with lots of updates, but maybe this database is kinda small to begin with anyway and the updates are reasonably cheap to process relative to how many spam numbers are out there.
        lsh123 2y ago
        That’s not what I saw in the code but I didn’t spend much time so I might be wrong. I’ll check it more carefully later. But if this indeed is whole DB then it’s very limited use case.
motohagiography 2y 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?
- j2kun 2y ago
  It is more like a symmetric cipher. Once you have a key you can decrypt everything encrypted with that key
  - motohagiography 2y 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.
    - j2kun 2y ago
      I don't see how a bad actor can "rug pull" when everyone has a different encryption key. A cryptographic scheme weakness is a threat to all computing systems, it's not worse for FHE. It's just that FHE relies on newer encryption than existing widely deployed crypto.
      - motohagiography 2y ago
        The main use case for FHE is to enable partial data sharing between parties who are forbidden from sharing data with one another, or for whom being in custody of it is too much of a liability. the reason I think the threat is worse for FHE is because it's going to be used to share encrypted versions of private information that isn't shared today, and realistically, the only people exploiting cryptographic weaknesses right now are intelligence agencies, where in the case of a repo of FHE enciphered PII shared with a vendor is suddenly decryptable by that vendor. my point is it's not the same as other encryption for those reasons.
attilakun 2y ago
Is there a good primer that explains the math basis of this?
- j2kun 2y ago
  https://www.jeremykun.com/2024/05/04/fhe-overview/ https://www.jeremykun.com/2024/05/04/fhe-overview/
yalogin 2y 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?
- nightpool 2y 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.
  - chipsrafferty 2y 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.
    - nightpool 2y ago
      > Unless the operating system for iPhones is open source and one can verify which version they have installed There are a lot of security engineers out there reverse engineering Apple's iOS versions and payloads, especially ones installed on the phones of activists and other dissidents who may be under government surveillance. While in theory Apple could build a compromised OS and serve it only to a single IP or whatever, the reputational risk if they were to be discovered would be enormous. Compared to when the processing is happening on Apple's servers, where it's impossible to tell for sure if you're being wiretapped, there's just too much of a risk of detection and tipping off the target.
- bobbylarrybobby 2y 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.
oulipo 2y ago
How does it compare to the FHE from https://zama.ai https://zama.ai ?
- rhindi 2y 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 2y ago
    I was curious about that choice as well. I guess they also just wanted to operate on integers and not floats
menkalinan 2y 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?
- karulont 2y ago
  Check my comment here for some intuition: https://news.ycombinator.com/item?id=41115179 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.

322 points by yAak 2y ago

[dead]

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 2y 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.
colmmacc 2y 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.
- tedunangst 2y 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?
  - colmmacc 2y ago
    The lookup has to come from your phone, which implicitly discloses you. Encrypting the caller-id symmetrically or asymmetrically wouldn't get privacy, because the receiver would have the decryption key. Hashing it, even with a seed, would be dumb because it's enumerable as you pointed out. But encrypting the entire query does work, because it becomes on a homomorphic search on uniform looking data. So the receiver has no idea what you queried. That said, research on things like memory access side-channels is thin here. Like if I take a guess and try a query for my guess number, are there timings there that could be exploited because of cache effects? I have no idea, but a lot of PIR schemes have fallen to this.
    - tedunangst 2y ago
      Okay, I figure if Apple wanted, they could simply query every number and see which disk blocks get read. But now maybe I'm confused. They read the whole database on every query?
      - colmmacc 2y ago
        My understanding of encrypted search in FHE is that there can be multiple copies of the same search key, and that search keys aren't simply in-place encrypted versions of themselves - as encrypted fields in a database are - but are mappings embedded in a higher dimensional space that is encrypted. That reads like sci-fi nonsense, but the "on the metal" result is that a search key will translate to a set of memory locations that are combined to determine the match, and a separate query for the same search key will translate to a different (but potentially overlapping) set of memory locations that produce the same result.
        MBCook 2y ago
        Do I have this right? If the server could actually decode things it would’ve gotten something that could be decrypted into let’s say 15 phone numbers. A little bit like if they were hashed, to simplify. So the answer the server returns isn’t who the phone number belongs to, it’s who those 15 phone numbers belong to. And then the client can decrypt it and just get the one that it cares about. But unlike if you were just doing hash buckets no one who saw the data going back-and-forth could actually understand any of it. Correct? Is this only really good for data to look up cases? I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds.
        fragmede 2y ago
        Theoretically it can, but the tech isn't quite there yet, so we don't know for sure.
        ElFitz 2y ago
        > I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds. Well yes. There was this: - https://news.ycombinator.com/item?id=21638639 https://news.ycombinator.com/item?id=21638639 - https://news.ycombinator.com/item?id=31933995 https://news.ycombinator.com/item?id=31933995 - https://azeemba.com/posts/homomorphic-encryption-with-images.html https://azeemba.com/posts/homomorphic-encryption-with-images... And quite a few more.
Dylan16807 2y 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 2y ago
add a seed.
silasdavis 2y 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.

bluedevilzn 2y 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.

MBCook 2y 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.
- deleted 2y ago
  [deleted]
- oblvious-earth 2y 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 2y 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.

gumby 2y 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 2y 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)
- dllthomas 2y 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.
  - tempay 2y ago
    That's not the use case mentioned here. The example given is blocking known spam callers and displaying identity information on the incoming call screen. To do this without homomorphic encryption requires the entire DB to be sent to every client. Even if size wasn't an issue (which it is), it's hard to update it frequently. Homomorphic encryption means you can ask Apple "who is calling me" without Apple knowing who is calling you.
    - MBCook 2y ago
      Not really. You could do it the way the Have I Been Pwned database works. You hash your query and then send only the first X number of bits. The server returns all results that hash up to that same first X number of bits. The server doesn’t know exactly what number you were looking for, and you don’t have to download the entire database. But in this case the server WOULD be able to figure out the set of possible phone numbers you were asking about. Because of the complexity of passwords the search space would be a lot larger. So privacy wise this does seem better.

golol 2y ago

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

Jerrrrrrry 2y ago
> move a simulation into an inaccessible parallel universe. more like, "move a computation into an progressed, but still unknown, state"

tiffanyh 2y 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 2y 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 2y 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!
- ChadNauseam 2y 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?

ReptileMan 2y 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 2y 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.
- saagarjha 2y ago
  I don't think the set of bad numbers needs to be encrypted.
  - vlovich123 2y ago
    It does - otherwise you would know which numbers are queried to process the query, letting you narrow things down (ie huge side channel and thus not HE anymore).
    - saagarjha 2y ago
      How so? You can just query all the numbers and discard results you don't want.
      - vlovich123 2y ago
        Sure, you can query the database all you want. The important property is that the server cannot observe the client querying the database - processing a query occurs in an encrypted space that it does not have the keys to. Similarly, one would expect that each query, even if it's for the same phone number, would be observed to be reading randomly from the database each time.

nmadden 2y 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?

GTP 2y ago
Is the used scheme fully homomorphic encryption or just homomorphic wrt a specific operation? Because they only mention "homomorphic" without the "fully".
- fboemer 2y ago
  Swift Homomorphic Encryption implements the Brakerski-Fan-Vercauteren (BFV) HE scheme (https://eprint.iacr.org/2012/078 https://eprint.iacr.org/2012/078, https://eprint.iacr.org/2012/144 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]
  - Jommi 2y ago
    That’s awesome. I’m part of a cryptography group working on more applied uses of homomorphic encryption, is there a way to contact you?
- nmadden 2y ago
  With respect to IND-CCA, it doesn’t matter. Neither is compatible.
hansvm 2y 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).

joeisaveggie 2y ago

[flagged]

tpurves 2y ago

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

your-username 2y ago

[flagged]

idkdotcom 2y ago

[dead]

lsh123 2y 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?

jayd16 2y ago
The server never gets the plaintext at all. It only ever receives encrypted data that it cannot read.
- vlovich123 2y 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.
  - lsh123 2y ago
    Exactly, plain text phone number in the same db row
    - vlovich123 2y ago
      Yeah but as I wrote elsewhere, the DB isn’t a KV store of plain text numbers and their encrypted representation. Instead the entire database would be encrypted and you’d do set containment operations in encrypted space which wouldn’t /couldn’t leak anything about your query (modulo unexpected side channels in the design). I don’t know how they do this efficiently and at scale with lots of updates, but maybe this database is kinda small to begin with anyway and the updates are reasonably cheap to process relative to how many spam numbers are out there.
      - lsh123 2y ago
        That’s not what I saw in the code but I didn’t spend much time so I might be wrong. I’ll check it more carefully later. But if this indeed is whole DB then it’s very limited use case.

motohagiography 2y 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?

j2kun 2y ago
It is more like a symmetric cipher. Once you have a key you can decrypt everything encrypted with that key
- motohagiography 2y 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.
  - j2kun 2y ago
    I don't see how a bad actor can "rug pull" when everyone has a different encryption key. A cryptographic scheme weakness is a threat to all computing systems, it's not worse for FHE. It's just that FHE relies on newer encryption than existing widely deployed crypto.
    - motohagiography 2y ago
      The main use case for FHE is to enable partial data sharing between parties who are forbidden from sharing data with one another, or for whom being in custody of it is too much of a liability. the reason I think the threat is worse for FHE is because it's going to be used to share encrypted versions of private information that isn't shared today, and realistically, the only people exploiting cryptographic weaknesses right now are intelligence agencies, where in the case of a repo of FHE enciphered PII shared with a vendor is suddenly decryptable by that vendor. my point is it's not the same as other encryption for those reasons.

attilakun 2y ago

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

j2kun 2y ago
https://www.jeremykun.com/2024/05/04/fhe-overview/ https://www.jeremykun.com/2024/05/04/fhe-overview/

yalogin 2y 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?

nightpool 2y 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.
- chipsrafferty 2y 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.
  - nightpool 2y ago
    > Unless the operating system for iPhones is open source and one can verify which version they have installed There are a lot of security engineers out there reverse engineering Apple's iOS versions and payloads, especially ones installed on the phones of activists and other dissidents who may be under government surveillance. While in theory Apple could build a compromised OS and serve it only to a single IP or whatever, the reputational risk if they were to be discovered would be enormous. Compared to when the processing is happening on Apple's servers, where it's impossible to tell for sure if you're being wiretapped, there's just too much of a risk of detection and tipping off the target.
bobbylarrybobby 2y 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.

oulipo 2y ago

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

rhindi 2y 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 2y ago
  I was curious about that choice as well. I guess they also just wanted to operate on integers and not floats

menkalinan 2y 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?

karulont 2y ago
Check my comment here for some intuition: https://news.ycombinator.com/item?id=41115179 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.