Ideal-SVP ⇒ Ring-SIS

Ideal-SVP implies Ring-SIS.

Statement

Migrated verbatim from shortest-integer-solution § Ring-SIS:

Ring-SIS enjoys the same worst-case-to-average-case hardness as plain SIS, now reducing from ideal-SVP (shortest vectors in ideal lattices), and enables $O(n\log n)$ arithmetic and $O(n\log q)$-bit keys — LM06.

Notes

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Ideal-SVP has no wiki page.
• Concrete efficiency claims (O(n log n) arithmetic, O(n log q)-bit keys) are bundled into the same bullet as the reduction and share its single citation.