You are looking at a specific version 20130309:133724 of this paper. See the latest version.

Paper 2013/052

Some Complexity Results and Bit Unpredictable for Short Vector Problem

Kuan Cheng

Abstract

In this paper, we prove that finding the approximate shortest vector with length in $[\lambda_{1},\gamma \lambda_{1} ]$ could be reduced to GapSVP. We also prove that shortest vector problem could also be reduced to GapSVP with a small gap. As the complexity of uSVP is not very clear, we improve crurrent complexity results\cite{AD2011} of uSVP, proving uSVP could be reduced from SVP deterministically. What's more, we prove that the search version of uSVP could be reduced to decisional version of uSVP with almost the same gap. At last, based on the results above, we prove a bit-unpredictable property of SVP.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Not published yet
Keywords
LatticeSVPuSVPGapSVP
Contact author(s)
ckkcdh @ hotmail com
History
2013-03-09: last of 3 revisions
2013-02-06: received
See all versions
Short URL
https://ia.cr/2013/052
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.