Details

Autor(en) / Beteiligte

• Guo, Qian
• Johansson, Thomas
• Mårtensson, Erik
• Stankovski, Paul

Titel

Coded-BKW with Sieving

Ist Teil von

• 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2017,Hong Kong, China,2017-12-03 - 2017-12-07, 2017, Vol.10624, p.323-346

Ort / Verlag

Cham: Springer International Publishing

Erscheinungsjahr

2017

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the BKW algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For Regev parameters q=n2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q=n^2$$\end{document} and noise level σ=n1.5/(2πlog22n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma = n^{1.5}/(\sqrt{2\pi }\log _{2}^{2}n)$$\end{document}, the asymptotic complexity is 20.895n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{0.895n} $$\end{document} in the standard setting, improving on the previously best known complexity of roughly 20.930n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{0.930n} $$\end{document}. Also for concrete parameter instances, improved performance is indicated.