33 results sorted by ID
Lightweight Dynamic Linear Components for Symmetric Cryptography
S. M. Dehnavi, M. R. Mirzaee Shamsabad
Foundations
In this paper, using the concept of equivalence of mappings we characterize all of the one-XOR matrices which are used in hardware applications and propose a family of lightweight linear mappings for software-oriented applications in symmetric cryptography. Then, we investigate interleaved linear mappings and based upon this study, we present generalized dynamic primitive LFSRs along with dynamic linear components for construction of diffusion layers.
From the mathematical...
Few-weight linear codes over $\mathbb{F}_p$ from $t$-to-one mappings
René Rodríguez-Aldama
Foundations
For any prime number $p$, we provide two classes of linear codes with few weights over a $p$-ary alphabet. These codes are based on a well-known generic construction (the defining-set method), stemming on a class of monomials and a class of trinomials over finite fields. The considered monomials are Dembowski-Ostrom monomials $x^{p^{\alpha}+1}$, for a suitable choice of the exponent $\alpha$, so that, when $p>2$ and $n\not\equiv 0 \pmod{4}$, these monomials are planar. We study the...
NTRU+: Compact Construction of NTRU Using Simple Encoding Method
Jonghyun Kim, Jong Hwan Park
Public-key cryptography
NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes.
In...
Two new classes of permutation trinomials over $\mathbb{F}_{q^3}$ with odd characteristic
Xi Xie, Nian Li, Linjie Xu, Xiangyong Zeng, Xiaohu Tang
Let $q$ be an odd prime power and ${\mathbb F}_{q^3}$ be the finite field with $q^3$ elements.
In this paper, we propose two classes of permutation trinomials of ${\mathbb F}_{q^3}$ for an arbitrary odd characteristic based on the multivariate method and some subtle manipulation of solving equations with low degrees over finite fields. Moreover, we demonstrate that these two classes of permutation trinomials are QM inequivalent to all known permutation polynomials over ${\mathbb F}_{q^3}$....
An Efficient CRT-based Bit-parallel Multiplier for Special Pentanomials
Yin Li, Yu Zhang
Implementation
The Chinese remainder theorem (CRT)-based multiplier is a new type of hybrid bit-parallel multiplier, which can achieve nearly the same time complexity compared with the fastest multiplier known to date with reduced space complexity. However, the current CRT-based multipliers are only applicable to trinomials. In this paper, we propose an efficient CRT-based bit-parallel multiplier for a special type of pentanomial $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}+1, 5k<m\leq 7k$. Through transforming the...
Fast hybrid Karatsuba multiplier for Type II pentanomials
Yin Li, Yu Zhang, Wei He
Implementation
We continue the study of Mastrovito form of Karatsuba multipliers under the shifted polynomial basis (SPB), recently introduced by Li et al. (IEEE TC (2017)).
A Mastrovito-Karatsuba (MK) multiplier utilizes the Karatsuba algorithm (KA) to optimize polynomial multiplication and the Mastrovito approach to combine it with the modular reduction. The authors developed a MK multiplier for all trinomials, which obtain a better space and time trade-off compared with previous non-recursive Karatsuba...
A note on short invertible ring elements and applications to cyclotomic and trinomials number fields
Thomas Attema, Ronald Cramer, Chaoping Xing
Foundations
Ring-SIS based $\Sigma$-protocols require the construction of a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These protocols impose various requirements on the subset $\mathcal{C}$, and constructing a good or even optimal challenge set is a non-trivial task that involves making various trade-offs. </p>
In particular, the set $\mathcal{C}$ should be 'large', elements in $\mathcal{C}$ should be 'small', differences of distinct elements in $\mathcal{C}$...
On equivalence between known families of quadratic APN functions
Lylia Budaghyan, Marco Calderini, Irene Villa
Secret-key cryptography
We study a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are CCZ-equivalent to the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a...
On the Complexity of non-recursive $n$-term Karatsuba Multiplier for Trinomials
Yin Li, Shantanu Sharma, Yu Zhang, Xingpo Ma, Chuanda Qi
Implementation
The $n$-term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one.
In this contribution, we proposed a novel hybrid $GF(2^m)$ Karatsuba multiplier using $n$-term KA for irreducible trinomials of arbitrary degree, i.e., $x^m+x^k+1$ where $m\geq2k$.
We multiply two $m$-term polynomials using $n$-term KA, by decomposing $m$ into $n\ell+r$, such that $r<n, \ell$.
Combined with shifted polynomial basis (SPB), a new approach other...
N-term Karatsuba Algorithm and its Application to Multiplier designs for Special Trinomials
Yin Li, Yu Zhang, Xiaoli Guo, Chuanda Qi
Foundations
In this paper, we propose a new type of non-recursive Mastrovito multiplier for $GF(2^m)$ using a $n$-term Karatsuba algorithm (KA), where $GF(2^m)$ is defined by an irreducible trinomial, $x^m+x^k+1, m=nk$. We show that such a type of trinomial combined with the $n$-term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low complexity architecture. The optimal parameter $n$ is further studied.
As the main contribution of this...
Fast Montgomery-like Square Root Computation over $GF(2^m)$ for All Trinomials
Yin Li, Yu Zhang
Foundations
This letter is concerned with an extension of square root computation over $GF(2^m)$ defined by irreducible trinomials. We introduce a new type of Montgomery-like square root formulae, which is more efficient compared with classic square root operation. By choosing proper Montgomery factor regarding to different types of trinomials, the space and time complexities of our proposal outperform or match the best results. Furthermore, a practical application of the Montgomery-like square root in...
Some Results on the Known Classes of Quadratic APN Functions
Lilya Budaghyan, Tor Helleseth, Nian Li, Bo Sun
Foundations
In this paper, we determine the Walsh spectra of three classes of quadratic APN functions and we prove that the class of quadratic trinomial APN functions constructed by Gölo\u glu is affine equivalent to Gold functions.
Mastrovito Form of Non-recursive Karatsuba Multiplier for All Trinomials
Yin Li, Xingpo Ma, Yu Zhang, Chuanda Qi
We present a new type of bit-parallel non-recursive Karatsuba multiplier over $GF(2^m)$ generated by an arbitrary irreducible trinomial. This design effectively exploits Mastrovito approach and shifted polynomial basis (SPB) to reduce the time complexity and Karatsuba algorithm to reduce its space complexity.
We show that this type of multiplier is only one $T_X$ slower than the fastest bit-parallel multiplier for all trinomials, where $T_X$ is the delay of one 2-input XOR gate. Meanwhile,...
Koblitz curves over quadratic fields
Thomaz Oliveira, Julio López, Daniel Cervantes-Vázquez, Francisco Rodríguez-Henríquez
In this work, we retake an old idea that Koblitz presented in
his landmark paper, where he suggested the possibility of defining anomalous elliptic curves over the base field F4. We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over F4 that are equipped with efficient endomorphisms. To the best of our knowledge these...
CRITERION OF MAXIMAL PERIOD OF A TRINOMIAL OVER NONTRIVIAL GALOIS RING OF ODD CHARACTERISTIC
Vadim N. Tsypyschev, Julia S. Vinogradova
Secret-key cryptography
In earlier eighties of XX century A.A.Nechaev has obtained the criterion of full period of a Galois polynomial over primary residue ring modulo power of 2. Also he has obtained necessary conditions of maximal period of the Galois polynomial over such ring in terms of coefficients of this polynomial.
Further A.S.Kuzmin has obtained analogous results for the case of Galois polynomial over primary residue ring of odd characteristic .
Later the first author of this article has carried ...
Low Space Complexity CRT-based Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials
Jiajun Zhang, Haining Fan
By selecting the largest possible value of k∈(n/2,2n/3], we further reduce the AND and XOR gate complexities of the CRT-based hybrid parallel GF(2^n) polynomial basis multipliers for the irreducible trinomial f = u^n + u^k + 1 over GF(2): they are always less than those of the current fastest parallel multipliers – quadratic multipliers, i.e., n^2 AND gates and n^2-1 XOR gates. Our experimental results show that among the 539 values of n∈[5,999] such that f is irreducible for...
A Chinese Remainder Theorem Approach to Bit-Parallel GF(2^n) Polynomial Basis Multipliers for Irreducible Trinomials
Haining Fan
We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF(2^n) multiplication operation can be avoided. This leads to an alternative
representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel GF(2^n) multipliers for irreducible trinomials u^n + u^k + 1
on GF(2) where 1 < k ≤ n=2. For some values of n, our architectures have the same...
On the Primitivity of Trinomials over Small Finite Fields
YUjuan Li, Jinhua Zhao, Huaifu Wang
In this paper, we
explore the primitivity of trinomials over small finite fields. We
extend the results of the primitivity of trinomials $x^{n}+ax+b$
over ${\mathbb{F}}_{4}$ \cite{Li} to the general form
$x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials
$x^{n}+ax^{k}+b$ with $b$ being the primitive element of
${\mathbb{F}}_{4}$ and $a+b\neq1$ is primitive over
${\mathbb{F}}_{4}$ if and only if all the others are primitive over
${\mathbb{F}}_{4}$. And we can...
New bit-parallel Montgomery multiplier for trinomials using squaring operation
Yin Li, Yiyang Chen
In this paper, a new bit-parallel Montgomery multiplier for $GF(2^m)$ is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this approach and a carefully chosen Montgomery factor, the Montgomery multiplication can be transformed into a composition of small polynomial multiplications and Montgomery squarings, which are simpler and more efficient. Explicit...
A new class of hyper-bent functions and Kloosterman sums
Chunming Tang, Yanfeng Qi
This paper is devoted to the characterization of hyper-bent functions.
Several classes of hyper-bent functions have been studied, such as
Charpin and Gong's $\sum\limits_{r\in R}\mathrm{Tr}_{1}^{n}
(a_{r}x^{r(2^m-1)})$ and Mesnager's $\sum\limits_{r\in R}\mathrm{Tr}_{1}^{n}(a_{r}x^{r(2^m-1)})
+\mathrm{Tr}_{1}^{2}(bx^{\frac{2^n-1}{3}})$, where $R$ is a set of representations of the cyclotomic
cosets modulo $2^m+1$ of full size $n$ and $a_{r}\in \mathbb{F}_{2^m}$.
In this paper, we...
Toeplitz matrix-vector product based GF(2^n) shifted polynomial basis multipliers for all irreducible pentanomials
Jiangtao Han, Haining Fan
Foundations
Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix...
On the Primitivity of some Trinomials over Finite Fields
LI Yujuan, WANG Huaifu, ZHAO Jinhua
Secret-key cryptography
In this paper, we give
conditions under which the trinomials of the form $x^{n}+ax+b$ over
finite field ${\mathbb{F}}_{p^{m}}$ are not primitive and
conditions under which there are no primitive trinomials of the
form $x^{n}+ax+b$ over finite field ${\mathbb{F}}_{p^{m}}$. For
finite field ${\mathbb{F}}_{4}$, We show that there are no primitive
trinomials of the form $x^{n}+x+\alpha$, if $n\equiv1\mod 3$ or
$n\equiv0\mod 3$ or $n\equiv4\mod 5$.
Bit-Parallel $GF(2^{n})$ Squarer Using Shifted Polynomial Basis
Xi Xiong, Haining Fan
We present explicit formulae and complexities of bit-parallel shifted polynomial basis (SPB)
squarers in finite field $GF(2^{n})$s generated by general irreducible trinomials
$x^{n}+x^{k}+1$ ($0< k <n$) and type-II irreducible pentanomials
$x^{n}+x^{k+1}+x^{k}+x^{k-1}+1$ ($3<k<(n-3)/2$). The complexities of the proposed squarers
match or slightly outperform the previous best results.
These formulae can also be used to design polynomial basis Montgomery squarers without any...
2011/606
Last updated: 2011-12-08
$GF(2^{n})$ Subquadratic Polynomial Basis Multipliers for Some Irreducible Trinomials
Xi Xiong, Haining Fan
Foundations
The $GF(2^{n})$ multiplication operation in polynomial basis can be represented as a matrix-vector product form,
and the matrix is often called the Mastrovito matrix.
The Toeplitz matrix-vector product approach has been used to design subquadratic shifted polynomial basis multipliers.
In order to apply this approach to subquadratic polynomial basis multipliers,
this Mastrovito matrix should be transformed into a Toeplitz matrix.
In this paper, two transformation methods are proposed
for...
Low Complexity Cubing and Cube Root Computation over $\F_{3^m}$ in Polynomial Basis
Omran Ahmadi, Francisco Rodríguez-Henriquez
We present low complexity formulae for the computation
of cubing and cube root over $\F_{3^m}$ constructed using special classes of irreducible
trinomials, tetranomials and pentanomials.
We show that for all those special classes of polynomials, field cubing and field cube root operation
have the same computational complexity when implemented in hardware or software platforms.
As one of the main applications of these two field arithmetic operations lies in pairing-based
cryptography, we also...
Optimal Irreducible Polynomials for GF(2^m) Arithmetic
Michael Scott
Implementation
The irreducible polynomials recommended for use by multiple standards documents are in fact far from optimal on many platforms. Specifically they are suboptimal in terms of performance, for the
computation of field square roots and in the application of the ``almost inverse'' field inversion algorithm. In this paper we question the need for the standardisation of irreducible polynomials in the first place, and derive the ``best'' polynomials to use depending on the underlying processor...
Another Look at Square Roots and Traces (and Quadratic Equations) in Fields of Even Characteristic
Roberto Avanzi
We discuss irreducible polynomials that can be
used to speed up square root extraction in fields of characteristic two.
We call such polynomials \textit{square root friendly}.
The obvious applications are to point halving methods for elliptic curves
and divisor halving methods for hyperelliptic curves.
We note the existence of square root friendly trinomials of a given
degree when we already know that an irreducible trinomial of the same
degree exists, and formulate a conjecture on the...
Classes of Quadratic APN Trinomials and Hexanomials and Related Structures
Lilya Budaghyan, Claude Carlet
Secret-key cryptography
A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from $\mathbb{F}_{2^{2m}}$ to $\mathbb{F}_{2^{2m}}$. We check for $m=3$ that some of these functions are CCZ-inequivalent to power functions.
Low Complexity Bit-Parallel Square Root Computation over GF($2^m$) for all Trinomials
Francisco Rodríguez-Henríquez, Guillermo Morales-Luna, Julio López-Hernández
Foundations
In this contribution we introduce a low-complexity bit-parallel algorithm for computing square roots over binary extension fields. Our proposed method can be applied for any type of irreducible polynomials. We derive explicit formulae for the space and time complexities associated to the square root operator when working with binary extension fields generated using irreducible trinomials. We show that for those finite fields, it is possible to compute the square root of an arbitrary field...
Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials
Francisco Rodríguez-Henríquez, Guillermo Morales-Luna, Nazar A. Saqib, Nareli Cruz-Cortés
Foundations
In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF($2^m$). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, $P(X) = X^m + X^k + 1$, with $m$ and $k$ odd numbers and when implemented in hardware
platforms. Under these conditions, our...
A note on efficient computation of cube roots in characteristic 3
Paulo S. L. M. Barreto
The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.
Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic
Jean-Claude Bajard, Laurent Imbert, Graham A. Jullien
Implementation
We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a
subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$.
Using the Chinese Remainder Theorem, we represent the elements of
$\mathrm{GF}(2^k)$; i.e. the polynomials in
$\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder
modulo a set of $n$ pairwise prime trinomials,
$T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$.
Our algorithm is based on Montgomery's multiplication...
Redundant Trinomials for Finite Fields of Characteristic $2$
Christophe Doche
Implementation
In this paper we introduce a new way to represent elements of a finite field of
characteristic $2$.
We describe a new type of polynomial basis, called
{\it redundant trinomial basis}
and discuss how to implement it efficiently.
Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$
when no irreducible trinomial of degree $n$ exists.
Tests with {\tt NTL} show that
improvements for squaring and exponentiation are respectively
up to $45$\% and $25$\%.
More attention is given to...
In this paper, using the concept of equivalence of mappings we characterize all of the one-XOR matrices which are used in hardware applications and propose a family of lightweight linear mappings for software-oriented applications in symmetric cryptography. Then, we investigate interleaved linear mappings and based upon this study, we present generalized dynamic primitive LFSRs along with dynamic linear components for construction of diffusion layers. From the mathematical...
For any prime number $p$, we provide two classes of linear codes with few weights over a $p$-ary alphabet. These codes are based on a well-known generic construction (the defining-set method), stemming on a class of monomials and a class of trinomials over finite fields. The considered monomials are Dembowski-Ostrom monomials $x^{p^{\alpha}+1}$, for a suitable choice of the exponent $\alpha$, so that, when $p>2$ and $n\not\equiv 0 \pmod{4}$, these monomials are planar. We study the...
NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes. In...
Let $q$ be an odd prime power and ${\mathbb F}_{q^3}$ be the finite field with $q^3$ elements. In this paper, we propose two classes of permutation trinomials of ${\mathbb F}_{q^3}$ for an arbitrary odd characteristic based on the multivariate method and some subtle manipulation of solving equations with low degrees over finite fields. Moreover, we demonstrate that these two classes of permutation trinomials are QM inequivalent to all known permutation polynomials over ${\mathbb F}_{q^3}$....
The Chinese remainder theorem (CRT)-based multiplier is a new type of hybrid bit-parallel multiplier, which can achieve nearly the same time complexity compared with the fastest multiplier known to date with reduced space complexity. However, the current CRT-based multipliers are only applicable to trinomials. In this paper, we propose an efficient CRT-based bit-parallel multiplier for a special type of pentanomial $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}+1, 5k<m\leq 7k$. Through transforming the...
We continue the study of Mastrovito form of Karatsuba multipliers under the shifted polynomial basis (SPB), recently introduced by Li et al. (IEEE TC (2017)). A Mastrovito-Karatsuba (MK) multiplier utilizes the Karatsuba algorithm (KA) to optimize polynomial multiplication and the Mastrovito approach to combine it with the modular reduction. The authors developed a MK multiplier for all trinomials, which obtain a better space and time trade-off compared with previous non-recursive Karatsuba...
Ring-SIS based $\Sigma$-protocols require the construction of a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These protocols impose various requirements on the subset $\mathcal{C}$, and constructing a good or even optimal challenge set is a non-trivial task that involves making various trade-offs. </p> In particular, the set $\mathcal{C}$ should be 'large', elements in $\mathcal{C}$ should be 'small', differences of distinct elements in $\mathcal{C}$...
We study a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are CCZ-equivalent to the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a...
The $n$-term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. In this contribution, we proposed a novel hybrid $GF(2^m)$ Karatsuba multiplier using $n$-term KA for irreducible trinomials of arbitrary degree, i.e., $x^m+x^k+1$ where $m\geq2k$. We multiply two $m$-term polynomials using $n$-term KA, by decomposing $m$ into $n\ell+r$, such that $r<n, \ell$. Combined with shifted polynomial basis (SPB), a new approach other...
In this paper, we propose a new type of non-recursive Mastrovito multiplier for $GF(2^m)$ using a $n$-term Karatsuba algorithm (KA), where $GF(2^m)$ is defined by an irreducible trinomial, $x^m+x^k+1, m=nk$. We show that such a type of trinomial combined with the $n$-term KA can fully exploit the spatial correlation of entries in related Mastrovito product matrices and lead to a low complexity architecture. The optimal parameter $n$ is further studied. As the main contribution of this...
This letter is concerned with an extension of square root computation over $GF(2^m)$ defined by irreducible trinomials. We introduce a new type of Montgomery-like square root formulae, which is more efficient compared with classic square root operation. By choosing proper Montgomery factor regarding to different types of trinomials, the space and time complexities of our proposal outperform or match the best results. Furthermore, a practical application of the Montgomery-like square root in...
In this paper, we determine the Walsh spectra of three classes of quadratic APN functions and we prove that the class of quadratic trinomial APN functions constructed by Gölo\u glu is affine equivalent to Gold functions.
We present a new type of bit-parallel non-recursive Karatsuba multiplier over $GF(2^m)$ generated by an arbitrary irreducible trinomial. This design effectively exploits Mastrovito approach and shifted polynomial basis (SPB) to reduce the time complexity and Karatsuba algorithm to reduce its space complexity. We show that this type of multiplier is only one $T_X$ slower than the fastest bit-parallel multiplier for all trinomials, where $T_X$ is the delay of one 2-input XOR gate. Meanwhile,...
In this work, we retake an old idea that Koblitz presented in his landmark paper, where he suggested the possibility of defining anomalous elliptic curves over the base field F4. We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over F4 that are equipped with efficient endomorphisms. To the best of our knowledge these...
In earlier eighties of XX century A.A.Nechaev has obtained the criterion of full period of a Galois polynomial over primary residue ring modulo power of 2. Also he has obtained necessary conditions of maximal period of the Galois polynomial over such ring in terms of coefficients of this polynomial. Further A.S.Kuzmin has obtained analogous results for the case of Galois polynomial over primary residue ring of odd characteristic . Later the first author of this article has carried ...
By selecting the largest possible value of k∈(n/2,2n/3], we further reduce the AND and XOR gate complexities of the CRT-based hybrid parallel GF(2^n) polynomial basis multipliers for the irreducible trinomial f = u^n + u^k + 1 over GF(2): they are always less than those of the current fastest parallel multipliers – quadratic multipliers, i.e., n^2 AND gates and n^2-1 XOR gates. Our experimental results show that among the 539 values of n∈[5,999] such that f is irreducible for...
We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF(2^n) multiplication operation can be avoided. This leads to an alternative representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel GF(2^n) multipliers for irreducible trinomials u^n + u^k + 1 on GF(2) where 1 < k ≤ n=2. For some values of n, our architectures have the same...
In this paper, we explore the primitivity of trinomials over small finite fields. We extend the results of the primitivity of trinomials $x^{n}+ax+b$ over ${\mathbb{F}}_{4}$ \cite{Li} to the general form $x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials $x^{n}+ax^{k}+b$ with $b$ being the primitive element of ${\mathbb{F}}_{4}$ and $a+b\neq1$ is primitive over ${\mathbb{F}}_{4}$ if and only if all the others are primitive over ${\mathbb{F}}_{4}$. And we can...
In this paper, a new bit-parallel Montgomery multiplier for $GF(2^m)$ is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this approach and a carefully chosen Montgomery factor, the Montgomery multiplication can be transformed into a composition of small polynomial multiplications and Montgomery squarings, which are simpler and more efficient. Explicit...
This paper is devoted to the characterization of hyper-bent functions. Several classes of hyper-bent functions have been studied, such as Charpin and Gong's $\sum\limits_{r\in R}\mathrm{Tr}_{1}^{n} (a_{r}x^{r(2^m-1)})$ and Mesnager's $\sum\limits_{r\in R}\mathrm{Tr}_{1}^{n}(a_{r}x^{r(2^m-1)}) +\mathrm{Tr}_{1}^{2}(bx^{\frac{2^n-1}{3}})$, where $R$ is a set of representations of the cyclotomic cosets modulo $2^m+1$ of full size $n$ and $a_{r}\in \mathbb{F}_{2^m}$. In this paper, we...
Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix...
In this paper, we give conditions under which the trinomials of the form $x^{n}+ax+b$ over finite field ${\mathbb{F}}_{p^{m}}$ are not primitive and conditions under which there are no primitive trinomials of the form $x^{n}+ax+b$ over finite field ${\mathbb{F}}_{p^{m}}$. For finite field ${\mathbb{F}}_{4}$, We show that there are no primitive trinomials of the form $x^{n}+x+\alpha$, if $n\equiv1\mod 3$ or $n\equiv0\mod 3$ or $n\equiv4\mod 5$.
We present explicit formulae and complexities of bit-parallel shifted polynomial basis (SPB) squarers in finite field $GF(2^{n})$s generated by general irreducible trinomials $x^{n}+x^{k}+1$ ($0< k <n$) and type-II irreducible pentanomials $x^{n}+x^{k+1}+x^{k}+x^{k-1}+1$ ($3<k<(n-3)/2$). The complexities of the proposed squarers match or slightly outperform the previous best results. These formulae can also be used to design polynomial basis Montgomery squarers without any...
The $GF(2^{n})$ multiplication operation in polynomial basis can be represented as a matrix-vector product form, and the matrix is often called the Mastrovito matrix. The Toeplitz matrix-vector product approach has been used to design subquadratic shifted polynomial basis multipliers. In order to apply this approach to subquadratic polynomial basis multipliers, this Mastrovito matrix should be transformed into a Toeplitz matrix. In this paper, two transformation methods are proposed for...
We present low complexity formulae for the computation of cubing and cube root over $\F_{3^m}$ constructed using special classes of irreducible trinomials, tetranomials and pentanomials. We show that for all those special classes of polynomials, field cubing and field cube root operation have the same computational complexity when implemented in hardware or software platforms. As one of the main applications of these two field arithmetic operations lies in pairing-based cryptography, we also...
The irreducible polynomials recommended for use by multiple standards documents are in fact far from optimal on many platforms. Specifically they are suboptimal in terms of performance, for the computation of field square roots and in the application of the ``almost inverse'' field inversion algorithm. In this paper we question the need for the standardisation of irreducible polynomials in the first place, and derive the ``best'' polynomials to use depending on the underlying processor...
We discuss irreducible polynomials that can be used to speed up square root extraction in fields of characteristic two. We call such polynomials \textit{square root friendly}. The obvious applications are to point halving methods for elliptic curves and divisor halving methods for hyperelliptic curves. We note the existence of square root friendly trinomials of a given degree when we already know that an irreducible trinomial of the same degree exists, and formulate a conjecture on the...
A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from $\mathbb{F}_{2^{2m}}$ to $\mathbb{F}_{2^{2m}}$. We check for $m=3$ that some of these functions are CCZ-inequivalent to power functions.
In this contribution we introduce a low-complexity bit-parallel algorithm for computing square roots over binary extension fields. Our proposed method can be applied for any type of irreducible polynomials. We derive explicit formulae for the space and time complexities associated to the square root operator when working with binary extension fields generated using irreducible trinomials. We show that for those finite fields, it is possible to compute the square root of an arbitrary field...
In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF($2^m$). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, $P(X) = X^m + X^k + 1$, with $m$ and $k$ odd numbers and when implemented in hardware platforms. Under these conditions, our...
The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.
We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$. Using the Chinese Remainder Theorem, we represent the elements of $\mathrm{GF}(2^k)$; i.e. the polynomials in $\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder modulo a set of $n$ pairwise prime trinomials, $T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$. Our algorithm is based on Montgomery's multiplication...
In this paper we introduce a new way to represent elements of a finite field of characteristic $2$. We describe a new type of polynomial basis, called {\it redundant trinomial basis} and discuss how to implement it efficiently. Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$ when no irreducible trinomial of degree $n$ exists. Tests with {\tt NTL} show that improvements for squaring and exponentiation are respectively up to $45$\% and $25$\%. More attention is given to...