The numerous and huge operations involved in homomorphic encryption applications require fast arithmetic. RNS arithmetic is popular in their software implementations. In this context, we proposed a hierarchical approach for RNS base extension. It leads to 50-60 % reduction of both computation time and constant storage requirements for large homomorphic parameters in our experimental setup. When state-of-the-art parameters are not suitable for our approach, we propose to use equivalent parameters leading to similar reductions.

The paper explores hardware supports for replaying instructions to protect processors against some fault injection attacks. A replay instruction is added to the instruction set of a small 32-bit RISC processor to allow the automatic and parametrized replay of sequences of instructions. Various detection elements are added to the processor, implemented on FPGA, and compared in terms of performances, cost and fault coverage. The proposed extension leads to significant improvements compared to software protections for a small silicon overhead.

This paper deals with hardware implementations for lattice-based cryptography. Various CPA and CCA secure algorithms for LWE, RLWE and MLWE problems have been studied, parallelized, implemented and compared on FPGA using high-level synthesis. The impact of PRNG choices on the implementations performances and costs is also evaluated. HLS allows us to compare various sets of algorithms, architectures and parameters with a reduced design effort. Our results are often similar to state-of-the-art for various speed and cost trade-offs. Sometimes we obtain better results thanks to the exploration of numerous architecture and algorithm optimizations.

Base extension is a critical operation in RNS implementations of asymmetric cryptosystems. In this paper, we propose a new way to perform base extensions using a hierarchical approach for computing the Chinese remainder theorem. For well chosen parameters, it significantly reduces the computational cost and still ensures a high level of internal parallelism. We illustrate the interest of the proposed approach on the cost of typical arithmetic primitives used in asymmetric cryptography. We also demonstrate improvements in FPGA implementations of base extensions on typical elliptic curve cryptography field sizes using high-level synthesis tools.

Among various power reduction methods, variable bit-width arithmetic units have been proposed in approximate computing literature. In this paper, we add a variable bit-width memory unit in a RISC-V processor. Integrating both computation and memory units with variable bit-width leads to a power reduction: from 7% to 29% for Sobel filter application and from 13% to 24% for an application that computes the position of a robotic arm (forwardk2j). We also propose a global energy model for a RISC-V processor with variable bit-width units (for computation and memory). This model allows us to evaluate the impact of various parameters in both the software application (e.g., the amount of instructions that can be executed with a reduced bit-width) and the hardware architecture (e.g., impact of potential reduction for each unit).

In this paper, we present modular multipliers for hardware implementations of (hyper)-elliptic curve cryptography on FPGAs. The prime modulus P is generic and can be configured at run-time to provide flexible circuits. A finely-pipelined architecture is proposed for overlapping the partial products and reductions steps in the pipeline of hardwired DSP slices. For instance, 2, 3, or 4 independent multiplications can share the hardware resources at the same time to overlap internal latencies. We designed a tool, distributed as open source, for generating VHDL codes with various parameters: width of operands, number of logical multipliers per physical one, speed or area optimization, possible use of BRAMs, target FPGA. Our modular multipliers lead to, at least, 2 times faster as well as 2 times smaller circuits than state of the art operators.

This paper proposes a computational method for 2D 8×8 DCT based on algebraic integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed algebraic integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of$3.6\cdot 10^8$2D DCTs of size 8×8 every second, with corresponding pixel rate of$2.3\cdot 10^{10}$pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm$^2$. The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz$\cdot$V$_{sup}^2$.

Somewhat Homomorphic Encryption (SHE) schemes allow to carry out operations on data in the cipher domain. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. For many years, practical parameters of SHE schemes were overestimated, leading to only consider the FFT algorithm to accelerate SHE in hardware. Nevertheless, recent work demonstrates that parameters can be lowered without compromising the security [1]. Following this trend, this work investigates the benefits of using Karatsuba algorithm instead of FFT for the Fan-Vercauteren (FV) Homomorphic Encryption scheme. The proposed accelerator relies on an hardware/software co-design approach, and is designed to perform fast arithmetic operations on degree 2,560 polynomials with 135 bits coefficients, allowing to compute small algorithms homomorphically. Compared to a functionally equivalent design using FFT, our accelerator performs an homomorphic multiplication in 11.9 ms instead of 15.46 ms, and halves the size of logic utilization and registers on the FPGA.

The papers in this special issue focus on computer arithmetic which is used in many applications, usually totally silently (one should keep in mind that even when running programs that are not at all numeric, memory addresses are computed, which involves additions, multiplications, and sometimes divisions). However, in some areas, it plays a central role.

Somewhat Homomorphic Encryption (SHE) schemes can be used to carry out operations on ciphered data. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. The principle limitation of SHE is the size of ciphertext compared to the size of the message. This issue can be addressed by using a batching technique that “packs” several messages into one ciphertext. However, this method leads to important drawbacks in standard implementations. This paper presents a fast hardware/software co-design implementation of an encryption procedure using the Karatsuba algorithm. Our hardware accelerator is 1.5 times faster than the state of the art for 1 encryption and 4 times faster for 4 encryptions.

We propose an hybrid representation of large integers, or prime field elements, combining both positional and residue number systems (RNS). Our hybrid position-residues (HPR) number system mixes a high-radix positional representation and digits represented in RNS. RNS offers an important source of parallelism for addition, subtraction and multiplication operations. But, due to its non-positional property, it makes comparisons and modular reductions more costly than in a positional number system. HPR offers various trade-offs between internal parallelism and the efficiency of operations requiring position information. Our current application domain is asymmetric cryptography where HPR significantly reduces the cost of some modular operations compared to state-of-the-art RNS solutions.

Somewhat Homomorphic Encryption (SHE) schemes allow to carry out operations on data in the cipher domain. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. Most practical Somewhat Homomorphic Encryption (SHE) schemes require the implementation of fast polynomial arithmetic, that is why hardware accelerators usually target the FFT/NTT algorithm. This paper proposes a co-design hardware/software approach to accelerate SHE using Karatsuba algorithm. Depending on the needs, Karatsuba algorithm allows to implement additional computations to the hardware in order to reduce software computation time. Our accelerator is designed to speed up arithmetic on degree 2560 polynomials with 125 bits coefficients. We provide 3 different approaches: An area efficient design, a balanced design, and a performance-oriented design. Our accelerator performs a polynomial multiplication in respectively 2.46 ms, 1.70 ms and 1.24 ms, and a relinearization operation in 2.28 ms, 1.53 ms and 1.1 ms, while a functionally equivalent design using the FFT [1] performs the multiplication in 1.96 ms and the relinearization in 4.79 ms for hardware resources consumption equivalent to the balanced design.

A fast RNS modular inversion for finite fields arithmetic has been published at CHES 2013 conference. It is based on the binary version of the plus-minus Euclidean algorithm. In the context of elliptic curve cryptography (i.e., 160-550 bits finite fields), it significantly speeds-up modular inversions. In this paper, we propose an improved version based on both radix 2 and radix 3. This new algorithm leads to 30 percent speed-up for a maximal area overhead about 4 percent on Virtex 5 FPGAs.

The paper presents details on fast and secure GF(2^m) multipliers dedicated to elliptic curve cryptography applications. Presented design approach aims at high efficiency and security against side channel attacks of a hardware multiplier. The security concern in the design process of a GF(2^m) multiplier is quite a novel concept. Basing on the results obtained in course of conducted research it is argued that, as well as efficiency of the multiplier impacts the efficiency of the cryptoprocessor, the security level of the multiplier impacts the security level of the whole cryptoprocessor. Thus the goal is to find a tradeoff, to compromise efficiency, in terms of speed and area, and security of the multiplier. We intend to secure the multiplier by masking the operation, either by uniformization or by randomization of the power consumption of the device during its work. The design methodology is half automated. The analyzed field sizes are the standard ones, which ensure that a cryptographic system is mathematically safe. The described architecture is based on principles of Mastrovito multiplication method. It is very flexible and enables to improve the resistance against side channel attacks without degrading the multiplier efficiency.

The paper describes a new RNS (residue number system) modular multiplication algorithm, for finite field arithmetic over FP, based on a reduced number of moduli in base extensions with only 3n=2 moduli instead of 2n for standard ones. Our algorithm reduces both the number of elementary modular multiplications (EMMs) and the number of stored precomputations for large asymmetric cryptographic applications such as elliptic curve cryptography or Diffie-Hellman (DH) cryptosystem. It leads to faster operations and smaller circuits.

Scalar recoding is popular to speed up ECC scalar multiplication: non-adjacent form, double-base number system, multi-base number system. But fast recoding methods require pre-computations: multiples of base point or off-line conversion. In this paper, we present a multi-base recoding method for ECC scalar multiplication based on i) a greedy algorithm starting least significant terms first, ii) cheap divisibility tests by multi-base elements and iii) fast exact divisions by multi-base elements. Multi-base terms are obtained on-the-fly using a special recoding unit which operates in parallel to curve-level operations and at very high speed. This ensures that all recoding steps are performed fast enough to schedule the next curve-level operations without interruptions. The proposed method can be fully implemented in hardware without pre-computations. We report FPGA implementation details and very good performances compared to state-of-art results.

In this paper we provide a comparison of different modular multipliers suitable for use in an elliptic curve processor, when working with a Mersenne prime modulus. Mersenne primes allow for the use of fast modular reduction techniques. Several multipliers are presented that can be implemented solely in slice logic. A design that makes use of the DSP48E blocks on Virtex 5 FPGAs is also described. The different multipliers are compared for speed, area and power consumption when implemented on a Virtex 5 FPGA.

Differential Fault Analysis (DFA) is a real threat for elliptic curve cryptosystems. This paper describes an elliptic curve cryptoprocessor unit resistant against fault injection. This resistance is provided by the use of parity preserving logic gates in the operating structure of the ECC unit, which is based on borrow-save adders. The proposed countermeasure provides a high coverage fault detection and induces an acceptable area overhead (+ 38 %).

This work deals with hardware evaluation of the sine and cosine functions for the same argument simultaneously. The proposed method uses trigonometric identities, small lookup tables and low-degree polynomial approximations with very sparse coefficients. Most of the multiplications are replaced by a small number of additions or subtractions, this leads to small and fast circuits

Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite---and sometimes small---number of bits. This is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree- i coefficient has at most m i fractional bits; in other words, it is a rational number with denominator 2 m i . We provide a general and efficient method for finding the best polynomial approximation under this constraint. Moreover, our method also applies if some other constraints (such as requiring some coefficients to be equal to some predefined constants or minimizing relative error instead of absolute error) are required.

Algorithms for Euclidean (i.e., integer) division by a constant operation are presented. They allow fast computation for some values of the divisor (known at compile time) or also when both quotient and modulus are required. These algorithms are based on the multiply-accumulate instruction and the 40-bit arithmetic available in DSPs such as the ST100 DSP from STMicroelectronics. The results are demonstrated in the case of standard speech coding applications.

This paper presents small FPGA implementations of low precision polynomial approximations of functions without multipliers. Our method uses degree-2 or degree-3 polynomial approximations with at most 3-bit coefficients and low-precision estimations of the powers of x. Here we denote by 3-bit coefficients values with at most 3 nonzero and possibly noncontiguous signed bits (e.g., 1.0010001~). This leads to very small operators by replacing the costly multipliers by a small number of additions. Our method provides approximations with very low average error and is suitable for signal processing applications.

This paper presents some improvements on the optimization of hardware multiplication by constant matrices. We focus on the automatic generation of circuits that involve constant matrix multiplication, i.e., multiplication of a vector by a constant matrix. The proposed method, based on number recoding and dedicated common subexpression factorization algorithms, was implemented in a VHDL generator. Our algorithms and generator have been extended to the case of some digital filters based on multiplication by a constant matrix and delay operations. The obtained results on several applications have been implemented on FPGAs and compared to previous solutions. Up to 40 percent area and speed savings are achieved.

A unified view of most previous table-lookup-and-addition methods (bipartite tables, SBTM, STAM, and multipartite methods) is presented. This unified view allows a more accurate computation of the error entailed by these methods, which enables a wider design space exploration, leading to tables smaller than the best previously published ones by up to 50 percent. The synthesis of these multipartite architectures on Virtex FPGAs is also discussed. Compared to other methods involving multipliers, the multipartite approach offers the best speed/area tradeoff for precisions up to 16 bits. A reference implementation is available at http://www.ens-lyon.fr/LIP/Arenaire/.

We present some improvements on the optimization of hardware multiplication by constant matrices. We focus on the automatic generation of circuits that involve constant matrix multiplication (CMM), i.e. multiplication of a vector by a constant matrix. The proposed method, based on number recoding and dedicated common sub-expression factorization algorithms was implemented in a VHDL generator. The obtained results on several applications have been implemented on FPGAs and compared to previous solutions. Up to 40% area and speed savings are achieved.

This paper presents an unified view of most previous table-lookup-and-addition methods: bipartite tables, SBTM, STAM and multipartite methods. This new definition allows a more accurate computation of the error entailed by these methods. Being more general, it also allows an exhaustive design space exploration which has been implemented, and leads to tables smaller than previously published ones by up to 50%. Some results have been synthesised for Virtex FPGAs, and are discussed.

This paper deals with the computation of reciprocals, square roots, inverse square roots, and some elementary functions using small tables, small multipliers, and, for some functions, a final "large" (almost full-length) multiplication. We propose a method, based on argument reduction and series expansion, that allows fast evaluation of these functions in high precision. The strength of this method is that the same scheme allows the computation of all these functions. We estimate the delay, the size/number of tables, and the size/number of multipliers and compare with other related methods.

The Table Maker's Dilemma is the problem of always getting correctly rounded results when computing the elementary functions. After a brief presentation of this problem, we present new developments that have helped us to solve this problem for the double-precision exponential function in a small domain. These new results show that this problem can be solved, at least for the double-precision format, for the most usual functions.

We present a new class of number systems, called Semi-Logarithmic Number Systems, that constitute a family of various compromises between floating-point and logarithmic number systems. This allows trade between the speed of the arithmetic operations and the size of the required tables. We give arithmetic algorithms (addition/subtraction, multiplication, division) for the Semi-Logarithmic Number Systems, and we compare these number systems to the classical floating-point or logarithmic number systems.

The Table Maker's Dilemma is the problem of always getting exactly rounded results when computing the elementary functions. After a brief presentation of this problem, we present new developments that helped us to solve this problem for the double precision exponential function in a small domain. These new results show that this problem can be solved, at least for the double precision format, for the most usual functions.

We present a new class of number systems, called semi-logarithmic number systems, that constitute a family of various compromises between floating-point and logarithmic number systems. We propose arithmetic algorithms for the semi-logarithmic number systems, and we compare these number systems to the classical floating-point or logarithmic number systems.>