"Fully homomorphic" means "a computation can be done on two encrypted values without decrypting them." It is an extension of partially homomorphic systems, whic

"Fully homomorphic" means "a computation can be done on two encrypted values without decrypting them." It is an extension of partially homomorphic systems, which allow some computation which cannot be extended to arbitrary computations. A good usage case for partially homomorphic systems is public elections. Suppose given E(x) and E(y) you can efficiently compute E(x + y). Now imagine that you arrange a set of bit-fields as: 1000 1100 0111 0111 0100 1110 0010 1001 (random) (check bits) (votes Alice) (votes Bob) In other words, the current vote tally is being represented as a number E(0x8C774E29). You can now create two ballots, E(0xBF010100) and E(0xBF010001). You can add either of those ballots to the vote tally even though you cannot read the vote tally. We can make all of these numbers public knowledge without disclosing your vote -- i.e. a public database can say "Alice's vote was E(0xBF010100)" and "Bob's vote was E(0xDB010001)" and once that encryption is performed, third parties cannot actually verify that Alice didn't vote for Bob or vice versa. So any member of the population can take the public database and confirm that the arithmetic was done properly on the encrypted vote tallies, without figuring out what the actual votes were. Then at the highest level, the tally can be decrypted to find out that Alice won the vote, without disclosing exactly who voted for her. The "check bits" form here a sum of votes as a quick check that someone didn't just add some random ballot in there to screw with the system. Of course, you need more bits as you want to have more candidates and more voters; and there are problems with confirming that a number looks like 0x010100 and not 0x050500. But fundamentally you can get these really cool cryptographic voting systems which preserve the anonymity of your vote at the lowest level, but can be audited at the lowest level (i.e. we can potentially remove votes, say, from people who were not alive at the time of the election), the votes have perfectly auditable mathematics up to the regional level due to the public databases of encrypted votes; and then once the population is large enough to suitably anonymize the vote, you can decrypt and tally votes publicly too. Now that's if you just have some function esum such that esum(E(x), E(y)) = E(x + y). If you have enough to make a full set of logical gates, you could in principle do an entire computation on a set of inputs which you couldn't possibly know, so that the "cloud" could "compute" with your data without ever actually knowing it.