5 ms·

The last time I tried to play with encrypted circuit code it was extremely, extremely, extremely slow. To put this into context: just adding and subtracting 64

The last time I tried to play with encrypted circuit code it was extremely, extremely, extremely slow. To put this into context: just adding and subtracting 64 bit numbers on a garbled circuit was considered quite a complex operation - taking several seconds to several minutes to evaluate. Needless to say - I was very disappointed. I had originally started looking into FHE, functional encryption, and hommomorphic encryption as a novel solution to several trust problems in the Bitcoin world (as you could potentially write fully self-contained, encrypted, ECDSA signing and verification programs that could operate as fully decentralized autonomous entities.) So when researcher say that FHE is holy grail type stuff - they really aren't joking. My question is: how long until any of this stuff will work for large algorithms?

williamjennings 11y ago
The efficiency of application to long algorithms and large datasets is a function of available computing power. Certain problems in coding theory can be reduced to homomorphic calculation, but it takes petabytes of data to represent the solution space. I would recommend Moore's Law as an approximate formula which is useful for guessing what year you will be able to run programs at home on your personal computer. These days, conservative estimates for the number of transistors on a chip should double every 2 years.
- darkmighty 11y ago
  Can you elaborate on those coding problem reducible to homomorphic calculations? I'm very interested. I thought I heard the converse, homomorphic calculations using coding (my rough understanding of Learning With Errors).
  - williamjennings 11y ago
    How well do you understand the term "homomorphism"? Search engines are the most common example, in general.
    - darkmighty 11y ago
      Just to be clear, you're referring to coding theory (https://en.wikipedia.org/wiki/Coding_theory https://en.wikipedia.org/wiki/Coding_theory) in the sense of geometric codes from information theory, right? I fail to see an obvious way search engines fit in.
      - williamjennings 11y ago
        Coding theory is the matrix algebra of information theory. You should understand the meaning of the word "homomorphism" as it is used in Multilinear Algebra before you read about how search engines score results in an unbiased manner. This is not the type of thing you can read by haphazardly browsing wikipedia. Believe you me that I have tried inasmuch. You need to buy books, read journal articles, and then learn through a graduate level math course. The best advice I can give you is to read about how search engines calculate "hits", and to search through scholar.google.com before you check wikipedia.org!
- yshalabi 11y ago
  That was true in an age where single threaded performance also saw similiar improvements. But those days a gone. The power wall and transister scaling also ate factors here. Today, increases in compute capabilities enabling new technology requires new architectures that match the problems. Similarly to how GPUs enabled deep learning.
  - williamjennings 11y ago
    Your writing is grammatically incoherent. Please make more of an effort to express yourself correctly. GPUs did not enable deep learning, they brought it to desktop scale.
Ar-Curunir 11y ago
Garbled circuits are a different cryptographic primitive to FHE. Modern GC implementations are super quick and pretty practical. FHE is another story, though, as you state.
oznathan 11y ago
FHE will probably take a while to become practical. Remember, the first schema was published only in 2009, which is very recent in cryptography standards. Secure multi-party computation can achieve similar objectives (compute on encrypted data-sets), but is much more mature research-wise (first schema dates back to the 70s) and can be practical for large algorithms today. See http://enigma.media.mit.edu/ http://enigma.media.mit.edu/ (disclosure - I'm one of the founders)
- deleted 11y ago
  [deleted]

williamjennings 11y ago

The efficiency of application to long algorithms and large datasets is a function of available computing power. Certain problems in coding theory can be reduced to homomorphic calculation, but it takes petabytes of data to represent the solution space. I would recommend Moore's Law as an approximate formula which is useful for guessing what year you will be able to run programs at home on your personal computer. These days, conservative estimates for the number of transistors on a chip should double every 2 years.

darkmighty 11y ago
Can you elaborate on those coding problem reducible to homomorphic calculations? I'm very interested. I thought I heard the converse, homomorphic calculations using coding (my rough understanding of Learning With Errors).
- williamjennings 11y ago
  How well do you understand the term "homomorphism"? Search engines are the most common example, in general.
  - darkmighty 11y ago
    Just to be clear, you're referring to coding theory (https://en.wikipedia.org/wiki/Coding_theory https://en.wikipedia.org/wiki/Coding_theory) in the sense of geometric codes from information theory, right? I fail to see an obvious way search engines fit in.
    - williamjennings 11y ago
      Coding theory is the matrix algebra of information theory. You should understand the meaning of the word "homomorphism" as it is used in Multilinear Algebra before you read about how search engines score results in an unbiased manner. This is not the type of thing you can read by haphazardly browsing wikipedia. Believe you me that I have tried inasmuch. You need to buy books, read journal articles, and then learn through a graduate level math course. The best advice I can give you is to read about how search engines calculate "hits", and to search through scholar.google.com before you check wikipedia.org!
yshalabi 11y ago
That was true in an age where single threaded performance also saw similiar improvements. But those days a gone. The power wall and transister scaling also ate factors here. Today, increases in compute capabilities enabling new technology requires new architectures that match the problems. Similarly to how GPUs enabled deep learning.
- williamjennings 11y ago
  Your writing is grammatically incoherent. Please make more of an effort to express yourself correctly. GPUs did not enable deep learning, they brought it to desktop scale.

Ar-Curunir 11y ago

Garbled circuits are a different cryptographic primitive to FHE. Modern GC implementations are super quick and pretty practical. FHE is another story, though, as you state.

oznathan 11y ago

FHE will probably take a while to become practical. Remember, the first schema was published only in 2009, which is very recent in cryptography standards. Secure multi-party computation can achieve similar objectives (compute on encrypted data-sets), but is much more mature research-wise (first schema dates back to the 70s) and can be practical for large algorithms today. See http://enigma.media.mit.edu/ http://enigma.media.mit.edu/ (disclosure - I'm one of the founders)

deleted 11y ago
[deleted]