4 ms·

All FHE schemes can run a full-blown virtual machine, but you might not live long enough to see Ubuntu finish booting up.

throwaway613834 9y ago
What are the time complexities like? Do they actually do better than "factor the RSA key, then compute the output, then re-encrypt"?
- warkdarrior 9y ago
  The paper at http://www.shoup.net/papers/helib.pdf http://www.shoup.net/papers/helib.pdf should give you an idea of what goes in a HE scheme. They also report performance of multiplying two 1024x1024 matrices: 473 seconds.
whatidonteven 9y ago
Aren't there MASSIVE (read: showstopper) complications when you want to use FHE for "looping" computations? I always thought FHE was only good if you can fully unroll your "fixed-length" computation, and even then you can only use each "program" once without compromising security.
- middleorigin 9y ago
  Hmm so it doesn't work well with variable length data?
  - whatidonteven 9y ago
    You could say that. Every time you want to run a computation on your FHE-enabled VPS you would need to upload data proportional to the maximum number of operations in the computation. Otherwise, re-running the same computation with a different input gives away information about both of your inputs and about the computation.
- swordswinger12 9y ago
  The short answer is yes. There are some (slow) ways to fix this: https://people.csail.mit.edu/nickolai/papers/goldwasser-we.pdf https://people.csail.mit.edu/nickolai/papers/goldwasser-we.p...
  - whatidonteven 9y ago
    Their construction relies on two unproven conjectures. In particular the "Extractable Witness Encryption" conjecture is impossible under a reasonable falsifiable assumption: https://pdfs.semanticscholar.org/8587/dba4ff31e8118e9bd5914af303614ce90a44.pdf https://pdfs.semanticscholar.org/8587/dba4ff31e8118e9bd5914a... Under that assumption, general purpose differing-inputs obfuscation cannot exist. The way I understand it, FHE being applicable to anything other than "unwrapping a path through a circuit" seems implausible. Any claims of arbitrary encrypted computation should be viewed with the highest dose of skepticism.

throwaway613834 9y ago

What are the time complexities like? Do they actually do better than "factor the RSA key, then compute the output, then re-encrypt"?

warkdarrior 9y ago
The paper at http://www.shoup.net/papers/helib.pdf http://www.shoup.net/papers/helib.pdf should give you an idea of what goes in a HE scheme. They also report performance of multiplying two 1024x1024 matrices: 473 seconds.

whatidonteven 9y ago

Aren't there MASSIVE (read: showstopper) complications when you want to use FHE for "looping" computations? I always thought FHE was only good if you can fully unroll your "fixed-length" computation, and even then you can only use each "program" once without compromising security.

middleorigin 9y ago
Hmm so it doesn't work well with variable length data?
- whatidonteven 9y ago
  You could say that. Every time you want to run a computation on your FHE-enabled VPS you would need to upload data proportional to the maximum number of operations in the computation. Otherwise, re-running the same computation with a different input gives away information about both of your inputs and about the computation.
swordswinger12 9y ago
The short answer is yes. There are some (slow) ways to fix this: https://people.csail.mit.edu/nickolai/papers/goldwasser-we.pdf https://people.csail.mit.edu/nickolai/papers/goldwasser-we.p...
- whatidonteven 9y ago
  Their construction relies on two unproven conjectures. In particular the "Extractable Witness Encryption" conjecture is impossible under a reasonable falsifiable assumption: https://pdfs.semanticscholar.org/8587/dba4ff31e8118e9bd5914af303614ce90a44.pdf https://pdfs.semanticscholar.org/8587/dba4ff31e8118e9bd5914a... Under that assumption, general purpose differing-inputs obfuscation cannot exist. The way I understand it, FHE being applicable to anything other than "unwrapping a path through a circuit" seems implausible. Any claims of arbitrary encrypted computation should be viewed with the highest dose of skepticism.