## Abstract

In 2009, Bl¨omer and Naewe proposed the Generalized Shortest Vector Problem (GSVP). We initiate the study of the promise problem (GAPSAM) for GSVP. It is a promise problem associated with estimating the subspace avoiding minimum. We show GAPSAM_{c·n} lies in coNP, where c is a constant. Furthermore, we study relationships between GAPSAM of a lattice and the nth successive minimum, the shortest basis, and the shortest vector in the dual of the saturated sublattice, and obtain new transference theorems for GAPSAM. Then, using the new transference theorems, we give various deterministic polynomial time reductions among the promise problems for some lattice problems. We also show GAPSAM_{γ} can be reduced to the promise problem associated to the Closest Vector Problem (GAPCVP_{γ}) under a deterministic polynomial time rank-preserving reduction.

Original language | English (US) |
---|---|

Pages (from-to) | 37-49 |

Number of pages | 13 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 9543 |

DOIs | |

State | Published - Mar 1 2016 |

## Keywords

- Polynomial time reduction
- The generalized shortest vector problem
- The saturated sublattice
- Transference theorems