论文检索
期刊
全部知识仓储预印本开放期刊机构
高级检索

NTRU公钥密码的量子算法攻击研究OACSCDCSTPCD

Research on Quantum Algorithm Attack of NTRU Public Key Cryptography

中文摘要

NTRU作为近期NIST征集的后量子密码算法之一,分析其量子安全性具有重要意义.2015年,Fluhrer基于Grover搜索算法给出对NTRU公钥密码的量子攻击.在乘积多项式模式下,该攻击对小系数多项式私钥f1f2的搜索具有平方加速效果.然而,该攻击不仅需要一个强量子Oracle假设,且需要在Grover叠加查询过程中多次维护一个指数大的列表.针对此问题,本文发现Claw-Finding量子算法对NTRU密码具有同样的攻击效果.然而,原Claw-Finding算法中针对的函数输出值为单比特,不适用于分析NTRU.本文对原Claw-Finding算法进行修改,即当访问的两个函数输出为比特串时,算法依然可以找到Claw.基于此,本文给出在私钥搜索方面具有平方加速的量子攻击算法,避免了强量子Oracle的假设,且不需要维护指数大的列表.最后,本文给出所提量子攻击与Fluhrer攻击方法的比较.

董经;蔡彬彬;吴宇森;高飞;秦素娟;温巧燕

北京邮电大学网络与交换技术国家重点实验室,北京100876密码科学技术国家重点实验室,北京100878

信息技术与安全科学

NTRU;Claw-Finding算法;Grover算法

《密码学报》 2021 (006)

948-959 / 12

中央高校基本科研业务费专项资金(2019XD-A01);国家自然科学基金(61972048,61976024)

10.13868/j.cnki.jcr.000489

评论

下载量:0
点击量:3