Search

In this paper, we presented a method of minimizing the number of overlapped partial products in the accumulation of four-term Karatsuba multiplication. This method reduced the summation of 13 overlapped partial products to 9 and the summation of 40 overlapped partial products to 24 in the case of four-term Karatsuba multiplication and eight-term Karatsuba multiplication, respectively. Moreover, to deal with the problem of negative multiplicands introduced by the choice in the evaluation of four-term Karatsuba multiplication, we further presented a method of converting negative multiplicands to non-negative multiplicands. In this way, our method would lead to the reduction of summation complexity and not using signed multipliers. Compared to the original Karatsuba multiplication designs, our proposed Karatsuba-like multiplication with optimal interpolation would lead to up to 7.7% reduction in ADP (area-delay-product) in ASIC implementations, and up to 20.2% reduction in ADP compared with built-in designs of Synopsys Design Compiler.

In this brief, we proposed a highly-optimized FPGA-based implementation of the Ed448 digital signature algorithm. Despite significant progress in elliptic curve cryptography (ECC) implementations, Ed448 hardware architecture, to the best of our knowledge, has not been investigated in the literature. In this work, we demonstrate a high throughput while maintaining low resource architecture for Ed448 by employing a new combined algorithm for refined Karatsuba-based multiplier with precise scheduling. Furthermore, a compact distributed memory unit is developed to increase speed while keeping the area low. Our variable-base-point Ed448 architecture performs 327 signatures and 189 verifications per second at a notably higher security level of 224 bits, using not more than 6,617 Slices and 16 DSPs on a Xilinx Artix-7 FPGA. We also proposed possible countermeasures and extensions to Ed448 to counter the physical attacks.

Lattice-based cryptography (LBC) is one of the promising post-quantum candidates which offers good security and performance. The most time consuming operations in LBC is the polynomial multiplication, which can be performed through widely explored algorithms like schoolbook polynomial multiplication algorithm (SPMA) and Number Theoretic Transform (NTT). However, Karatsuba algorithm with better complexity compared to SPMA, is not widely studied for FPGA implementation of LBC. In this brief, we proposed an optimized SPMA-Karatsuba (SK) architecture with novel technique to implement the negacyclic convolution. The proposed architecture is more than $2.09\times $ faster in expense of 96.06% additional hardware resources compared to the state-of-the-art SPMA architecture. This shows that the combination of SPMA and Karatsuba algorithm can produce hardware architecture with higher speed yet maintain balanced area-time efficiency compared to SPMA-only architecture. This is especially useful for developing IoT edge nodes or gateway devices that require high speed but able to tolerate some additional hardware area.

Cryptography systems have become inseparable parts of almost every communication device. Among cryptography algorithms, public-key cryptography, and in particular elliptic curve cryptography (ECC), has become the most dominant protocol at this time. In ECC systems, polynomial multiplication is considered to be the most slow and area consuming operation. This article proposes a novel hardware architecture for efficient field-programmable gate array (FPGA) implementation of Finite-field multipliers for ECC. Proposed hardware was implemented on different FPGA devices for various operand sizes, and performance parameters were determined. Comparing to state-of-the-art works, the proposed method resulted in a lower combinational delay and area–delay product indicating the efficiency of design.

Saber, the only module-learning with rounding-based algorithm in NIST’s third round of post-quantum cryptography (PQC) standardization process, is characterized by simplicity and flexibility. However, energy-efficient implementation of Saber is still under investigation since the commonly used number theoretic transform can not be utilized directly. In this manuscript, an energy-efficient configurable crypto-processor supporting multi-security-level key encapsulation mechanism of Saber, is proposed. First, an 8-level hierarchical Karatsuba framework is utilized to reduce degree-256 polynomial multiplication to the coefficient-wise multiplication. Second, a hardware-efficient Karatsuba scheduling strategy and an optimized pre-/post-processing structure is designed to reduce the area overheads of scheduling strategy. Third, a task-rescheduling-based pipeline strategy and truncated multipliers are proposed to enable fine-grained processing. Moreover, multiple parameter sets are supported in LWRpro to enable configurability among various security scenarios. Enabled by these optimizations, LWRpro requires 1066, 1456 and 1701 clock cycles for key generation, encapsulation, and decapsulation of Saber768. The post-layout version of LWRpro is implemented with TSMC 40 nm CMOS process within 0.38 mm2. The throughput for Saber768 is up to 275k encapsulation operations per second and the energy efficiency is 0.15 uJ/encapsulation while operating at 400 MHz, achieving nearly $50\times $ improvement and $31\times $ improvement, respectively compared with current PQC hardware solutions.

High-performance Elliptic Curve Cryptography (ECC) implementation in encryption authentication severs has become a challenge due to the explosive growth of e-commerce's demand for speed and security. Point multiplication (PM) is the most common and complex operation in ECC which directly determines the performance of the whole system. This article proposes a 6CC-6CC (clock cycle) dual-field PM architecture and a 6CC-4CC dual-field PM architecture based on maximizing utilization of Karatsuba multipliers and re-ordering schedule strategy in PM. The Montgomery Ladder algorithm used in PM is modified to a 4CC algorithm for better resource utilization and parallel computation. To solve the frequency drop problem while working on large finite field, the PM architectures for high and low field are carefully studied to have universal critical path length and balanced performance. Both of the architectures are implemented over GF(2571) and GF(2283) on Xilinx Virtex-5 and Virtex-7 FPGAs (Field-Programmable Gate Array) for comparison. The 6CC-6CC architecture is shown to have the best performance on GF(2571), which achieves one PM operation in $17.44~\mu s$ using 81549 LUTs (Look-Up-Table) with the frequency of 197.2 MHz on Virtex-5, and $12.55~\mu s$ using 80970 LUTs with the frequency of 274.1 MHz on Virtex-7. The 6CC-4CC architecture performs better on GF(2283) with the shortest computation time. It takes only $3.21~\mu s$ to finish one PM operation on Virtex-5 and $2.22~\mu s$ on Virtex-7, which are faster than all the previous designs. The implementation results prove that the proposed architectures have state-of-the-art performance as well as higher versatility for ECC designs.

We continue the study of Mastrovito form of Karatsuba (MK) multipliers under the shifted polynomial basis (SPB). An MK multiplier utilizes Karatsuba algorithm and Mastrovito approach to optimize polynomial multiplication and modular reduction, which lead to a better space and time tradeoff for all trinomials. Based on this work, we make two types of contributions: 1) We derive a new modular reduction formulation for constructing Mastrovito matrix associated with special types of pentanomials, i.e., Types I, II, and Type C.1 pentanomial. Through related formulations, we demonstrate that Type I pentanomial is less efficient than Type II because of a more complicated modular reduction under the same SPB; conversely, Type C.1 pentanomial is as good as Type II under generalized polynomial basis (GPB). 2) We introduce a new MK multiplier for Type II pentanomial. It is shown that our proposal is only one $T_{X}$ slower than the fastest quadratic multipliers for Type II pentanomial, but its space complexity is roughly 3/4 of those schemes. To the best of our knowledge, it is the first time for hybrid multiplier to achieve such a time delay bound.

In this brief, a non-least positive form (NLP) based modular multiplication method that combines Karatsuba and schoolbook multiplication is applied in Montgomery modular multiplication, which saves 2 base multiplications compared to Karatsuba-only designs and allows pipeline structure to make most use of the parallelism in large modular multiplications. Based on this method, 256-bit and 512-bit modular multipliers are constructed with 3-way and 4-way NLP multipliers on FPGA platform. Implemented on Virtex-6, the 256-bit design can perform a modular multiplication in 62.6 ns and only requires 3.5K LUTs and 24 DSPs, which exhibits low-latency and low-cost among previous works.

The ${n}$ -term Karatsuba algorithm (KA) is an extension of 2-term KA, which can obtain even fewer multiplications than the original one. The existing ${n}$ -term Karatsuba hybrid $\textit {GF}(2^{m})$ multipliers rely on factorization of ${m}$ or ${m}-1$ , so that put a confinement to these schemes. In this contribution, we use a new decomposition ${m}={n}\ell +{r}$ , such that $0\leq {r} and $0\leq {r} , and propose a novel ${n}$ -term Karatsuba hybrid $\textit {GF}(2^{m})$ multiplier for an arbitrary irreducible trinomial ${x}^{m}+{x}^{k}+1, {m}\geq 2{k}$ . Combined with shifted polynomial basis, a new approach (other than Mastrovito approach) is introduced to exploit the spatial correlations among different subexpressions. We investigate the explicit space and time complexities, and discuss related upper and lower bounds. As a main contribution, the flexibilities of ${n}, \ell $ and ${r}$ make our proposal approaching optimal for any given ${m}$ . The space complexity can achieve to ${m^{2}}/{2}+{O}({\sqrt {11} {m}^{3/2}}/{2})$ , which roughly matches the best result of current hybrid multipliers for special trinomials. Meanwhile, its time complexity is slightly higher than the counterparts, but can be improved for a new class of trinomials. In particular, we demonstrate that the hybrid multiplier for ${x}^{m}+{x}^{k}+1$ , where ${k}$ is approaching $\frac {m}{2}$ , can achieve a better space-time trade-off than any other trinomials.

Toom–Cook multiplication is a theoretically more efficient multiplication algorithm than traditionally used Karatsuba and schoolbook multiplication but is rarely used in practical hardware designs due to its inherent exact divisions, which are time-consuming and difficult for parallel and serial acceleration. This brief proposes a method of division-free Toom–Cook multiplication based Montgomery modular multiplication, which makes it possible for Toom–Cook multiplication to be applied in practical and efficient hardware implementations. We also provide a hardware implementation of modular multipliers of 256 bits and 1024 bits with advantages on area-time-product over previous researches.

We propose bit-parallel GF(2 m ) multipliers for irreducible trinomials using an n-term Karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2 m ) depend on the choice of an irreducible trinomial x m + x k + 1 defining GF(2 m ) and values n, m 0 such that m = nm 0 or m = nm 0 + 1. It is possible to achieve a space-time tradeoff by choosing proper values for k, n, and m 0 . For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m ∈ [399, 450] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T X higher than the fastest multipliers, where T X is the delay of one 2-input XOR gate.

Overlap-Free Karatsuba Algorithm (OFKA) combined with block recombination approach (OFKABR) can improve the complexity of the original OFKA to obtain efficient implementation of polynomial basis multiplication over finite field $GF(2^{m})$ . In this paper, we have further proposed a modified OFKABR (MOFKABR) strategy to reduce the space and time complexities of the best-known method. The proposed strategy is also extended to obtain a low-complexity versatile multiplier, which is designed to support the generalized multiplication on a wider range of field size for $m_{1}\leq m\leq m_{\lambda }$ . Using the proposed MOFKABR approach, the proposed digit-serial versatile multiplier can achieve subquadratic space complexity when compared with the existing digit-serial versatile multipliers.

Digit-serial systolic multipliers over $GF(2^m)$ based on the National Institute of Standards and Technology (NIST) recommended trinomials play a critical role in the real-time operations of cryptosystems. Systolic multipliers over $GF(2^m)$ involve a large number of registers of size $O(m^2)$ which results in significant increase in area complexity. In this paper, we propose a novel low register-complexity digit-serial trinomial-based finite field multiplier. The proposed architecture is derived through two novel coherent interdependent stages: (i) derivation of an efficient hardware-oriented algorithm based on a novel input-operand feeding scheme and (ii) appropriate design of novel low register-complexity systolic structure based on the proposed algorithm. The extension of the proposed design to Karatsuba algorithm (KA)-based structure is also presented. The proposed design is synthesized for FPGA implementation and it is shown that it (the design based on regular multiplication process) could achieve more than 12.1 percent saving in area-delay product and nearly 2.8 percent saving in power-delay product. To the best of the authors’ knowledge, the register-complexity of proposed structure is so far the least among the competing designs for trinomial based systolic multipliers (for the same type of multiplication algorithm).

In this paper, we propose a new type of non-recursive Mastrovito multiplier for $\text {GF}(2^{m})$ using an $n$ -term Karatsuba algorithm (KA), where $\text {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 paper, the lower bound of the space complexity of our proposal is about $O({m^{2}}/{2})+m^{3/2})$ . Meanwhile, the time complexity matches the best Karatsuba multiplier known to date. To the best of our knowledge, it is the first time that Karatsuba-based multiplier has reached such a space complexity bound while maintaining a relatively low time delay.

This paper presents an efficient implementation of elliptic curve cryptography (ECC) over the National Institute of Standards and Technology (NIST) K-233 curve for 8-bit AVR microcontrollers commonly used for sensor nodes in wireless sensor networks. Until now, several ECC implementations over NIST-compliant curves have been presented on 8-bit sensor nodes. However, most of them do not provide 112-bit security level currently recommended by NIST. Although some works provide more than 112-bit security level, their performance needs to be improved in order to be executed properly on resource-constrained sensor nodes. For optimizing the performance of ECC, we focus on the efficiency of field arithmetics and propose several optimization techniques. First, we present a novel polynomial multiplication technique based on multiplier encoding. The proposed method significantly reduces the required number of registers for a multiplier, which allows the larger block size for the Karatsuba Block-Comb method. The proposed method provides around 17.05% of improvement compared with the best result previously presented. Second, we optimize modular squaring and reduction algorithms considering the features of 8-bit AVR, and each of them provides around 21.86% and 3.7% improvements compared with the related works. With proposed methods, we present two versions of ECC implementation: (highly fast) $HF$ and (highly secure) $HS$ over NIST K-233 curve on an 8-bit ATmega128. Especially, $HF$ version outperforms the best result previously implemented on the same curve by 18.6% and 34.5% for a variable and a fixed-based scalar multiplication, respectively. Furthermore, on the 8-bit AVR platform, our ECC implementation shows the best performance compared with other existing implementations over both NIST-standardized prime or binary curves.

Three-operation multiplication (TOM) over binary extension field is frequently encountered in cryptosystems such as elliptic curve cryptography. Though digit-serial polynomial basis multipliers are usually preferred for the realization of TOM due to their efficient tradeoff in implementation complexity, the Karatsuba algorithm (KA)-based strategy is rarely employed to reduce the complexity further. Based on this reason, in this paper, we derive a novel low-complexity implementation of TOM based on a new KA-based digit-serial multiplier. The proposed TOM is obtained through two novel coherent interdependent efforts: 1) mapping an efficient KA-based algorithm into a novel digit-serial multiplier and 2) obtaining a new TOM structure through the novel derivation of the TOM algorithm. From the estimated results, it is shown that the proposed structure has significant lower area-time-complexities when compared with the existing competing TOMs. The proposed TOM is highly regular with low-complexity, and hence can be employed in many cryptographic applications.

Recent studies on the performance of private set operations have examined the use of homomorphic public-key encryption and the technique of representing sets as polynomials in a cryptographic model. These polynomial-based solutions require intensive polynomial arithmetic that exhibit quadratic computational complexity. In an effort to develop practical algorithms for private set operations, various well-known techniques such as Karatsuba’s algorithm or the fast Fourier transform (FFT) can be used to reduce the complexity of polynomial computations. The FFT appears to be the obvious best choice; however, the use of FFTs in the implementation of polynomial-based set operations may lead to certain subtle technical problems. These problems become particularly serious when the cardinality of the sets is dynamic. Furthermore, our experiment shows that Karatsuba’s algorithm delivers higher performance than the FFT in our application, provided that a reasonable response time is important. In addition, our experimental implementation demonstrates the heuristic bound on cardinality for which Karatsuba’s algorithm outperforms the FFT. This value can be used to determine the superior optimization techniques and settings in the deployment of private set operation schemes.

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, its space complexity is roughly 3/4 of those multipliers. To the best of our knowledge, it is the first time that our scheme has reached such a time delay bound. This result outperforms previously proposed non-recursive Karatsuba multipliers.

Multipliers requiring large bit lengths have a major impact on the performance of many applications, such as cryptography, digital signal processing (DSP) and image processing. Novel, optimised designs of large integer multiplication are needed as previous approaches, such as schoolbook multiplication, may not be as feasible due to the large parameter sizes. Parameter bit lengths of up to millions of bits are required for use in cryptography, such as in lattice-based and fully homomorphic encryption (FHE) schemes. This paper presents a comparison of hardware architectures for large integer multiplication. Several multiplication methods and combinations thereof are analysed for suitability in hardware designs, targeting the FPGA platform. In particular, the first hardware architecture combining Karatsuba and Comba multiplication is proposed. Moreover, a hardware complexity analysis is conducted to give results independent of any particular FPGA platform. It is shown that hardware designs of combination multipliers, at a cost of additional hardware resource usage, can offer lower latency compared to individual multiplier designs. Indeed, the proposed novel combination hardware design of the Karatsuba-Comba multiplier offers lowest latency for integers greater than 512 bits. For large multiplicands, greater than 16,384 bits, the hardware complexity analysis indicates that the NTT-Karatsuba-Schoolbook combination is most suitable.

Systolic implementation of Karatsuba algo- rithm (KA)-based digit-serial multiplier over $GF(2^{m})$ on field- programmable gate array (FPGA) platforms has many attractive features, such as efficient tradeoff in area-time complexity and high-throughput rate. But on the other side, it suffers from high register-complexity, which leads to increase in area and power consumption. In this paper, we present an algorithm and architecture for efficient FPGA implementation of KA-based digit-serial systolic multiplier over $GF(2^{m})$ based on the National Institute of Standards and Technology (NIST) recommended polynomials. A number of efficient techniques have been explored and used to realize efficient implementation of these multipliers. First, we propose a novel KA-based approach, where the computational complexity is significantly reduced compared with the existing one. Second, we propose efficient register minimization techniques, such as redundant register removal, two-stage pipelining, and register sharing to reduce the register complexity of the proposed structure. Third, we adopt an efficient FPGA-specific digit-parallel implementation strategy to optimize the area-time–power complexities of the proposed structure on FPGA platforms. The results obtained from FPGA synthesis indicate that the proposed multiplier (for field based on NIST trinomial $GF(2^{233})$ ) has significantly lower area–time–power complexities than the existing designs, e.g., the proposed structure could achieve 65.7% and 73.6% reduction on area-delay product and power-delay product over the best of existing KA-based systolic structures, respectively.

In the literature, the generalized $(a, b)$ - way Karatsuba algorithm (KA) is a well-known high-precision technique for implementing a subquadratic digit-serial multiplication. We present here the corrections to the space and complexities pertaining to addition operations in $(a, b)$ -way KA approach.

In this paper, we introduce a highly optimized software implementation of standards-compliant elliptic curve cryptography (ECC) for wireless sensor nodes equipped with an 8-bit AVR microcontroller. We exploit the state-of-the-art optimizations and propose novel techniques to further push the performance envelope of a scalar multiplication on the NIST P-192 curve. To illustrate the performance of our ECC software, we develope the prototype implementations of different cryptographic schemes for securing communication in a wireless sensor network, including elliptic curve Diffie–Hellman (ECDH) key exchange, the elliptic curve digital signature algorithm (ECDSA), and the elliptic curve Menezes–Qu–Vanstone (ECMQV) protocol. We obtain record-setting execution times for fixed-base, point variable-base, and double-base scalar multiplication. Compared with the related work, our ECDH key exchange achieves a performance gain of roughly 27% over the best previously published result using the NIST P-192 curve on the same platform, while our ECDSA performs twice as fast as the ECDSA implementation of the well-known TinyECC library. We also evaluate the impact of Karatsuba’s multiplication technique on the overall execution time of a scalar multiplication. In addition to offering high performance, our implementation of scalar multiplication has a highly regular execution profile, which helps to protect against certain side-channel attacks. Our results show that NIST-compliant ECC can be implemented efficiently enough to be suitable for resource-constrained sensor nodes.

It is well-known that the $(a,b)$ -way Karatsuba algorithm (KA) with $a\neq b$ is used for efficient digit-serial multiplication with subquadratic space complexity architecture. In this paper, based on $(a,b)$ -way KA decomposition, we have derived a novel $k$ -way block recombination KA (BRKA) decomposition for digit-serial multiplication. The proposed $k$ -way BRKA is formed by a power of 2 polynomial decomposition. By theoretical analysis, it is shown that $k$ -way BRKA can provide the necessary tradeoff between space and time complexity. Using (4,2)-way KA to construct the proposed $k$ -way BRKA architecture in $GF(2^{409})$ , it is shown that the proposed 2-way BRKA approach requires less area, and the proposed 8-way BRKA approach requires less computation time and less area-time product compared to compared the existing $(a,b)$ -way KA decomposition.

The WG stream ciphers are based on the WG (Welch-Gong) transformation and possess proved randomness properties. In this paper we propose nine new hardware designs for the two classes of WG(29,11) and WG-16. For each class, we design and implement three versions of standard, pipelined and serial. For the first time, we use the polynomial basis (PB) representation to design and implement the WG(29,11) and WG-16. We consider traditional PB multiplier for the WG(29,11), and, the traditional and Karatsuba multipliers for the WG-16. For efficient field operations, we propose an irreducible trinomial for the WG(29,11). For the WG-16, a new formulation of its permutation which requires only 8 multipliers is introduced. In these designs, the multipliers in the transforms arefurther reduced by utilizing a novel computation for the trace of the multiplication of two field elements. We have implemented theproposed designs in ASIC using CMOS 65 nm technology. The results show that the proposed standard WG(29,11) consumes less area and slightly enhances the normalized throughput, compared to the existing counterparts. For the WG-16, throughput of theproposed pipelined instance outperforms the previous designs. Moreover, the speed of the proposed WG-16 designs meet the peak bit rates for the 4 G specifications.

Subquadratic multiplication algorithm has received significant attention of cryptographic hardware researchers for efficient implementation public-key cryptosystems. In this paper, we derive a new shifted MPB (SMPB) representation based on modified polynomial basis (MPB). We have shown that by using MPB and SMPB, the proposed double basis multiplication can be transformed into Toeplitz matrix-vector product (TMVP) structure. Furthermore, by employing this formulation of double basis multiplication, we show that three-operand multiplication over GF(2 m ) for all trinomials can be realized efficiently by the recursive TMVP (RTMVP) formulation. To perform the three-operand multiplication with the RTMVP formulation, we have derived a new RTMVP decomposition scheme. The proposed single- and double-multiplications can, respectively, use TMVP and RTMVP decompositions to achieve subquadratic space complexity architectures. By theoretical analysis, it is shown that the proposed subquadratic multipliers involve significantly less space complexity and less computation time compared to the existing subquadratic multipliers using TMVP and Karatsuba algorithms. Moreover, our proposed double-multiplication design can be used in several applications involving successive multiplications, such as exponentiation, inversion, and elliptic curve point multiplication.

Karatsuba algorithm (KA) is popularly used for high-precision multiplication by divide-and-conquer approach. Recently, subquadratic digit-serial multiplier based on $(a,2)$ -way KA decomposition is proposed in [1]. In this paper, we extend a $(a,2)$ -way KA to derive a generalized $(a,b)$ -way KA decomposition with $a\neq b$ . We have shown that $(a,2)$ -way KA and mult-way KA are special cases of the proposed $(a,b)$ -way KA decomposition. Based on the proposed KA decomposition, we have established two types of subquadratic digit-serial multipliers, namely, the KA-based multiplier and the recombined KA-based multiplier. From theoretical analysis, as well as, from synthesis results we have shown that the proposed KA-based multipliers have significantly less delay and less area-delay product (ADP) compared to the existing naive digit-serial multipliers.

Shifted polynomial basis (SPB) and generalized polynomial basis (GPB) are two variations of polynomial basis representation. SPB/GPB have potential for efficient bit-level and digit-level implementations of multiplication over binary extension fields. This paper presents a (b,2)-way KA decomposition for digit-serial multiplication with low-space complexity. Based on the proposed parallel (b,2)-way KA scheme, we derive a novel scalable SPB/GPB multiplier. Analytical results show that the proposed multiplier could achieve the desired trade-off between space and time complexities. Our proposed multiplier is modular, regular, and suitable for very-large-scale integration (VLSI) implementations. It involves significantly less area complexity, less computation time and less energy consumption compared to the existing digit-serial and scalable multipliers.

Karatsuba algorithm (KA) is popularly used for high-precision multiplication of long binary polynomials. The only well-known subquadratic multipliers using KA scheme are, however, based on conventional two-operand polynomial multiplication. In this paper, we propose a novel approach based on 2-way and 3-way KA decompositions for computing three-operand polynomial multiplications. Using these novel KA decompositions, we present here a new subquadratic Montgomery multiplier. Our proposed multiplier involves less area and less delay compared to the schoolbook three-operand multiplier as well as the two-operand multipliers based on conventional KA decomposition. We have used the proposed three-operand Montgomery multiplication to derive a novel efficient scheme for m-ary exponentiation, and proposed a novel architecture for exponentiation. We have analyzed the complexities of proposed design, and shown that the proposed exponentiator can have a small lower bound on time complexity amounting to √m-1 multiplication delays, while traditional exponentiators require nearly m multiplication delays. From synthesis results, it is shown that the proposed exponentiator using subquadratic three-operand multiplier approach has significantly less time complexity, less area-delay product, and less power consumption than the existing exponentiators. Moreover, exponentiation-based cryptosystems, such as pairing based cryptography, could achieve high-speed operation using by our proposed multiplier and m-ary exponentiator.

It is well known that Chinese Remainder Theorem (CRT) can be used to construct efficient algorithms for multiplication of polynomials over GF(2). In this note, we show how to select an appropriate set of modulus polynomials to obtain minimal number of multiplications.

This paper presents complexity analysis [both in application-specific integrated circuits (ASICs) and on field-programmable gate arrays (FPGAs)] and efficient FPGA implementations of bit parallel mixed Karatsuba-Ofman multipliers (KOM) over GF(2m) . By introducing the common expression sharing and the complexity analysis on odd-term polynomials, we achieve a lower gate bound than previous ASIC discussions. The analysis is extended by using 4-input/6-input lookup tables (LUT) on FPGAs. For an arbitrary bit-depth, the optimum iteration step is shown. The optimum iteration steps differ for ASICs, 4-input LUT-based FPGAs and 6-input LUT-based FPGAs. We evaluate the LUT complexity and area-time product tradeoffs on FPGAs with different computer-aided design (CAD) tools. Furthermore, the experimental results on FPGAs for bit parallel modular multipliers are shown and compared with previous implementations. To the best of our knowledge, our bit parallel multipliers consume the least resources among known FPGA implementations to date.

In this paper, we present a new method for multiplying polynomials in Chebyshev form. Our approach has two steps. First, the well-known Karatsuba's algorithm is applied to polynomials constructed by using Chebyshev coefficients. Then, from the obtained result, extra arithmetic operations are used to write the final result in Chebyshev form. The proposed algorithm has a quadratic computational complexity. We also compare our method to other approaches.

Large integer modular multiplication (MM) and modular exponentiation (ME) are the foundation of most public-key cryptosystems, specifically RSA, Diffie-Helleman, EIGamal, and the elliptic curve cryptosystems. Thus, MM algorithms have been studied widely and extensively. Most of the work is based on the well-known Montgomery multiplication method and its variants, which require standard multiplication operations. Despite their better complexity orders, Karatsuba and FFT algorithms seem to rarely be used for hardware implementation. In this paper, we review their hardware complexity and propose original implementations of MM and ME that become useful for 24-bit operators (Karatsuba algorithm) or 373-bit operators (FFT algorithm).

Hyperelliptic curves (HEC) look promising for cryptographic applications, because of their short operand size compared to other public-key schemes. The operand sizes seem well suited for small processor architectures, where memory and speed are constrained. However, the group operation has been believed to be too complex and, thus, HEC have not been used in this context so far. In recent years, a lot of effort has been made to speed up group operation of genus-2 HEC. In this paper, we increase the efficiency of the genus-2 and genus-3 hyperelliptic curve cryptosystems (HECC). For certain genus-3 curves, we can gain almost 80 percent performance for a group doubling. This work not only improves Gaudry and Harley's algorithm, but also improves the original algorithm introduced by Cantor [1987]. Contrary to common belief, we show that it is also practical for certain curves to use Cantor's algorithm to obtain the highest efficiency for the group operation. In addition, we introduce a general reduction method for polynomials according to Karatsuba. We implemented our most efficient group operations on Pentium and ARM microprocessors.

The Karatsuba-Ofman algorithm starts with a way to multiply two 2-term (i.e., linear) polynomials using three scalar multiplications. There is also a way to multiply two 3-term (i.e., quadratic) polynomials using six scalar multiplications. These are used within recursive constructions to multiply two higher-degree polynomials in subquadratic time. We present division-free formulae, which multiply two 5-term polynomials with 13 scalar multiplications, two 6-term polynomials with 17 scalar multiplications, and two 7-term polynomials with 22 scalar multiplications. These formulae may be mixed with the 2-term and 3-term formulae within recursive constructions, leading to improved bounds for many other degrees. Using only the 6-term formula leads to better asymptotic performance than standard Karatsuba. The new formulae work in any characteristic, but simplify in characteristic 2. We describe their application to elliptic curve arithmetic over binary fields. We include some timing data.

We introduce a generalized method for constructing subquadratic complexity multipliers for even characteristic field extensions. The construction is obtained by recursively extending short convolution algorithms and nesting them. To obtain the short convolution algorithms, the Winograd short convolution algorithm is reintroduced and analyzed in the context of polynomial multiplication. We present a recursive construction technique that extends any d point multiplier into an n=d/sup k/ point multiplier with area that is subquadratic and delay that is logarithmic in the bit-length n. We present a thorough analysis that establishes the exact space and time complexities of these multipliers. Using the recursive construction method, we obtain six new constructions, among which one turns out to be identical to the Karatsuba multiplier. All six algorithms have subquadratic space complexities and two of the algorithms have significantly better time complexities than the Karatsuba algorithm.

This paper presents a new bit-parallel multiplier for the finite field GF(2/sup m/) defined by an irreducible all-one polynomial. In order to reduce the complexity of the multiplier, we introduce a redundant representation and use the well-known multiplication method proposed by Karatsuba. The main idea is to combine the redundant representation and the Karatsuba method to design an efficient bit-parallel multiplier. As a result, the proposed multiplier requires about 25 percent fewer AND/XOR gates than the previously proposed multipliers using an all-one polynomial, while it has almost the same time delay as the previously proposed ones.

A bit parallel structure for a multiplier with low complexity in Galois fields is introduced. The multiplier operates over composite fields GF((2/sup n/)/sup m/), with k=nm. The Karatsuba-Ofman algorithm (A. Karatsuba and Y. Ofmanis, 1963) is investigated and applied to the multiplication of polynomials over GF(2/sup n/). It is shown that this operation has a complexity of order O(k/sup log23/) under certain constraints regarding k. A complete set of primitive field polynomials for composite fields is provided which perform module reduction with low complexity. As a result, multipliers for fields GF(2/sup k/) up to k=32 with low gate counts and low delays are listed. The architectures are highly modular and thus well suited for VLSI implementation.

In this comment, we show that the gate complexity of Karatsuba polynomial multipliers presented in the above paper can be reduced by exploring the common subexpressions.

For original paper see P.L. Montgomery, ibid., vol.54, no.3, p.362-369, (2005). We show that multiplication complexities of n-term Karatsuba-Like formulae of GF(2)[x] (7