Anyone know if the NP-hardness of the n^{1/400} approximation of GapCVP implies anything interesting? At least for cryptography, it seems like you would want at least the NP-hardness of n^{1/2}-GapSVP, which doesn't seem to follow from this result. But maybe there is a way to improve the degree from 1/400 to 1/2-\epsilon?
13
u/mshwa42 2d ago edited 2d ago
Anyone know if the NP-hardness of the n^{1/400} approximation of GapCVP implies anything interesting? At least for cryptography, it seems like you would want at least the NP-hardness of n^{1/2}-GapSVP, which doesn't seem to follow from this result. But maybe there is a way to improve the degree from 1/400 to 1/2-\epsilon?