Lattice Based Cryptography – Getting Inside

Hello again,

While this might not be the best title for this blog, I guess I will have to make do with this to begin with.

Lattice Based Cryptographic systems are currently an active area of research in Cryptology and in Theoretical Computer Science as well. Many researchers including Oded Regev , Miklos Ajtai , Daniele Micciancio’s and Chris Peikert have contributed to this field.

The field was officially kicked off by a ground-breaking work of Ajtai in which he discovered that lattices could be used for constructing cryptographic primitives.

But I have got ahead of myself already. I guess, I am tremendously handicapped in my writing skills.

Lets back up. I need to tell you what lattices are. Further, I will have to tell you about why do we care about this new mechanism. There are loads of other questions you could think of. I would have to start slowly and thats what I do now.

A lattice a set of points in n-dimesional plane with periodic structure. (I will give a more formal definition later) Lets just say for the moment that they look like a neat laid out grid. I would like you to think about a simple lattice – the set of points with integral co-ordinates in 2-dimensional plane. This is the lattice Z^2.

You might ask why in heaven’s name does any one study these structures. If you are interested in exploring the historical context behind this, I would only say that they were extremely useful in solving Diophantine Equations . Basically here you are looking for “integral” solutions to a set of equations where the number of unknowns is more than the number of equations. The desired “set of points” (all with integral co-ordinates) is a subset of some lattice determined by the input equations. Already those of you who are familiar with linear algebra can look ahead and feel that Linear Algebra will certainly have some bearing upon where are we headed. You can also feel the vague hint of connection with Integer (and Linear) Programming.

Okay, enough. If you want to study more of the historical background behind lattices, I would suggest that you go and read some text like this on Geometry of numbers.

Now given the number theoretic importance of lattices, you might be ready for the connection with cryptography which is what this blog will mainly delve on.

But first, let me address a very basic question – what is so nice about these lattices that they, at the moment, are on the radar of researchers in cryptography? Towards the end of my previous blog, I talked about worst case hardness and average case hardness.

I said that lattice based schemes are based on worst case hardness of lattice problems. What this means is unlike factoring, where by saying factoring integers is hard we mean that there exist integers which are hard to factor; lattices are more fun.

To illustrate the point further, consider this – there are some integers which are easier to factor (even integers or maybe you can say multiples of small primes). So, saying factoring is hard is not enough. You need to “concoct a number” factoring which is hard. Thus, factoring is based on worst case hardness assumption. That is, the average case is not as hard as worst case.

Aha! thats where lattices steal the ball. With lattice based schemes the average case is every bit as hard as the worst case.

The above discussion about worst case hardness of lattice problems has been taken from Scott Aaronson’s insightful discussion of the topic on his blog.

So, finally, the moment. Lets throw in the formal definition of a lattice.

Given a bunch of n-linearly independent vectors from \mathcal{R}^m (kept inside a matrix B), the lattice generated by them is the set of vectors Bx = v where x is an integer vector which holds “what integral amount x_{i}” of vector b_{i} do we want to keep in v.

Notice that the Basis Vectors above are from $m-dimensional$ space. Further, their components are not “restricted” to be integers. It is the coefficients in the linear combination that need to be integral. (That is, your x_{i}s are integral).

m is the dimension of the lattice. n is its rank. Full rank lattices have m=n.

Its not necessary that a full rank lattice of rank n will hit all points in Z^n as you can verify for yourself. For example consider the following Basis with vectors \begin{pmatrix}1\\1\end{pmatrix} and \begin{pmatrix}0\\2\end{pmatrix}. Clearly they hit only those points sum of whose coordinates is even.

Can you characterize the condition on the Basis vectors for a n-dimesional full rank lattice  so that they hit Z^n?

Better still can you figure out when will two Bases be equivalent?

Perhaps thats the topic for my next blog. But do try it in the meantime.

Posted in Lattice Based Cryptography | Tagged | Leave a comment

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.

Posted in Uncategorized | Leave a comment

Hello world!

Hello Everybody,

This is Akash Kumar and I am a Computer Science Student at Georgia Tech.

I find Theory extremely compelling and hence this blog. I will take you on this tour as I am taking it right now – hopefully conveying the beauty of the subject.

Feel free to comment – I hope an exchange of ideas will help me (and maybe you) immensely.

Thats it for now

Bye and have a nice day

Some good theory blogs to follow

1) Dick Lipton’s blog

2) Lance Fortnow’s blog

3) Scott Aaronson’s blog

Posted in Uncategorized | Leave a comment