The SVP problem in Lattice Cryptography is said to be NP-hard under "randomized reductions". What does the phrase "randomized reductions" mean?
Does it mean the "basis" is randomly transformed? If so, why can we not use LLL(lenstra-lenstra-lovasz) algorithm to get a "more orthogonal" set of basis vectors? And would this reduce the hardness of the SVP problem?
Excuse the use of colloquialism in "more orthogonal". I hope it doesn't make the question ambiguous
EDIT: Source for the definition of the SVP: https://en.wikipedia.org/wiki/Lattice_problem
The word reduction is used in the context of algorithmic complexity, as @MishaLavrov correctly pointed out.
https://en.wikipedia.org/wiki/Reduction_(complexity)
The definition of SVP never pointed to a randomized transformation of the lattice basis. But, the SVP problem is indeed easier to solve using a "good" basis (short and orthogonal). This can be verified through a quick glance of the GGH cryptosystem.
https://en.wikipedia.org/wiki/GGH_encryption_scheme
And among other basis reduction algorithms the LLL can be used to obtain a "good" basis (short and orthogonal)