13 ms·
Fully Homomorphic Encryption (FHE)
- viro 5y agohonestly FHE is voodoo to me
- 3np 5y agoMaybe it helps to think of HE you're already familiar with. For example, RSA is homomorphic under multiplication - so you can multiply two ciphertexts and get back an encrypted result. If this can be done for the right subset of operations, you can construct a fully homomorphic scheme. To get anything deeper than that intuitive understanding you'd have to dive into individual protocols :) https://crypto.stackexchange.com/questions/3555/homomorphic-cryptosystems-in-rsa https://crypto.stackexchange.com/questions/3555/homomorphic-...
- schoen 5y ago> For example, RSA is homomorphic under multiplication - so you can multiply two ciphertexts and get back an encrypted result. That's also related to why blind signatures work, but also to why RSA padding is necessary (to intentionally break this property!). https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_signatures https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_sign... https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_against_plain_RSA https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga... I guess blind signatures may also helpful for this intuition.
- jcbsd 5y agoCheck this out: https://6min.zama.ai https://6min.zama.ai Helps to demystify the voodoo :)
- acjohnson55 5y agoThis seems pretty revolutionary, if indeed arbitrary C++ programs can be written as FHE. Are there any key limitations?
- entire-name 5y agoIt has a dependency on XLS[cc], so they share their limitations: https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler#limitations https://github.com/google/fully-homomorphic-encryption/tree/...
- BelenusMordred 5y ago> Are there any key limitations? It's slow, you would not want any part of your program that isn't security critical using it.
- R0b0t1 5y agoThis may not always be true.
- hansvm 5y agoSlowness is necessary to some degree. Early stopping leaks information, so FHE algorithms wind up being worst-case for all inputs (e.g., O(N) to find the value for a key).
- DaiPlusPlus 5y agoI think `O(log n)` for key-lookup, assuming fully-indexed data, should be sufficient, as that's the worst-case lookup time in a balanced tree. Methinks this has interesting implications for storage-optimizations: in many situations we will significantly-optimize for certain use-cases at the expense of others (e.g. O(1) or sub-O(log n) retrieval at the cost of super-O(log n) insert or modifications) - but because now you know your program cannot appear to operate faster than O(log n) for any operation you could de-optimize some parts of your program which in turn allow you to improve sub-O(log n) parts to be O(log n), e.g. insert/update performance.
- Dylan16807 5y agoO(log n) lookups are impossible under FHE. Let's say you have a sorted array, and try to do a binary search. For each 'if', the only way to calculate it is to take both branches and combine them later. So for x branches in a row, you need to do 2^x calculations. O(2^logn) = O(n) If you have a tree that uses pointers, you're even worse off. Chasing a pointer under FHE has a cost O(y), where y is the size of your memory. Assuming y is proportional to n, that's O(n log n) just to look up a single key.
- deleted 5y ago[deleted]
- bsdnoob 5y agoanyone mind explaining how this works?
- coolspot 5y agoThis one helped me to grasp the idea: https://blog.cryptographyengineering.com/2012/01/02/very-casual-introduction-to-fully/ https://blog.cryptographyengineering.com/2012/01/02/very-cas...
- dang 5y agoThere's also https://developers.googleblog.com/2021/06/our-latest-updates-on-fully-homomorphic-encryption.html https://developers.googleblog.com/2021/06/our-latest-updates... (via https://news.ycombinator.com/item?id=27505741 https://news.ycombinator.com/item?id=27505741).
- dcow 5y agoI found https://homomorphicencryption.org https://homomorphicencryption.org to be a helpful resource as well.
- ignoramous 5y agoAnd: 1. https://cseweb.ucsd.edu/~daniele/LatticeLinks/FHE.html https://cseweb.ucsd.edu/~daniele/LatticeLinks/FHE.html 2. https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html
- josephg 5y agoThis is super cool! For a long time I've wanted a database in the cloud where my cloud provider can't quietly look through all my data. Thats easy enough to do by encrypting specific database entries, but the problem comes from indexing. Most of the obvious ways you could implement an index accidentally end up leaking information as a result of their access patterns. I'm curious if this approach could be used to build database indexes, and if so, whats the performance cost in using it? I read about an approach a few years ago which needed hundreds of milliseconds of computation for simple operations. Has the state of the art improved?
- warkdarrior 5y agoFor (database) index structures, you want something like Oblix: https://people.eecs.berkeley.edu/~raluca/oblix.pdf https://people.eecs.berkeley.edu/~raluca/oblix.pdf [PDF]
- Ar-Curunir 5y agoMore generally you want systems that implement oblivious accesses. There’s been a lot of cool work recently in making thi more practical, and I’m excited to see how it pans out in the near future :) I will also note that for efficiency, Oblix relies on Intel SGX. I’m not sure if a purely cryptographic solution can provide the same security and efficiency properties.
- warkdarrior 5y agoORAM provides the purely cryptographic solution, but you have to pick your scheme based on the amount of leakage you are willing to have. In the worst case accessing one row in a database would require reading the whole database.
- ignoramous 5y agoWell, FHE may not be there yet but there are other approaches using functional encryption (?) [ref] concepts, like this one I stumbled upon: https://www.cossacklabs.com/blog/secure-search-over-encrypted-data-acra-se.html https://www.cossacklabs.com/blog/secure-search-over-encrypte... [ref] https://cseweb.ucsd.edu/~daniele/LatticeLinks/FE.html https://cseweb.ucsd.edu/~daniele/LatticeLinks/FE.html
- schmorptron 5y agoDamn, it's 8 in the morming and I was really confused what fully homophobic encryption was supposed to be. That aside, this could be really useful though, if it gets implemented without too much performance loss. It might make using cloud storage services or stuff like Google Photos less problematic. Are there any examples of software services that already successfuly use this?
- qwerty456127 5y agoThis is a common confusion. Google homophobic encryption and you'll find quite a number of results.
- PeterisP 5y agoAre there any benchmarks to estimate its usability? I first encountered FHE many years ago, but while the concept is cool, the performance hit (IIRC I saw literally a million times slowdown back then) made it absolutely impractical for non-toy problems. And whenever I see reports, they tend to note that it's slow, just as this project (https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler https://github.com/google/fully-homomorphic-encryption/tree/...) notes "the run-times of the FHE-C++ operations are likely to be too long to be practical at this time.", it does not provide any data on just how slow it is. Are there measurements on how long the demos take to execute, so that I can evaluate if it has the potential for some specific idea without having to set up the build system to try it out myself? E.g. run the same string capitalization demo on 100, 10 000 and 1 000 0000 characters to benchmark its speed.
- Iv 5y agoCynical remark: all processes requiring a million times more cycles is the dream of many chip-making companies.
- de_keyboard 5y agoIs it though? If chips had fewer practical applications, fewer people will buy them.
- Iv 5y agoOh right now there is no shortage of needs, thanks to AI applications mostly, but I could see homomorphic encryption as the next moat that datacenters propose.
- ivanhoe 5y agoDoes it also make it proportionally slower to brute-force attack it?
- lentilcorba 5y agoSure, if the algorithm you want to brute force is slower, it will take longer to break it. This is e.g. why password hashes use the slow bcrypt rather then the fast SHA-256 hashing algorithm. [https://auth0.com/blog/hashing-passwords-one-way-road-to-security/#No-Need-for-Speed https://auth0.com/blog/hashing-passwords-one-way-road-to-sec...]
- rhindi 5y agoIf it helps, we did a mini site to explain FHE: https://6min.zama.ai https://6min.zama.ai
- _nub3 5y agoI wonder why nobody mentioned palisade, a mature and open source FHE. > PALISADE now supports the BGV, BFV, CKKS, and FHEW schemes and a more secure variant of the TFHE scheme, including bootstrapping. From https://palisade-crypto.org/ https://palisade-crypto.org/
- oulipo 5y agoAnd also Concrete by Zama, coded in Rust https://github.com/zama-ai/concrete https://github.com/zama-ai/concrete
- IceTDrinker 5y agoMy guess would be usability, the google approach let's anyone knowing C++ (constrained by the supported sets of operations from the language) actually create an FHE program without having to know anything about crypto. Maybe PALISADE is not user friendly enough? Just a wild guess I never used PALISADE
- YeGoblynQueenne 5y ago>> FHE can change the way computations are performed by preserving privacy end-to-end, thereby giving users even greater confidence that their information will remain private and secure. "Even greater"! Wow! Even greater than what?
- 3np 5y agoEven greater than “pinky promise”, which is the current status quo and equal to 0.
- IceTDrinker 5y agoThe idea today is that you rely on sharing a key with the server (through a secure protocol) but the server still has to decrypt your data to do anything with it and then encrypt it back and send the result to you. With FHE, if the server runs FHE software then you can encrypt your data with your secret key without ever disclosing it to the server (as it does not need it to compute stuff on your data). The benefits are many: the server never has to know anything about your data (imagine a MedTech company doing diagnosis, your medical data will be safe from their prying eyes). If the server is compromised, the attacker cannot look at your data, potentially no more private information leak! On the regulatory side you potentially don't have to worry about GDPR anymore, you can't access the data of your users.
- jcbsd 5y agoAlso, you don't have to care where the data is being stored, because if it's fully end-to-end encrypted, location is far less of an issue (to your GDPR point). Alleviates a lot of the talk around the security risks posed by the unrestricted sale and transfer of sensitive data to foreign adversaries (China, Russia) that dominates the political landscape in the U.S.
- egberts1 5y agoFHE is useful for nation-state to groom for certain “patterns”.
- ssmiler 5y agoOther threads on HE compilers: Microsoft/EVA - https://news.ycombinator.com/item?id=25193863 https://news.ycombinator.com/item?id=25193863 Alchemy - https://news.ycombinator.com/item?id=18265948 https://news.ycombinator.com/item?id=18265948 Cingulata - https://news.ycombinator.com/item?id=23437737 https://news.ycombinator.com/item?id=23437737 And a good overview of HE compilers/libraries https://arxiv.org/pdf/2101.07078.pdf https://arxiv.org/pdf/2101.07078.pdf
- blauditore 5y agoI'm trying to understand what kind of computations would be done on encrypted data. For cases where computation depends on the raw data (conditionally), this would not be feasible. For other cases, such as e.g. training some ML model to map inputs to output, this could also be done on any non-homomophically ecrypted data. What are actually use cases for computations on FHE data? Edit: Thinking of it more, I could imagine some sort of image transformations (e.g. a blur filter) as applications - but those are fairly corner use cases, are there more broad ones?
- ohgodplsno 5y agoHospital saves data about a patient in a theoretical common file that tracks all his health info, but solely belongs to the patient. Insurance wants to add data about some reimbursements for glasses they've done, but should not be allowed to see his medical conditions. FHE lets you work on the data and update it without ever revealing the contents.
- danuker 5y agoSo, you could do the same with an append-only log with no read permissions?
- ElFitz 5y agoAccept that, in the case of your append-only log, you need to trust that someone is applying that lack of read permission to themselves. And that they do it well.
- duckerude 5y agoCouldn't regular asymmetric encryption take care of that? Just encrypt each entry with the patient's public key. I think you only need homomorphic encryption if the transformation is something that the owner of data can't or shouldn't do themselves. It would be overkill for simple financial information.
- gnull 5y agoRemember that FHE does not ensure authenticity of your data by default, it provides only privacy. If you send your server two encryped numbers and ask to multiply them for you, the server may send you their addition instead, or just encrypt some constant it chooses and send you that. And you can't check that your data was processed the way you want. If you want authenticated FHE, that will be even slower. For anyone who wanted a database to query privately, you can look at dishonest majority generic MPC protocols. Here, you will need N servers instead of just one. You will secret-share your inputs between them, and let them do computations on the shares. As long as at least one of the N servers is acting in your interest, you are safe. But if all servers unite their shares, they can recover your values.
- qayxc 5y ago> If you send your server two encryped numbers and ask to multiply them for you, the server may send you their addition instead, or just encrypt some constant it chooses and send you that. That's not what FHE intends to solve. You have the exact same problem with any kind of remote processing, encrypted or not. I don't see why you think it's important to point out the obvious.
- klempotres 5y agoBecause it is crucial in practice, right?
- qayxc 5y agoIs it, though? OTOH I cannot think of a single service or provider thereof that makes any guarantees about the trustworthiness of the actual calculation being performed as suggested by the GP. While trusted computing could be used for such verification, I'm not aware of any commercial real world implementation. I'd be genuinely happy to be made aware of one, though, so please feel free to point me to one.
- anonymousDan 5y ago
- polskibus 5y agoIs that project used by google (or anyone else) for anything? I would be interested in production usage of such library before trying it out.
- Gxtaillon 5y agoIs this the first published implementation of that Booleanifier technique? Google/Bing/DuckDuckGo either return nothing or return nothing related for Booleanifier.
- praash 5y agoWhilst demonstrating incredible bleeding edge technology, the Hangman example is hardcoded. https://github.com/google/fully-homomorphic-encryption/blob/main/transpiler/examples/hangman/hangman_api.cc https://github.com/google/fully-homomorphic-encryption/blob/... It's such a convenient parody of a classic programming exercise that it must be intentional. I can't help laughing at how that one file is saying two things at once: "Uh, it's one-word Hangman. Dead simple. Nothing up our sleeves. I have Real Stuff to do, give me a break." "Our product is working great, but there's some minor fixes to do. Let's hold a meeting on how to really get this multi-word support cracked. Maybe add 'privacy-aware' and 'digitalization'?" Surprisingly, it's also making it very easy to understand what is actually relevant in the project.
- not_kurt_godel 5y agoSame thing with the calculator example. It's not doing anything with FHE. Do any of the examples actually do anything??
- PeterisP 5y agoIMHO the key thing is that any proper hangman implementation would require much more computing on the FHE side than the six if-statements it currenly has. Currently even for such a toy problem as much as possible is moved to the non-FHE client.
- sometimesshit 5y agoHomomorphic always felt like a magic to me. it blow me away when I first heard it.
- rhindi 5y agoIt's really great to see more big companies getting into this game, ease of adoption is really the key here. When it comes to FHE, there are 3 underlying paradigms you can target with compilers: 1. boolean circuits, where you represent your program as encrypted boolean gates. The advantage is that it's as generic as it gets, the drawback is that it's slow. TFHE is great for that, and it's what is shown here. 2. arithmetic circuits, where you represent your program as a combination of encrypted additions and multiplications. This goes much faster, but you are quickly limited in terms of usecases because you can only do a certain number of arithmetic operations. CKKS/SEAL targets that: https://www.microsoft.com/en-us/research/project/microsoft-seal/ https://www.microsoft.com/en-us/research/project/microsoft-s... 3. functional circuits, where you represent your program as a combination of homomorphic functions. Advantage is that you can do very complex things like deep neural network, the drawback being that you have limitations of the bits of precision for the computations. Concrete targets that: https://zama.ai/concrete/ https://zama.ai/concrete/
- ganafagol 5y agoThese are all the same paradigm, in priciple. 2 is a special case of 3 and 1 is a special case of 2. All circuits differing in how powerful the processing nodes are.
- rhindi 5y agoYes, in practice however it makes a difference. Consider for example computing the ReLu function for a neural network: - With boolean circuits you need to run dozens of boolean gates, which means a lot of underlying crypto ops. Works but expensive. - with arithmetic circuits, you would approximate it using polynomials. Works but not with high precision. - with functional circuits, you encore the function as a single “bootstrapping” operation. Works in a single crypto op. Performance / precision tradeoffs will be very different in these 3 cases
- swiley 5y agoThe probably like it because it will let them run whatever they want on end user devices without having to deal with interference from the user.
- johbjo 5y agoOne real world use-case of ~HE is blind auctions, where no one can see the bids. Electronic voting is tangential. Encrypted storage for random cloud services should be at least decades away.
- thangalin 5y ago> Electronic voting is tangential. Of possible interest is a design for an online deliberation system: https://bytebucket.org/djarvis/world-politics/raw/master/docs/manual/manual.pdf https://bytebucket.org/djarvis/world-politics/raw/master/doc... HE would be useful to help hide the votes.