CryptoDB
On the Integer Polynomial Learning with Errors Problem
| Authors: | |
|---|---|
| Download: | |
| Presentation: | Slides |
| Abstract: | Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem (\textsf{PLWE}$^f$) in which the underlying \emph{polynomial} ring $\mZ_q[x]/f$ is replaced with the (related) modular \emph{integer} ring $\mZ_{f(q)}$; the corresponding problem is known as \emph{Integer Polynomial Learning with Errors} (\textsf{I-PLWE}$^f$). Cryptosystems based on \textsf{I-PLWE}$^f$ and its variants can exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the \textsf{ThreeBears} cryptosystem. Unfortunately, the average-case hardness of \textsf{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 \textsf{I-PLWE}$^f$, proving its computational equivalence with the search variant of its counterpart problem \textsf{PLWE}$^f$. Our reductions apply to a large class of defining polynomials~$f$. To obtain our results, we employ a careful adaptation of R\'{e}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 \textsf{ThreeBears}, enjoys one-way (OW-CPA) security provably based on the search variant of~\textsf{I-PLWE}$^f$. |
Video from PKC 2021
BibTeX
@article{pkc-2021-30983,
title={On the Integer Polynomial Learning with Errors Problem},
booktitle={Public-Key Cryptography - PKC 2021},
publisher={Springer},
doi={10.1007/978-3-030-75245-3_8},
author={Julien Devevey and Amin Sakzad and Damien Stehlé and Ron Steinfeld},
year=2021
}