Dimension-preserving reductions between lattice problems. Stephens-Davidowitz, N. 2015.
Dimension-preserving reductions between lattice problems [pdf]Paper  abstract   bibtex   115 downloads  
Computational problems on lattices have found a remarkable number of applications in computer science. In particular, over the past twenty years, many strong cryptographic primitives have been constructed with their security based on the (worst-case) hardness of various lattice problems. Due to their importance, there has been much work towards understanding the relationship between these problems. For the parameters that typically interest us, the fastest known algorithms for lattice problems run in time that is exponential in the dimension of the lattice. Therefore, we are typically interested in reductions that preserve this dimension. (We actually relax this notion slightly and consider a reduction to be ``dimension-preserving'' if it increases the dimension by at most an additive constant.) We summarize many of the known results in this area.

Downloads: 115