量子科技中心_量科网

该研究团队针对从非均匀概率分布𝒟（如LPN、LWE或密码场景）中猜测加密密钥这一基础问题展开研究。经典最优算法会按密钥可能性降序枚举，而Montanaro（2011）提出的量子最优算法则是精妙的Grover搜索。 团队首次给出Montanaro算法的紧致分析，证明其运行时间为2^(H_(2/3)(𝒟)/2)，其中H_α(·)表示参数为α的Renyi熵。值得注意的是，这直接源于密码学界长期忽视的Arikan不等式（1996）——该信息论结果严格界定了经典密钥猜测的运行时间上限为2^(H_(1/2)(𝒟))。 由于对所有非均匀分布𝒟都满足H_(2/3)(𝒟) < H_(1/2)(𝒟)，该工作获得了超过二次方的量子加速比s>2。具体数值示例如：对Kyber使用的二项分布和典型密码分布，量子加速比s>2.04；对LPN中参数p=0.1的n重伯努利分布，s>2.27；而对Alekhnovich加密中p=Θ(n^(-1/2))的小误差LPN，甚至可实现无界量子加速s=Ω(n^(1/12))。 另一核心成果是首次系统分析多密钥场景下的猜测问题。当攻击从𝒟分布独立采样的多个密钥时，研究显示：对于乘积分布𝒟=χ^n，经典方案每密钥猜测成本为2^H(𝒟)，量子方案为2^(H(𝒟)/2)（H(χ)为香农熵）；而Arikan不等式表明单密钥场景下经典和量子成本分别为2^(H_(1/2)(𝒟))和2^(H_(2/3)(𝒟)/2)。由H(𝒟) < H_(2/3)(𝒟) < H_(1/2)(𝒟)可知，多密钥场景下每密钥猜测成本显著低于单密钥场景。