This work deals with the energy-efficient, high-speed and high-security implementation of elliptic curve scalar multiplication, elliptic curve Diffie-Hellman (ECDH) key exchange and elliptic curve digital signatures on embedded devices using FourQ and incorporating strong countermeasures to thwart a wide variety of side-channel attacks. First, we set new speed records for constant-time curve-based scalar multiplication, DH key exchange and digital signatures at the 128-bit security level with implementations targeting 8, 16 and 32-bit microcontrollers. For example, our software computes a static ECDH shared secret in ~6.9 million cycles (or 0.86 seconds @8 MHz) on a low-power 8-bit AVR microcontroller which, compared to the fastest Curve25519 and genus-2 Kummer implementations on the same platform, offers 2× and 1.4× speedups, respectively. Similarly, it computes the same operation in ~495 thousand cycles on a 32-bit ARM Cortex-M4 microcontroller, achieving a factor-1.9 speedup when compared to the fastest Curve25519 implementation targeting another Cortex-M4 platform. A similar speed performance is observed in the case of digital signatures. Second, we engineer a set of side-channel countermeasures taking advantage of FourQ's rich arithmetic and propose a secure implementation that offers protection against a wide range of sophisticated side-channel attacks, including differential power analysis (DPA). Despite the use of strong countermeasures, the experimental results show that our FourQ software is still efficient enough to outperform implementations of Curve25519 that only protect against timing attacks. Finally, we perform a differential power analysis evaluation of our software running on an ARM Cortex-M4, and report that no leakage was detected with up to 10 million traces. These results demonstrate the potential of deploying FourQ on low-power applications such as protocols forthe Internet of Things.

The papers in this special section examine the impact of cryptographic engineering in a post-quantum world. The vast majority of public-key cryptosystems currently in use is based on integer factorization and (elliptic curve) discrete logarithm problems, which are believed to be intractable with current computing technology. However, these hard problems can be solved in polynomial time by using Shor’s algorithm (or one of its variants) on a quantum computer. Recent progress towards the development of a largescale, fault-tolerant quantum computer has motivated the interest for post-quantum cryptography (a.k.a. quantum-safe or quantum-resistant cryptography) by governments, enterprises and the cryptography community.

Advancement in pairing-based protocols has had a major impact on the applicability of cryptography to the solution of more complex real-world problems. However, the computation of pairings in software still needs to be optimized for different platforms including emerging embedded systems and high-performance PCs. Few works in the literature have considered implementations of pairings on the former applications despite their growing importance in a post-PC world. In this paper, we investigate the efficient computation of the Optimal-Ate pairing over special class of pairing friendly Barreto-Naehrig curves in software at different security levels. We target both applications and perform our implementations on ARM-powered processors (with and without NEON instructions) and PC processors. We exploit state-of-the-art techniques and propose new optimizations to speed up the computation in the different levels including tower field and curve arithmetic. In particular, we extend the concept of lazy reduction to inversion in extension fields, analyze an efficient alternative for the sparse multiplication used inside the Miller’s algorithm and reduce further the cost of point/line evaluation formulas in affine and projective homogeneous coordinates. In addition, we study the efficiency of using M-type and D-type sextic twists in the pairing computation and carry out a detailed comparison between affine, Jacobian, and homogeneous coordinate systems. Our implementations on various mass-market emerging embedded devices significantly improve the state-of-the-art of pairing computation on ARM-powered devices and x86-64 PC platforms. For ARM implementations we achieved considerably faster computations in comparison to the counterparts.

We present an innovative methodology for accelerating the elliptic curve point formulas over prime fields. This flexible technique uses the substitution of multiplication with squaring and other cheaper operations by exploiting the fact that field squaring is generally less costly than multiplication. Applying this substitution to the traditional formulas, we obtain faster point operations in unprotected sequential implementations. We also show the significant impact our methodology has in protecting against simple side- channel (SSCA) attacks. We modify the elliptic curve cryptography (ECC) point formulas to achieve a faster atomic structure when applying side-channel atomicity protection. In contrast to previous atomic operations that assume that squarings are indistinguishable from multiplications, our new atomic structure offers true SSCA-protection because it includes squaring in its formulation. Moreover, we extend our implementation to parallel architectures such as Single-Instruction Multiple-Data (SIMD). With the introduction of a new coordinate system and the flexibility of our methodology, we present, to our knowledge, the fastest formulas for SIMD-based schemes that are capable of executing three and four operations simultaneously. Finally, a new parallel SSCA-protected scheme is proposed for multiprocessor/parallel architectures by applying the atomic structure presented in this work. Our parallel and atomic operations are shown to be significantly faster than previous implementations.

In this paper, distributed arithmetic (DA) has been used to implement a fully parallel LUT-based DA wavelet filterbank with interlaced input registers. In our scheme, decimation has been seamlessly integrated into the filter structure to achieve the same throughput performance as polyphase-based filterbanks. However, because partitioning of the filters is avoided, our scheme gives more flexibility to implement the LUT-DA structure, and consequently, lets designers maximize area utilization on LUT-based FPGAs. Our architecture has been designed for orthonormal and biorthogonal wavelets, and implemented on an Altera Stratix II FPGA. Significant reduction in terms of area requirements and increased throughput performance are achieved when compared to other DWT filterbanks based on DA, convolution or the lifting scheme.