Breaking randomized mixed-radix scalar multiplication algorithms

Jérémie Detrey 1 Laurent Imbert 2
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we present a novel, powerful attack on a recently introduced randomized scalar multiplication algorithm based on covering systems of congruences. Our attack can recover the whole key with very few traces, even when those only provide partial information on the sequence of operations. In an attempt to solve the issues raised by the broken algorithm, we designed a constant-time version with no secret dependent branching nor memory access based on the so-called mixed-radix number system. We eventually present our conclusions regarding the use of mixed-radix representations as a randomization setting.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02309203
Contributor : Laurent Imbert <>
Submitted on : Wednesday, October 9, 2019 - 9:46:57 AM
Last modification on : Friday, October 18, 2019 - 10:44:29 AM

File

attack-csc.pdf
Files produced by the author(s)

Identifiers

Collections

LIRMM | ECO | UNIV-LORRAINE | LORIA | LORIA-ALGO | MIPS | INRIA | UNIV-MONTPELLIER

Citation

Jérémie Detrey, Laurent Imbert. Breaking randomized mixed-radix scalar multiplication algorithms. LATINCRYPT 2019 - 6th International Conference on Cryptology and Information Security in Latin America, Oct 2019, Santiago de Chile, Chile. pp.24-39, ⟨10.1007/978-3-030-30530-7_2⟩. ⟨lirmm-02309203⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

42

Files downloads

23

Contact

CCSD