The numerous and huge operations involved in homomorphic encryption applications require fast arithmetic. RNS arithmetic is popular in their software implementations. In this context, we proposed a hierarchical approach for RNS base extension. It leads to 50-60 % reduction of both computation time and constant storage requirements for large homomorphic parameters in our experimental setup. When state-of-the-art parameters are not suitable for our approach, we propose to use equivalent parameters leading to similar reductions.

This paper deals with hardware implementations for lattice-based cryptography. Various CPA and CCA secure algorithms for LWE, RLWE and MLWE problems have been studied, parallelized, implemented and compared on FPGA using high-level synthesis. The impact of PRNG choices on the implementations performances and costs is also evaluated. HLS allows us to compare various sets of algorithms, architectures and parameters with a reduced design effort. Our results are often similar to state-of-the-art for various speed and cost trade-offs. Sometimes we obtain better results thanks to the exploration of numerous architecture and algorithm optimizations.

The conference offers a note of thanks and lists its reviewers.

ARINC 653 introduces the concept of partition that allows time and space isolation in real-time avionic systems. Tasks are assigned to partitions according to various objective functions or constraints such as safety, performance, and security. Some of these objective functions may be conflicting as an improvement of one objective leads to a decrease of another. For example, improving safety by active redundancy may decrease performance. In this paper, we investigate the conflicting aspect between schedulability and security in Time and Space Partitioning (TSP) systems. Many researches have shown that enforcing the security of a system results in an overhead affecting its schedulability. We formulate a design space exploration (DSE) process with a meta-heuristic to explore solutions defined by the tasks to partitions assignment according to security requirements and timing constraints. Experiments are conducted with the Cheddar scheduling analyzer to characterize applications that are concerned by this conflicting issue and to evaluate the tradeoffs between schedulability and security.

Base extension is a critical operation in RNS implementations of asymmetric cryptosystems. In this paper, we propose a new way to perform base extensions using a hierarchical approach for computing the Chinese remainder theorem. For well chosen parameters, it significantly reduces the computational cost and still ensures a high level of internal parallelism. We illustrate the interest of the proposed approach on the cost of typical arithmetic primitives used in asymmetric cryptography. We also demonstrate improvements in FPGA implementations of base extensions on typical elliptic curve cryptography field sizes using high-level synthesis tools.

We propose an hybrid representation of large integers, or prime field elements, combining both positional and residue number systems (RNS). Our hybrid position-residues (HPR) number system mixes a high-radix positional representation and digits represented in RNS. RNS offers an important source of parallelism for addition, subtraction and multiplication operations. But, due to its non-positional property, it makes comparisons and modular reductions more costly than in a positional number system. HPR offers various trade-offs between internal parallelism and the efficiency of operations requiring position information. Our current application domain is asymmetric cryptography where HPR significantly reduces the cost of some modular operations compared to state-of-the-art RNS solutions.

A fast RNS modular inversion for finite fields arithmetic has been published at CHES 2013 conference. It is based on the binary version of the plus-minus Euclidean algorithm. In the context of elliptic curve cryptography (i.e., 160-550 bits finite fields), it significantly speeds-up modular inversions. In this paper, we propose an improved version based on both radix 2 and radix 3. This new algorithm leads to 30 percent speed-up for a maximal area overhead about 4 percent on Virtex 5 FPGAs.

The paper describes a new RNS (residue number system) modular multiplication algorithm, for finite field arithmetic over FP, based on a reduced number of moduli in base extensions with only 3n=2 moduli instead of 2n for standard ones. Our algorithm reduces both the number of elementary modular multiplications (EMMs) and the number of stored precomputations for large asymmetric cryptographic applications such as elliptic curve cryptography or Diffie-Hellman (DH) cryptosystem. It leads to faster operations and smaller circuits.