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 $\RR^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 $\begin{pmatrix}1\\1\end{pmatrix}$ and $\begin{pmatrix}2\\0\end{pmatrix}$ as your Basis Vectors. 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.
No comments:
Post a Comment