SCIENCE@home

A KZ Reduction Algorithm

Jinming Wen,X. Chang

Published 2017 in arXiv.org

ABSTRACT

The Korkine-Zolotareff (KZ) reduction is one of the often used reduction strategies for decoding lattices. A KZ reduction algorithm involves solving shortest vector problems (SVPs) and basis expansion. In this paper, first we improve the commonly used Schnorr-Euchner search strategy for solving SVPs. Then, we derive upper bounds on the magnitudes of the entries of any solution of a SVP when its basis matrix is LLL reduced. These upper bounds only involve the parameter of the LLL reduction and the dimension of the solution and they are useful for analyzing the complexity of the basis expansion in a KZ reduction algorithm. Finally, we modify the basis expansion method proposed by Zhang et al. and combine it with the improved Schnorr-Euchner search strategy to give a new KZ reduction algorithm. Simulation results show that the new KZ reduction algorithm is much faster and numerically more stable than the KZ reduction algorithm proposed by Zhang et al., especially when the basis matrix is ill conditioned.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    arXiv.org

  • Publication date

    2017-02-27

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1702.08152
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-40 of 40 references · Page 1 of 1

CITED BY