Optimizing $c$-sum BKW and Faster Quantum Variant for LWE
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).
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}
}
EUVIMED