EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Optimizing $c$-sum BKW and Faster Quantum Variant for LWE

Jinzheng Cao, Qingfeng Cheng, Jian Weng

IACR Communications in Cryptology · 07.10.2024

DOI: 10.62056/a6qj5w7sf ↗

Kurz gefasst

Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 07.10.2024. Verfasst von Jinzheng Cao und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Learning with Errors (LWE) problem has become one of the most prominent candidates of post-quantum cryptography, offering promising potential to meet the challenge of quantum computing. From a theoretical perspective, optimizing algorithms to solve LWE is a vital task for the analysis of this cryptographic primitive. In this paper, we propose a fine-grained time/memory trade-off method to analyze c-sum BKW variants for LWE in both classical and quantum models, then offer new complexity bounds for multiple BKW variants determined by modulus q, dimension k, error rate alpha, and stripe size b. Through our analysis, optimal parameters can be efficiently found for different settings, and the minimized complexities are lower than existing results. Furthermore, we enhance the performance of c-sum BKW in the quantum computing model by adopting the quantum Meet-in-the-Middle technique as c-sum solver instead of the naive c-sum technique. Our complexity trade-off formula also applies to the quantum version of BKW, and optimizes the theoretical quantum time and memory costs, which are exponentially lower than existing quantum c-sum BKW variants.

Zitieren

APA

Cao, J., Cheng, Q., & Weng, J. (2024). Optimizing $c$-sum BKW and Faster Quantum Variant for LWE. IACR Communications in Cryptology. https://doi.org/10.62056/a6qj5w7sf

Vancouver

Cao J, Cheng Q, Weng J. Optimizing $c$-sum BKW and Faster Quantum Variant for LWE. IACR Communications in Cryptology. 2024. doi:10.62056/a6qj5w7sf

BibTeX
@article{Cao2024,
  author = {Cao, Jinzheng and Cheng, Qingfeng and Weng, Jian},
  title = {Optimizing $c$-sum BKW and Faster Quantum Variant for LWE},
  journal = {IACR Communications in Cryptology},
  year = {2024},
  doi = {10.62056/a6qj5w7sf}
}
Kostenlos starten →