Notes for UMich EECS 598 (2015): Clean-up

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.

Homework 3

Problem 1. I can do this for all $\sout{\gamma \ge 1+\epsilon }$ for any fixed positive ε, or alternatively, for density $\sout{\le \frac{\sout{C}}{\sout{\epsilon +\log \gamma }}}$ for any fixed positive ε. However, my method breaks down once we move to the original formulation with γ=1+o(1)​.

Updated on 13 January. The homework problem definitely should assume use either density $\le \frac{C}{\epsilon +\log \gamma }$ or assume $\gamma \ge 1+\epsilon$ for some ε>0. Otherwise, this would contradict the last sentence of lecture note 5. For simplicity, I will assume γ≥2.

WLoG, assume $a_1$ is the largest entry in a. By the density constraint, we have a1​≥γn/C. We set $B=\lceil \gamma \sqrt{n}\rceil$ in Frieze’s attack, then any γ-approximation of the shortest non-zero vector is in the form of (z0​)=B(zzn+1​​). Assuming $\mathbf{z}$ is not a multiple of $\mathbf{x}$ and following the same argument in lecture note 5, we find ${\mathbf{a}}^{\mathsf{T}}\mathbf{y}=0$ for y=z−zn+1​x​=0. Moreover, $\mathbf{y}$ has at least two non-zero entries, since all entries in $\mathbf{a}$ are positive.

Let $S$ be the set of tuples of integer vectors and integers $(\mathbf{z},z_{n+1},\mathbf{x},\mathbf{y},i)$ s.t. $|\mathbf{z}|\le \gamma \sqrt{n},|z_{n+1}|\le 2\gamma \sqrt{n},\mathbf{x}\in {\{0,1\}}^n,\mathbf{y}=\mathbf{z}-z_{n+1}\mathbf{x}$ and $i\ge 2$ is the smallest index s.t. yi​​=0. Note that $\mathbf{y},i$ are uniquely determined by z,zn+1​,x. If we sample non-largest entries in $\mathbf{a}$ uniformly at random, we have $$\underset{\mathbf{a}}{\mathrm{Pr}}\left[\exists s\in S:{\mathbf{a}}^{\mathsf{T}}\mathbf{y}=0\right]\le \sum _{s\in S}\underset{\mathbf{a}}{\mathrm{Pr}}\left[a_i=\frac{-{\sum }_{j\ne i}{a}_j{y}_j}{y_i}\right]\le \frac{|S|}{{\gamma }^{n/C}}.$$

We now bound ∣S∣. Let X=[2−1​,21​)n, then for any two distinct integer vectors z,z′, we have (z+X)∩(z′+X)=∅. Moreover, for any integer vector $\mathbf{z}$ of length at most γn​, we have (z+X)⊆(γ+1)n​B. Therefore, by counting the volume, $$|S|\le V_n(\gamma +1{)}^n{n}^{n/2}\cdot (2\gamma \sqrt{n}+1)\cdot 2^n\sim 2\gamma \sqrt{\pi }(8\pi e(\gamma +1{)}^2{)}^{n/2}.$$ If we set C=1/5, we get ∣S∣/γn/C=o(γ1−n/2)=o(2−n/2).

For large enough n, we use Frieze’s attack with the above B; for small n’s we can solve the subset-sum problem using brute force. This solves all but an exponentially small fraction of subset-sum instances of density $\le \frac{1}{5\log \gamma }$ in polynomial time using an ${\mathsf{S}\mathsf{V}\mathsf{P}}_{\gamma }$ oracle.

Question. In lecture note 5, the author did not fix $\mathbf{x}$ when considering the probability of aTy=0. This seems to be an error, because $\mathbf{y}$ is dependent on $\mathbf{a}$ (because $\mathbf{x}$ is dependent on a,s), and the right-hand side of ‘a1​=y1​−∑i=2n​ai​yi​​’ is highly non-independent of a1​. 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 $2^n$ is killed by 2−εn2.

Problem 2. This is true due to the uniqueness of QDU/LDQ decomposition and that $(\mathbf{Q}\mathbf{D}\mathbf{U}{)}^{-\mathsf{T}}$ is exactly in the form of LDQ.

Problem 3. This seems beyond the scope of the (incomplete) lecture notes and beyond my knowledge base.

Homework 4

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.

Problem 1(a). This problem is trivial if $q$ is a prime power (using Gaussian elimination). For general q, the problem seems non-trivial to me. I’m very interested to learn how the algorithm for general $\sout{q}$ 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 3D-MATCHING≤mP​INV-SUBMATRIX-Z30​. Here, $\text{INV-}\text{SUBMATRIX-}{\mathbb{Z}}_{30}$ is the problem of deciding whether there is an invertible $n\times n$ submatrix of a given $n\times m$ matrix over Z30​.

More precisely, the problem can be solved in polynomial time if $q$ has at most two distinct prime factors and one prime factor is known; and the problem is NP-hard if $q$ 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 q. Even if not, when all prime factors of $q$ are super-polynomially large and the matrix is sampled uniformly at random, the first $n$ 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 $\mathbf{A}=\left(\begin{array}{cc}\mathbf{P}& \mathbf{R}\end{array}\right)\mathbf{Q}$ for invertible matrix $\mathbf{P}$ and permutation matrix Q, we have L⊥(A)=L⊥(P−1A). Therefore, we can replace $\mathbf{A}$ by P−1A, which has ${\mathbf{I}}_n$ as a submatrix (position determined by Q), without changing the lattice.

Problem 1(c). Writing $\mathbf{A}=\mathbf{P}\left(\begin{array}{cc}{\mathbf{I}}_n& \overline{\mathbf{A}}\end{array}\right)\mathbf{Q}$ for invertible matrix $\mathbf{P}$ and permutation matrix Q, we have $${\mathcal{L}}^{\perp }(\mathbf{A})=\left\{{\mathbf{Q}}^{-1}\left(\begin{array}{c}q\mathbf{u}-\overline{\mathbf{A}}\mathbf{v}\\ \mathbf{v}\end{array}\right):\mathbf{u}\in {\mathbb{Z}}^n,\mathbf{v}\in {\mathbb{Z}}^{m-n}\right\}.$$ The basis can be chosen as $$\mathbf{B}={\mathbf{Q}}^{-1}\left(\begin{array}{cc}q{\mathbf{I}}_n& -\overline{\mathbf{A}}\\ & {\mathbf{I}}_{m-n}\end{array}\right).$$

Problem 1(d). For typical parameters, we use the property that a random $\mathbf{A}$ contains an invertible $n\times n$ submatrix with high probability (say, with probability 1−p), and we reduce SIS to ‘SIS with small noise’ at the price of removing p-fraction of solvable instances. Conditioned on $\mathbf{A}$ containing an invertible $n\times n$ submatrix, we write A=P(In​​A′​)Q. Note that ${\mathbf{A}}^{\prime }$ is uniformly random. We use the ‘SIS with small noise’ oracle to get $\mathbf{z},\mathbf{e}$ s.t. $\mathbf{z}\ne 0,{\mathbf{A}}^{\prime }\mathbf{z}=\mathbf{e}$ and $\mathbf{e}$ is small. Now, ${\mathbf{Q}}^{-1}\left(\begin{array}{c}-\mathbf{e}\\ \mathbf{z}\end{array}\right)$ is a non-zero small (because $\mathbf{e},\mathbf{z}$ are small and $\mathbf{Q}$ only permutes the indices) solution to Ax=0.

Problem 2. For any multi-secret LWE distinguisher, construct the following LWE distinguisher that internally runs the multi-secret LWE distinguisher:

1. At the beginning, sample $t^{\prime }\stackrel{\$}{\leftarrow }[t]$ and ${\mathbf{s}}_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q^n$ for t′<i≤t.
2. Whenever LWE distinguisher asks for a new challenge tuple (a,b1​,…,bt​), ask for an LWE challenge pair (a,b), sample $b_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$ for $i<t^{\prime }$ and $e_i\stackrel{\$}{\leftarrow }\chi$ for t′<i≤t, and return $$(\mathbf{a},b_1,\dots ,b_{t^{\prime }-1},b,⟨\mathbf{a},{\mathbf{s}}_{t^{\prime }+1}⟩+e_{t^{\prime }+1},\dots ,⟨\mathbf{a},{\mathbf{s}}_t⟩+e_t)$$ to the LWE distinguisher.
3. At the end, output whatever the multi-secret LWE distinguisher outputs.

The LWE distinguisher has advantage (at least) $1/t$ 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 nlogq, but its public-key is of size ∼n2log2q. So does dual Regev (GPV) scheme. If the problem is indeed talking about Regev’s encryption, we could simply use the $n$ instances with shared A. This blows up the public key/ciphertext sizes by a constant factor.