Timing-optimized hardware implementation to accelerate polynomial multiplication in the NTRU algorithm

Eros Camacho-Ruiz; Santiago Sánchez-Solano; Piedad Brox; Macarena C. Martínez-Rodríguez

doi:10.1145/3445979

Timing-optimized hardware implementation to accelerate polynomial multiplication in the NTRU algorithm

Eros Camacho-Ruiz
, Santiago Sánchez-Solano
, Piedad Brox
, Macarena C. Martínez-Rodríguez

Tietotekniikka

Tutkimustuotos: Artikkeli › Tieteellinen › vertaisarvioitu

10 Sitaatiot (Scopus)

Abstrakti

Post-quantum cryptographic algorithms have emerged to secure communication channels between electronic devices faced with the advent of quantum computers. The performance of post-quantum cryptographic algorithms on embedded systems has to be evaluated to achieve a good trade-off between required resources (area) and timing. This work presents two optimized implementations to speed up the NTRUEncrypt algorithm on a system-on-chip. The strategy is based on accelerating the most time-consuming operation that is the truncated polynomial multiplication. Hardware dedicated modules for multiplication are designed by exploiting the presence of consecutive zeros in the coefficients of the blinding polynomial. The results are validated on a PYNQ-Z2 platform that includes a Zynq-7000 SoC from Xilinx and supports a Python-based programming environment. The optimized version that exploits the presence of double, triple, and quadruple consecutive zeros offers the best performance in timing, in addition to considerably reducing the possibility of an information leakage against an eventual attack on the device, making it practically negligible.

Alkuperäiskieli	Englanti
Artikkeli	35
Sivumäärä	16
Julkaisu	ACM Journal on Emerging Technologies in Computing Systems
Vuosikerta	17
Numero	3
DOI - pysyväislinkit	https://doi.org/10.1145/3445979
Tila	Julkaistu - heinäk. 2021
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Rahoitus

This work was supported in part by the TEC2017-83557-R project from the Spanish Government and AT17 5926 USE from Junta de Andalucía, both with support from the P.O. FEDER of European Union, and the LINKA20216 project from CSIC. Authors’ addresses: E. Camacho-Ruiz, S. Sánchez-Solano, and P. Brox, Microelectronics Institute of Sevilla, CSIC/ University of Seville, Américo Vespucio 28, 41219, Seville, Spain, 41092; emails: {camacho, santiago, brox}@imse-cnm. csic.es; M. C. Martínez-Rodríguez, Tampere University, Korkeakoulunkatu 1, 33720, Tampere, Finland; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2021 Association for Computing Machinery. 1550-4832/2021/05-ART35 $15.00 https://doi.org/10.1145/3445979

Julkaisufoorumi-taso

Jufo-taso 1

!!ASJC Scopus subject areas

Software
Hardware and Architecture
Electrical and Electronic Engineering

Pääsy asiakirjaan

10.1145/3445979

Siteeraa tätä

@article{50aada2f37c74a158b5c0275ebfd0fd7,

title = "Timing-optimized hardware implementation to accelerate polynomial multiplication in the NTRU algorithm",

abstract = "Post-quantum cryptographic algorithms have emerged to secure communication channels between electronic devices faced with the advent of quantum computers. The performance of post-quantum cryptographic algorithms on embedded systems has to be evaluated to achieve a good trade-off between required resources (area) and timing. This work presents two optimized implementations to speed up the NTRUEncrypt algorithm on a system-on-chip. The strategy is based on accelerating the most time-consuming operation that is the truncated polynomial multiplication. Hardware dedicated modules for multiplication are designed by exploiting the presence of consecutive zeros in the coefficients of the blinding polynomial. The results are validated on a PYNQ-Z2 platform that includes a Zynq-7000 SoC from Xilinx and supports a Python-based programming environment. The optimized version that exploits the presence of double, triple, and quadruple consecutive zeros offers the best performance in timing, in addition to considerably reducing the possibility of an information leakage against an eventual attack on the device, making it practically negligible. ",

keywords = "Embedded systems, NTRU, Post-quantum cryptography, SoC",

author = "Eros Camacho-Ruiz and Santiago S{\'a}nchez-Solano and Piedad Brox and Mart{\'i}nez-Rodr{\'i}guez, \{Macarena C.\}",

note = "Funding Information: This work was supported in part by the TEC2017-83557-R project from the Spanish Government and AT17 5926 USE from Junta de Andaluc{\'i}a, both with support from the P.O. FEDER of European Union, and the LINKA20216 project from CSIC. Authors{\textquoteright} addresses: E. Camacho-Ruiz, S. S{\'a}nchez-Solano, and P. Brox, Microelectronics Institute of Sevilla, CSIC/ University of Seville, Am{\'e}rico Vespucio 28, 41219, Seville, Spain, 41092; emails: \{camacho, santiago, brox\}@imse-cnm. csic.es; M. C. Mart{\'i}nez-Rodr{\'i}guez, Tampere University, Korkeakoulunkatu 1, 33720, Tampere, Finland; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. {\textcopyright} 2021 Association for Computing Machinery. 1550-4832/2021/05-ART35 \$15.00 https://doi.org/10.1145/3445979 Publisher Copyright: {\textcopyright} 2021 Association for Computing Machinery.",

year = "2021",

month = jul,

doi = "10.1145/3445979",

language = "English",

volume = "17",

journal = "ACM Journal on Emerging Technologies in Computing Systems",

issn = "1550-4832",

publisher = "ACM",

number = "3",

}

TY - JOUR

T1 - Timing-optimized hardware implementation to accelerate polynomial multiplication in the NTRU algorithm

AU - Camacho-Ruiz, Eros

AU - Sánchez-Solano, Santiago

AU - Brox, Piedad

AU - Martínez-Rodríguez, Macarena C.

N1 - Funding Information: This work was supported in part by the TEC2017-83557-R project from the Spanish Government and AT17 5926 USE from Junta de Andalucía, both with support from the P.O. FEDER of European Union, and the LINKA20216 project from CSIC. Authors’ addresses: E. Camacho-Ruiz, S. Sánchez-Solano, and P. Brox, Microelectronics Institute of Sevilla, CSIC/ University of Seville, Américo Vespucio 28, 41219, Seville, Spain, 41092; emails: {camacho, santiago, brox}@imse-cnm. csic.es; M. C. Martínez-Rodríguez, Tampere University, Korkeakoulunkatu 1, 33720, Tampere, Finland; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2021 Association for Computing Machinery. 1550-4832/2021/05-ART35 $15.00 https://doi.org/10.1145/3445979 Publisher Copyright: © 2021 Association for Computing Machinery.

PY - 2021/7

Y1 - 2021/7

N2 - Post-quantum cryptographic algorithms have emerged to secure communication channels between electronic devices faced with the advent of quantum computers. The performance of post-quantum cryptographic algorithms on embedded systems has to be evaluated to achieve a good trade-off between required resources (area) and timing. This work presents two optimized implementations to speed up the NTRUEncrypt algorithm on a system-on-chip. The strategy is based on accelerating the most time-consuming operation that is the truncated polynomial multiplication. Hardware dedicated modules for multiplication are designed by exploiting the presence of consecutive zeros in the coefficients of the blinding polynomial. The results are validated on a PYNQ-Z2 platform that includes a Zynq-7000 SoC from Xilinx and supports a Python-based programming environment. The optimized version that exploits the presence of double, triple, and quadruple consecutive zeros offers the best performance in timing, in addition to considerably reducing the possibility of an information leakage against an eventual attack on the device, making it practically negligible.

AB - Post-quantum cryptographic algorithms have emerged to secure communication channels between electronic devices faced with the advent of quantum computers. The performance of post-quantum cryptographic algorithms on embedded systems has to be evaluated to achieve a good trade-off between required resources (area) and timing. This work presents two optimized implementations to speed up the NTRUEncrypt algorithm on a system-on-chip. The strategy is based on accelerating the most time-consuming operation that is the truncated polynomial multiplication. Hardware dedicated modules for multiplication are designed by exploiting the presence of consecutive zeros in the coefficients of the blinding polynomial. The results are validated on a PYNQ-Z2 platform that includes a Zynq-7000 SoC from Xilinx and supports a Python-based programming environment. The optimized version that exploits the presence of double, triple, and quadruple consecutive zeros offers the best performance in timing, in addition to considerably reducing the possibility of an information leakage against an eventual attack on the device, making it practically negligible.

KW - Embedded systems

KW - NTRU

KW - Post-quantum cryptography

KW - SoC

U2 - 10.1145/3445979

DO - 10.1145/3445979

M3 - Article

AN - SCOPUS:85122616491

SN - 1550-4832

VL - 17

JO - ACM Journal on Emerging Technologies in Computing Systems

JF - ACM Journal on Emerging Technologies in Computing Systems

IS - 3

M1 - 35

ER -

Timing-optimized hardware implementation to accelerate polynomial multiplication in the NTRU algorithm

Abstrakti

Rahoitus

Julkaisufoorumi-taso

!!ASJC Scopus subject areas

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä