Subquadratic space complexity Gaussian normal basis multipliers over GF(2m) based on Dickson–Karatsuba decomposition

Gaussian normal basis (GNB) of the even-type is popularly used in elliptic curve cryptosystems. Efficient GNB multipliers could be realised by Toeplitz matrix-vector decomposition to realise subquadratic space complexity architectures. In this study, Dickson polynomial representation is proposed as...

Full description

Saved in:
Bibliographic Details
Published in:IET circuits, devices & systems devices & systems, 2015-09, Vol.9 (5), p.336-342
Main Authors: Pan, Jeng-Shyang, Lee, Chiou-Yng, Li, Yao
Format: Article
Language:English
Subjects:
Algorithms
bit-multiplications
Complexity
computational complexity
Computer systems
Curves
Decomposition
Dickson polynomial representation
Digital signatures
elliptic curve cryptosystems
even-type
Gaussian normal basis multipliers
Gaussian processes
Matrices (mathematics)
matrix decomposition
Multipliers
parallel GNB multiplier
Polynomials
public key cryptography
recursive Dickson-Karatsuba decomposition
recursive estimation
subquadratic space complexity architectures
Toeplitz matrices
Toeplitz matrix-vector decomposition
vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Gaussian normal basis (GNB) of the even-type is popularly used in elliptic curve cryptosystems. Efficient GNB multipliers could be realised by Toeplitz matrix-vector decomposition to realise subquadratic space complexity architectures. In this study, Dickson polynomial representation is proposed as an alternative way to represent an GNB of characteristic two. The authors have derived a novel recursive Dickson–Karatsuba decomposition to achieve a subquadratic space-complexity parallel GNB multiplier. By theoretical analysis, it is shown that the proposed subquadratic multiplier saves about 50% bit-multiplications compared with the corresponding subquadratic GNB multiplication using Toeplitz matrix-vector product approach.
ISSN:1751-858X
1751-8598
1751-8598
DOI:10.1049/iet-cds.2014.0276