The first day of the 2nd Bar-Ilan Winter school on Cryptography featured lectures by Oded Regev, Vadim Lyubashevsky and Chris Peikert. Oded gave an excellent introduction to the lattices, stating various properties of the lattices, the definitions of the "so called" hard computational problems like the Shortest Vector Problem (SVP), Shortest Independent Vectors problem (SIVP) and the Closest Vector Problem (CVP), along with the summary of the known results related to the computational aspects of these problems. This first lecture laid a great platform for the remaining talks of the day.
The second talk by Vadim gave an introduction to the Smallest Integer Solution (SIS) problem, which is as follows:
given n random vectors a1, ...., an, we have to find out a "non-trivial" solution z1, ...., zn, where each Zi belongs to {-1, 0, 1} such that, the following condition holds:
z1 a1 + z2 a2 + .... + zn an = 0 mod M
In some sense, the above problem can be viewed as an instance of the sub-set sum problem. Vadim then showed the relationship of SIS to the Lattice problems and presented a very simple collision resistant hash function, whose security is based on the difficulty of solving SIS. He then talked about the properties of the Gaussian distribution, which is very much used in al most any lattice based crypto primitive.
The last two lectures of the first day were given by Chris Peikert. His first lecture was on the introduction to the Learning with Errors (LWE) problem. This problem is a fundamental problem in lattices and used in many popular lattice based crypto primitives. The problem first introduced by Oded Regev can be viewed as a complementary problem to the SIS. The problem is as follows:
given random vectors a1, ..., an and the products b1, ...., bn, where each bi is of the following form:
bi = (ai, s) + ei,
where (ai, s) denotes the dot product of ai and s, s is a secret and each "ei" is a small "Gaussian" noise (error), it is hard to find the secret s or the error vectors e1, ...., en. Anyone who is familar with Coding theory can easily see that this problem is related to the general problem of decoding, where ai's constitute the generator matrix of a linear code and s constitutes the message and ei's constitute the error vector and we have to find out the original message s. The LWE problem can be veiwed as a special form of the general decoding problem.
One very interesting property of the LWE problem in contrast to the classical hard problems (like CDH and the DDH problem) is that the search and the decision version of the LWE problem are equivalent. The decision version of the LWE problem is that we cannot distinguish between the pairs (a1, b1), ..., (an, bn) where bi's are random and the pairs (a1, b1), ..., (an, bn), where bi's are now of the form (ai, s) + ei. Chris then very nicely explained the Regev's public key crypto system based on LWE.
The second talk by Chris presented a very nice and new application of LWE, namely the construction of a PRF using LWE. This result is going to be presented in Eurocrypt 2012. Actually Chris has three papers in Eurocrypt 2012, related to the lattices and he presented two of them during the four days of the school. Though I did not completely understood the construction but I got a feel of the underlying idea and I found it very intersting. Goldreich, Goldwasser and Micali (GGM84) in their seminal work showed how to construct PRFs based on PRGs. However the algorithm requires k iterations for a k-length input. Naor and Reingold showed how to construct PRFs using synthesizers. Informally, a synthesizer S is a deterministic function from D x D to D (here D is some finite set or a domain), such that for any a1, ..., am and b1, ..., bm, selected uniformly from the set D, for some polynomial m, the m^2 outputs
{S(ai, bj)}
should be pseudorandom. Given a synthesizer, we can construct a PRF by using recursion as follows: let x = x1, ..., xk be the input for the PRF. Corresponding to each xi, we will select random si, 0 (corresponding to xi = 0) and si, 1 (corresponding to xi = 1). Now to get the value of the PRF for x1, ...., xk, we will construct a sort of binary tree. At the leaf levels, we have k nodes, corresponding to x1, ..., xk. At the next higher level, depending upon whether xi = 0 or xi = 1, we place si, 0 or si, 1. Then at the next higher level, we apply the synthesizer S on the elements at the lower level as follows: the first synthesizer S will be applied on s1, * and s2, * (here * will be either 0 or 1, depending upon the input for the PRF). The second synthesizer will be applied on s3, * and s4, * and so on and the last synthesizer will be applied on sk-1, * and sk, *. We recursively apply this logic to the next higher level, where we apply a synthesizer to the two childrens at the lower level and like this we reach the root level, whose value is the final output of the PRF. This construction is somewhat similar to the one used while constructing the Merkle tree. The pseudo-randomnss of the final output follows from the properties of the synthesizers. The idea used in the paper by Chris is to construct synthesizers based on LWE.
The slides and the videos of all the lectures will be available in the school website and I think that anyone who wants to get an introduction to the Lattice based cryptography should look into these materials. I also have the print outs of all the slides and if anyone is interested to look at them, I would be very happy to give the print outs.
The second talk by Vadim gave an introduction to the Smallest Integer Solution (SIS) problem, which is as follows:
given n random vectors a1, ...., an, we have to find out a "non-trivial" solution z1, ...., zn, where each Zi belongs to {-1, 0, 1} such that, the following condition holds:
z1 a1 + z2 a2 + .... + zn an = 0 mod M
In some sense, the above problem can be viewed as an instance of the sub-set sum problem. Vadim then showed the relationship of SIS to the Lattice problems and presented a very simple collision resistant hash function, whose security is based on the difficulty of solving SIS. He then talked about the properties of the Gaussian distribution, which is very much used in al most any lattice based crypto primitive.
The last two lectures of the first day were given by Chris Peikert. His first lecture was on the introduction to the Learning with Errors (LWE) problem. This problem is a fundamental problem in lattices and used in many popular lattice based crypto primitives. The problem first introduced by Oded Regev can be viewed as a complementary problem to the SIS. The problem is as follows:
given random vectors a1, ..., an and the products b1, ...., bn, where each bi is of the following form:
bi = (ai, s) + ei,
where (ai, s) denotes the dot product of ai and s, s is a secret and each "ei" is a small "Gaussian" noise (error), it is hard to find the secret s or the error vectors e1, ...., en. Anyone who is familar with Coding theory can easily see that this problem is related to the general problem of decoding, where ai's constitute the generator matrix of a linear code and s constitutes the message and ei's constitute the error vector and we have to find out the original message s. The LWE problem can be veiwed as a special form of the general decoding problem.
One very interesting property of the LWE problem in contrast to the classical hard problems (like CDH and the DDH problem) is that the search and the decision version of the LWE problem are equivalent. The decision version of the LWE problem is that we cannot distinguish between the pairs (a1, b1), ..., (an, bn) where bi's are random and the pairs (a1, b1), ..., (an, bn), where bi's are now of the form (ai, s) + ei. Chris then very nicely explained the Regev's public key crypto system based on LWE.
The second talk by Chris presented a very nice and new application of LWE, namely the construction of a PRF using LWE. This result is going to be presented in Eurocrypt 2012. Actually Chris has three papers in Eurocrypt 2012, related to the lattices and he presented two of them during the four days of the school. Though I did not completely understood the construction but I got a feel of the underlying idea and I found it very intersting. Goldreich, Goldwasser and Micali (GGM84) in their seminal work showed how to construct PRFs based on PRGs. However the algorithm requires k iterations for a k-length input. Naor and Reingold showed how to construct PRFs using synthesizers. Informally, a synthesizer S is a deterministic function from D x D to D (here D is some finite set or a domain), such that for any a1, ..., am and b1, ..., bm, selected uniformly from the set D, for some polynomial m, the m^2 outputs
{S(ai, bj)}
should be pseudorandom. Given a synthesizer, we can construct a PRF by using recursion as follows: let x = x1, ..., xk be the input for the PRF. Corresponding to each xi, we will select random si, 0 (corresponding to xi = 0) and si, 1 (corresponding to xi = 1). Now to get the value of the PRF for x1, ...., xk, we will construct a sort of binary tree. At the leaf levels, we have k nodes, corresponding to x1, ..., xk. At the next higher level, depending upon whether xi = 0 or xi = 1, we place si, 0 or si, 1. Then at the next higher level, we apply the synthesizer S on the elements at the lower level as follows: the first synthesizer S will be applied on s1, * and s2, * (here * will be either 0 or 1, depending upon the input for the PRF). The second synthesizer will be applied on s3, * and s4, * and so on and the last synthesizer will be applied on sk-1, * and sk, *. We recursively apply this logic to the next higher level, where we apply a synthesizer to the two childrens at the lower level and like this we reach the root level, whose value is the final output of the PRF. This construction is somewhat similar to the one used while constructing the Merkle tree. The pseudo-randomnss of the final output follows from the properties of the synthesizers. The idea used in the paper by Chris is to construct synthesizers based on LWE.
The slides and the videos of all the lectures will be available in the school website and I think that anyone who wants to get an introduction to the Lattice based cryptography should look into these materials. I also have the print outs of all the slides and if anyone is interested to look at them, I would be very happy to give the print outs.
No comments:
Post a Comment