Presents the front cover, title page, cover page, or splash screen of the proceedings record.

International audience

Modular exponentiation, or scalar multiplication, is core to today's main stream public key cryptographic systems. In this article we generalize the classical fractional wNAF method for modular exponentiation - the classical method uses a digit set of the form {1, 3, . . . , m} which is extended here to any set of odd integers of the form {1, d2, . . . , dn}. We propose a general modular exponentiation algorithm based on a generalization of the frac-wNAF recoding and a new precomputation scheme. We also give general formula for the average density of non-zero therms in these representations, prove that there are infinitely many optimal sets for a given number of digits and show that the asymptotic behavior, when those digits are randomly chosen, is very close to the optimal case.

In this paper we present efficient algorithms to take advantage of the double-base number system in the context of elliptic curve scalar multiplication. We propose a generalized version of Yao's exponentiation algorithm allowing the use of general double-base expansions instead of the popular double base chains. We introduce a class of constrained double base expansions and prove that the average density of non-zero terms in such expansions is O( log k/ log log k) for any large integer k. We also propose an efficient algorithm for computing constrained expansions and finally provide a comprehensive comparison to double-base chain expansions, including a large variety of curve shapes and various key sizes.

In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).