Hacker News Reader

Comment by Uptrenda | Hacker News Reader

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?

View on HN

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/ (disclosure - I'm one of the founders)

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.

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.

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).

How well do you understand the term "homomorphism"?

Search engines are the most common example, in general.

Just to be clear, you're referring to 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.

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.

Reply on news.ycombinator.com