Sphere Decoding Algorithm Based on a New Radius Definition

摘要

The problem of integer least squares (ILSP) is playing a significant role in cryptography. ILSP is equivalent to finding the closest lattice point to a given point and is known to be NP-hard. Sphere decoding (SD) is an effective method for solving the ILSP. In this paper, we mainly solve ILSP by the sphere decoding algorithm (SDA). One of the key issues in SDA is how to implement a more effective tree pruning strategy. In this paper a new definition for sphere radius is proposed as a tree pruning strategy to reduce the computational complexity. The core idea of our algorithm (K-SE-SD) is to sacrifice a relatively small reduction in accuracy to reduce relatively more time complexity. Our experiments demonstrate that on average the proposed idea can reduce about 70.8% running time with an accuracy of 86.8% when k = [n/3], where n is the lattice dimension.