Homomorphic Encryption

July 5, 2009 at 7:58 am (security, theory)

Even though I came across homomorphic function while studying discrete mathemtical structures in undergrad, I only had a vague idea what application it had. An IBM fellow has found an encryption mechanism that is homomorphic. That is, if the encryption function is f(), then it is homomorphic on operation + then

f(a+b) = f(a) + f(b)

This means that if a is encrypted and b is also encrypted (with function f), then to add them, there is no need to decrypt a and b, to add them. You can operate on the encrypted versions themselves. Why? Because f is homomorphic.

This has profound implications on its applications. If everything is seen as operation on data, then one need not really know what the data is, but can still operate on the data by working on their encrypted versions.

When more of the computing is moving to cloud, data privacy needs to be assured for (see, for example, how Facebook tried to take ownership, but failed). Homomorphic encryption is a technical solution to the problem, as opposed to policy based solution (licenses, MoUs etc.)

This is just theory so far. Not all operations can be made homomorphic for example. Research has to be done along this dimension to find ways to make all operations homomorphic. This seems to be going to take long time as the article mentions that it will take at least a decade to get it done. 10 years is too much a time in this modern world to bet on a technology for long time. Who knows what ‘s in store for future?

Moreover, the functions may not be purely homomorphic. After some operations, the original data may be corrupted (who knows whether is function is purely homomorphic until it is proven?). The solution proposed by the inventor is to double encrypt the data and periodically re-encrypt the inner encryption layer by decrypting it.

What about the key management problems?

Leave a Comment

There are Two Kinds of People

December 13, 2007 at 5:04 pm (theory, wisdom)

Perfection-oriented and Performance-oriented:

The people in the category perfection-oriented have a natural intellectual curiosity. They are constantly searching for better ways of doing things, new methods, new tools. They search for perfection, but they take pleasure in the search itself, knowing perfectly well that perfection can not be accomplished. To the people in this category, failure is a normal part of the strive for perfection. In fact, failure gives a deeper understanding of why a particular path was unsuccessful, making it possible to avoid similar paths in the future.

The people in the category performance-oriented on the contrary, do not at all strive for perfection. Instead they have a need to achieve performance immediately. Such performance leaves no time for intellectual curiosity. Instead, techniques already known to them must be applied to solve problems. To these people, failure is a disaster whose sole feature is to harm instant performance. Similarly, learning represents the possibility of failure and must thus be avoided if possible. To the people in this category, knowledge in other people also represents a threat. As long as everybody around them use tools, techniques, and methods that they themselves know, they can count on outperforming these other people. But when the people around them start learning different, perhaps better, ways, they must defend themselves.

Leave a Comment

Mathematica Induction is Also a Kind of Deduction

May 30, 2007 at 6:44 am (theory)

Peter Suber, here, makes it clear that mathematical induction is also a kind of deduction. In a typical case of induction, the conclusion has some information that does not follow from the premises. While in deduction, the conclusion has some information that logically follows from the premises. In his own words, deductions tautologously restates its premises.

In the same way, in mathematical induction, the conclusion has some information that follows from what is latent in the premises.

Peter: Mathematical induction is deductive, however, because the sample plus a rule about the unexamined cases actually gives us information about every member of the class. Hence the conclusion of a mathematical induction does not contain more information than was latent in the premises. Mathematical inductions therefore conclude with deductive certainty.

We can prove that smallest number (2) is divisible by 2. We can also prove that every next even number after the even number that is divisible by 2 is also divisible by 2. This is the rule of induction. And the sample case together with the rule is enough to say that all even numbers are divisible by 2.

The induction consists of three steps:

  1. Prove that P (some assertion/principle) holds for the minimal case.
  2. In the induction case, we introduce an hypothesis that it is true for some case (our assumption) and prove that it is true for the successor case.
  3. Then we discharge the hypothesis and make a conditional statement out of the hypothesis and conclusion.
  4. 1,2,3 taken together shows us that P is true for all cases. If we don’t use the minimal case in 1, then P is true for the case we started with and all the successors and not for all possible cases. Thus it is necessary to start with the minimal case.

The induction step is basically a conditional statement, where the condition is the antecedent and we derive the consequent.

There are other subtleties too. Peter again: Perhaps it does not go without saying that if we are to use mathematical induction to prove that some theorem applies to “all possible cases”, then those cases must somehow be enumerable and tightly linked to successive integers. We have to be able to speak about the minimal case, the nth case, and the successor of a given case. So it is perfect for proving theorems about integers themselves. The theorem that all even numbers are divisible by 2 clearly has a minimal case, namely 2, and each case (even number) clearly has a successor (the next even number). We could not use mathematical induction to prove that all hackers smell like pizza.

So, the sample set should be totally ordered set?

It takes ingenuity to decide whether to use mathematical induction or not to prove something. It necessitates one parameter upon which we can build our proof and that parameter should indeed be representative of the desired property of the thing in hand.

Leave a Comment

Follow

Get every new post delivered to your Inbox.