Paper 2011/556 Original: eprint.iacr.org/2011/556 ↗
GF(2^n) redundant representation using matrix embedding
Abstract
By embedding a Toeplitz matrix-vector product (MVP) of dimension $n$ into a circulant MVP of dimension $N=2n+\delta -1$, where $\delta $ can be any nonnegative integer, we present a $GF(2^n)$ multiplication algorithm. This algorithm leads to a new redundant representation, and it has two merits: 1. The flexible choices of $\delta$ make it possible to select a proper $N$ such that the multiplication operation in ring $GF(2)[x]/(x^N+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(2^n)$ redundant representations, and in fact they are approximately equal to 2 for all applicable cases.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2014-09-30: last updated
- 2011-10-11: published
- Short URL
- https://ia.cr/2011/556
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}