[HN Gopher] Swift Homomorphic Encryption
___________________________________________________________________
Swift Homomorphic Encryption
Author : yAak
Score : 169 points
Date : 2024-07-30 16:40 UTC (6 hours ago)
(HTM) web link (www.swift.org)
(TXT) w3m dump (www.swift.org)
| bluedevilzn wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| I believe Safari does the same as well, so not even
| technically the first at Apple if I'm correct?
| Groxx wrote:
| After reading the technical details... I'm really not sure
| tbh: https://support.apple.com/guide/security/password-
| monitoring...
|
| I'm sure someone here understands that and can answer
| conclusively, but that's not me today.
| cedws wrote:
| 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 wrote:
| A TEE would be a cheaper and more straightforward solution,
| though.
| saagarjha wrote:
| They also mean if you break the TEE then your privacy
| guarantees are lost. This, of course, has happened many
| times.
| tedunangst wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Theoretically it can, but the tech isn't quite there yet,
| so we don't know for sure.
| Dylan16807 wrote:
| 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 wrote:
| add a seed.
| silasdavis wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| tempay wrote:
| Indeed, I wasn't clear enough in my original message that
| it was under the assumption that you want to keep the
| caller 100% private from Apple.
|
| Though there is a valid argument that you're still
| leaking information (e.g. "Person X received a call at
| 21:05:43"), but I'm not sure how you could possibly make
| an API that avoided that given the time sensitive nature
| of identifying callers.
| shortstuffsushi wrote:
| I think Swift in this case is just referring to the programming
| language, Swift, and not a characteristic of the encryption
| library itself
| dllthomas wrote:
| Right, but that doesn't make it not funny.
| layer8 wrote:
| I didn't look at domain at first and ended up being quite
| disappointed. :)
| ganyu wrote:
| At least 10^4 times slower than raw code, i think
|
| That makes HE anything but Swift (
| bawolff wrote:
| Its like high-temperature super conductors, its all relative.
| golol wrote:
| I find homomorphic encryption fascinating as it can in some sense
| move a simulation into an inaccessible parallel universe.
| tiffanyh wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| > 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?
| mhitza wrote:
| Not OP, nor do I understand what he's referring to, but
| https://theanarchistlibrary.org/special/index is a good
| starting point.
| 317070 wrote:
| "The Utopia of Rules: On Technology, Stupidity, and the
| Secret Joys of Bureaucracy", by David Graeber might be good
| for this one, though some of Graeber's other books also
| apply.
| saagarjha wrote:
| > 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.
| bawolff wrote:
| > 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.
| hansvm wrote:
| 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_gril wrote:
| 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.
| ReptileMan wrote:
| 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 wrote:
| 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 wrote:
| I don't think the set of bad numbers needs to be encrypted.
| nmadden wrote:
| 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 wrote:
| Is the used scheme _fully_ homomorphic encryption or just
| homomorphic wrt a specific operation? Because they only mention
| "homomorphic" without the "fully".
| hansvm wrote:
| 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).
| nmadden wrote:
| 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 wrote:
| 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.
___________________________________________________________________
(page generated 2024-07-30 23:00 UTC)