Parallel algorithms for elliptic curve cryptography scalar multiplication using the binary and naf methods

• Ano de defesa: 2021
• Autor(a) principal: Reis, Paulo Ricardo Borré
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Laboratório Nacional de Computação Científica; Coordenação de Pós-Graduação e Aperfeiçoamento (COPGA); Brasil; LNCC; Programa de Pós-Graduação em Modelagem Computacional
• Palavras-chave em Português: Criptografia clássica; Criptografia pós-quântica; Criptografia de curvas elípticas; Multiplicação por escalar; Algoritmos paralelos; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://tede.lncc.br/handle/tede/336

Part of the cryptographic protocols used in modern communications is based on Elliptic Curves, such as Elliptic Curve Based Diffie–Hellman (ECDH) and Elliptic Curve Digital Signature Algorithm (ECDSA). Also, some post-quantum algorithms are based on Elliptic Curves, such as Supersingular Isogeny Diffie–Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE), which was a strong competitor in National Institute of Stan- dards and Technology (NIST) post-quantum cryptography standardization process. Such protocols depend on the scalar multiplication, a computational expensive operation inside Elliptic Curve Cryptography (ECC). This work presents parallelization techniques used to speed up this operation. It extends parallel methods used for modular exponentiation to scalar multiplication, being able to determine the optimal number of processors that yields the greatest speedup. This is accomplished by using a load balancing technique, where the processing load is distributed evenly among the processors. A parallelization technique using Width-w Non-adjacent Form (w-NAF) is also presented. Experiments are done to evaluate the proposed algorithms, being held for.