4
$\begingroup$

In "Efficient reductions among lattice problems" by Micciancio (2007) it is said, that

SVP reduces to SIVP in their exact versions.

I did not found anything about this fact, is a reduction that trivial? Does the same hold for their approximation versions?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

It is non-trivial, You need to see the Corollary 7 in Mic07, Micciancio proved that a series of problems (including CVP and SIVP) in the Euclidean norm are equivalent in their exact version under polynomial time rank-preserving reductions. And in GMSS99, Goldreich et al showed a reduction from SVP to CVP, So, combination of both, you got a reduction from SVP to SIVP. As for the approximation versions, you could see Noah Stephens-Davidowitz's paper NSD16.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you, that helps a lot! $\endgroup$
    – user108492
    Mar 25 at 13:33
  • $\begingroup$ In Stephens-Davidowitz's paper, it is mentioned that SIVP_gamma reduces to SVP_gamma, but he said that he is not aware of any other source. He gave a proof, as far as I can see, but his paper is not been officially published. Is there anything behind? Does the relation hold? $\endgroup$
    – user108492
    Mar 25 at 13:40
  • $\begingroup$ Yes, But I don't know if it will be published later, Maybe this proof is too trivial to published, In fact, the reduction is from $SIVP_{\sqrt{n}\gamma}$ to $SVP_{\gamma}$. Maybe, If someone can do better than $\sqrt{n}$ between two approximate factors, there will be a publication $\endgroup$
    – constantine
    Mar 25 at 14:40
  • $\begingroup$ Ah, I see, thanks again! $\endgroup$
    – user108492
    Mar 25 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.