Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography
The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland, Castryck a...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-04-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/8/858 |
| _version_ | 1797537720491311104 |
|---|---|
| author | Alberto Pedrouzo-Ulloa Juan Ramón Troncoso-Pastoriza Nicolas Gama Mariya Georgieva Fernando Pérez-González |
| author_facet | Alberto Pedrouzo-Ulloa Juan Ramón Troncoso-Pastoriza Nicolas Gama Mariya Georgieva Fernando Pérez-González |
| author_sort | Alberto Pedrouzo-Ulloa |
| collection | DOAJ |
| description | The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland, Castryck and Vercauteren has some important consequences on the security of the multivariate RLWE problem with “non-coprime” cyclotomics; this attack transforms instances of <i>m</i>-RLWE with power-of-two cyclotomic polynomials of degree <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><msub><mo>∏</mo><mi>i</mi></msub><msub><mi>n</mi><mi>i</mi></msub></mrow></semantics></math></inline-formula> into a set of RLWE samples with dimension <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo movablelimits="true" form="prefix">max</mo><mi>i</mi></msub><mrow><mo>{</mo><msub><mi>n</mi><mi>i</mi></msub><mo>}</mo></mrow></mrow></semantics></math></inline-formula>. This is especially devastating for low-degree cyclotomics (e.g., <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>Φ</mo><mn>4</mn></msub><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><mn>1</mn><mo>+</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></semantics></math></inline-formula>). In this work, we revisit the security of multivariate RLWE and propose new alternative instantiations of the problem that avoid the attack while still preserving the advantages of the multivariate structure, especially when using low-degree polynomials. Additionally, we show how to parameterize these instances in a secure and practical way, therefore enabling constructions and strategies based on <i>m</i>-RLWE that bring notable space and time efficiency improvements over current RLWE-based constructions. |
| first_indexed | 2024-03-10T12:20:13Z |
| format | Article |
| id | doaj.art-5e78e1230ba14bdb9cbb29c86ab76162 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T12:20:13Z |
| publishDate | 2021-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-5e78e1230ba14bdb9cbb29c86ab761622023-11-21T15:33:11ZengMDPI AGMathematics2227-73902021-04-019885810.3390/math9080858Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based CryptographyAlberto Pedrouzo-Ulloa0Juan Ramón Troncoso-Pastoriza1Nicolas Gama2Mariya Georgieva3Fernando Pérez-González4AtlanTTic Research Center, Universidade de Vigo, 36310 Vigo, SpainLaboratory for Data Security, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, SwitzerlandInpher, CH-1015 Lausanne, SwitzerlandInpher, CH-1015 Lausanne, SwitzerlandAtlanTTic Research Center, Universidade de Vigo, 36310 Vigo, SpainThe “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland, Castryck and Vercauteren has some important consequences on the security of the multivariate RLWE problem with “non-coprime” cyclotomics; this attack transforms instances of <i>m</i>-RLWE with power-of-two cyclotomic polynomials of degree <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><msub><mo>∏</mo><mi>i</mi></msub><msub><mi>n</mi><mi>i</mi></msub></mrow></semantics></math></inline-formula> into a set of RLWE samples with dimension <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo movablelimits="true" form="prefix">max</mo><mi>i</mi></msub><mrow><mo>{</mo><msub><mi>n</mi><mi>i</mi></msub><mo>}</mo></mrow></mrow></semantics></math></inline-formula>. This is especially devastating for low-degree cyclotomics (e.g., <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mo>Φ</mo><mn>4</mn></msub><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><mn>1</mn><mo>+</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></semantics></math></inline-formula>). In this work, we revisit the security of multivariate RLWE and propose new alternative instantiations of the problem that avoid the attack while still preserving the advantages of the multivariate structure, especially when using low-degree polynomials. Additionally, we show how to parameterize these instances in a secure and practical way, therefore enabling constructions and strategies based on <i>m</i>-RLWE that bring notable space and time efficiency improvements over current RLWE-based constructions.https://www.mdpi.com/2227-7390/9/8/858tensor of number fieldslattice cryptographyhomomorphic encryptionring learning with errorsmultivariate rings |
| spellingShingle | Alberto Pedrouzo-Ulloa Juan Ramón Troncoso-Pastoriza Nicolas Gama Mariya Georgieva Fernando Pérez-González Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography Mathematics tensor of number fields lattice cryptography homomorphic encryption ring learning with errors multivariate rings |
| title | Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography |
| title_full | Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography |
| title_fullStr | Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography |
| title_full_unstemmed | Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography |
| title_short | Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography |
| title_sort | revisiting multivariate ring learning with errors and its applications on lattice based cryptography |
| topic | tensor of number fields lattice cryptography homomorphic encryption ring learning with errors multivariate rings |
| url | https://www.mdpi.com/2227-7390/9/8/858 |
| work_keys_str_mv | AT albertopedrouzoulloa revisitingmultivariateringlearningwitherrorsanditsapplicationsonlatticebasedcryptography AT juanramontroncosopastoriza revisitingmultivariateringlearningwitherrorsanditsapplicationsonlatticebasedcryptography AT nicolasgama revisitingmultivariateringlearningwitherrorsanditsapplicationsonlatticebasedcryptography AT mariyageorgieva revisitingmultivariateringlearningwitherrorsanditsapplicationsonlatticebasedcryptography AT fernandoperezgonzalez revisitingmultivariateringlearningwitherrorsanditsapplicationsonlatticebasedcryptography |