Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 3, homework 4 and lecture note 5.
This series of blog entries are complementary to the course lecture notes. Since I have nothing I want to add for lecture note 6, there will not be a dedicated entry for that. Also, there is basically only one paragraph of comments to lecture note 5, buried in the solution to homework 3 problem 1. Together with that homework 3 and 4 are short, I decided to merge all these into one entry.
I can do this for all for any fixed positive or alternatively, for density for any fixed positive
However, my method breaks down once we move to the original formulation with
Updated on 13 January. The homework problem definitely should assume use either density or assume for some Otherwise, this would contradict the last sentence of lecture note 5. For simplicity, I will assume
WLoG, assume is the largest entry in By the density constraint, we have We set in Frieze’s attack, then any approximation of the shortest non-zero vector is in the form of Assuming is not a multiple of and following the same argument in lecture note 5, we find for Moreover, has at least two non-zero entries, since all entries in are positive.
Let be the set of tuples of integer vectors and integers s.t. and is the smallest index s.t. Note that are uniquely determined by If we sample non-largest entries in uniformly at random, we have
We now bound Let then for any two distinct integer vectors we have Moreover, for any integer vector of length at most we have Therefore, by counting the volume, If we set we get
For large enough we use Frieze’s attack with the above for small we can solve the subset-sum problem using brute force. This solves all but an exponentially small fraction of subset-sum instances of density in polynomial time using an oracle.
Question. In lecture note 5, the author did not fix when considering the probability of This seems to be an error, because is dependent on (because is dependent on and the right-hand side of is highly non-independent of I cannot make a useful estimation of the probability of this event. The conclusion in the lecture note is unaffected, because the extra loss of is killed by
Problem 2. This is true due to the uniqueness of QDU/LDQ decomposition and that is exactly in the form of
Problem 3. This seems beyond the scope of the (incomplete) lecture notes and beyond my knowledge base.
Clearly, starting from this homework, the course entered the phase of using lattice assumptions to construct cryptographic objects. The lecture notes, on the other hand, cover nothing about this topic.
This problem is trivial if is a prime power (using Gaussian elimination).
For general the problem seems non-trivial to me.
I’m very interested to learn how the algorithm for general works.
Note that if we’re not restricted to permuting the columns but arbitrary invertible operations over them, the problem is again simple using Smith normal form.
Updated today later. I posted this question to IIIS WeChat group, and a few alumni/students had a discussion. Tianqi Yang suggested looking at matroid structure and Qi Zhang suggested this could be NP-hard. Indeed, Wikipedia says computing the maximum common independent subset of three (general) matroids is NP-hard, and this StackExchange response by Sahil Singla suggests a simpler reduction from 3D matching.
With these hints, it’s straightforward to come up with Here, is the problem of deciding whether there is an invertible submatrix of a given matrix over
More precisely, the problem can be solved in polynomial time if has at most two distinct prime factors and one prime factor is known; and the problem is NP-hard if has at least three distinct prime factors and two of them are known.
This shouldn’t affect most use cases in cryptography. I suppose people will use a prime power Even if not, when all prime factors of are super-polynomially large and the matrix is sampled uniformly at random, the first columns will be invertible with overwhelming probability, so we don’t have to deal with this NP-hard problem at all.
Problem 1(b). Writing for invertible matrix and permutation matrix we have Therefore, we can replace by which has as a submatrix (position determined by without changing the lattice.
Problem 1(c). Writing for invertible matrix and permutation matrix we have The basis can be chosen as
Problem 1(d). For typical parameters, we use the property that a random contains an invertible submatrix with high probability (say, with probability and we reduce SIS to ‘SIS with small noise’ at the price of removing fraction of solvable instances. Conditioned on containing an invertible submatrix, we write Note that is uniformly random. We use the ‘SIS with small noise’ oracle to get s.t. and is small. Now, is a non-zero small (because are small and only permutes the indices) solution to
Problem 2. For any multi-secret LWE distinguisher, construct the following LWE distinguisher that internally runs the multi-secret LWE distinguisher:
- At the beginning, sample and for
- Whenever LWE distinguisher asks for a new challenge tuple ask for an LWE challenge pair sample for and for and return to the LWE distinguisher.
- At the end, output whatever the multi-secret LWE distinguisher outputs.
The LWE distinguisher has advantage (at least) of that of the multi-secret LWE distinguisher.
Problem 3. I don’t know what cryptosystem was discussed in the lecture. Regev’s LWE-based encryption has ciphertext size but its public-key is of size So does dual Regev (GPV) scheme. If the problem is indeed talking about Regev’s encryption, we could simply use the instances with shared This blows up the public key/ciphertext sizes by a constant factor.