### Abstract

We introduce a new variant MP LWE of the Learning With Errors problem LWE making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial- LWE problem PLWE parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.

Original language | English |
---|---|

Title of host publication | Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings |

Editors | Jonathan Katz, Hovav Shacham |

Place of Publication | Cham Switzerland |

Publisher | Springer |

Pages | 283-297 |

Number of pages | 15 |

Volume | 10403 |

ISBN (Electronic) | 9783319636979 |

ISBN (Print) | 9783319636962 |

DOIs | |

Publication status | Published - 2017 |

Event | Advances in Cryptology 2017 - Santa Barbara, United States of America Duration: 20 Aug 2017 → 24 Aug 2017 Conference number: 37 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer International (AG) |

Volume | 10403 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Advances in Cryptology 2017 |
---|---|

Abbreviated title | CRYPTO 2017 |

Country | United States of America |

City | Santa Barbara |

Period | 20/08/17 → 24/08/17 |

### Keywords

- LWE
- PLWE
- Public-key encryption

### Cite this

*Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings*(Vol. 10403, pp. 283-297). (Lecture Notes in Computer Science ; Vol. 10403 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-63697-9_10

}

*Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings.*vol. 10403, Lecture Notes in Computer Science , vol. 10403 , Springer, Cham Switzerland, pp. 283-297, Advances in Cryptology 2017, Santa Barbara, United States of America, 20/08/17. https://doi.org/10.1007/978-3-319-63697-9_10

**Middle-product learning with errors.** / Roşca, Miruna; Sakzad, Amin; Stehle, Damien Noel; Steinfeld, Ron.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Middle-product learning with errors

AU - Roşca, Miruna

AU - Sakzad, Amin

AU - Stehle, Damien Noel

AU - Steinfeld, Ron

PY - 2017

Y1 - 2017

N2 - We introduce a new variant MP LWE of the Learning With Errors problem LWE making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial- LWE problem PLWE parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.

AB - We introduce a new variant MP LWE of the Learning With Errors problem LWE making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial- LWE problem PLWE parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.

KW - LWE

KW - PLWE

KW - Public-key encryption

UR - http://www.scopus.com/inward/record.url?scp=85028458328&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-63697-9_10

DO - 10.1007/978-3-319-63697-9_10

M3 - Conference Paper

SN - 9783319636962

VL - 10403

T3 - Lecture Notes in Computer Science

SP - 283

EP - 297

BT - Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings

A2 - Katz, Jonathan

A2 - Shacham, Hovav

PB - Springer

CY - Cham Switzerland

ER -