Fast and Error-Free Negacyclic Integer Convolution using Extended Fourier Transform

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00350544" target="_blank" >RIV/68407700:21230/21:00350544 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-78086-9_22" target="_blank" >https://doi.org/10.1007/978-3-030-78086-9_22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-78086-9_22" target="_blank" >10.1007/978-3-030-78086-9_22</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Fast and Error-Free Negacyclic Integer Convolution using Extended Fourier Transform

Popis výsledku v původním jazyce

With the rise of lattice cryptography,(negacyclic) convolution has received increased attention. Eg, the NTRU scheme internally employs cyclic polynomial multiplication, which is equivalent to the standard convolution, on the other hand, many Ring-LWE-based cryptosystems perform negacyclic polynomial multiplication. A method by Crandall implements an efficient negacyclic convolution over a finite field of prime order using an extended Discrete Galois Transform (DGT)–a finite field analogy to Discrete Fourier Transform (DFT). Compared to DGT, the classical DFT runs faster by an order of magnitude, however, it suffers from inevitable rounding errors due to finite floating-point number representation. In a recent Fully Homomorphic Encryption (FHE) scheme by Chillotti et al. named TFHE, small errors are acceptable (although not welcome), therefore we decided to investigate the application of DFT for negacyclic convolution. The primary goal of this paper is to suggest a method for fast negacyclic convolution over integer coefficients using an extended DFT. The key contribution is a thorough analysis of error propagation, as a result of which we derive parameter bounds that can guarantee even error-free results. We also suggest a setup that admits rare errors, which allows to increase the degree of the polynomials and/or their maximum norm at a fixed floating-point precision. Finally, we run benchmarks with parameters derived from a practical TFHE setup. We achieve around 24x better times than the generic NTL library (comparable to Crandall’s method) and around 4x better times than a naıve approach with DFT, with no errors.

Název v anglickém jazyce

Fast and Error-Free Negacyclic Integer Convolution using Extended Fourier Transform

Popis výsledku anglicky

With the rise of lattice cryptography,(negacyclic) convolution has received increased attention. Eg, the NTRU scheme internally employs cyclic polynomial multiplication, which is equivalent to the standard convolution, on the other hand, many Ring-LWE-based cryptosystems perform negacyclic polynomial multiplication. A method by Crandall implements an efficient negacyclic convolution over a finite field of prime order using an extended Discrete Galois Transform (DGT)–a finite field analogy to Discrete Fourier Transform (DFT). Compared to DGT, the classical DFT runs faster by an order of magnitude, however, it suffers from inevitable rounding errors due to finite floating-point number representation. In a recent Fully Homomorphic Encryption (FHE) scheme by Chillotti et al. named TFHE, small errors are acceptable (although not welcome), therefore we decided to investigate the application of DFT for negacyclic convolution. The primary goal of this paper is to suggest a method for fast negacyclic convolution over integer coefficients using an extended DFT. The key contribution is a thorough analysis of error propagation, as a result of which we derive parameter bounds that can guarantee even error-free results. We also suggest a setup that admits rare errors, which allows to increase the degree of the polynomials and/or their maximum norm at a fixed floating-point precision. Finally, we run benchmarks with parameters derived from a practical TFHE setup. We achieve around 24x better times than the generic NTL library (comparable to Crandall’s method) and around 4x better times than a naıve approach with DFT, with no errors.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Cyber Security Cryptography and Machine Learning

ISBN

978-3-030-78085-2

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

19

Strana od-do

282-300

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Basel

Místo konání akce

Be'er Sheva

Datum konání akce

8. 7. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—