On promise problem of the Generalized Shortest Vector Problem

Wenwen Wang, Kewei Lv

Research output: Contribution to journalArticlepeer-review

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 GAPSAMc·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.

Keywords

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

Fingerprint

Dive into the research topics of 'On promise problem of the Generalized Shortest Vector Problem'. Together they form a unique fingerprint.

Cite this