9 ms·

Homomorphic encryption in iOS 18

377 points by surprisetalk 2y ago

ted537 2y ago
It's cool how neural networks, even convulutional ones, are one of the few applications that you can compute through homomorphic encryption without hitting a mountain of noise/bootstrapping costs. Minimal depth hurrhah!
- j2kun 2y ago
  I don't think Apple is doing this. They compute the embedding on device in the clear, and then just do the nearest-neighbor part in HE (which does lots of dot products but no neural network). There are people doing NNs in HE, but most implementations do indeed require bootstrapping, and for that reason they usually use CKKS.
sillysaurusx 2y ago
I was going to make my usual comment of FHE being nice in theory but too slow in practice, and then the article points out that there’s now SHE (somewhat homomorphic encryption). I wasn’t aware that the security guarantees of FHE could be relaxed without sacrificing them. That’s pretty cool. Is there any concrete info about noise budgets? It seems like that’s the critical concern, and I’d like to understand at what point precisely the security breaks down if you have too little (or too much?) noise.
- bawolff 2y ago
  Im not an expert on this, but my understanding is "noise" is less a security breakdown and more the entire system breaksdown. That is where the "somewhat" comes in, unlike "full" where the system can do (expensive) things to get rid of noise, in somewhat the noise just accumulates until the system stops working. (Definitely talking out of my hat here)
  - sillysaurusx 2y ago
    Interesting! Are there any security concerns with SHE? If not, it sounds like all of the benefits of FHE with none of the downsides, other than the noise overwhelming the system. If that’s true, and SHE can run at least somewhat inexpensively, then this could be big. I was once super hyped about FHE till I realized it couldn’t be practical, and this has my old excitement stirring again.
    - Ar-Curunir 2y ago
      Most FHE schemes are constructed out of SHE schemes. Also, there’s nothing preventing FHE from being practical, it’s just that existing constructions are not as fast we would like them to be
    - bawolff 2y ago
      My impression is that SHE are still relatively expensive, not as crazy as FHE but still slow enough to preclude many usecases and the noise breakdown can happen relatively quickly making them not work for most algorithms people want to use FHE for.
    - j2kun 2y ago
      Wait until you see all the ASICs getting taped out by various companies right now.
- ruined 2y ago
  it's incredibly algorithm-dependent. if you look into the thesis that originates the 'bootstrapping' technique to transform SHE algorithms into FHE, they determine the noise limit of their specific algorithm in section 7.3 and then investigate expanding the noise limit in 8 and 10. (written in 2009) http://crypto.stanford.edu/craig/craig-thesis.pdf http://crypto.stanford.edu/craig/craig-thesis.pdf some newer FHE don't encounter a noise limit or don't use the bootstrapping technique.
  - Ar-Curunir 2y ago
    All known FHE schemes use bootstrapping
    - ruined 2y ago
      i expected that, but a search turned up several things claiming to implement fhe without bootstrapping. i didn't investigate and i can't say i'm familiar so maybe they're bogus
      - Ar-Curunir 2y ago
        Correction: all known even-remotely-practical schemes rely on bootstrapping. See https://crypto.stackexchange.com/questions/103341/fully-homomorphic-encryption-without-bootstrapping https://crypto.stackexchange.com/questions/103341/fully-homo...
        slow_typist 2y ago
        As always, there is no free lunch.
      - j2kun 2y ago
        I did see an arxiv paper a while back that claimed to use category theory to do this, but my best bet was it was not secure.
- Ar-Curunir 2y ago
  SHE doesn’t relax security guarantees, it relaxes the class of supported computations
- 3s 2y ago
  SHE vs FHE has nothing to do with security. Instead, it’s about how many operations (eg homomorphic multiplications and additions) can be performed before the correctness of the scheme fails due to too much noise accumulating in the ciphertext. Indeed all FHE schemes are also SHE schemes. What typically makes FHE expensive computationally is a “bootstrapping” step for removing the noise that accumulated after X operations and threatening correctness. After bootstrapping you can do another X operations. Rinse and repeat until you finish the computation to you want to perform.
- twodave 2y ago
  Not sure whether they use FHE or not (the literature I’m looking at simply says “homomorphic”), but we use ElectionGuard at our company to help verify elections for our customers. So there are definitely some practical uses.
timsneath 2y ago
More here: https://www.swift.org/blog/announcing-swift-homomorphic-encryption/ https://www.swift.org/blog/announcing-swift-homomorphic-encr...
- GeekyBear 2y ago
  > One example of how we’re using this implementation in iOS 18, is the new Live Caller ID Lookup feature, which provides caller ID and spam blocking services. 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. Privacy by design is always nice to see.
  - gus_massa 2y ago
    I don't undertand how it can work. I assume the spam list is shared by all users, oherwise it will no be useful at all: Let's supouse Apple is evil (or they recive an order from a judge) and they want to know who is calling 5555-1234 1) Add a new empty "spam" numbers encrypted database to the server (so there are now two encrypted databases in the system) 2) Add the encrited version of 5555-1234 to it. 3) When someone checks, reply the correct answer from the real database and also check in the second one and send the reply to the police.
    - colejohnson66 2y ago
      Encryptions uses per-device keys.
    - GeekyBear 2y ago
      > they recive an order from a judge You can't be forced to hand over customer data after you have designed a system so that your servers don't ever have that information stored in the first place, court order or no.
    - jakelazaroff 2y ago
      How would they decrypt the answer from the database?
j16sdiz 2y ago
> The two hops, the two companies, are already acting in partnership, so what is there technically in the relay setup to stop the two companies from getting together—either voluntarily or at the secret command of some government—to compare notes, as it were, and connect the dots? The OHTTP scheme does not _technically_ prevent this. It increases the number parties need to cooperate to extract this information, hoping it would be caught somewhere in the pipeline.
- chikere232 2y ago
  and if a government say already forced ISPs to collect metadata about who connects to whom and when, I imagine they don't even need to bother getting data from the relay hosts
eviks 2y ago
> There is no trust me bro element. > Barring some issue being found in the math or Apple’s implementation of it Yes, is you bar the "trust me bro" element in your definition, you'll by definition have no such element. Reality, though, doesn't care about your definition, so in reality this is exactly the "trust me bro" element that exists > But we’re already living in a world where all our data is up there, not in our hands. If that's your real view, then why do you care about all this fancy encryption at all? It doesn't help if everything is already lost
- rpearl 2y ago
  I mean if you'd like, you could reimplement the necessary client on an airgapped computer, produce an encrypted value, take that value to a networked computer, send it to the server, obtain an encrypted result that the server could not possibly know how to decrypt, and see if it has done the computation in question. No trust is required. You could also observe all bits leaving the device from the moment you initialize it and determine that only encrypted bits leave and that no private keys leave, which only leaves the gap of some side channel at the factory, but you could perform the calculation to see that the bits are only encrypted with the key you expect them to be encrypted with.
  - Krasnol 2y ago
    How is this comment useful to the OPs valid arguments?
sneak 2y ago
> This should be fine: vectorization is a lossy operation. But then you would know that Amy takes lots of pictures of golden retrievers, and that is a political disaster. This downplays the issue. Knowing that Alice takes lots of screenshots of Winnie the Pooh memes means that Alice’s family gets put into Xinjiang concentration camps, not just a political disaster. (This is a contrived example: iCloud Photos is already NOT e2ee and this is already possible now; but the point stands, as this would apply to people who have iCloud turned off, too.)
- troad 2y ago
  Agreed. And for a less contrived example, people may have photos of political protests that they attended (and the faces of others present), screenshots that include sensitive messages, subversive acts, etc. It's worth noting though that it's now possible to opt in to iCloud Photo e2ee with "Advanced Data Protection". [0] [0] https://support.apple.com/en-us/102651 https://support.apple.com/en-us/102651
  - sneak 2y ago
    iCloud Photo e2ee still shares hashes of the plaintext with Apple, which means they can see the full list of everyone who has certain files, even if they all have e2ee enabled. They can see who had it first, and who got it later, and which sets of iCloud users have which unique files. It effectively leaks a social graph. It’s also not available in China.
    - troad 2y ago
      Interesting, good to know.
- saagarjha 2y ago
  That's the joke/implication.
vrtx0 2y ago
Is the Apple Photos feature mentioned actually implemented using Wally, or is that just speculation? From a cursory glance, the computation of centroids done on the client device seems to obviate the need for sending embedded vectors of potentially sensitive photo details — is that incorrect? I’d be curious to read a report of how on-device-only search (using latest hardware and software) is impacted by disabling the feature and/or network access…
- aeontech 2y ago
  According to this post on Apple's Machine Learning blog, yes, Wally is the method used for this feature. https://machinelearning.apple.com/research/homomorphic-encryption https://machinelearning.apple.com/research/homomorphic-encry...
  - vrtx0 2y ago
    Thank you! This is exactly the information the OP seems to have missed. It seems to confirm my suspicion that the author’s concerns about server-side privacy are unfounded — I think: > The client decrypts the reply to its PNNS query, which may contain multiple candidate landmarks. A specialized, lightweight on-device reranking model then predicts the best candidate… [please correct me if I missed anything — this used to be my field, but I’ve been disabled for 10 years now, so grain of salt]
    - chikere232 2y ago
      The devil is in the proprietary details though.
      - vrtx0 2y ago
        Sorry, what do you mean by “proprietary details”?
        sbuk 2y ago
        They are alluding to the fact that the implementation is closed source, and therefore "untrustworthy". It's a trite point, of course, but not without some merit.
rkagerer 2y ago
This would be even more exciting if there were some way to guarantee your phone, the servers, etc. are running untampered implementations, and that the proxies aren't colluding with Apple.
- avianlyric 2y ago
  If someone or something can tamper with your phone, then nobody needs to collude with proxies or Apple. They can just ask your phone to send them exactly what they want, without all the homomorphic encryption dance. The idea that Apple is going to use this feature to spy on you, completely misses the fact that they own the entire OS on your phone, and are quite capable of directly spying on you via your phone if they wanted to.
- timsneath 2y ago
  That is exactly the goal of Private Cloud Compute, part of the fabric of Apple Intelligence: https://security.apple.com/blog/private-cloud-compute/#:~:text=We%20consider%20allowing%20security%20researchers%20to%20verify%20the%20end%2Dto%2Dend%20security%20and%20privacy%20guarantees%20of%20Private%20Cloud%20Compute%20to%20be%20a%20critical%20requirement%20for%20ongoing%20public%20trust%20in%20the%20system https://security.apple.com/blog/private-cloud-compute/#:~:te....
- cryptonector 2y ago
  Upgrades have to be possible. What you want probably is attestation that you're running a generally available version that other users run too as opposed to one specially made for you, but since a version could be made for all those subject to surveillance this wouldn't be enough either. I'm not sure there's a way out of this that doesn't involve open source and repeatable builds (and watch out for Reflections on Trusting Trust).
antman 2y ago
Is there any library for e.g. fhm hash table lookup or similar? I have seen papers but have not seen a consensus of what a useful implementatio is
- hoppp 2y ago
  OpenFHE could be what you looking for. https://openfhe.org/ https://openfhe.org/
chikere232 2y ago
> You are Apple. You want to make search work like magic in the Photos app, so the user can find all their “dog” pictures with ease. What if you're a user and you don't care about searching for "dog" in your own photos, you might not even use the Photos app, but apple still scans all your photos and sends data off device without asking you? Perhaps this complicated dance works, perhaps they have made no mistakes, perhaps no one hacks or coerces the relay host providers... they could still have just asked for consent the first time you open Photos (if you ever do) before starting the scan.
- plandis 2y ago
  You can vote with your wallet and get a Pine Phone or something similar, I guess.
- deleted 2y ago
  [deleted]
- voidUpdate 2y ago
  Android does this too. I don't really want all my photos indexed like that, I just want a linear timeline of photos, but I cant turn off their "memories" thing or all the analysis they do to them
  - buran77 2y ago
    The "memories" part can be trivially done locally and probably is, it's really just reading the picture's "date taken", so it's conceptually as easy as a "sort by date". My old Android with whatever Photos app came with it (not Google's) shows this despite being disconnected for so long. There's nothing stopping either Apple or Google from giving users an option to just disable these connected features, globally or per-app. Just allow a "no cloud services" toggle switch in the Photos app, get the warning that $FEATURES will stop working, and be done. I know why Google isn't doing this, they're definitely monetizing every bit of that analyzed content. Not really sure about Apple though, might be that they consider their setup with HE as being on par with no cloud connectivity privacy wise.
t43562 2y ago
I never even knew images could be searched this way on a phone and the iPhone users in my family don't either. A huge privacy-bruising feature for nothing in our case.
- OkGoDoIt 2y ago
  I’ve been using it a lot recently. Multiple times even today while I’ve been trying to find just the right photos of my theater for a brochure I’m putting together. I have over 100,000 photos in Apple photos so even if I vaguely remember when I took a photo it’s still difficult to find it manually. As a concrete example, someone on my team today asked me “can you send me that photo from the comedy festival a couple years ago that had the nice projections on the proscenium?”. I searched apple photos (on my phone, while hiking through a park) for “sketchfest theater projection”. It used the OCR to find Sketchfest and presumably the vector embeddings of theater and projection. The one photo she was referring to was the top result. It’s pretty impressive. It can’t always find the exact photo I’m thinking of the first time, but I can generally find any vaguely-remembered photo from years ago without too much effort. It is pretty magical. You should get in the habit of trying it out, you’ll probably be pleasantly surprised.
  - deleted 2y ago
    [deleted]
- vrtx0 2y ago
  Do you mean the ability to search in Apple Photos is “privacy-bruising”, or are you referring to landmark identification? If the latter, please note that this feature doesn’t actually send a query to a server for a specific landmark — your device does the actual identification work. It’s a rather clever feature in that sense…
hoppp 2y ago
Its using Concrete from Zama. I didn't like their license because it's BSD-3-Clause-Clear but then they state: "Zama’s libraries are free to use under the BSD 3-Clause Clear license only for development, research, prototyping, and experimentation purposes. However, for any commercial use of Zama's open source code, companies must purchase Zama’s commercial patent license" So Its not free, you need to pay for patent license, and they don't disclose how much. I recommend OpenFHE as an alternative Free open source solution. I know its C++ and not Rust, but no patent license and it can do the same thing the blog post wants to do, it even has more features like proxy-reencryption that I think Concrete can't do.
- nine_k 2y ago
  How is this "BSD-licensed but only for research" not self-contradictory? It's like saying: "FREE* candy! (Free to look at, eating is $6.95 / pound)"
  - gus_massa 2y ago
    They use the patent loophole. From https://www.zama.ai/post/open-source https://www.zama.ai/post/open-source > If a company open sources their code under BSD3-clear, they can sell additional licenses to use the patents included in the open source code. In this case, it still isn’t the software that is sold, but rather the usage rights of the patented intellectual property it contains. Every day I like the Apache licence more.
  - nabla9 2y ago
    BSD+"additional clause" is not BSD. Just like 3+1 is not 3.
    - eli 2y ago
      Wouldn't the patent still be a problem with the standard BSD license? BSD would grant you license to redistribute the software but not necessarily the patent rights to use it.
      - 2y ago
k__ 2y ago
Don't they have TEE?
- j2kun 2y ago
  Doing it on device would require too much data, and TEEs have side-channel vulnerabilities making it difficult to deploy securely in prod.
RicoElectrico 2y ago
[flagged]
- barnabee 2y ago
  This is about additional new photo search capabilities that are enabled by default and powered by sending (encrypted) data derived from your photos to the cloud, not locally powered AI search.
  - sbuk 2y ago
    *Homomorphically encrypted. Be precise. Deliberately handwaving it away as "mere" encryption paints a worse picture than it actually is. Yes, possibly should have been opt-in, and a more human-friendly explanation of how it works would help. However, it's not nearly as bad as HN would have you believe. Very much a case of them pointing out that the emperor is naked, when in fact they have a few shirt buttons missing...
    - barnabee 2y ago
      Fair point, and you are right that in theory this pretty much fully preserves privacy. On the other hand, I am old enough and grumpy enough to still believe the correct number of connections an OS should make to the internet that aren't explicitly requested by the user taking an action or enabling a job/setting is zero ;-)
  - solsane 2y ago
    To be fair, it sounds like it's both. Local, AI powered 'neural hashing' + SHE
williamtrask 2y ago
I love homomorphic encryption, but why can't they just do a neural search locally? - iOS Photos -> Vectors - Search Query "Dog photos" -> Vectors - Result (Cosine Similarity): Look some dog photos! iPhones have plenty of local storage and compute power for doing this kind of thing when the phone is idle. And cosine similarity can work quickly at runtime.
- orf 2y ago
  That’s what they do
- dialup_sounds 2y ago
  Apparently they only do the cloud HE song and dance for landmarks, which is too big of a data set to realistically keep on-device.
  - deleted 2y ago
    [deleted]
- woadwarrior01 2y ago
  Here's an open source iOS app[1] that does that. Incidentally, it's built using Apple's own MobileCLIP[2] models. [1]: https://github.com/fguzman82/CLIP-Finder2 https://github.com/fguzman82/CLIP-Finder2 [2]: https://github.com/apple/ml-mobileclip https://github.com/apple/ml-mobileclip
- jerf 2y ago
  Because the blog post needs some sort of concrete example to explain, but all concrete examples of fully-homeomorphic encryption are generally done better locally at the moment due to the extreme costs of FHE.
- internetter 2y ago
  I discuss this in the post: > This seems like a lot of data the client is getting anyway. I don’t blame you for questioning if the server is actually needed. The thing is, the stored vectors that are compared against are by far the biggest storage user. Each vector can easily be multiple kilobytes. The paper discusses a database of 35 million entries divided across 8500 clusters.
AshamedCaptain 2y ago
There is another reason which I dislike this which is that now Apple has reason for "encrypted" data to be sent randomly or at least every time you take a picture. If in the future they silently change the photos app (a real risk that I have really emphasized in the past) they can now silently pass along a hash of the photo and noone would be the wiser. If an iPhone was not sending any traffic whatsoever to the mothership, at least it would ring alarm bells if it suddenly started doing so.
- commandersaki 2y ago
  Isn't this the same argument that they can change any part of the underlying OS and compromise the security by exfiltrating secret data? Why specific to this Photos feature.
  - cryptonector 2y ago
    No. GP means that if the app was not already phoning home then seeing it phone home would ring alarm bells, but if the app is always phoning home if you use it at all then you can't see "phoning home" as an alarm -- you either accept it or abandon it. Whereas if the app never phoned home and then upon upgrade it started to then you could decide to kill it and stop using the app / phone. Of course, realistically <.00001% of users would even check for unexpected phone home, or abandon the platform over any of this. So in a way you're right.
    - commandersaki 2y ago
      The post also said that now phoning home isn’t an alarm that Apple could subvert the Photos app by passing a hash of the photo (presumably sensitive data). My contention is that Apple could do that for virtually any app that talks to the mothership, and is not unique to Photos.
      - AshamedCaptain 2y ago
        Which is why I point the dangers of accepting this behavior as normal. I'm assuming you mean they could siphon the hashes of my photos through any other channel (e.g. even when calling the mothership to check for updates), but this is not entirely true. For example, were I to take a million photos, such traffic would suspiciously increase proportionally. If you accept that every photo captured will send traffic to the mothership, like the story here, then that is no longer something you can check, either. In any case, as others have mentioned, no one cares. In fact, I could argue that the scenario I'm forecasting is exactly what has already happened: the photos app suddenly started sending opaque blobs for every photo captured. A paranoid guy noticed this traffic and asked Apple about it. Apple replied with a flimsy justification, but users then go to ridiculous extremes to justify that this is not Apple spying on them, but a new super-secret-magic-sauce that cannot possibly be used to exfiltrate their data, despite the fact that Apple has provided exactly 0 verifiable assurances about it (and in fact has no way to do so). And the paranoid guy will no longer be able to notice extra per-photo traffic in the future.
JayShower 2y ago
This is so cool! I first learned about homomorphic encryption in the context of an election cybersecurity class and it seemed so pie-in-the-sky, something that would unlikely be used for general practical purposes and only ever in very niche areas. Seeing a big tech company apply it in a core product like this really does feel like a step in the right direction towards taking back some privacy.
deleted 2y ago
[deleted]
_verandaguy 2y ago
I'm not an expert in homomorphic encryption by any stretch (and I'm arguably the target audience for this blog post — a curious novice), but there's one thing I don't quite get from this post. In the "appeal to cryptographers" section (which I really look forward to being fulfilled by someone, hopefully soon!), HE is equated to post-quantum cryptography. As far as I know, most current post-quantum encryption focuses on the elimination of Diffie-Hellman schemes (both over finite fields and over elliptic curves) since those are vulnerable to Shor's algorithm. However, it's clear from the code samples later in the post (and not explained in the text, afaict) that a public key gets used to re-encrypt the resultant value of a homomorphic add or multiply. Is this a case of false equivalence (in the sense that HE != post-quantum), or is it more the case that there's some new asymmetric cryptography scheme that's not vulnerable to Shor's?
- j2kun 2y ago
  All modern HE schemes rely on post-quantum crypto. For example, the ring-LWE problem used by BFV is the same as Kyber (ML-KEM) but with different parameters. The twist in FHE is that the server also has an encryption of the user's secret key, which adds an assumption called "circular security", and that's needed to do some homomorphic operations like key switching.
  - _verandaguy 2y ago
    Right on, thanks for the explanation! So what gets called the "public key" in the blog post is just the (self?-)encrypted secret key from the user? I'll read up on your other points after work -- appreciate the search ledes :)
    - j2kun 2y ago
      The public key is also just like a normal public key, but the encrypted secret key is often called an evaluation key or a key switching key, or some other names. (It's also public in the security sense)
ge96 2y ago
This is a neat topic I want to get into more myself Searching encrypted stuff is what I wondered about, in the past I had to decrypt everything before I could use the standard sql search LIKE Funny post today about cosine similarity
renecito 2y ago
oh, if Apple had a very simple setting to toggle off sending photos to iCloud, oh, wait!!!
Raymond122 2y ago
[dead]
egorfine 2y ago
There is an app that does the photo search locally on iPhones and it feels nothing short of magic: https://queryable.app/ https://queryable.app/
moore1112 2y ago
You don't need to search much more to find out how to spy or track your boyfriend's phone. Given that males are more likely than women to cheat and that cheating rates are higher than ever, it makes sense that you would want to understand how to track your partner's phone. To spy on your lovers or anybody else, please mail her. Infocyberrecoveryinc@gmail.com

377 points by surprisetalk 2y ago

It's cool how neural networks, even convulutional ones, are one of the few applications that you can compute through homomorphic encryption without hitting a mountain of noise/bootstrapping costs. Minimal depth hurrhah!

j2kun 2y ago
I don't think Apple is doing this. They compute the embedding on device in the clear, and then just do the nearest-neighbor part in HE (which does lots of dot products but no neural network). There are people doing NNs in HE, but most implementations do indeed require bootstrapping, and for that reason they usually use CKKS.

sillysaurusx 2y ago

I was going to make my usual comment of FHE being nice in theory but too slow in practice, and then the article points out that there’s now SHE (somewhat homomorphic encryption). I wasn’t aware that the security guarantees of FHE could be relaxed without sacrificing them. That’s pretty cool. Is there any concrete info about noise budgets? It seems like that’s the critical concern, and I’d like to understand at what point precisely the security breaks down if you have too little (or too much?) noise.

bawolff 2y ago
Im not an expert on this, but my understanding is "noise" is less a security breakdown and more the entire system breaksdown. That is where the "somewhat" comes in, unlike "full" where the system can do (expensive) things to get rid of noise, in somewhat the noise just accumulates until the system stops working. (Definitely talking out of my hat here)
- sillysaurusx 2y ago
  Interesting! Are there any security concerns with SHE? If not, it sounds like all of the benefits of FHE with none of the downsides, other than the noise overwhelming the system. If that’s true, and SHE can run at least somewhat inexpensively, then this could be big. I was once super hyped about FHE till I realized it couldn’t be practical, and this has my old excitement stirring again.
  - Ar-Curunir 2y ago
    Most FHE schemes are constructed out of SHE schemes. Also, there’s nothing preventing FHE from being practical, it’s just that existing constructions are not as fast we would like them to be
  - bawolff 2y ago
    My impression is that SHE are still relatively expensive, not as crazy as FHE but still slow enough to preclude many usecases and the noise breakdown can happen relatively quickly making them not work for most algorithms people want to use FHE for.
  - j2kun 2y ago
    Wait until you see all the ASICs getting taped out by various companies right now.
ruined 2y ago
it's incredibly algorithm-dependent. if you look into the thesis that originates the 'bootstrapping' technique to transform SHE algorithms into FHE, they determine the noise limit of their specific algorithm in section 7.3 and then investigate expanding the noise limit in 8 and 10. (written in 2009) http://crypto.stanford.edu/craig/craig-thesis.pdf http://crypto.stanford.edu/craig/craig-thesis.pdf some newer FHE don't encounter a noise limit or don't use the bootstrapping technique.
- Ar-Curunir 2y ago
  All known FHE schemes use bootstrapping
  - ruined 2y ago
    i expected that, but a search turned up several things claiming to implement fhe without bootstrapping. i didn't investigate and i can't say i'm familiar so maybe they're bogus
    - Ar-Curunir 2y ago
      Correction: all known even-remotely-practical schemes rely on bootstrapping. See https://crypto.stackexchange.com/questions/103341/fully-homomorphic-encryption-without-bootstrapping https://crypto.stackexchange.com/questions/103341/fully-homo...
      - slow_typist 2y ago
        As always, there is no free lunch.
    - j2kun 2y ago
      I did see an arxiv paper a while back that claimed to use category theory to do this, but my best bet was it was not secure.
Ar-Curunir 2y ago
SHE doesn’t relax security guarantees, it relaxes the class of supported computations
3s 2y ago
SHE vs FHE has nothing to do with security. Instead, it’s about how many operations (eg homomorphic multiplications and additions) can be performed before the correctness of the scheme fails due to too much noise accumulating in the ciphertext. Indeed all FHE schemes are also SHE schemes. What typically makes FHE expensive computationally is a “bootstrapping” step for removing the noise that accumulated after X operations and threatening correctness. After bootstrapping you can do another X operations. Rinse and repeat until you finish the computation to you want to perform.
twodave 2y ago
Not sure whether they use FHE or not (the literature I’m looking at simply says “homomorphic”), but we use ElectionGuard at our company to help verify elections for our customers. So there are definitely some practical uses.

timsneath 2y ago

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

GeekyBear 2y ago
> One example of how we’re using this implementation in iOS 18, is the new Live Caller ID Lookup feature, which provides caller ID and spam blocking services. 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. Privacy by design is always nice to see.
- gus_massa 2y ago
  I don't undertand how it can work. I assume the spam list is shared by all users, oherwise it will no be useful at all: Let's supouse Apple is evil (or they recive an order from a judge) and they want to know who is calling 5555-1234 1) Add a new empty "spam" numbers encrypted database to the server (so there are now two encrypted databases in the system) 2) Add the encrited version of 5555-1234 to it. 3) When someone checks, reply the correct answer from the real database and also check in the second one and send the reply to the police.
  - colejohnson66 2y ago
    Encryptions uses per-device keys.
  - GeekyBear 2y ago
    > they recive an order from a judge You can't be forced to hand over customer data after you have designed a system so that your servers don't ever have that information stored in the first place, court order or no.
  - jakelazaroff 2y ago
    How would they decrypt the answer from the database?

j16sdiz 2y ago

> The two hops, the two companies, are already acting in partnership, so what is there technically in the relay setup to stop the two companies from getting together—either voluntarily or at the secret command of some government—to compare notes, as it were, and connect the dots? The OHTTP scheme does not _technically_ prevent this. It increases the number parties need to cooperate to extract this information, hoping it would be caught somewhere in the pipeline.

chikere232 2y ago
and if a government say already forced ISPs to collect metadata about who connects to whom and when, I imagine they don't even need to bother getting data from the relay hosts

eviks 2y ago

> There is no trust me bro element. > Barring some issue being found in the math or Apple’s implementation of it Yes, is you bar the "trust me bro" element in your definition, you'll by definition have no such element. Reality, though, doesn't care about your definition, so in reality this is exactly the "trust me bro" element that exists > But we’re already living in a world where all our data is up there, not in our hands. If that's your real view, then why do you care about all this fancy encryption at all? It doesn't help if everything is already lost

rpearl 2y ago
I mean if you'd like, you could reimplement the necessary client on an airgapped computer, produce an encrypted value, take that value to a networked computer, send it to the server, obtain an encrypted result that the server could not possibly know how to decrypt, and see if it has done the computation in question. No trust is required. You could also observe all bits leaving the device from the moment you initialize it and determine that only encrypted bits leave and that no private keys leave, which only leaves the gap of some side channel at the factory, but you could perform the calculation to see that the bits are only encrypted with the key you expect them to be encrypted with.
- Krasnol 2y ago
  How is this comment useful to the OPs valid arguments?

sneak 2y ago

> This should be fine: vectorization is a lossy operation. But then you would know that Amy takes lots of pictures of golden retrievers, and that is a political disaster. This downplays the issue. Knowing that Alice takes lots of screenshots of Winnie the Pooh memes means that Alice’s family gets put into Xinjiang concentration camps, not just a political disaster. (This is a contrived example: iCloud Photos is already NOT e2ee and this is already possible now; but the point stands, as this would apply to people who have iCloud turned off, too.)

troad 2y ago
Agreed. And for a less contrived example, people may have photos of political protests that they attended (and the faces of others present), screenshots that include sensitive messages, subversive acts, etc. It's worth noting though that it's now possible to opt in to iCloud Photo e2ee with "Advanced Data Protection". [0] [0] https://support.apple.com/en-us/102651 https://support.apple.com/en-us/102651
- sneak 2y ago
  iCloud Photo e2ee still shares hashes of the plaintext with Apple, which means they can see the full list of everyone who has certain files, even if they all have e2ee enabled. They can see who had it first, and who got it later, and which sets of iCloud users have which unique files. It effectively leaks a social graph. It’s also not available in China.
  - troad 2y ago
    Interesting, good to know.
saagarjha 2y ago
That's the joke/implication.

vrtx0 2y ago

Is the Apple Photos feature mentioned actually implemented using Wally, or is that just speculation? From a cursory glance, the computation of centroids done on the client device seems to obviate the need for sending embedded vectors of potentially sensitive photo details — is that incorrect? I’d be curious to read a report of how on-device-only search (using latest hardware and software) is impacted by disabling the feature and/or network access…

aeontech 2y ago
According to this post on Apple's Machine Learning blog, yes, Wally is the method used for this feature. https://machinelearning.apple.com/research/homomorphic-encryption https://machinelearning.apple.com/research/homomorphic-encry...
- vrtx0 2y ago
  Thank you! This is exactly the information the OP seems to have missed. It seems to confirm my suspicion that the author’s concerns about server-side privacy are unfounded — I think: > The client decrypts the reply to its PNNS query, which may contain multiple candidate landmarks. A specialized, lightweight on-device reranking model then predicts the best candidate… [please correct me if I missed anything — this used to be my field, but I’ve been disabled for 10 years now, so grain of salt]
  - chikere232 2y ago
    The devil is in the proprietary details though.
    - vrtx0 2y ago
      Sorry, what do you mean by “proprietary details”?
      - sbuk 2y ago
        They are alluding to the fact that the implementation is closed source, and therefore "untrustworthy". It's a trite point, of course, but not without some merit.

rkagerer 2y ago

This would be even more exciting if there were some way to guarantee your phone, the servers, etc. are running untampered implementations, and that the proxies aren't colluding with Apple.

avianlyric 2y ago
If someone or something can tamper with your phone, then nobody needs to collude with proxies or Apple. They can just ask your phone to send them exactly what they want, without all the homomorphic encryption dance. The idea that Apple is going to use this feature to spy on you, completely misses the fact that they own the entire OS on your phone, and are quite capable of directly spying on you via your phone if they wanted to.
timsneath 2y ago
That is exactly the goal of Private Cloud Compute, part of the fabric of Apple Intelligence: https://security.apple.com/blog/private-cloud-compute/#:~:text=We%20consider%20allowing%20security%20researchers%20to%20verify%20the%20end%2Dto%2Dend%20security%20and%20privacy%20guarantees%20of%20Private%20Cloud%20Compute%20to%20be%20a%20critical%20requirement%20for%20ongoing%20public%20trust%20in%20the%20system https://security.apple.com/blog/private-cloud-compute/#:~:te....
cryptonector 2y ago
Upgrades have to be possible. What you want probably is attestation that you're running a generally available version that other users run too as opposed to one specially made for you, but since a version could be made for all those subject to surveillance this wouldn't be enough either. I'm not sure there's a way out of this that doesn't involve open source and repeatable builds (and watch out for Reflections on Trusting Trust).

antman 2y ago

Is there any library for e.g. fhm hash table lookup or similar? I have seen papers but have not seen a consensus of what a useful implementatio is

hoppp 2y ago
OpenFHE could be what you looking for. https://openfhe.org/ https://openfhe.org/

chikere232 2y ago

> You are Apple. You want to make search work like magic in the Photos app, so the user can find all their “dog” pictures with ease. What if you're a user and you don't care about searching for "dog" in your own photos, you might not even use the Photos app, but apple still scans all your photos and sends data off device without asking you? Perhaps this complicated dance works, perhaps they have made no mistakes, perhaps no one hacks or coerces the relay host providers... they could still have just asked for consent the first time you open Photos (if you ever do) before starting the scan.

plandis 2y ago
You can vote with your wallet and get a Pine Phone or something similar, I guess.
deleted 2y ago
[deleted]
voidUpdate 2y ago
Android does this too. I don't really want all my photos indexed like that, I just want a linear timeline of photos, but I cant turn off their "memories" thing or all the analysis they do to them
- buran77 2y ago
  The "memories" part can be trivially done locally and probably is, it's really just reading the picture's "date taken", so it's conceptually as easy as a "sort by date". My old Android with whatever Photos app came with it (not Google's) shows this despite being disconnected for so long. There's nothing stopping either Apple or Google from giving users an option to just disable these connected features, globally or per-app. Just allow a "no cloud services" toggle switch in the Photos app, get the warning that $FEATURES will stop working, and be done. I know why Google isn't doing this, they're definitely monetizing every bit of that analyzed content. Not really sure about Apple though, might be that they consider their setup with HE as being on par with no cloud connectivity privacy wise.

t43562 2y ago

I never even knew images could be searched this way on a phone and the iPhone users in my family don't either. A huge privacy-bruising feature for nothing in our case.

OkGoDoIt 2y ago
I’ve been using it a lot recently. Multiple times even today while I’ve been trying to find just the right photos of my theater for a brochure I’m putting together. I have over 100,000 photos in Apple photos so even if I vaguely remember when I took a photo it’s still difficult to find it manually. As a concrete example, someone on my team today asked me “can you send me that photo from the comedy festival a couple years ago that had the nice projections on the proscenium?”. I searched apple photos (on my phone, while hiking through a park) for “sketchfest theater projection”. It used the OCR to find Sketchfest and presumably the vector embeddings of theater and projection. The one photo she was referring to was the top result. It’s pretty impressive. It can’t always find the exact photo I’m thinking of the first time, but I can generally find any vaguely-remembered photo from years ago without too much effort. It is pretty magical. You should get in the habit of trying it out, you’ll probably be pleasantly surprised.
- deleted 2y ago
  [deleted]
vrtx0 2y ago
Do you mean the ability to search in Apple Photos is “privacy-bruising”, or are you referring to landmark identification? If the latter, please note that this feature doesn’t actually send a query to a server for a specific landmark — your device does the actual identification work. It’s a rather clever feature in that sense…

hoppp 2y ago

Its using Concrete from Zama. I didn't like their license because it's BSD-3-Clause-Clear but then they state: "Zama’s libraries are free to use under the BSD 3-Clause Clear license only for development, research, prototyping, and experimentation purposes. However, for any commercial use of Zama's open source code, companies must purchase Zama’s commercial patent license" So Its not free, you need to pay for patent license, and they don't disclose how much. I recommend OpenFHE as an alternative Free open source solution. I know its C++ and not Rust, but no patent license and it can do the same thing the blog post wants to do, it even has more features like proxy-reencryption that I think Concrete can't do.

nine_k 2y ago
How is this "BSD-licensed but only for research" not self-contradictory? It's like saying: "FREE* candy! (Free to look at, eating is $6.95 / pound)"
- gus_massa 2y ago
  They use the patent loophole. From https://www.zama.ai/post/open-source https://www.zama.ai/post/open-source > If a company open sources their code under BSD3-clear, they can sell additional licenses to use the patents included in the open source code. In this case, it still isn’t the software that is sold, but rather the usage rights of the patented intellectual property it contains. Every day I like the Apache licence more.
- nabla9 2y ago
  BSD+"additional clause" is not BSD. Just like 3+1 is not 3.
  - eli 2y ago
    Wouldn't the patent still be a problem with the standard BSD license? BSD would grant you license to redistribute the software but not necessarily the patent rights to use it.
    - 2y ago

k__ 2y ago

Don't they have TEE?

j2kun 2y ago
Doing it on device would require too much data, and TEEs have side-channel vulnerabilities making it difficult to deploy securely in prod.

RicoElectrico 2y ago

[flagged]

barnabee 2y ago
This is about additional new photo search capabilities that are enabled by default and powered by sending (encrypted) data derived from your photos to the cloud, not locally powered AI search.
- sbuk 2y ago
  *Homomorphically encrypted. Be precise. Deliberately handwaving it away as "mere" encryption paints a worse picture than it actually is. Yes, possibly should have been opt-in, and a more human-friendly explanation of how it works would help. However, it's not nearly as bad as HN would have you believe. Very much a case of them pointing out that the emperor is naked, when in fact they have a few shirt buttons missing...
  - barnabee 2y ago
    Fair point, and you are right that in theory this pretty much fully preserves privacy. On the other hand, I am old enough and grumpy enough to still believe the correct number of connections an OS should make to the internet that aren't explicitly requested by the user taking an action or enabling a job/setting is zero ;-)
- solsane 2y ago
  To be fair, it sounds like it's both. Local, AI powered 'neural hashing' + SHE

williamtrask 2y ago

I love homomorphic encryption, but why can't they just do a neural search locally? - iOS Photos -> Vectors - Search Query "Dog photos" -> Vectors - Result (Cosine Similarity): Look some dog photos! iPhones have plenty of local storage and compute power for doing this kind of thing when the phone is idle. And cosine similarity can work quickly at runtime.

orf 2y ago
That’s what they do
dialup_sounds 2y ago
Apparently they only do the cloud HE song and dance for landmarks, which is too big of a data set to realistically keep on-device.
- deleted 2y ago
  [deleted]
woadwarrior01 2y ago
Here's an open source iOS app[1] that does that. Incidentally, it's built using Apple's own MobileCLIP[2] models. [1]: https://github.com/fguzman82/CLIP-Finder2 https://github.com/fguzman82/CLIP-Finder2 [2]: https://github.com/apple/ml-mobileclip https://github.com/apple/ml-mobileclip
jerf 2y ago
Because the blog post needs some sort of concrete example to explain, but all concrete examples of fully-homeomorphic encryption are generally done better locally at the moment due to the extreme costs of FHE.
internetter 2y ago
I discuss this in the post: > This seems like a lot of data the client is getting anyway. I don’t blame you for questioning if the server is actually needed. The thing is, the stored vectors that are compared against are by far the biggest storage user. Each vector can easily be multiple kilobytes. The paper discusses a database of 35 million entries divided across 8500 clusters.

AshamedCaptain 2y ago

There is another reason which I dislike this which is that now Apple has reason for "encrypted" data to be sent randomly or at least every time you take a picture. If in the future they silently change the photos app (a real risk that I have really emphasized in the past) they can now silently pass along a hash of the photo and noone would be the wiser. If an iPhone was not sending any traffic whatsoever to the mothership, at least it would ring alarm bells if it suddenly started doing so.

commandersaki 2y ago
Isn't this the same argument that they can change any part of the underlying OS and compromise the security by exfiltrating secret data? Why specific to this Photos feature.
- cryptonector 2y ago
  No. GP means that if the app was not already phoning home then seeing it phone home would ring alarm bells, but if the app is always phoning home if you use it at all then you can't see "phoning home" as an alarm -- you either accept it or abandon it. Whereas if the app never phoned home and then upon upgrade it started to then you could decide to kill it and stop using the app / phone. Of course, realistically <.00001% of users would even check for unexpected phone home, or abandon the platform over any of this. So in a way you're right.
  - commandersaki 2y ago
    The post also said that now phoning home isn’t an alarm that Apple could subvert the Photos app by passing a hash of the photo (presumably sensitive data). My contention is that Apple could do that for virtually any app that talks to the mothership, and is not unique to Photos.
    - AshamedCaptain 2y ago
      Which is why I point the dangers of accepting this behavior as normal. I'm assuming you mean they could siphon the hashes of my photos through any other channel (e.g. even when calling the mothership to check for updates), but this is not entirely true. For example, were I to take a million photos, such traffic would suspiciously increase proportionally. If you accept that every photo captured will send traffic to the mothership, like the story here, then that is no longer something you can check, either. In any case, as others have mentioned, no one cares. In fact, I could argue that the scenario I'm forecasting is exactly what has already happened: the photos app suddenly started sending opaque blobs for every photo captured. A paranoid guy noticed this traffic and asked Apple about it. Apple replied with a flimsy justification, but users then go to ridiculous extremes to justify that this is not Apple spying on them, but a new super-secret-magic-sauce that cannot possibly be used to exfiltrate their data, despite the fact that Apple has provided exactly 0 verifiable assurances about it (and in fact has no way to do so). And the paranoid guy will no longer be able to notice extra per-photo traffic in the future.

JayShower 2y ago

This is so cool! I first learned about homomorphic encryption in the context of an election cybersecurity class and it seemed so pie-in-the-sky, something that would unlikely be used for general practical purposes and only ever in very niche areas. Seeing a big tech company apply it in a core product like this really does feel like a step in the right direction towards taking back some privacy.

deleted 2y ago

[deleted]

_verandaguy 2y ago

I'm not an expert in homomorphic encryption by any stretch (and I'm arguably the target audience for this blog post — a curious novice), but there's one thing I don't quite get from this post. In the "appeal to cryptographers" section (which I really look forward to being fulfilled by someone, hopefully soon!), HE is equated to post-quantum cryptography. As far as I know, most current post-quantum encryption focuses on the elimination of Diffie-Hellman schemes (both over finite fields and over elliptic curves) since those are vulnerable to Shor's algorithm. However, it's clear from the code samples later in the post (and not explained in the text, afaict) that a public key gets used to re-encrypt the resultant value of a homomorphic add or multiply. Is this a case of false equivalence (in the sense that HE != post-quantum), or is it more the case that there's some new asymmetric cryptography scheme that's not vulnerable to Shor's?

j2kun 2y ago
All modern HE schemes rely on post-quantum crypto. For example, the ring-LWE problem used by BFV is the same as Kyber (ML-KEM) but with different parameters. The twist in FHE is that the server also has an encryption of the user's secret key, which adds an assumption called "circular security", and that's needed to do some homomorphic operations like key switching.
- _verandaguy 2y ago
  Right on, thanks for the explanation! So what gets called the "public key" in the blog post is just the (self?-)encrypted secret key from the user? I'll read up on your other points after work -- appreciate the search ledes :)
  - j2kun 2y ago
    The public key is also just like a normal public key, but the encrypted secret key is often called an evaluation key or a key switching key, or some other names. (It's also public in the security sense)

ge96 2y ago

This is a neat topic I want to get into more myself Searching encrypted stuff is what I wondered about, in the past I had to decrypt everything before I could use the standard sql search LIKE Funny post today about cosine similarity

renecito 2y ago

oh, if Apple had a very simple setting to toggle off sending photos to iCloud, oh, wait!!!

Raymond122 2y ago

[dead]

egorfine 2y ago

There is an app that does the photo search locally on iPhones and it feels nothing short of magic: https://queryable.app/ https://queryable.app/

moore1112 2y ago

You don't need to search much more to find out how to spy or track your boyfriend's phone. Given that males are more likely than women to cheat and that cheating rates are higher than ever, it makes sense that you would want to understand how to track your partner's phone. To spy on your lovers or anybody else, please mail her. Infocyberrecoveryinc@gmail.com