### 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 ). Springer. https://doi.org/10.1007/978-3-319-63697-9_10