A Guide to Fully Homomorphic Encryption

Post by darkmighty » Thu, Dec 17, 2015, 10:23 AM UTC

williamjennings wrote: post #18

Uptrenda wrote: post #16

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 enc…

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. Thes…

Post by williamjennings » Thu, Dec 17, 2015, 10:52 AM UTC

darkmighty wrote: post #22

williamjennings wrote: post #18

Earlier quoted context omitted.

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. Thes…

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

Post by [deleted] » Thu, Dec 17, 2015, 12:01 PM UTC

oznathan wrote: post #23

Uptrenda wrote: post #16

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 enc…

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…

Post by yshalabi » Thu, Dec 17, 2015, 12:54 PM UTC

williamjennings wrote: post #18

Uptrenda wrote: post #16

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 enc…

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. Thes…

Post by marcosdumay » Thu, Dec 17, 2015, 1:56 PM UTC

gizmo686 wrote: post #7

Others wrote: post #3

Earlier quoted context omitted.

To address just one of your points, quantum computation is not a silver bullet. It does not work the way one might think it works. Not many researchers are saying that they will replace classical computers, and for good reason. For many, or even most, computational tasks there is no way to get a large quantum speedup. (And classical computers have had a lot more R&D put into them.) Although easy integer factoring wil…

The (provably) best "general purpose" quantum algorithm is Grover's algorithm. The problem it solves is as follows: Given an arbitrary function f(x), and a desired output k, find the unique input z such that f(z)=k. We can see that using classical computers, this problem is O(n), where n is the size of the domain of f. However, Grover's algorithm can solve this problem in O(sqrt(n)). It has been shown that O(sqrt(n))…