Sunday, December 27, 2009

Some snapshots of Theoretical Computer Science from my Camera

I am no authority on the subject. All that I will say below is based on the brief (and ongoing!) tour of this fascinating field.

If you want a more rigorous account, I would suggest that you look into places like Dick Lipton's blog , Luca Trevisan's blog or some other of the many beautiful sources which wikipedia and google will return.

This is supposed to be a realxed introductory pathway into some aspects of the field. I will include what I feel are really amazing insights that many theorists came over the years and will hopefully share my enthusiasm with you about the field. I hope that you will also provide some nice and refreshing insights which I will benefit from. That might sound like me being selfish; but thats me.

Anyway, where to begin?

I do not intend to keep the discussions very light. That will defeat the purpose of making an effort to explain nice things that I am studying. Nor do I want to elaborate on research frontiers for the simple reason that I cannot do that at this moment.

Therefore, I would just blabber about topics I think I can share some refreshing insights about.

Lets begin the tour with (probably) esoteric Lattice Based Cryptography .

I guess you all know what a good cryptosystem is. One popular cryptosystem is RSA which is based on the assumption that factoring of integers is hard. Please note that it is believed that factoring integers is not NP Complete. (It is possibly easier)

NP Complete problems involve searching for the solution in an exponential sized solution space which forms the core of their difficulty.

(Certainly there is a possibility that some fiendishly clever technique is looming behind the corner which enables a quick scan through the solution space - but I discount that possibility. In other words, I am assuming that P != NP)

Also they include (search version) a report if none exists clause which basically says that the algorithm looking for a particular property in the given setting should find one or report that the structure did not contain the object of interest.

Factoring does not involve a "report if none exists" clause. Further, factorisation can be solve using quantum computation in polynomial time.

Thus, we have fair amount of evidence to believe that factorisation is not NP Complete and if you ask me I am indeed going to bet against it being NP Complete.

So far so good.

What is the natural next step? We would like to base our cryptographic scheme on the hardness of some problem X "harder than factoring". We would like some X which is NP Hard - but as of now it seems too hard.

We are still trying though - the fight is on.

We have some lattice based cryptographic schemes which we think are safe from quantum computation attacks (so far).

Looking ahead, I will also tell you that whereas with factoring the security of the scheme using it depends on what we call average case hardness.

With Lattice Based Schemes you can have what we call worst case hardness.

I will detail upon these in my later blogs.

Thanks and have a good day.

No comments:

Post a Comment