Middle-product learning with errors

Miruna Roşca; Amin Sakzad; Damien Noel Stehle; Ron Steinfeld

doi:10.1007/978-3-319-63697-9_10

Middle-product learning with errors

Miruna Roşca, Amin Sakzad, Damien Noel Stehle, Ron Steinfeld

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

30 Citations (Scopus)

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	https://doi.org/10.1007/978-3-319-63697-9_10
Publication status	Published - 2017
Event	Advances in Cryptology 2017 - Santa Barbara, United States of America Duration: 20 Aug 2017 → 24 Aug 2017 Conference number: 37th https://link.springer.com/book/10.1007/978-3-319-63688-7 (Proceedings)

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/Territory	United States of America
City	Santa Barbara
Period	20/08/17 → 24/08/17
Internet address	https://link.springer.com/book/10.1007/978-3-319-63688-7 (Proceedings)

Keywords

LWE
PLWE
Public-key encryption

Access to Document

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

Cite this

@inproceedings{437f94a167e74ae09bb4fcaafaa6b951,

title = "Middle-product learning with errors",

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{\textquoteright}s which is exponential in n.",

keywords = "LWE, PLWE, Public-key encryption",

author = "Miruna Ro{\c s}ca and Amin Sakzad and Stehle, {Damien Noel} and Ron Steinfeld",

year = "2017",

doi = "10.1007/978-3-319-63697-9_10",

language = "English",

isbn = "9783319636962",

volume = "10403",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "283--297",

editor = "Katz, {Jonathan } and Shacham, {Hovav }",

booktitle = "Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings",

note = "Advances in Cryptology 2017, CRYPTO 2017 ; Conference date: 20-08-2017 Through 24-08-2017",

url = "https://link.springer.com/book/10.1007/978-3-319-63688-7",

}

Roşca, M, Sakzad, A, Stehle, DN & Steinfeld, R 2017, Middle-product learning with errors. in J Katz & H Shacham (eds), 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, California, 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 et al.
Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings. ed. / Jonathan Katz; Hovav Shacham. Vol. 10403 Cham Switzerland: Springer, 2017. p. 283-297 (Lecture Notes in Computer Science ; Vol. 10403 ).

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

N1 - Conference code: 37th

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

AN - SCOPUS:85028458328

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

T2 - Advances in Cryptology 2017

Y2 - 20 August 2017 through 24 August 2017

ER -

Middle-product learning with errors

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this