New Variants of Lattice Problems and Their NP-Hardness

摘要：

　　We introduce some new variants of lattice problems: Quadrant-SVP, Quadrant-CVP and Quadrant-GapCVP.All of them are NP-hard under deterministic reductions from subset sum problem.These new type of lattice problems have potential in construction of cryptosystems.Moreover, these new variant problems have reductions with standard SVP (shortest vector problem) and CVP (closest vector problem), this feature gives new way to study the complexity of SVP and CVP, especially for the proof of NP-hardness of SVP under deterministic reductions, which is an open problem up to now.

关键词： lattice complexity NP-hard deterministic reduction

作者: Wulu Li

作者单位: School of Mathematical Science Peking University Beijing,China

会议类型: 国际会议

会议名称: The 10th International Conference on Information Security Practice and Experience(ISPEC 2014)(第十届信息安全实践国际会议)

会议地点: 福州

会议语种:英文

页码: 511-523

在线出版日期: 2014-05-05（万方平台首次上网日期，不代表论文的发表时间）