Efficient bounded distance decoders for Barnes-Wall lattices

Daniele Micciancio; Antonio Nicolosi

doi:10.1109/ISIT.2008.4595438

Efficient bounded distance decoders for Barnes-Wall lattices

Daniele Micciancio
, Antonio Nicolosi

Department of Computer Science

University of California at San Diego

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

20 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 = A^k ≤ N ² of available processors, work for Barnes-Wall lattices in arbitrary dimension N = 2ⁿ, correct any error up to squared unique decoding radius d_min²/4, and run in worstcase time O (N log ² 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 log² N), to a fully parallel decoding circuit with polylogarithmic depth O(log² N) and polynomially many arithmetic gates.

Original language	English
Title of host publication	Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Pages	2484-2488
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2008.4595438
State	Published - 2008
Event	2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada Duration: 6 Jul 2008 → 11 Jul 2008

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095
ISSN (Electronic)	2157-8117

Conference

Conference	2008 IEEE International Symposium on Information Theory, ISIT 2008
Country/Territory	Canada
City	Toronto, ON
Period	6/07/08 → 11/07/08

Access to Document

10.1109/ISIT.2008.4595438

Cite this

@inproceedings{ac01dc5c23394fccaaa3cf0f3cdc4798,

title = "Efficient bounded distance decoders for Barnes-Wall lattices",

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

author = "Daniele Micciancio and Antonio Nicolosi",

year = "2008",

doi = "10.1109/ISIT.2008.4595438",

language = "English",

isbn = "9781424422579",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "2484--2488",

booktitle = "Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008",

note = "2008 IEEE International Symposium on Information Theory, ISIT 2008 ; Conference date: 06-07-2008 Through 11-07-2008",

}

Micciancio, D & Nicolosi, A 2008, Efficient bounded distance decoders for Barnes-Wall lattices. in Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008., 4595438, IEEE International Symposium on Information Theory - Proceedings, pp. 2484-2488, 2008 IEEE International Symposium on Information Theory, ISIT 2008, Toronto, ON, Canada, 6/07/08. https://doi.org/10.1109/ISIT.2008.4595438

Efficient bounded distance decoders for Barnes-Wall lattices. / Micciancio, Daniele; Nicolosi, Antonio.
Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008. 2008. p. 2484-2488 4595438 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient bounded distance decoders for Barnes-Wall lattices

AU - Micciancio, Daniele

AU - Nicolosi, Antonio

PY - 2008

Y1 - 2008

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

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

UR - https://www.scopus.com/pages/publications/52349103414

UR - https://www.scopus.com/pages/publications/52349103414#tab=citedBy

U2 - 10.1109/ISIT.2008.4595438

DO - 10.1109/ISIT.2008.4595438

M3 - Conference contribution

AN - SCOPUS:52349103414

SN - 9781424422579

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2484

EP - 2488

BT - Proceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008

T2 - 2008 IEEE International Symposium on Information Theory, ISIT 2008

Y2 - 6 July 2008 through 11 July 2008

ER -

Efficient bounded distance decoders for Barnes-Wall lattices

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this