TY - GEN
T1 - Middle-product learning with rounding problem and its applications
AU - Bai, Shi
AU - Boudgoust, Katharina
AU - Das, Dipayan
AU - Roux-Langlois, Adeline
AU - Wen, Weiqiang
AU - Zhang, Zhenfei
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2019.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - At CRYPTO 2017, Roşca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (P-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning With Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called Middle-Product Computational Learning With Rounding, an adaption of the computational LWR problem over rings, introduced by Chen et al. at ASIACRYPT 2018. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.
AB - At CRYPTO 2017, Roşca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (P-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning With Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called Middle-Product Computational Learning With Rounding, an adaption of the computational LWR problem over rings, introduced by Chen et al. at ASIACRYPT 2018. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.
KW - LWE
KW - LWR
KW - Middle-Product
KW - Public key encryption
UR - https://www.scopus.com/pages/publications/85076683752
U2 - 10.1007/978-3-030-34578-5_3
DO - 10.1007/978-3-030-34578-5_3
M3 - Conference contribution
AN - SCOPUS:85076683752
SN - 9783030345778
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 55
EP - 81
BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings
A2 - Galbraith, Steven D.
A2 - Moriai, Shiho
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Y2 - 8 December 2019 through 12 December 2019
ER -