International Association for Cryptologic Research

International Association
for Cryptologic Research


Julien Devevey


On the Integer Polynomial Learning with Errors Problem 📺
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$.
Non-Interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings 📺
We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.