.png){kind=icon}
返回
An improved BKW algorithm on the learning with rounding problem
.png){kind=icon}
OA
AI
DOI：10.1186/s42400-024-00339-0.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Blum-Kalai-Wasserman (BKW)算法是一种重要的组合算法，用于解决学习误差（LWE）和学习舍入（LWR）问题。2015年，Duc等人（发表于Oswald和Fischlin主编的EUROCRYPT 2015，Springer，柏林，2015）提出了首个直接应用于LWR的BKW算法，该算法由约减阶段和求解阶段组成。本文提出了一种改进的LWR求解BKW算法。对于约减阶段，我们设计了一种具有宽松碰撞条件的全新编码方法，并引入了后处理阶段；对于求解阶段，我们切换为更高效的带剪枝的快速傅里叶变换（FFT）区分器。与以往的LWR求解BKW算法相比，我们的新BKW算法在所考虑的实例中实现了4.0–48.5比特的时间复杂度改进。此外，通过在约减阶段引入一种新颖的启发式方法，我们的算法进一步将样本复杂度提高了3.7–48.7比特。
Keyword:
Post-quantum cryptography
Learning with rounding problem
Learning with errors problem
The BKW algorithm
期刊
C
IF:
3.7
论文数:
606
被引数:
1.0K
机构
引用论文
.png){kind=icon}
查看更多内容