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

Computing Sciences

Research output: Contribution to journal › Article › Scientific › peer-review

10 Citations (Scopus)

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.

Original language	English
Article number	35
Number of pages	16
Journal	ACM Journal on Emerging Technologies in Computing Systems
Volume	17
Issue number	3
DOIs	https://doi.org/10.1145/3445979
Publication status	Published - Jul 2021
Publication type	A1 Journal article-refereed

Funding

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

Keywords

Embedded systems
NTRU
Post-quantum cryptography
SoC

Publication forum classification

Publication forum level 1

ASJC Scopus subject areas

Software
Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1145/3445979

Cite this

@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

Abstract

Funding

Keywords

Publication forum classification

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this