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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2021

Confidentiality

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

Article name in the collection

Cyber Security Cryptography and Machine Learning

ISBN

978-3-030-78085-2

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

19

Pages from-to

282-300

Publisher name

Springer Nature Switzerland AG

Place of publication

Basel

Event location

Be'er Sheva

Event date

Jul 8, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—