Efficient bounded distance decoders for Barnes-Wall lattices

Daniele Micciancio, Antonio Nicolosi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

Abstract

We describe a new family of parallelizable bounded distance decoding algorithms for the Barnes-Wall lattices, and analyze their decoding complexity. The algorithms are parameterized by the number p = Ak ≤ N 2 of available processors, work for Barnes-Wall lattices in arbitrary dimension N = 2n, correct any error up to squared unique decoding radius dmin2/4, and run in worstcase time O (N log 2 N/√p). Depending on the value of the parameter p, this yields efficient decoding algorithms ranging from a fast sequential algorithm with quasilinear decoding complexity O(N log2 N), to a fully parallel decoding circuit with polylogarithmic depth O(log2 N) and polynomially many arithmetic gates.

Original languageEnglish
Title of host publicationProceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Pages2484-2488
Number of pages5
DOIs
StatePublished - 2008
Event2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada
Duration: 6 Jul 200811 Jul 2008

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101

Conference

Conference2008 IEEE International Symposium on Information Theory, ISIT 2008
Country/TerritoryCanada
CityToronto, ON
Period6/07/0811/07/08

Fingerprint

Dive into the research topics of 'Efficient bounded distance decoders for Barnes-Wall lattices'. Together they form a unique fingerprint.

Cite this