We present novel strategies and concrete algorithms for the parallel computation of the Supersingular Isogeny-based Diffie-Hellman key exchange (SIDH) protocol when executed on multi-core platforms. The most relevant design idea exploited by our approach is that of concurrently computing scalar multiplication operations along with a parallelized version of the strategies required for constructing and evaluating large smooth degree isogenies. We report experimental results showing that a three-core implementation of our parallel approach achieves an acceleration factor of 1.45 compared against a sequential implementation of the Supersingular Isogeny Key Encapsulation (SIKE) protocol instantiated with the prime p751

Abstract The supersingular isogeny Diffie–Hellman key exchange protocol (SIDH) was introduced by Jao and De Feo in 2011. SIDH operates on supersingular elliptic curves defined over , where p is a large prime number of the form and e A and e B are positive integers such that . A variant of the SIDH protocol, dubbed extended SIDH (eSIDH), is presented. The eSIDH makes use of primes of the form . Here ℓ B and ℓ C are two small prime numbers; f is a cofactor; and e A , e B , and e C are positive integers such that . It is shown that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys faster field arithmetic than the one associated with traditional SIDH primes. Furthermore, its richer opportunities for parallelism yield a noticeable speed‐up factor when implemented on multicore platforms. A supersingular isogeny key encapsulation (SIKE) instantiation using the prime eSIDH‐ p 765 yields an acceleration factor of 1.06, 1.15 and 1.14 over a SIKE instantiation with the prime SIKE‐ p 757 when implemented on k = {1, 2, 3}‐core processors. To the authors’ knowledge, this work reports the first multicore implementation of SIDH and SIKE.

Since its introduction by Jao and De Feo in 2011, the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol has positioned itself as a promising candidate for post-quantum cryptography. One salient feature of the SIDH protocol is that it requires exceptionally short key sizes. However, the latency associated to SIDH is higher than the ones reported for other post-quantum cryptosystem proposals. Aiming to accelerate the SIDH runtime performance, we present in this work several algorithmic optimizations targeting both elliptic-curve and field arithmetic operations. We introduce in the context of the SIDH protocol a more efficient approach for calculating the elliptic curve operation$P+[k]Q$. Our strategy achieves a factor 1.4 speedup compared with the popular variable-three-point ladder algorithm regularly used in the SIDH shared secret phase. Moreover, profiting from pre-computation techniques our algorithm yields a factor 1.7 acceleration for the computation of this operation in the SIDH key generation phase. We also present an optimized evaluation of the point tripling formula, and discuss several algorithmic and implementation techniques that lead to faster field arithmetic computations. A software implementation of the above improvements on an Intel Skylake Core i7-6700 processor gives a factor 1.33 speedup against the state-of-the-art software implementation of the SIDH protocol reported by Costello-Longa-Naehrig in CRYPTO 2016.

Since the discovery of identity-based encryption schemes in 2000, bilinear pairings have been used in the design of hundreds of cryptographic protocols. The most commonly used pairings are constructed from elliptic curves over finite fields with small embedding degree. These pairings can have different security, performance, and functionality characteristics, and were therefore classified into Types 1, 2, 3 and 4. In this paper, we observe that this conventional classification is not applicable to pairings from elliptic curves with embedding degree one. It is important to understand the security, efficiency, and functionality of these pairings in light of recent attacks on certain pairings constructed from elliptic curves with embedding degree greater than one. We define three kinds of pairings from elliptic curves with embedding degree one, discuss some subtleties with using them to implement pairing-based protocols, and provide an estimated cost of implementing them on modern processors.

A ciphertext-policy attribute-based encryption protocol uses bilinear pairings to provide control access mechanisms, where the set of user's attributes is specified by means of a linear secret sharing scheme. In this paper we present the design of a software cryptographic library that achieves record timings for the computation of a 126-bit security level attribute-based encryption scheme. We developed all the required auxiliary building blocks and compared the computational weight that each of them adds to the overall performance of this protocol. In particular, our single pairing and multi-pairing implementations achieve state-of-the-art time performance at the 126-bit security level.

Nowadays, electoral processes can be automated, using electronic devices and communication networks. The electronic voting systems allow easy voter casting and fast vote counting for electoral entities. In this paper, an electronic voting scheme is proposed, it performs the communication among voters and electoral entities with a minimal number of phases and cryptographic operations. The scheme uses a combination of the blind signature scheme proposed by Boldyreva in 2003 and the short signature proposed by Boneh–Lynn–Shacham in 2001. Both signatures use pairing-based cryptography and a special hash function known as map-to-point. The scheme generates small ballots which consist of just two messages, one blind signature and one short signature. We present experimental data showing that our pairing-based scheme is considerably more efficient than other blind signature e-voting schemes recently proposed whose security is based on the integer factorization problem or on the discrete logarithm problem over prime fields.

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form${\BBF_{{q^2}}}$, with$q = {p^n}$,$p$an odd prime and$n \geq 1$. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in${\BBF_{{q^2}}}$. The first algorithm is devoted to the case when$q \equiv 1\, {\rm mod}\, 4$, whereas the second one handles the case when$q \equiv 3\, {\rm mod}\,4$. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known.

A new class of polynomials was introduced by Bernstein (Bernstein 2007) which were later named by Sarkar as BernsteinRabin-Winograd (BRW) polynomials (Sarkar 2009). For the purpose of authentication, BRW polynomials offer considerable computational advantage over usual polynomials: (m - 1) multiplications for usual polynomial hashing versus ⌊m/2⌋ multiplications and ⌈log2m⌉ squarings for BRW hashing, where m is the number of message blocks to be authenticated. In this paper, we develop an efficient pipelined hardware architecture for computing BRW polynomials. The BRW polynomials have a nice recursive structure which is amenable to parallelization. While exploring efficient ways to exploit the inherent parallelism in BRW polynomials we discover some interesting combinatorial structural properties of such polynomials. These are used to design an algorithm to decide the order of the multiplications which minimizes pipeline delays. Using the nice structural properties of the BRW polynomials we present a hardware architecture for efficient computation of BRW polynomials. Finally, we provide implementations of tweakable enciphering schemes proposed in Sarkar 2009 which use BRW polynomials. This leads to the fastest known implementation of disk encryption systems.

This paper is devoted to the design of fast parallel accelerators for the cryptographic \eta_T pairing on supersingular elliptic curves over finite fields of characteristics two and three. We propose here a novel hardware implementation of Miller's algorithm based on a parallel pipelined Karatsuba multiplier. After a short description of the strategies that we considered to design our multiplier, we point out the intrinsic parallelism of Miller's loop and outline the architecture of coprocessors for the \eta_T pairing over {\bf F}_{2^m} and {\bf F}_{3^m}. Thanks to a careful choice of algorithms for the tower field arithmetic associated with the \eta_T pairing, we manage to keep the pipelined multiplier at the heart of each coprocessor busy. A final exponentiation is still required to obtain a unique value, which is desirable in most cryptographic protocols. We supplement our pairing accelerators with a coprocessor responsible for this task. An improved exponentiation algorithm allows us to save hardware resources. According to our place-and-route results on Xilinx FPGAs, our designs improve both the computation time and the area–time trade-off compared to previously published coprocessors.

We present low complexity formulae for the computation of cubing and cube root over IF3mconstructed 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 give in this paper a selection of irreducible polynomials that lead to low cost field cubing and field cube root computations for supersingular elliptic curves defined over IF3m, where m is a prime number in the pairing-based cryptographic range of interest, namely, m ∈ [47, 541].

Tweakable enciphering schemes are length-preserving block cipher modes of operation that provide a strong pseudorandom permutation. It has been suggested that these schemes can be used as the main building blocks for achieving in-place disk encryption. In the past few years, there has been an intense research activity toward constructing secure and efficient tweakable enciphering schemes. But actual experimental performance data of these newly proposed schemes are yet to be reported. In this paper, we present optimized FPGA implementations of six tweakable enciphering schemes, namely, HCH, HCTR, XCB, EME, HEH, and TET, using a 128-bit AES core as the underlying block cipher. We report the performance timings of these modes when using both pipelined and sequential AES structures. The universal polynomial hash function included in the specification of HCH, HCHfp (a variant of HCH), HCTR, XCB, TET, and HEH was implemented using a Karatsuba multiplier as the main building block. We provide detailed algorithm analysis of each of the schemes trying to exploit their inherent parallelism as much as possible. Our experiments show that a sequential AES core is not an attractive option for the design of these modes as it leads to rather poor throughput. In contrast, according to our place-and-route results on a Xilinx Virtex 4 FPGA, our designs achieve a throughput of 3.95 Gbps for HEH when using an encryption/decryption pipelined AES core, and a throughput of 5.71 Gbps for EME when using a encryption-only pipeline AES core. The performance results reported in this paper provide experimental evidence that hardware implementations of tweakable enciphering schemes can actually match and even outperform the data rates achieved by state-of-the-art disk controllers, thus showing that they might be used for achieving provably secure in-place hard disk encryption.

In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of ldquohardrdquo exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.

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 element with equal or better hardware efficiency than the one associated to the field squaring operation. Furthermore, a practical application of the square root operator in the domain of field exponentiation computation is presented. It is shown that by using as building blocks squarers, multipliers and square root blocks, a parallel version of the classical square-and-multiply exponentiation algorithm can be obtained. A hardware implementation of that parallel version may provide a speedup of up to 50% percent when compared with the traditional version.

This paper deals with the optimal computation of finite field exponentiation, which is a well-studied problem with many important applications in the areas of error-correcting codes and cryptography. It has been shown that the optimal computation of finite field exponentiation is a problem which is closely related to finding a suitable addition chain with the shortest possible length. However, it is also known that obtaining the shortest addition chain for a given arbitrary exponent is an NP-hard problem. As a consequence, heuristics are an obvious choice to compute field exponentiation with a semi-optimal number of underlying arithmetic operations. In this paper, we propose the use of an artificial immune system to tackle this problem. Particularly, we study the problem of finding both the shortest addition chains for exponentsewith moderate size (i.e., with a length of less than 20 bits), and for the huge exponents typically adopted in cryptographic applications, (i.e., in the range from 128 to 2048 bits).

Summary form only given. We present a generic parallel architecture for fast elliptic curve scalar multiplication over binary extension fields. We show how the parallel strategy followed in this work leads to high performance designs. We also implemented the proposed architecture on reconfigurable hardware devices where the predicted expeditious performance figures were actually obtained. The results achieved show that our proposed design is able to compute GF(2/sup 191/) elliptic curve scalar multiplication operations in 56.44 /spl mu/Secs.

The state-of-the-art Galois field GF(2/sup m/) multipliers offer advantageous space and time complexities when the field is generated by so special irreducible polynomial. To date, the best complexity results have been obtained when the irreducible polynomial is either a trinomial or an equally spaced polynomial (ESP). Unfortunately, there exist only a few irreducible ESPs in the range of interest for most of the applications, e.g., error-correcting codes, computer algebra, and elliptic curve cryptography. Furthermore, it is not always possible to find an irreducible trinomial of degree m in this range. For those cases where neither an irreducible trinomial nor an irreducible ESP exists, the use of irreducible pentanomials has been suggested. Irreducible pentanomials are abundant, and there are several eligible candidates for a given m. We promote the use of two special types of irreducible pentanomials. We propose new Mastrovito and dual basis multiplier architectures based on these special irreducible pentanomials and give rigorous analyses of their space and time complexity.