Cingulata: Run C++ code over encrypted data with fully homomorphic encryption
github.com
github.com
Here are some mature and actively-developed HE libraries:
https://github.com/homenc/HElib (By IBM, employed the inventor of FHE)
https://github.com/Microsoft/SEAL (Best tutorials)
https://palisade-crypto.org/software-library (High-quality codebase)
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
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-...
Other interesting things build on top of FHE:
sql database where data and queries are fully encrypted: https://github.com/zerodb/zerodb
fully encripted brainfuck vm: https://github.com/f-prime/arcanevm
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!
Were there any efforts of combining both approaches?
With a less than operator and the ability to encrypt chosen plaintext values, you can decrypt arbitrary messages in a linear (in message size) number of steps.
Arithmetic operations can often be used to build gadgets that bootstrap comparison operations. For instance, with addition and equality you can implement a comparison operation for low-medium cardinality fields.
The field is littered with negative results that are being sold as secure, practical systems. Be careful when using them on important data.
Isn't this a big assumption? The way I envision it is
1. client encrypts data with their key
2. server computes on data without decrypting and without needing the key
3. client decrypts computation output with their key.
Or is it always required at step 2 that the server also has the key needed for encryption (but not decryption obviously)?
The standard resilience criteria for modern multi-purpose encryption suppose that your scheme should be resistant to adaptive chosen-cipher attack. Chosen plaintext is a way weaker attack (the hierarchy being: known plaintext < chosen plaintext < chosen cipher < adaptative chosen cipher).
It may be OK for some situations, but it requires to be much more cautious than with regular crypto (which is already error-prone…).
Fwiw, bootstrapping is actually what makes FHE slow, not the actual addition/multiplication etc
I thought the speed was in the order of minutes for a single operation.
According to https://tfhe.github.io/tfhe/ states:
> Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms
Addition of two bits can be implemented using 5 binary gates (fulladder) Hence to add 2 32 bit numbers ~416ms => 2 additions per second
EDIT: Shame I cannot edit my original post
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?
There are tools to measure the security level of FHE schemes: https://bitbucket.org/malb/lwe-estimator/
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.
All data manipulation and -processing takes place on encrypted data, as opposed to the encrypted database you mentioned, which still decrypts its contents in memory prior to processing.
The reason homomorphic encryption is far from being ready for production, is that all operations (e.g. all your algorithms and programs) need to be transformed to a virtual circuit that operates on cipher text encrypted by a specific algorithm.
This is akin to translating your software into an inefficient byte code that's then dynamically executed by an obnoxiously slow interpreter.
The great part is that you can simply encrypt your data on a local (and trusted) machine, send the cipher text into the cloud for indexed storage or processing and do your queries or operations on encrypted data. At no point will your data ever be decrypted on the remote machine.
So there's great potential there w.r.t. privacy and cloud computing (and especially AI where training data is often the "magic sauce" that gives your company an edge over the competition) and SaaS.
>Does a system like cingulata offers encryption as strong or better than aes256gcm?
One of the security garuntees of aes-gcm is non malleablity. Any attempt to modify the ciphertext is detected. This is the key reason why GCM is popular over older methods like CBC. In homomorphic encryption, the entire point is to be able to able to do arbiteary computations on ciphertexts without decrypting. So even theoretically it would be impossible for homomorphic encryption to give same/better security properties as aes-gcm.
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).
As an English speaker, this makes me more confused about the pronunciation, not less.
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).
> History and Etymology for Cingulata New Latin, from Latin cingulum, cingula girdle + New Latin -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"
That's what happens when a language steals a foreign word (Latin in this case) and changes its pronunciation
In Latin the way groups of letters are pronounced it's (almost) unambigous, it's a phonetic alphabet itself
If you change the pronunciation, that part is lost and you have to rely on recollection instead of recognition
It also means that if you don't already know a word you can't be sure on how it is pronounced
The correct transliteration is Čajkovskij and the correct phonetic one is tɕɪˈkofskʲɪj
We are talking about classic Latin, born around the IV century b.c.
But it changed a lot over the centuries influenced by the Greeks, to the point that the Byzantin Roman empire chose Medieval Greek as official language at the end of the VI century and even before, their Latin was different from the classic Roman one. I think they abandoned Latin as official language in the third century to use Koinè Greek (sorry don't know the name in English) basically a Greek dialect, the first common form of Greek, used among all Hellenistic cities which eventually became modern Greek, still in use nowadays.
Most of the Latin found in science (like in the animal taxonomy) comes from "modern" ecclesiastic Latin which incorporated traits of vulgar and neighbors languages (French, German and Italian), it simplified the alphabet but reduced the symbols available so C was mad an affricate consonant.
In practice we have dealt with modern Latin or some form of it for the past 15 centuries, longer than Rome existed.
MW (from your link) says it's pronounced "siŋgyəˈlātə" which is definitely not "tchingulata", no matter what Latin says.
It also says that bus is pronounced ˈbəs, but it's a contraction of French omnibus, that comes from Latin omnibus, which is pronounced ɔmnibus (both in French and Latin), like goose, but with a much shorter oo sound.
Anyway the point was is English language that stole words from other languages and changed their pronunciation, not the other way around.
Yes, someone please explain Cingulata.
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.
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)[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)