{"id":2858,"date":"2010-02-03T05:21:49","date_gmt":"2010-02-03T13:21:49","guid":{"rendered":"http:\/\/palblog.fxpal.com\/?p=2858"},"modified":"2010-02-04T09:58:51","modified_gmt":"2010-02-04T17:58:51","slug":"how-to-compute-without-knowing-anything","status":"publish","type":"post","link":"https:\/\/blog.fxpal.net\/?p=2858","title":{"rendered":"How to compute without knowing anything"},"content":{"rendered":"

In my post on quantum inspired classical results<\/a>, I gave as one example Gentry’s recent discovery of a fully homomorphic encryption scheme. His beautiful work deserves its own blog post. Initially I approached his work with trepidation, worried that it would be so technical I would not understand anything without a lot of work. Others have mentioned not\u00a0 having looked at his work for the same reason. That is a shame! While the details are technical, the key idea, bootstrappable encryption, is both a non-obvious approach and an easily understandable concept.\u00a0 I remember smiling while I read the first couple of pages of his paper<\/a> in response to the elegance and surprising simplicity of his approach.<\/p>\n

As I described in my previous post<\/a>, a fully homomorphic encryption scheme enables arbitrary computations to be performed on encrypted data. In particular, it enables a trusted-but-curious third party to perform computations on data you have encrypted, return an encrypted result to you without having learned anything about the encrypted values which you can then decrypt to learn the result of the computation. Gentry’s 2009 scheme<\/a> answers an old\u00a0 for modern cryptography (1978) question as to whether fully homomorphic encryption schemes exist.<\/p>\n

Progress in homomorphic encryption over the intervening years focused on finding more powerful schemes that could perform more general types of computation over encrypted data than previous approaches. Fully homomorphic encryption is sometimes called algebraically homomorphic encryption or doubly homomorphic encryption because any scheme that supports the computation of arbitrary circuits consisting additions and multiplications can perform any computation. There are a number of schemes that are additively homomorphic, and a number that are multiplicatively homomorphic. More recently there have been schemes that can do more, most notably the one due to Boneh-Goh-Nissim that can do arbitrarily many additions and one level of multiplication (any degree 2 polynomial). See Fontaine-Galand 2007 for an excellent survey of homomorphic encryption<\/a>.<\/p>\n

Since the aim is a more powerful scheme, what other approach could researchers take than to try to find schemes that support more\u00a0 general types of computation? Gentry realized that instead of directly creating a more powerful scheme, he could build one from a weakly homomorphic scheme, if that scheme’s decryption circuit were sufficiently simple. More specifically, he saw that he could build a fully homomorphic scheme from any scheme that could homomorphically compute a slightly augmented version of its own decryption circuit. A scheme with this property is bootstrappable<\/em>.<\/p>\n

For example, if the reason a scheme can compute circuits of at most a certain depth is that after a certain amount of computation too much error accumulates so that upon decryption the wrong value is obtained, but that smaller amounts of error are handled in decryption, bootstrappable encryption enables refreshing<\/em> after some computation is done. The idea is to encrypt under a first key. Compute, but stop before the error grows too large. Encrypt under second key. Compute the decryption circuit which, since we stopped before the error grew too large,\u00a0 gives the correct value encrypted under the second key. The first key is no longer in the picture. Continue computation under second key, and repeat with a new key as often as needed. When the computation finishes, decrypting with the last key used gives the final result.<\/p>\n

In Gentry’s thesis<\/a>, he uses a jewelry maker to colorfully and clearly illustrate this idea of bootstrappable encryption: Suppose Alice wants her employees to assemble jewelry from valuable raw materials. While she trusts them to carry out the assembly correctly, she is worried they might steal something. So she puts the materials in secure, transparent boxes with gloves that enable the employees to work with the materials inside.\u00a0 Unfortunately, after a minute, the gloves stiffen so that the employees can no longer do the work.\u00a0 Suppose further that the employees can place objects in a box, but cannot get them out again. “To an employee that is assembling an intricate design, she gives him … a glove box containing the raw materials, but also several additional glove boxes. Each of these additional glove boxes holds a copy of her master key. To assemble the intricate design, the employee manipulates the materials in box #1 until the gloves stiff\u000ben. Then, he places box #1 inside box #2, where the latter box already contains a master key. Using the gloves for box #2, he opens box #1 with the master key, extracts the partially assembled trinket, and continues the assembly within box #2 until its gloves stiff\u000ben. He then places box #2 inside box #3, and so on.” However, “this trick will not work unless the employee can open box #i within box #(i+1), and have time to make a little bit of progress on the assembly, all before the gloves of box #(i + 1) stiff\u000ben. This is analogous to the requirement for a bootstrappable encryption scheme E — that the complexity of E’s (augmented) decryption circuit is less than what E can homomorphically evaluate.”<\/p>\n

Both his paper, and his thesis, are clearly written, exhibiting the care he put into communicating these ideas.\u00a0 Both also have a personal feel. For example, when reading the section heading “Bootstrappable yet?” the reader can feel the frustration Gentry must have felt each time he applied a new trick and saw that the decryption circuit still couldn’t quite be evaluated homomorphically by the scheme so that he would have to modify the scheme with yet another trick. The details of each of his successive schemes are quite technical, but some of them are quite interesting. For example, one of these tricks comes from server aided decryption, in which a client gives\u00a0 a computationally powerful server a hint so that the server can perform computations that make it easier for the client to decrypt. While as I mentioned in my previous post<\/a>, Gentry’s fully homomorphic scheme is not practical — it is a trillion times slower than computation on unencryption data — his first scheme is interesting in its own right in that it improves on Boneh-Goh-Nissim’s result by enabling greater multiplicative depth and supporting a larger plaintext space.<\/p>\n

Two more recent papers shed light on some of these technical details. Smart and Vercauteren’s paper<\/a> is a specialization of Gentry’s work that does not require an understanding of lattice cryptography to follow. The main purpose of the van Dijk, Gentry, Halevi, and Vaikuntanathan paper<\/a> is to provide a conceptual simple embodiment of many of the ideas in Gentry’s original paper.<\/p>\n

I look forward to watching the progress in this area. I’m\u00a0 particularly curious to see how quickly researchers will be able to make efficiency gains that will make fully homomorphic encryption practical.<\/p>\n","protected":false},"excerpt":{"rendered":"

In my post on quantum inspired classical results, I gave as one example Gentry’s recent discovery of a fully homomorphic encryption scheme. His beautiful work deserves its own blog post. Initially I approached his work with trepidation, worried that it would be so technical I would not understand anything without a lot of work. Others […]<\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[147,7],"tags":[174,173,148],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/2858"}],"collection":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2858"}],"version-history":[{"count":45,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/2858\/revisions"}],"predecessor-version":[{"id":2901,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=\/wp\/v2\/posts\/2858\/revisions\/2901"}],"wp:attachment":[{"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2858"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2858"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.fxpal.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2858"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}