Skip to Main content Skip to Navigation
Conference papers

On Using RSA/ECC Coprocessor for Ideal Lattice-Based Key Exchange

Aurélien Greuet 1 Simon Montoya 1, 2 Guénaël Renault 3, 2
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Polynomial multiplication is one of the most costly operations of ideal lattice-based cryptosystems. In this work, we study its optimizations when one of the operands has coefficients close to 0. We focus on this structure since it is at the core of lattice-based Key Encapsulation Mechanisms submitted to the NIST call for post-quantum cryptography. In particular, we propose optimization of this operation for embedded devices by using a RSA/ECC coprocessor that provides efficient and secure large-integer arithmetic. In this context, we compare Kronecker Substitution, already studied in [AHH + 19], with two specific algorithms that we introduce: KSV, a variant of this substitution, and an adaptation of the schoolbook multiplication, denoted Shift&Add. All these algorithms rely on the transformation of polynomial multiplication to large-integer arithmetic. Then, thanks to these algorithms, existing secure coprocessors dedicated to large-integer can be re-purposed in order to speed-up post-quantum schemes. The efficiency of these algorithms depends on the component specifications and the cryptosystem parameters set. Thus, we establish a methodology to determine which algorithm to use, for a given component, by only implementing basic large-integer operations. Moreover, the three algorithms are assessed on a chip ensuring that the theoretical methodology matches with practical results.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03330066
Contributor : Guénaël Renault Connect in order to contact the contributor
Submitted on : Tuesday, August 31, 2021 - 2:55:32 PM
Last modification on : Wednesday, September 29, 2021 - 4:51:00 PM

File

HWPolMult.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03330066, version 1

Citation

Aurélien Greuet, Simon Montoya, Guénaël Renault. On Using RSA/ECC Coprocessor for Ideal Lattice-Based Key Exchange. COSADE 2021, Oct 2021, Lugano, Switzerland. ⟨hal-03330066⟩

Share

Metrics

Record views

35

Files downloads

227