Brakedown's expander code

Ulrich Haböck

Paper 2023/769

Brakedown's expander code

Ulrich Haböck

, Polygon Labs

Abstract

This write-up summarizes the sampling analysis of the expander code from Brakedown [GLSTW21]. We elaborate their convexity argument for general linear expansion bounds, and we combine their approach with the one from Spielman [Sp96] to achieve asymptotic linear-time under constant field size. Choosing tighter expansion bounds we obtain more efficient parameters than [GLSTW21] for their 128 bit large field, reducing the encoding costs by 25% and beyond, and we provide a similar parameter set for the Mersenne prime field with modulus $p = 2^{31} - 1$, optimized by the combined Spielman-Brakedown approach.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: Linear Codes Expander Codes
Contact author(s): ulrich haboeck @ gmail com
History: 2023-05-30: approved; 2023-05-26: received; See all versions
Short URL: https://ia.cr/2023/769
License: CC BY-SA

BibTeX

@misc{cryptoeprint:2023/769,
      author = {Ulrich Haböck},
      title = {Brakedown's expander code},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/769},
      year = {2023},
      url = {https://eprint.iacr.org/2023/769}
}