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

Residue number systems provide efficient techniques for speeding up calculations and/or protecting against side channel attacks when used in the context of cryptographic engineering. One of the interests of such systems is their scalability, as the existence of large bases for some specialized systems is often an open question. In this paper, we present highly optimized methods for generating large bases for residue number systems and, in some cases, the largest possible bases. We show their efficiency by demonstrating their improvement over the state-of-the-art bases reported in the literature. This work make it possible to address the problem of the scalability issue of finding new bases for a specific system that arises whenever a parameter changes, and possibly open new application avenues.

Published in "IEEE Transactions on Emerging Topics in Computing, Volume: 9, Issue: 3, JulySeptember 2021" and orally presented at ARITH 2021.

In [1] the authors introduced the leak resistant arithmetic in RNS to randomize RSA modular exponentiation. This randomization is meant to protect implementations on embedded device from side channel analysis. We propose in this paper a lazy version of the approach of [1] in the case of right-to-left square-and-multiply exponentiation. We show that this saves roughly 30% of the computation when the randomization is done at each loop iteration. We also show that the level of randomization of the proposed approach is better than the one of [1] after a few number of loop iterations.

Copyright 2016 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.Cryptographic operations performed on an embedded device are vulnerable to side channel analysis and particularly to differential and correlation power analysis. The basic protection against such attacks is to randomize the data all along the cryptographic computations. In this paper we present a modular multiplication algorithm which can be used for randomization. We show that we can use it to randomize the modular exponentiation of the RSA cryptosystem. The proposed randomization is free of computation and induces a level of randomization from 210 to 215 for practical RSA modulus size.

Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this study, the authors propose the first ring signature scheme whose size is O (log 2 N ), where N is the number of users in the ring. They achieve this result by improving Chandran et al .’s ring signature scheme presented at the International Colloquium on Automata, Languages and Programming 2007. Their scheme uses a common reference string and non‐interactive zero‐knowledge proofs. The security of their scheme is proven without requiring random oracles.

Residue Number Systems (RNS) are naturally considered as an interesting candidate to provide efficient arithmetic for implementations of cryptosystems such as RSA, ECC (Elliptic Curve Cryptography), pairings, etc. More recently, RNS have been used to accelerate fully homomorphic encryption as lattice-based cryptogaphy. In this paper, we present an RNS algorithm resolving the Closest Vector Problem (CVP). This algorithm is particularly efficient for a certain class of lattice basis. It provides a full RNS Babai round-off procedure without any costly conversion into alternative positional number system such as Mixed Radix System (MRS). An optimized Cox-Rower architecture adapted to the proposed algorithm is also presented. The main modifications reside in the Rower unit whose feature is to use only one multiplier. This allows to free two out of three multipliers from the Rower unit by reusing the same one with an overhead of 3 more cycles per inner reduction. An analysis of feasibility of implementation within FPGA is also given.

The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,...,ABℓby the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.

All the existing fully homomorphic encryption schemes are based on three different problems, namely the bounded distance decoding problem over ideal lattice, the approximate greatest common divisor problem over integers, and the learning with error problem. In this paper, we unify the first two families of problems by introducing a new class of problems, which can be reduced from both problems. Based on this new problem, namely the bounded distance decoding over hidden ideal lattice, we present a new fully homomorphic encryption scheme. Since it is a combination of the two problems to some extent, the performance of our scheme lies between the ideal lattice based schemes and the integer based schemes. Furthermore, we also show a lower bound and upper bound of the problem that our scheme is based on. Assuming this security conjecture holds, we can incorporate smaller parameters, which will result in a scheme that is more efficient than both lattice based and integer based schemes. Hence, our scheme makes a perfect alternative to the state-of-art ring learning with error based schemes.

This paper deals with binary field multiplication. We use the bivariate representation of binary field called Double Polynomial System (DPS) presented in . This concept generalizes the composite field representation to every finite field. As shown in , the main interest of DPS representation is that it enables to use Lagrange approach for multiplication, and in the best case, Fast Fourier Transform approach, which optimizes Lagrange approach. We use here a different strategy from to perform reduction, and we also propose in this paper, some new approaches for constructing DPS. We focus on DPS, which provides a simpler and more efficient method for coefficient reduction. This enables us to avoid a multiplication required in the Montgomery reduction approach of , and thus to improve the complexity of the DPS multiplier. The resulting algorithm proposed in the present paper is subquadratic in space O(n1.31) and logarithmic in time. The space complexity is 33 percent better than in and 18 percent faster. It is asymptotically more efficient than the best known method (specifiably more efficient than when n ≥ 3,000). Furthermore, our proposal is available for every n and not only for n a power of two or three.

The selection of the elements of the bases in an RNS modular multiplication method is crucial and has a great impact in the overall performance.This work proposes specific sets of optimal RNS moduli with elements of Hamming weight three whose inverses used in the MRS reconstruction have very small Hamming weight. This property is exploited in RNS bases conversions, to completely remove and replace the products by few additions/subtractions and shifts, reducing the time complexity of modular multiplication.These bases are specially crafted to computation with operands of sizes 256 or more and are suitable for cryptographic applications such as the ECC protocols.

We propose a new number representation and arithmetic for the elements of the ring of integers modulo p. The so-called polynomial modular number system (PMNS) allows for fast polynomial arithmetic and easy parallelization. The most important contribution of this paper is the fundamental theorem of a modular number system, which provides a bound for the coefficients of the polynomials used to represent the set /spl Zopf//sub p/. However, we also propose a complete set of algorithms to perform the arithmetic operations over a PMNS, which make this system of practical interest for people concerned about efficient implementation of modular arithmetic.

We present a new multiplication algorithm for the implementation of elliptic curve cryptography (ECC) over the finite extension fields GF(p/sup k/) where p is a prime number greater than 2k. In the context of ECC we can assume that p is a 7-to-10-bit number, and easily find values for k which satisfy: p>2k, and for security reasons log/sub 2/(p)/spl times/k/spl sime/160. All the computations are performed within an alternate polynomial representation of the field elements which is directly obtained from the inputs. No conversion step is needed. We describe our algorithm in terms of matrix operations and point out some properties of the matrices that can be used to improve the design. The proposed algorithm is highly parallelizable and seems well adapted to hardware implementation of elliptic curve cryptosystems.