4 ms·

Are 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 lite

Are 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 ago
Cynical remark: all processes requiring a million times more cycles is the dream of many chip-making companies.
- de_keyboard 5y ago
  Is it though? If chips had fewer practical applications, fewer people will buy them.
  - Iv 5y ago
    Oh 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 ago
Does it also make it proportionally slower to brute-force attack it?
- lentilcorba 5y ago
  Sure, 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...]
gspr 5y ago
If "million times slowdown" is accurate, then by eyeballing that should take us roughly from the state of the art consumer processors of today back to the realm of the m68k. Sure, that's a giant gap. But I don't think it's outside the realm of possibility that there could be useful tasks done under those circumstances.
- PeterisP 5y ago
  To me m68k seems something like 10 000 times slower than modern hardware, not a million times. From the demo descriptions I get an impression (though there are no benchmarks to be sure) that it's much more limited than what could be done on a m68k.
  - cobbzilla 5y ago
    More accurate: an early 6502 or Z80 (circa late 70s/early 80s) with speeds in the low MHz range. So a ~40-year regression in performance.
    - ganafagol 5y ago
      And a from-0-to-100 gain in privacy. Calling this a "regression" is nonsense.
      - cobbzilla 5y ago
        for non-English speakers: colloquially, performance == speed. this is a regression in speed, I was making GP’s assessment more accurate.
    - PeterisP 5y ago
      m68k is the equivalent of those, it's late 70s/early80s, with speeds in the low MHz range (e.g. 7.67 MHz for the version in Sega Genesis) - but I haven't seen claims of FHE having that high of a performance (e.g. sum or filter a million numbers in a second as low MHz allows you to do) but only something an order of magnitude or two slower (e.g. 13ms/core for a bit operation might be treated as comparable to a 0.077 MHz microcomputer; you can parallelize over cores but that computer parallelized over bits), so we're talking about much more than a 40-year regression of performance, as it's slower than the first 1970s microcomputers which themselves were slower than the 1960s minicomputers, so perhaps the 1950s early transistor computers?
osaariki 5y ago
I've done work on low-latency FHE neural network inferencing [1] and we estimated the FLOPS to be approximately 4 times that of an Intel 8087 floating point coprocessor [2]. This was for a LeNet-5 network on the MNIST dataset with multicore evaluation on a workstation class machine. My view is that this is already fast enough to support use cases that really need the unique capabilities of FHE. Since this work we've been focused on making FHE more usable with compilers and tooling [3]. Currently most FHE is being programmed like that Intel 8087 was: with the equivalent of assembly by directly calling functions in FHE libraries to perform arithmetic and crypto operations. Imagine having to do register allocation by hand for all of your code. The EVA compiler [4] is meant to be like a "C compiler for FHE", hiding low-level crypto concerns and providing common optimizations. [1] "CHET: Compiler and Runtime for Homomorphic Evaluation of Tensor Programs": https://arxiv.org/pdf/1810.00845.pdf https://arxiv.org/pdf/1810.00845.pdf [2] https://en.wikipedia.org/wiki/Intel_8087 https://en.wikipedia.org/wiki/Intel_8087 [3] "EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation": https://arxiv.org/pdf/1912.11951.pdf https://arxiv.org/pdf/1912.11951.pdf [4] https://github.com/microsoft/EVA https://github.com/microsoft/EVA
LordGrey 5y ago
The github repo has benchmark versions of most of their examples that include built-in timers. I just checked both versions the "reverse a string" example (a single-core and a multi-core version) in an Ubuntu 20.04 VM: Single core: 2838.660s (47.31 minutes) Multi-core: 843.828s (14.06 minutes) The multi-core version was using four CPU cores, so slightly worse than a linear performance increase. Both versions lit up the fans in my MacBook Pro pretty hard. The string in question, by the way, was "hello" -- five characters long. Does this terrible performance match your previous findings? It is so bad I'm wondering if there is something wrong with my dev environment.

Iv 5y ago

Cynical remark: all processes requiring a million times more cycles is the dream of many chip-making companies.

de_keyboard 5y ago
Is it though? If chips had fewer practical applications, fewer people will buy them.
- Iv 5y ago
  Oh 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 ago

Does it also make it proportionally slower to brute-force attack it?

lentilcorba 5y ago
Sure, 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...]

gspr 5y ago

If "million times slowdown" is accurate, then by eyeballing that should take us roughly from the state of the art consumer processors of today back to the realm of the m68k. Sure, that's a giant gap. But I don't think it's outside the realm of possibility that there could be useful tasks done under those circumstances.

PeterisP 5y ago
To me m68k seems something like 10 000 times slower than modern hardware, not a million times. From the demo descriptions I get an impression (though there are no benchmarks to be sure) that it's much more limited than what could be done on a m68k.
- cobbzilla 5y ago
  More accurate: an early 6502 or Z80 (circa late 70s/early 80s) with speeds in the low MHz range. So a ~40-year regression in performance.
  - ganafagol 5y ago
    And a from-0-to-100 gain in privacy. Calling this a "regression" is nonsense.
    - cobbzilla 5y ago
      for non-English speakers: colloquially, performance == speed. this is a regression in speed, I was making GP’s assessment more accurate.
  - PeterisP 5y ago
    m68k is the equivalent of those, it's late 70s/early80s, with speeds in the low MHz range (e.g. 7.67 MHz for the version in Sega Genesis) - but I haven't seen claims of FHE having that high of a performance (e.g. sum or filter a million numbers in a second as low MHz allows you to do) but only something an order of magnitude or two slower (e.g. 13ms/core for a bit operation might be treated as comparable to a 0.077 MHz microcomputer; you can parallelize over cores but that computer parallelized over bits), so we're talking about much more than a 40-year regression of performance, as it's slower than the first 1970s microcomputers which themselves were slower than the 1960s minicomputers, so perhaps the 1950s early transistor computers?

osaariki 5y ago

I've done work on low-latency FHE neural network inferencing [1] and we estimated the FLOPS to be approximately 4 times that of an Intel 8087 floating point coprocessor [2]. This was for a LeNet-5 network on the MNIST dataset with multicore evaluation on a workstation class machine. My view is that this is already fast enough to support use cases that really need the unique capabilities of FHE. Since this work we've been focused on making FHE more usable with compilers and tooling [3]. Currently most FHE is being programmed like that Intel 8087 was: with the equivalent of assembly by directly calling functions in FHE libraries to perform arithmetic and crypto operations. Imagine having to do register allocation by hand for all of your code. The EVA compiler [4] is meant to be like a "C compiler for FHE", hiding low-level crypto concerns and providing common optimizations. [1] "CHET: Compiler and Runtime for Homomorphic Evaluation of Tensor Programs": https://arxiv.org/pdf/1810.00845.pdf https://arxiv.org/pdf/1810.00845.pdf [2] https://en.wikipedia.org/wiki/Intel_8087 https://en.wikipedia.org/wiki/Intel_8087 [3] "EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation": https://arxiv.org/pdf/1912.11951.pdf https://arxiv.org/pdf/1912.11951.pdf [4] https://github.com/microsoft/EVA https://github.com/microsoft/EVA

LordGrey 5y ago

The github repo has benchmark versions of most of their examples that include built-in timers. I just checked both versions the "reverse a string" example (a single-core and a multi-core version) in an Ubuntu 20.04 VM: Single core: 2838.660s (47.31 minutes) Multi-core: 843.828s (14.06 minutes) The multi-core version was using four CPU cores, so slightly worse than a linear performance increase. Both versions lit up the fans in my MacBook Pro pretty hard. The string in question, by the way, was "hello" -- five characters long. Does this terrible performance match your previous findings? It is so bad I'm wondering if there is something wrong with my dev environment.