@unpublished{SteDimensionpreservingReductions15,
  title = {Dimension-preserving reductions between lattice problems},
  abstract = {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.},
  url = {http://noahsd.com/latticeproblems.pdf},
  author = {{Stephens-Davidowitz}, Noah},
  year = {2015}
}

{"_id":"JPvr9yFg7cpE9qyL2","bibbaseid":"stephensdavidowitz-dimensionpreservingreductionsbetweenlatticeproblems-2015","downloads":97,"creationDate":"2018-05-30T23:17:50.395Z","title":"Dimension-preserving reductions between lattice problems","author_short":["Stephens-Davidowitz, N."],"year":2015,"bibtype":"unpublished","biburl":"https://dl.dropbox.com/s/26018h26wgh5c2o/bibbase.bib","bibdata":{"bibtype":"unpublished","type":"unpublished","title":"Dimension-preserving reductions between lattice problems","abstract":"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.","url":"http://noahsd.com/latticeproblems.pdf","author":[{"propositions":[],"lastnames":["Stephens-Davidowitz"],"firstnames":["Noah"],"suffixes":[]}],"year":"2015","bibtex":"@unpublished{SteDimensionpreservingReductions15,\n title = {Dimension-preserving reductions between lattice problems},\n abstract = {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. \n\nDue 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.) \n\nWe summarize many of the known results in this area.},\n url = {http://noahsd.com/latticeproblems.pdf},\n author = {{Stephens-Davidowitz}, Noah},\n year = {2015}\n}\n\n\n\n","author_short":["Stephens-Davidowitz, N."],"key":"SteDimensionpreservingReductions15","id":"SteDimensionpreservingReductions15","bibbaseid":"stephensdavidowitz-dimensionpreservingreductionsbetweenlatticeproblems-2015","role":"author","urls":{"Paper":"http://noahsd.com/latticeproblems.pdf"},"metadata":{"authorlinks":{"stephens-davidowitz, n":"https://www.noahsd.com/"}},"downloads":97},"search_terms":["dimension","preserving","reductions","between","lattice","problems","stephens-davidowitz"],"keywords":[],"authorIDs":["NsKfZS8svvuZwZEBa"],"dataSources":["j49aoDnSSLjzndmof","kxAEBDHXGfX8ATRE5","HhrFT8C8XJdJggbxX","hAtYxr4ZyBqfZJYWo","t7S757akkuDKXd4Lt","bNuEGB6D6ArYKZG7X","rNfpY7KpfzEnPHFDu"]}