Many homomorphic schemes exact a high price for security. During encryption, data undergo a kind of cosmic inflation: A single bit of plaintext may blow up to become thousands or even millions of bits of ciphertext. The encryption key can also become huge—from megabytes to gigabytes. Merely transmitting such bulky items would be costly; computing with the inflated ciphertext makes matters worse. Whereas adding or multiplying a few bits of plaintext can be done with a single machine instruction, performing the same operation on the inflated ciphertext requires elaborate software for high-precision arithmetic.
Much current work is directed toward mitigating these problems. For example, instead of encrypting each plaintext bit separately, multiple bits can be packed together, thereby “amortizing” the encryption effort and reducing overhead.
The ultimate test of practicality is to create a working implementation. Nigel P. Smart of the University of Bristol and Frederik Vercauteren of the Catholic University of Leuven were the first to try this. They built a somewhat homomorphic system, but could not extend it to full homomorphism; the bottleneck was an unwieldy process for generating huge encryption keys.
Gentry and Halevi, working with a somewhat different variant of the lattice-based algorithm, did manage to get a full system running. And they didn’t need to build it on IBM’s Blue Gene supercomputer, as they had initially planned; a desktop workstation was adequate. Nevertheless, the public key ballooned to 2.3 gigabytes, and generating it took two hours. The noise-abating re-encryptions took 30 minutes each.
In another implementation effort, Kristin Lauter of Microsoft Research, Michael Naehrig of the Eindhoven Institute of Technology and Vaikuntanathan show that large gains in efficiency are possible if you are willing to compromise on the requirement of full homomorphism. They do not promise to evaluate circuits of unbounded depth, but instead commit only to some small, fixed number of multiplications, along with unlimited additions. They have working code based on the learning-with-errors paradigm. Except at the highest security levels, key sizes are roughly a megabyte. Homomorphic addition takes milliseconds, multiplication generally less than a second. These timings are a vast improvement over earlier efforts, but it’s sobering to reflect that they are still an order of magnitude slower than the performance of the ENIAC in 1946.
Why is this voted to the top? There are many practical, efficient homomorphic encryption systems. The current problem is in integrating the various approaches together into a single performant, fully homomorphic encryption environment.
I don’t understand what you are disagreeing with. To run an AI safely, we need a performant fully homomorphic encryption environment, and the quote is pointing out that we are currently far from that, and you seem to agree with this when you say that we do not have such a thing and that this is “the current problem”.
...so instead of emoting, why don’t you tell us what is the start of the art? Are we up to ENIAC yet? Have we reached IBM System/360? Can we now run Apple IIs or wristwatches under homomorphic encryption?
Efficiency update http://www.americanscientist.org/issues/id.15906,y.2012,no.5,content.true,page.1,css.print/issue.aspx :
Why is this voted to the top? There are many practical, efficient homomorphic encryption systems. The current problem is in integrating the various approaches together into a single performant, fully homomorphic encryption environment.
I don’t understand what you are disagreeing with. To run an AI safely, we need a performant fully homomorphic encryption environment, and the quote is pointing out that we are currently far from that, and you seem to agree with this when you say that we do not have such a thing and that this is “the current problem”.
^^ does not reflect the current state of the art.
...so instead of emoting, why don’t you tell us what is the start of the art? Are we up to ENIAC yet? Have we reached IBM System/360? Can we now run Apple IIs or wristwatches under homomorphic encryption?