What if you want to query a search engine, but don't want to tell the search engine what you are looking for? You might consider encrypting your query, but if you use an ordinary encryption scheme, the search engine will not be able to manipulate your ciphertexts to construct a meaningful response. What you would like is a cryptographic equivalent of a photograph developer's "dark room", where the search engine can process your query intelligently without ever seeing it.
Or, what if you want to store your data on the internet, so that you can access it at your convenience? You want your data to remain private, even from the server that is storing them; so, you store your data in encrypt form. But you would also like to be able to access your data intelligently -- e.g., you would like the server to be able to return exactly those files containing the word `homomorphic' within five words of `encryption'. Again, you would like the server to be able to "process" your data while it remains encrypted.
A "fully homomorphic" encryption scheme creates exactly this cryptographic dark room. Using it, anyone can manipulate ciphertexts that encrypt data under some public key pk to construct a ciphertext that encrypts *any desired function* of that data under pk. Such a scheme is useful in the settings above (and many others).
In 2009, Gentry proposed the first efficient fully homomorphic encryption scheme. It is efficient in the sense that all algorithms run in time polynomial in the security parameter and the size of the function f that you are computing, and the size output ciphertext grows only linearly with the size of f's output (which is the best you can hope for). Although all algorithms run in polynomial time, there is still work to be done to make it truly practical.
Technically, Gentry begins by constructing a "somewhat homomorphic" encryption E that uses a mathematical object called an "ideal lattice". This scheme is somewhat homomorphic in the sense that E can handle only simple functions -- i.e., it can take encryptions of m_1, ..., m_t and compute a valid encryption of f(m_1, ..., m_t) only if f is in a class of simple functions. Gentry then shows how a somewhat homomorphic encryption scheme E can be "bootstrapped" to construct a fully homomorphic encryption scheme if E's decryption function f_{Dec} is simple enough -- in particular, if the complexity of f_{Dec} is a little bit less than the complexity of the simple functions that E can handle. He then shows that the decryption function in his ideal-lattice-based encryption scheme, with a few modifications, is simple enough to permit bootstrapping.
To understand fully homomorphic encryption and bootstrapping, the following physical analogy may help. Suppose that the owner of a jewelry store (Alice) wants her employees to assemble raw precious materials (diamonds, gold, etc.) into finished products, but she is worried about theft. She addresses the problem by constructing glove boxes for which only she has the key, and she puts the raw materials inside. Using the gloves, an employee can manipulate the items inside the box. Moreover, an employee can put things inside the box -- e.g., a soldering iron to use on the raw materials -- even though he cannot take anything out. Also, the box is transparent, so that an employee can see what he is doing. (In this analogy, encryption means that the employee is unable to take something out of the box, not that he is unable to see it.) After the employee is done, Alice can recover the finished product at her leisure. This analogy approximates the sort of functionality that one obtains with fully homomorphic encryption, but the analogy is inadequate in the sense that the glove box might become quite cluttered, whereas in the fully homomorphic encryption scheme only the final product need remain.
To understand bootstrapping, imagine that Alice's glove boxes are defective; after an employee uses the gloves for 1 minute, the gloves stiffen and become unusable. (This models the "defectiveness" of the "somewhat homomorphic" encryption scheme.) Unfortunately for Alice, even her fastest employee cannot assemble some of the more intricate designs in under a minute. But Alice is not only paranoid, but also smart. To an employee that is assembling an intricate design, she gives him (like before) 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 stiffen. 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 stiffen. He then places box 2 inside box 3, and so on. When the employee finally finishes his assembly inside box n, he hands the box to Alice. Of course, 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) stiffen. This is analogous to the requirement for a bootstrappable encryption scheme E -- that the complexity of E's decryption circuit is less than the complexity of functions that E can handle. As before, the physical analogy only goes so far. In the physical case, box i would grow as i increases, and consequently the extraction time would also grow, but our encryption scheme does not have analogous deficiencies. And, again, in our physical analogy, encryption corresponds to being unable to physically access the contents of the box. So, it is not a valid attack for the employee to copy the master key based on what he can see through the transparent box.
Craig Gentry. Fully homomorphic encryption using ideal lattices. STOC 2009: 169-178