TY - GEN

T1 - On the Integer Polynomial Learning with Errors problem

AU - Devevey, Julien

AU - Sakzad, Amin

AU - Stehlé, Damien

AU - Steinfeld, Ron

N1 - Funding Information:
This work was supported in part by European Union Horizon 2020 Research and Innovation Program Grant 780701, Australian Research Council Discovery Project Grant DP180102199, and by BPI-France in the context of the national project RISQ (P141580).
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85106442799&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-75245-3_8

DO - 10.1007/978-3-030-75245-3_8

M3 - Conference Paper

AN - SCOPUS:85106442799

SN - 9783030752446

T3 - Lecture Notes in Computer Science

SP - 184

EP - 214

BT - Public-Key Cryptography – PKC 2021

A2 - Garay, Juan A.

PB - Springer

CY - Cham Switzerland

T2 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021

Y2 - 10 May 2021 through 13 May 2021

ER -