Good basis vs bad basis: On the ability of Babai’s Round-off Method for solving the Closest Vector Problem
| Autor: | Muhammad Asyraf Asbullah, Arif Mandangan, Hailiza Kamarulhaili |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Journal of Physics: Conference Series. 1366:012016 |
| ISSN: | 1742-6596 1742-6588 |
| DOI: | 10.1088/1742-6596/1366/1/012016 |
| Popis: | A lattice basis is consisting of linearly independent basis vectors that span the lattice. A lattice in dimension of 2 and above have infinitely many bases. These bases have different quality in terms of the length (norm) and orthogonality of basis vectors. A lattice basis with reasonably short and orthogonal basis vectors is normally referred to as a ‘good basis’. On the contrary, a lattice basis with long and non-orthogonal basis vectors is normally referred to as a ‘bad basis’. The most establish hard problems in lattice are the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). The solutions of these NP-hard problems can be categorized as exact and approximation solutions. Since the hardness of these problems significantly grows once the lattice dimension increases, approximation methods for solving these problems are preferable in practice. Babai’s Round-off Method is an approximation method for solving the CVP. Executing this method by using different bases of the same lattice return outputs with different distance to the target vector. When the method is executed using a good basis, it works effectively for returning a lattice vector that is located close to the target vector. On the contrary, the method works ineffectively when it is executed using a bad basis where the returned lattice vector is located far from the target vector. In this study, we investigated the reasons behind this occurrence. For that purpose, we solved a CVP instance by executing the Babai’s Round-off Method using a good basis and a bad basis. As a result, we discovered how the norms and orthogonality of basis vectors play their role for influencing the quality of the output returned by the method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|