On the Integer Polynomial Learning with Errors problem

Julien Devevey, Amin Sakzad, Damien Stehlé, Ron Steinfeld

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem (PLWE f ) in which the underlying polynomial ring Zq[ x] / f is replaced with the (related) modular integer ring Zf(q); the corresponding problem is known as Integer Polynomial Learning with Errors (I-PLWE f ). Cryptosystems based on I-PLWE f and its variants can exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the ThreeBears cryptosystem. Unfortunately, the average-case hardness of I-PLWE f and its relation to more established lattice problems have to date remained unclear. We describe the first polynomial-time average-case reductions for the search variant of I-PLWE 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 public-key cryptosystem over integer rings. Our cryptosystem, which resembles ThreeBears, enjoys one-way (OW-CPA) security provably based on the search variant of I-PLWE f.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2021
Subtitle of host publication24th IACR International Conference on Practice and Theory of Public Key Cryptography Virtual Event, May 10–13, 2021 Proceedings, Part I
EditorsJuan A. Garay
Place of PublicationCham Switzerland
PublisherSpringer
Pages184-214
Number of pages31
ISBN (Electronic)9783030752453
ISBN (Print)9783030752446
DOIs
Publication statusPublished - 2021
Event24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021 - Virtual, Online
Duration: 10 May 202113 May 2021

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12710
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021
CityVirtual, Online
Period10/05/2113/05/21

Cite this