Search

A recent work of Sipasseuth, Plantard and Susilo proposed to accelerate lattice-based signature verifications and compress public key storage at the cost of a precomputation on a public key. This first approach, which focused on a restricted type of key, did not include most NIST candidates or most lattice representations in general. In this work, we first present a way to improve even further both their verification speed and their public key compression capability by using a generator of numbers that better suit the method needs. We then also generalize their framework to apply to q-ary lattice schemes as well as classical lattices using Hermite Normal Form, improving their security and applicable scope, thus exhibiting potential trade-offs to accelerate lattice-based signature verification in general and compression of the public key on the verifier side for unstructured lattices.

Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-Rmethod and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-Rrepresentation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches.

In this paper, we consider efficient RSA modular exponentiations $$x^K \mod N$$ xKmodN which are regular and constant time. We first review the multiplicative splitting of an integer xmodulo Ninto two half-size integers. We then take advantage of this splitting to modify the square-and-multiply exponentiation as a regular sequence of squarings always followed by a multiplication by a half-size integer. The proposed method requires around 16 % less word operations compared to Montgomery-ladder, square-always and square-and-multiply-always exponentiations. These theoretical results are validated by our implementation results which show an improvement by more than 12 % compared approaches which are both regular and constant time.

In Crypto 1997, Goldreich, Goldwasser and Halevi (GGH) proposed a lattice analogue of McEliece public key cryptosystem, in which security is related to the hardness of approximating the Closest Vector Problem in a lattice. Furthermore, they also described how to use the same principle of their encryption scheme to provide a signature scheme. Practically, this cryptosystem uses the Euclidean norm, l2-norm, which has been used in many algorithms based on lattice theory. Nonetheless, many drawbacks have been studied and these could lead to cryptanalysis of the scheme. In this article, we present a novel method of reducing a vector under the l∞-norm and propose a digital signature scheme based on it. Our scheme takes advantage of the l∞-norm to increase the resistance of the GGH scheme and to decrease the signature length. Furthermore, after some other improvements, we obtain a very efficient signature scheme, that trades the security level, speed and space.