Title: Middle-Product Learning With Errors: 10 years later
Abstract: Structured lattice problems such as Ring-LWE and Module-LWE are behind the most efficient post-quantum cryptosystems in use today. However, each instance relies on one fixed algebraic object, usually a single cyclotomic number field. If that ring turns out to have a hidden weakness, every scheme built on it is at risk. In 2017, Middle-Product Learning With Errors (MP-LWE) was introduced to avoid committing to any one ring. MP-LWE replaces multiplication in a fixed ring by the middle product of polynomials: multiply, then keep only the middle coefficients. The resulting problem is defined independently of any defining polynomial. It is provably at least as hard as Polynomial-LWE for an exponentially large family of polynomials, so security holds as long as just one member of that family stays hard. This talk starts from first principles. We show how the middle product leads directly to a simple public-key encryption scheme with quasi-linear key sizes and run-times, and to MPSign, a Fiat–Shamir signature that rests on a small-secret variant of MP-LWE. Both constructions keep the efficiency of ring-based schemes without depending on a single ring. We then survey a decade of progress, including: Middle-Product Learning with Rounding; the Titanium NIST submission; skew-polynomial generalisations linked to cyclic division algebras; the Peikert–Pepin framework that unifies all algebraically structured LWE variants. Finally, we present the most recent hardness results refining the original reduction that show a new unified reduction supersedes all previous ones. The talk ends with open problems at the intersection of information theory, algebra and post-quantum security.
Antonia Tulino
Univerisità Federico II, Napoli, Italy - New York University, NY USA, - Bell Labs, NJ, USA
Title: To be Announced
Rashmi Vinayak
Carnegie Mellon University, USA
Title: To be Announced
Michèle Wigger
Université Paris-Saclay, France