Decomposed LWE is Equivalent to Succinct LWE

Damiano Abram; Gal Arnon; Valerio Cini; Paul Lou; Giulio Malavolta; Lawrence Roy

Paper 2026/1829

Decomposed LWE is Equivalent to Succinct LWE

Damiano Abram, University of Edinburgh

Gal Arnon, Bocconi University

Valerio Cini, Bocconi University

Paul Lou, Bocconi University

Giulio Malavolta, Bocconi University

Lawrence Roy, IBM Research Zürich

Abstract

We prove that the Succinct Learning with Errors assumption, introduced by Wee (CRYPTO '24), and the Decomposed Learning with Errors assumption, introduced by Abram, Malavolta, and Roy (CRYPTO '25), are equivalent under appropriate parameter settings. Abram, Malavolta, and Roy proved that Succinct LWE implies Decomposed LWE. We establish the converse implication, showing that Decomposed LWE implies Succinct LWE.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: decomposed LWE succinct LWE
Contact author(s): abram damiano @ protonmail com
galarnon42 @ gmail com
cini valerio @ gmail com
paul96lou @ gmail com
giulio malavolta @ hotmail it
ldr709 @ gmail com
History: 2026-08-30: approved; 2026-08-28: received; See all versions
Short URL: https://ia.cr/2026/1829
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1829,
      author = {Damiano Abram and Gal Arnon and Valerio Cini and Paul Lou and Giulio Malavolta and Lawrence Roy},
      title = {Decomposed {LWE} is Equivalent to Succinct {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1829},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1829}
}