On promise problem of the Generalized Shortest Vector Problem

Wenwen Wang; Kewei Lv

doi:10.1007/978-3-319-29814-6_4

On promise problem of the Generalized Shortest Vector Problem

Wenwen Wang, Kewei Lv

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-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 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	https://doi.org/10.1007/978-3-319-29814-6_4
State	Published - Mar 1 2016

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

Keywords

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

Publisher link

10.1007/978-3-319-29814-6_4

Find It

Find It at U of M Libraries

Cite this

@article{6966473466124c5daaad4589f02b71e0,

title = "On promise problem of the Generalized Shortest Vector Problem",

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",

author = "Wenwen Wang and Kewei Lv",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.",

year = "2016",

month = mar,

day = "1",

doi = "10.1007/978-3-319-29814-6_4",

language = "English (US)",

volume = "9543",

pages = "37--49",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - On promise problem of the Generalized Shortest Vector Problem

AU - Wang, Wenwen

AU - Lv, Kewei

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016/3/1

Y1 - 2016/3/1

N2 - 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.

AB - 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.

KW - Polynomial time reduction

KW - The generalized shortest vector problem

KW - The saturated sublattice

KW - Transference theorems

UR - http://www.scopus.com/inward/record.url?scp=84960906263&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84960906263&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-29814-6_4

DO - 10.1007/978-3-319-29814-6_4

M3 - Article

AN - SCOPUS:84960906263

SN - 0302-9743

VL - 9543

SP - 37

EP - 49

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

On promise problem of the Generalized Shortest Vector Problem

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this