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
-
CC BY
BibTeX
@misc{cryptoeprint:2013/052,
author = {Kuan Cheng},
title = {Some Complexity Results and Bit Unpredictable for Short Vector Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/052},
year = {2013},
url = {https://eprint.iacr.org/2013/052}
}
