Paper 2011/556

GF(2^n) redundant representation using matrix embedding

Yongjia Wang, Xi Xiong, and Haining Fan

Abstract

By embedding a Toeplitz matrix-vector product (MVP) of dimension n into a circulant MVP of dimension N=2n+δ1, where δ can be any nonnegative integer, we present a GF(2n) multiplication algorithm. This algorithm leads to a new redundant representation, and it has two merits: 1. The flexible choices of δ make it possible to select a proper N such that the multiplication operation in ring GF(2)[x]/(xN+1) can be performed using some asymptotically faster algorithms, e.g. the Fast Fourier Transformation (FFT)-based multiplication algorithm; 2. The redundant degrees, which are defined as N/n, are smaller than those of most previous GF(2n) redundant representations, and in fact they are approximately equal to 2 for all applicable cases.

Note: We move the result in the work of IACR eprint 2011/606 (Xi Xiong and Haining Fan) into this work, see Section VI.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.not published
Keywords
Finite fieldsredundant representationmatrix-vector productshifted polynomial basisFFT.
Contact author(s)
fhn @ tsinghua edu cn
History
2014-09-30: revised
2011-10-11: received
See all versions
Short URL
https://ia.cr/2011/556
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/556,
      author = {Yongjia Wang and Xi Xiong and Haining Fan},
      title = {{GF}(2^n) redundant representation using matrix embedding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/556},
      year = {2011},
      url = {https://eprint.iacr.org/2011/556}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.