一种基于多尺度循环窗口的固定重量向量拒绝采样方法及装置

本发明涉及后量子密码，尤其涉及一种基于多尺度循环窗口的固定重量向量拒绝采样方法及装置，用于后量子密钥封装机制（key encapsulation mechanism，kem）的密钥生成、封装或加密过程。

背景技术：

1、基于编码的后量子密钥封装机制是一类重要的后量子密码方案[gaborit, p.,aguilar-melchor, c., aragon, n., bettaieb, s., bidoux, l., blazy, o.,deneuville, j.c., persichetti, e., zémor, g., bos, j., et al.: hamming quasi-cyclic (hqc). tech. rep., pqc-hqc team, https://pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf (aug. 2025).]。以汉明准循环（hamming quasi-cyclic，hqc）密钥封装方案为例，根据hqc官方文档，其密钥生成阶段需要采样固定重量秘密向量 、，封装或加密阶段需要采样固定重量随机向量 、 及错误向量 ；上述向量参与形成解密过程中的噪声项：

2、。

3、比特翻转密钥封装（bit flipping key encapsulation，bike）等准循环编码方案同样在密钥生成或封装阶段使用固定重量向量。

4、上述方案的解密失败率（decryption failure rate，dfr）不仅与噪声项或错误项的总汉明重量有关，还可能与支撑点在循环位置上的局部分布有关。传统固定重量采样主要保证输出向量具有指定汉明重量及预定采样分布，通常不对多个循环窗口长度上的局部支撑点数量同时设置限制。

5、已有研究表明，局部聚集结构可能改变译码器所面对的噪声分布。在hqc中，guo与johansson[guo, q., johansson, t.: a new decryption failure attack againsthqc. in: moriai, s., wang, h. (eds.) advances in cryptology - asiacrypt 2020.pp. 353-382. springer international publishing, cham (2020).]以及guan等[guan,c., et al.: compact hqc with new (un)balance. iacr cryptology eprint archive,report 2026/461 (2026).]研究了与解密失败相关的非均衡或局部聚集现象；在bike中，wang等人[wang, t., wang, a., wang, x.: exploring decryption failures of bike:new class of weak keys and key recovery attacks. in: pqcrypto 2023.]提出的聚集性质涉及支撑点聚集于连续循环位置的情形，matthews与mcmillon[matthews, g.l.,mcmillon, e.: a combinatorial approach to avoiding weak keys in the bikecryptosystem. designs, codes and cryptography 93, 3413–3436 (2025).]还研究了弱密钥结构。已有防御或检测思路可以针对一个预定窗口长度或一种预定结构设置判定条件，但单一尺度主要控制与该尺度相对应的局部聚集，对其他长度区间所诱导的容量上界可能较松。

6、hqc现有固定重量向量采样可采用sendrier改进的费舍尔—耶茨置换（fisher–yates shuffle）方法并配合拒绝采样，以保证固定重量、位置唯一性和预定分布，并已有常数时间硬件实现[schöffel, m., feldmann, j., wehn, n.: efficient hardwareimplementation of constant time sampling for hqc. arxiv:2309.16493 (2023).]。该类底层拒绝主要服务于固定重量采样本身，并不等同于本发明针对多个循环窗口尺度所施加的局部密度约束；同时，拒绝次数依赖秘密候选数据时还需要考虑计时侧信道风险。

7、因此，在将单一窗口尺度的局部密度约束作为已有技术或对照方案考虑时，仍至少存在如下技术问题：

8、（1）单一尺度只能直接限定一种窗口长度，其对其他窗口长度诱导的支撑点容量上界可能过松，容易遗漏尺度不同的聚集形态；

9、（2）若单纯收紧单一尺度阈值以覆盖更多窗口长度，可能造成拒绝率、期望采样次数和采样空间损失不必要地增加；

10、（3）缺少由多个不同尺度共同形成的跨窗口长度容量上界包络，以及用于判断各尺度是否非冗余的统一数学表达；

11、（4）缺少在目标窗口排除能力、拒绝概率、实现开销和采样空间损失之间进行联合配置的固定重量向量采样方法。

技术实现思路

1、本发明针对在基于编码的后量子密钥封装机制的固定重量向量采样过程中，如何在采样开销和采样空间损失可评估的条件下，同时限制多个不同空间范围上的局部支撑点聚集，减少单一窗口尺度对其他长度聚集形态的遗漏的问题，提出一种基于多尺度循环窗口的固定重量向量拒绝采样方法及装置。本发明的目的在于设置至少两个不同长度的循环窗口及其对应支撑点数量上界，使固定重量采样输出同时满足全部尺度约束，并由各尺度共同形成跨窗口长度的确定性容量上界包络，以排除超过所述容量上界包络的局部聚集窗口。本发明还旨在提供可复现的参数选择、拒绝概率评估、采样空间损失评估和常数时间实现方式，并使该方法能够在具有固定重量循环向量采样环节的不同基于编码的密码机制及不同采样位置中实施。

2、为了实现上述目的，本发明采用以下技术方案：

3、本发明一方面提出一种基于多尺度循环窗口的固定重量向量拒绝采样方法，包括：

4、设置至少两个不同的循环窗口长度，并为每个循环窗口长度分别配置一个对应的局部支撑点数量上限值；

5、生成一个具有指定长度和指定汉明重量的二进制向量，作为候选向量；

6、在所述候选向量的构造过程中，针对候选向量当前已确定的支撑集部分，分别在所述至少两个不同的循环窗口长度下，确定各循环窗口内实际包含或将要包含的支撑点数量是否超过该窗口长度对应的所述上限值；

7、当在任一循环窗口长度下，存在任一循环窗口内的支撑点数量超过该窗口长度对应的所述上限值，则拒绝当前候选向量，并重新生成新的候选向量；

8、当候选向量在所述至少两个不同的循环窗口长度下，均满足全部循环窗口内的支撑点数量不超过各自对应上限值的条件时，接受该候选向量，并将该候选向量输出给密码机制的密钥生成流程、封装流程或加密流程。

9、进一步地，对于任意给定的循环窗口长度  ，由全部尺度共同形成的容量上界包络按照以下方式确定：

10、分别计算每个尺度  在所述窗口长度  下所诱导的局部容量上界，所述局部容量上界等于由若干个完整的长度为  的子窗口所容纳的最大支撑点数与剩余不足一个完整子窗口所容纳的最大支撑点数之和；再取全部尺度下局部容量上界的最小值，并将该最小值限制为不超过所述指定汉明重量，以得到容量上界包络；其中 ，。

11、进一步地，各所述尺度按照非冗余方式配置：

12、至少存在第一窗口长度和第二窗口长度，以及第一尺度和第二尺度；

13、删除第一尺度后，在至少第一窗口长度上，由全部剩余尺度形成的容量上界包络的取值严格大于删除前全部尺度形成的容量上界包络的取值；

14、并且，删除第二尺度后，在至少第二窗口长度上，由全部剩余尺度形成的容量上界包络的取值严格大于删除前全部尺度形成的容量上界包络的取值。

15、进一步地，所述候选向量通过在全部具有所述指定汉明重量的向量空间中进行均匀随机采样而生成；经过一次或多次拒绝后首次合格的候选向量，在最终输出的接受集合上保持均匀分布。

16、进一步地，所述方法施加于密码机制的密钥生成阶段中的固定重量秘密向量，和/或施加于密码机制的封装阶段或加密阶段中的固定重量随机向量；密码机制中的错误向量使用独立配置的多尺度约束，或者不对所述错误向量施加多尺度约束。

17、进一步地，当所述候选向量涉及秘密数据时，完整遍历全部循环窗口长度和全部循环窗口位置，不因发现任一超限情况而提前终止检测，并将各检测结果的比较标志以掩码运算方式累积生成总拒绝标志。

18、进一步地，采用固定批次策略实现常数时间拒绝采样：

19、预先生成固定数量的候选向量作为一个批次；

20、对所述批次中的全部候选向量依次统计各循环窗口内实际包含的支撑点数量；

21、以掩码方式从所述批次中选择首个满足全部尺度约束的候选向量作为输出；

22、若所述批次中不存在满足全部尺度约束的候选向量，则返回预定义的采样失败状态，或者继续生成并检测下一个固定数量的批次。

23、进一步地，还包括参数配置步骤：

24、根据安全分析确定至少一个目标窗口长度及在该目标窗口长度下待排除的局部聚集形态所需的最低支撑点数；

25、选择所述循环窗口长度及对应的局部支撑点数量上限值，使得容量上界包络在所述目标窗口长度上的取值小于所述局部聚集形态所需最低支撑点数，以确定性排除该目标窗口形态；

26、估计各候选约束下的联合接受概率，并删除对容量上界包络和拒绝集合均无实质贡献的冗余尺度。

27、本发明还提出一种基于多尺度循环窗口的固定重量向量拒绝采样装置，包括：

28、候选向量生成单元，用于生成一个具有指定长度和指定汉明重量的二进制向量，作为候选向量；

29、多尺度配置单元，设置至少两个不同的循环窗口长度，并为每个循环窗口长度分别配置一个对应的局部支撑点数量上限值；

30、多尺度检测单元，用于在所述候选向量的构造过程中，针对候选向量当前已确定的支撑集部分，分别在所述至少两个不同的循环窗口长度下，确定各循环窗口内实际包含或将要包含的支撑点数量是否超过该窗口长度对应的所述上限值；

31、拒绝控制单元，用于当在任一循环窗口长度下，存在任一循环窗口内的支撑点数量超过该窗口长度对应的所述上限值，则拒绝当前候选向量，并重新生成新的候选向量；

32、接受输出单元，用于当候选向量在所述至少两个不同的循环窗口长度下，均满足全部循环窗口内的支撑点数量不超过各自对应上限值的条件时，接受该候选向量，并将该候选向量输出给密码机制的密钥生成流程、封装流程或加密流程。

33、本发明还提出一种密码设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述任一项所述的一种基于多尺度循环窗口的固定重量向量拒绝采样方法。

34、与仅保证总汉明重量的固定重量采样方法或仅采用单一循环窗口长度约束的采样方法相比，本发明至少具有如下有益效果：

35、（1）本发明通过设置至少两个不同的循环窗口长度及对应的支撑点数量上限值，能够在采样阶段确定性排除在任一目标窗口长度内包含超过该尺度容量上界的支撑点数量的聚集形态；在所定义的循环窗口局部密度风险模型下，能够有效减少敌手可利用的弱样本集合。

36、（2）多个不同尺度共同形成容量上界包络，即各单尺度容量上界的下包络，不同尺度可以分别在不同窗口长度范围上形成更紧的约束；在各尺度按照非冗余方式配置时，多尺度约束能够同时处理单一尺度难以兼顾的短范围高密度聚集和较长范围累计聚集。

37、（3）窗口长度、支撑点数量上限值及尺度数量可根据安全性分析和实现需求联合配置，并可通过联合接受概率控制拒绝后的期望采样次数，从而在窗口排除能力和实现开销之间进行量化权衡。

38、（4）当底层候选向量相互独立并在全部具有指定汉明重量的向量空间上均匀采样时，重复拒绝至首次合格所得输出在接受集合上保持均匀分布，便于对采样空间损失进行量化评估，为安全性分析提供可预期的分布基础。