Abstract
Several recent proposals of efficient publickey encryption are based on variants of the polynomial learning with errors problem (PLWE ^{f} ) in which the underlying polynomial ring Z_{q}[ x] / f is replaced with the (related) modular integer ring Z_{f}_{(}_{q}_{)}; the corresponding problem is known as Integer Polynomial Learning with Errors (IPLWE ^{f} ). Cryptosystems based on IPLWE ^{f} and its variants can exploit optimised biginteger arithmetic to achieve good practical performance, as exhibited by the ThreeBears cryptosystem. Unfortunately, the averagecase hardness of IPLWE ^{f} and its relation to more established lattice problems have to date remained unclear. We describe the first polynomialtime averagecase reductions for the search variant of IPLWE ^{f}, proving its computational equivalence with the search variant of its counterpart problem PLWE ^{f}. Our reductions apply to a large class of defining polynomials f. To obtain our results, we employ a careful adaptation of Rényi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions. As an application, we present a deterministic publickey cryptosystem over integer rings. Our cryptosystem, which resembles ThreeBears, enjoys oneway (OWCPA) security provably based on the search variant of IPLWE ^{f}.
Original language  English 

Title of host publication  PublicKey Cryptography – PKC 2021 
Subtitle of host publication  24th IACR International Conference on Practice and Theory of Public Key Cryptography Virtual Event, May 10–13, 2021 Proceedings, Part I 
Editors  Juan A. Garay 
Place of Publication  Cham Switzerland 
Publisher  Springer 
Pages  184214 
Number of pages  31 
ISBN (Electronic)  9783030752453 
ISBN (Print)  9783030752446 
DOIs  
Publication status  Published  2021 
Event  International Conference/Workshop on Practice and Theory in Public Key Cryptography 2021  Online, United States of America Duration: 10 May 2021 → 13 May 2021 Conference number: 24th https://link.springer.com/book/10.1007/9783030752453 (Proceedings) https://pkc.iacr.org/2021/ (Website) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  12710 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Conference/Workshop on Practice and Theory in Public Key Cryptography 2021 

Abbreviated title  PKC 2021 
Country/Territory  United States of America 
Period  10/05/21 → 13/05/21 
Internet address 
