10 ms·
Cingulata: Run C++ code over encrypted data with fully homomorphic encryption
- asdfaoeu 6y ago47 upvotes, no comments. I'm guessing no one understands this.
- jacobush 6y agoYep. Was hoping for someone to debunk or explain. My (probably deeply flawed) hunch was that one would need some kind of specialised virtual machine or something to make homomorphic stuff. I'm babbling now. Yes, someone please explain Cingulata.
- qayxc 6y agoCingulata is a system for secure, privacy preserving applications based on homomorphic encryption. Homomorphic encryption is a form of cryptography that allows for operations on encrypted content to yield the same results (though encrypted) as if applied to plain text input. Basically, the framework takes algorithms implemented in C++ into a virtual boolean circuit that operates on encrypted data. This means you can run your database, AI training, page ranking, etc. on encrypted data for a truly end-to-end encrypted processing or computation on untrusted devices or environments (cloud computing!). This comes at a price, though, as the virtual circuit is basically a software interpreter for your original algorithm and thus is abysmally slow compared to the original code... At least that's my understanding of the system.
- radres 6y agoSo I can give an executable to anyone in the world and they cannot get to my source code?
- layoutIfNeeded 6y agoNo. You have a function F which maps inputs x to outputs y. You transform this function into new one F', that will map the encrypted inputs encrypt(x) to the encrypted outputs encrypt(y), without knowing how to decrypt. F(x) = y F'(encrypt(x)) = encrypt(y)
- russfink 6y agoThis is correct. Additionally, the entity performing the computation does not get to learn the answer. This is an important distinction between a technique such as this, and software obfuscation.
- aruss 6y agoNot quite. The data is encrypted, the computation is not. Through the use of universal circuits (circuits that run other circuits) you could give an encrypted executable to an untrusted party to run on encrypted data, but note that the result of this computation is encrypted as well (so, the executable would be useless for the other party -- only you would be able to use the results). In fact, this idea underpins the crucial idea behind FHE: bootstrapping.
- marius_k 6y agoAre these operations encrypted also? Is this method more efficient rather than returning a mapping of all possible unencrypted inputs and outputs for a given operation. [edit] I just did the math. 1. mapping of adding two bytes would make ~64kB list of values. 2. mapping of adding two i32 would make ~73786976294838.2MB list of values (looks like encryption would do a better job)
- aruss 6y agoIt's a requirement of these algorithms that they run in polynomial time with respect to the size of the input. They're large polynomials with big constants, but they're dwarfed by the exponentials you're considering.
- pimlottc 6y ago> Cingulata (pronounced "tchingulata") As an English speaker, this makes me more confused about the pronunciation, not less.
- pmelendez 6y agoAs a non-native English speaker living in a English speaking country, I appreciate the phonetic guidance of a fairly uncommon word
- tzs 6y agoDid that really provide any phonetic guidance? All it appears to say is that it is just like "cingulata" except the "c" should be pronounced "tch". As you note "cingulata" is fairly uncommon. I have no idea how to pronounce that, and so their guidance still leaves me in the dark about everything but the first letter. For phonetic guidance something using the International Phonetic Alphabet seems like the way to go. I think that would give something like this: tʃiŋgyəˈlātə, -ätə That's just a guess taking the IPA for cingulata from Merrian-Webster (siŋgyəˈlātə, -ätə) and replacing the "s" with the "tʃ" that the Macmillan dictionary gives for the "tch" in "latch", which is the first word that came to mind that has a "tch". (Also, I believe many publications use their own variants on the IPA, so I'm not sure that what I gave is actually proper. If MW and/or Macmillian have their own, the above could be some weird bastardization with little meaning).
- zimpenfish 6y agoSame. You can't just steal words[1] and change the pronunciation! [1] https://en.wikipedia.org/wiki/Cingulata https://en.wikipedia.org/wiki/Cingulata
- asjw 6y agoCingulata comes from the Latin words cingŭla or cingŭlum and it should be pronounced with the soft C (like in Tchaikovsky) > History and Etymology for Cingulata New Latin, from Latin cingulum, cingula girdle + New Latin -ata https://www.merriam-webster.com/dictionary/Cingulata#:~:text=History%20and%20Etymology%20for%20Cingulata,cingula%20girdle%20%2B%20New%20Latin%20-ata https://www.merriam-webster.com/dictionary/Cingulata#:~:text... It's a common mistake English speakers do all the times The rule is quite simple: a C followed by the vocals e and i is always pronounced tch in Latin. Latins used K for "hard C" like in "corn" and S for the s sound like in "cent"
- entelechy 6y agoGreat work! This allows to perform arbitrary computation on untrusted devices. However last time I checked computation in this scheme is ridiculously slow: on modern machines, cutting edge implementation of FHE manage to get around 100 integer operations per second. Never the less there have been some brave startups trying to commercialise this technology: https://venturebeat.com/2020/02/18/enveil-raises-10-million-for-enterprise-scale-homomorphic-encryption/ https://venturebeat.com/2020/02/18/enveil-raises-10-million-... Other interesting things build on top of FHE: sql database where data and queries are fully encrypted: https://github.com/zerodb/zerodb https://github.com/zerodb/zerodb fully encripted brainfuck vm: https://github.com/f-prime/arcanevm https://github.com/f-prime/arcanevm
- rhindi 6y agoThere are two main approaches to FHE: homomorphic boolean circuits and homomorphic numerical processing. In the former (eg Cingulata), you convert a program into a boolean circuit, and evaluate each gate homomorphically. While this is general purpose, it also means you decompose functions that could be done in one instruction into multiple binary operations (so very slow). That’s usually what people refer to when they say FHE is slow. The other approach consists of operating directly on encrypted integers or reals, and finding ways to do more complex computations (like a square function) in one step. While this is obviously much faster, it is also limited to whatever operations is supported by the scheme. This is what people refer to when they say FHE can only do certain things. For years, the tradeoff has basically been slow and general purpose, or fast and limited. But there are new scheme being worked on that will be published soon that enable to go way beyond what’s currently done, such as doing efficient deep learning over encrypted data and other complex numerical processing. Lots is coming out of labs and will be on the market within 2 years!
- entelechy 6y agoohh interesting! Are there any opensource implementations of homomorphic numerical processing? Were there any efforts of combining both approaches?
- speedgoose 6y agoHow encrypted and private is the encrypted data in such systems? When I looked at encrypted databases, the real ones, not the encrypted at rest databases, I read comments saying that the crypto was relatively too weak to have any use outside research. That it is a neat research topic, it will be great eventually, but it's not ready for production. So I went with the classic and simple solution : encrypt with aes256gcm, and decrypt and reencrypt if I manipulate the data. Does a system like cingulata offers encryption as strong or better than aes256gcm?
- rhindi 6y agoAll modern FHE is lattice based, so pretty strong if you chose the right parameters. But of course if you dont chose secure parameters.. well, it wont be secure :) There are tools to measure the security level of FHE schemes: https://bitbucket.org/malb/lwe-estimator/ https://bitbucket.org/malb/lwe-estimator/
- speedgoose 6y agoI guess only experts should chose the parameters.
- rhindi 6y agoYou have formulas to calculate the security level given a threat model, so the compiler could in theory do it automatically. Just specify that you wants 128 bits of security or whatever, and it will do the rest.
- ssmiler 6y agoCingulata automatically chooses secure parameters using https://github.com/CEA-LIST/CinguParam https://github.com/CEA-LIST/CinguParam module. It's a separate project because our intention is to provide an easier/faster way to chose HE parameters than lwe-estimator. You need to provide only the multiplicative depth (or the circuit describing the computation for example) and CinguParam will automatically generate the code snippet/parameter file for the HE scheme you want. Also as CinguParam contains a database of HE parameters the actual parameter generation is really faster than using lwe-estimator. There is a lot of work to be done on this project in order to automatize parameter database update, generate HE parameters more precisely using circuit representation instead of multiplicative depth, take into account HE libraries implementation details (RNS, NTT), etc.
- dekhn 6y agoDuring the COVID freakout, I opined that all the CPU/GPU spent on Folding@Home was unlikely to create any sort of interesting breakthrough and it used an absurd amount of CPU/GPU to not make breakthroughs. In the past, I've been kind of opposed to using FHE on health data (seems wasteful; instead, should be run on trusted compute with a decrypt and encrypt key). But for the amount of wasted compute in CPU/GPU for molecular dynamics... coudl we instead process encyrpted health data on consumer devices (I'm not aware of any health data analytics problems that need to scale over millions of consumer devices).
- lacker 6y agoFor “big data” type tasks, the cost of shuffling around the data to thousands of different consumer devices probably makes it ineffective. You’re better off just paying for one centralized data warehouse, rather than all the custom coding and decentralized bandwidth to make some consumer-based strategy work. This seems more like it could be useful for building things like decentralized encryption protocols.
- xsamgreen 6y agoFHE is undergoing standardization right now. The leading algorithm candidates are based on lattice crypto which is currently quantum-safe: https://homomorphicencryption.org/ https://homomorphicencryption.org/ Here are some mature and actively-developed HE libraries: https://github.com/homenc/HElib https://github.com/homenc/HElib (By IBM, employed the inventor of FHE) https://github.com/Microsoft/SEAL https://github.com/Microsoft/SEAL (Best tutorials) https://palisade-crypto.org/software-library https://palisade-crypto.org/software-library (High-quality codebase) https://github.com/tfhe/tfhe https://github.com/tfhe/tfhe (Fast boolean logic, used by Cingulata) Good introductory material is hard to come by, but I like the first half of this talk: https://simons.berkeley.edu/talks/intro-fhe-and-tfhe https://simons.berkeley.edu/talks/intro-fhe-and-tfhe
- hansdieter1337 6y agoReminds me of my work with CryptDB. A framework to run SQL queries over encrypted data: https://github.com/CryptDB/cryptdb https://github.com/CryptDB/cryptdb One important fact about homomorphic and other encryption schemes you can calculate on: It leaks information! E.g., if enc(x) + enc(y) = enc(z), you gain the knowledge that x + y = z. With enough data, it’s easy to obtain the unencrypted data without the secret(s).
- gautamcgoel 6y agoI think you meant homomorphic, not homophobic...
- hansdieter1337 6y agoah, hehe, yes indeed. Thank you, auto-correct
- aruss 6y agoI did part of a PhD in this field; your comment about information leakage is not true. FHE schemes are IND-CPA secure, which means you can't test for equality in the encrypted space (Note that in the standard definition of homomorphic encryption, you're only guaranteed that Dec(Enc(x+y)) = Dec(Enc(x) + Enc(y)) = x + y). Your comment only applies to schemes where you can test for equality in the encrypted space, which are not IND-CPA secure and should never be used in practice (except in some extreme scenarios where you can/need to make some strong assumptions).