On the Ring-LWE and Polynomial-LWE Problems
| Autor: | Damien Stehlé, Miruna Rosca, Alexandre Wallet |
|---|---|
| Přispěvatelé: | École normale supérieure de Lyon (ENS de Lyon), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Bitdefender [Bucharest], École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Jazyk: | angličtina |
| Předmět: |
Polynomial
Ring (mathematics) Reduction (recursion theory) Polynomial ring 0102 computer and information sciences 02 engineering and technology Algebraic number field 01 natural sciences Ring of integers Combinatorics [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Monic polynomial Learning with errors ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Cryptology – EUROCRYPT 2018 EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications, Apr 2018, Tel Aviv, Israel Advances in Cryptology – EUROCRYPT 2018 Advances in Cryptology – EUROCRYPT 2018 ISBN: 9783319783802 EUROCRYPT (1) |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-319-78381-9_6 |
| Popis: | The Ring Learning With Errors problem (\(\mathsf {RLWE}\)) comes in various forms. Vanilla \(\mathsf {RLWE}\) is the decision dual-\(\mathsf {RLWE}\) variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual \(\mathcal {O}_K^{\vee }\) of the ring of integers \(\mathcal {O}_K\) of a specified number field K. In primal-\(\mathsf {RLWE}\), the secret instead belongs to \(\mathcal {O}_K\). Both decision dual-\(\mathsf {RLWE}\) and primal-\(\mathsf {RLWE}\) enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (\(\mathsf {PLWE}\)), which is not defined using a ring of integers \(\mathcal {O}_K\) of a number field K but a polynomial ring \(\mathbb {Z}[x]/f\) for a monic irreducible \(f \in \mathbb {Z}[x]\). We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is non-uniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal \(\mathsf {RLWE}\) and \(\mathsf {PLWE}\) that work for a family of polynomials f that is exponentially large as a function of \(\deg f\) (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for \(\mathsf {RLWE}\) for arbitrary number fields. The reductions incur error rate increases that depend on intrinsic quantities related to K and f. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|