对1K-AES结构的量子滑动攻击
Abstract
<p indent="0mm">随着量子技术的不断发展, 对称密码算法的量子安全性受到人们的广泛关注. 聚焦1K-AES的安全性,分别利用量子滑动攻击和经典滑动攻击对1K-AES进行了安全性分析. 一方面, 对最后一轮包含列混淆的1K-AES, 在无需量子随机存储的条件下, 利用CNS算法能够在查询复杂度为<inline-formula id="INLINEA1"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup>2<italic>n</italic>/5</sup>)和经典存储规模为<inline-formula id="INLINEA2"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/5</sup>)的条件下将成功率由63%提升到74%, 其中<italic>n</italic>表示分组大小. 若使用量子随机存储, 利用通用量子claw查找算法能够在查询复杂度为<inline-formula id="INLINEA3"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/3</sup>)和量子存储规模为<inline-formula id="INLINEA4"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/3</sup>)的条件下将成功率提升到100%. 同时, 在经典选择明文攻击条件下, 本文将经典滑动攻击的成功率也提升到了100%. 另一方面, 对最后一轮无列混淆的1K-AES, 利用通用量子claw查找算法实施量子滑动攻击, 其查询和存储复杂度均为<inline-formula id="INLINEA5"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/3</sup>). 与经典滑动攻击相比, 该方法实现了亚指数加速; 与Grover搜索相比, 查询复杂度从<inline-formula id="INLINEA6"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/2</sup>)降低至<inline-formula id="INLINEA7"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="9.0pt"><mml:mrow><mml:mi mathsize="9.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2<sup><italic>n</italic>/3</sup>).</p>
