5 ms·

Great work! This allows to perform arbitrary computation on untrusted devices. However last time I checked computation in this scheme is ridiculously slow: on

Great 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 ago
There 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 ago
  ohh interesting! Are there any opensource implementations of homomorphic numerical processing? Were there any efforts of combining both approaches?
  - bargle0 6y ago
    HEAAN and HEmat are two libraries for numerical processing that you can find on github. They’re not perfect, and require work to get in to shape for real distributed computation.
  - hedora 6y ago
    Note that most useful homomorphic numerical encryption schemes are easily breakable. Once you have equality you can usually de-anonymize user data. Many companies have been burnt by this. 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.
    - bondarchuk 6y ago
      >and the ability to encrypt chosen plaintext values 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)?
      - rhindi 6y ago
        The server doesn’t need the decryption key, ever. Thats the whole point in fact. FHE is end to end encryption for compute. However there is sometimes a public key used, called an evaluation key.
      - littlestymaar 6y ago
        > Isn't this a big assumption? 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…).
- deleted 6y ago
  [deleted]
Jyaif 6y ago
Where did you get the "100 integer operations per second"? I thought the speed was in the order of minutes for a single operation.
- entelechy 6y ago
  Indeed I didn't remember it correctly: According to https://tfhe.github.io/tfhe/ 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
  - joshuamorton 6y ago
    This would mean that ~2500 CPUs could do 5000 operations per second, which is amusingly close to the same compute-per-square-foot as the ENIAC.

rhindi 6y ago

There 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 ago
ohh interesting! Are there any opensource implementations of homomorphic numerical processing? Were there any efforts of combining both approaches?
- bargle0 6y ago
  HEAAN and HEmat are two libraries for numerical processing that you can find on github. They’re not perfect, and require work to get in to shape for real distributed computation.
- hedora 6y ago
  Note that most useful homomorphic numerical encryption schemes are easily breakable. Once you have equality you can usually de-anonymize user data. Many companies have been burnt by this. 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.
  - bondarchuk 6y ago
    >and the ability to encrypt chosen plaintext values 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)?
    - rhindi 6y ago
      The server doesn’t need the decryption key, ever. Thats the whole point in fact. FHE is end to end encryption for compute. However there is sometimes a public key used, called an evaluation key.
    - littlestymaar 6y ago
      > Isn't this a big assumption? 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…).
deleted 6y ago
[deleted]

Jyaif 6y ago

Where did you get the "100 integer operations per second"? I thought the speed was in the order of minutes for a single operation.

entelechy 6y ago
Indeed I didn't remember it correctly: According to https://tfhe.github.io/tfhe/ 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
- joshuamorton 6y ago
  This would mean that ~2500 CPUs could do 5000 operations per second, which is amusingly close to the same compute-per-square-foot as the ENIAC.