1 Search Results for "Bai, Shi"


Document
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices

Authors: Shi Bai, Damien Stehlé, and Weiqiang Wen

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/( sqrt(2) * gamma) to the unique Shortest Vector Problem (uSVP) with parameter gamma for any gamma > 1 that is polynomial in the lattice dimension n. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.

Cite as

Shi Bai, Damien Stehlé, and Weiqiang Wen. Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 76:1-76:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.ICALP.2016.76,
  author =	{Bai, Shi and Stehl\'{e}, Damien and Wen, Weiqiang},
  title =	{{Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{76:1--76:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.76},
  URN =		{urn:nbn:de:0030-drops-62085},
  doi =		{10.4230/LIPIcs.ICALP.2016.76},
  annote =	{Keywords: Lattices, Bounded Distance Decoding Problem, Unique Shortest Vector Problem, Sparsification}
}
  • Refine by Author
  • 1 Bai, Shi
  • 1 Stehlé, Damien
  • 1 Wen, Weiqiang

  • Refine by Classification

  • Refine by Keyword
  • 1 Bounded Distance Decoding Problem
  • 1 Lattices
  • 1 Sparsification
  • 1 Unique Shortest Vector Problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail