一种面积高效的双态可配置NTT硬件加速器

矩阵向量乘法是基于格的后量子密码(Post-Quantum Cryptography,PQC)方案的主要计算瓶颈。利用数论变换(Number Theoretic Transform,NTT)能将矩阵向量乘法的计算复杂度从O(N^(2))降到O(Nlog_(2)N),从而可以进一步提高后量子密码方案的计算速度。文章基于现场可编程门阵列(Field Programmable Gate Array,FPGA)提出了一种面积高效的双态可配置NTT硬件加速器,能高效地执行Kyber和Dilithium算法中的NTT运算。文章所提方案使用的模乘器通过查找表(Look Up Table,LUT)技术压缩数据位宽降低取模成本后,利用KRED算法对结果约简。此外,结合优化后的无冲突NTT数据流,文章所提出的双态可配置NTT加速器可以高效完成计算。文章所提出的NTT硬件加速器在Xilinx Artix-7平台上进行了验证。相较于参考文献方案,文章所提出的双态可配置NTT硬件加速器在保持对Kyber和Dilithium算法通用性的同时,在计算性能和硬件开销等方面表现更好。

NTT架构研究及其FPGA硬件优化实现

量子计算机的发展对现有公钥体系的影响是实质性的.在众多后量子密码流派中,格基密码方案因其安全性、高效性等优良特点而成为了主流技术路线.密码算法在各实现平台的运行效率是后量子算法评估进程中的重要指标.FPGA(Field Programmable Gate Array)具有并行性架构,是密码体系实际部署时的重要硬件平台.近年来,后量子算法的硬件优化实现研究吸引了越来越多的关注.针对格基密码算法中计算复杂度最高、耗时最长的操作——环上多项式乘法计算,本文对主流的加速技术——数论变换技术(Number-Theoretic Transform,NTT)进行了系统研究,根据参数不同将其分为标准NTT(Standard-NTT,SNTT)、删减NTT(Truncated-NTT,TNTT)、混合NTT(Hybrid-NTT,HNTT).为了提高适用性,设计了一种统一型、可常数时间执行、支持多参数的硬件电路,支持三种NTT架构,结合Karatsuba技巧,将对应系数相乘中乘法次数减少20%.针对NTT的核心操作——蝴蝶变换,设计了一种紧凑型、低时延的电路结构,可实现正向NTT、对应系数相乘、逆向NTT功能,同时支持CooleyTukey和Gentleman-Sande两种结构;提出一种新的系数访存模式,采用“交叉存储型”结构,使用双口BRAM将计算后的系数“对角交叉”变换位置后存储在原地址,利用双Bank存储模式满足蝴蝶变换单元的数据吞吐量;对Barrett约减算法进行修改,提出一种适用于多模值的模约减硬件单元,用加法和移位代替其中的乘法操作,减少乘法器资源的消耗.本方案使用Verilog HDL语言在Xilinx公司Artix-7系列XC7A200TFBG484-2型号FPGA芯片上进行了纯硬件优化实现.与当前研究相比,本设计在面积上减少12%-62.6%,时间上提升5.5%-49.8%.此外,我们还对高吞吐量的并行设计进行了优化实现,优化后的二并行、四并行架构时间上分别加速两倍、四倍,面积消耗仅为单结构的1.45倍、2.58倍.

zk-SNARK中数论变换的硬件加速方法研究

简洁非交互式零知识证明能够生成长度固定的证明并快速进行验证,极大地推动了零知识证明在数字签名、区块链及分布式存储等领域的应用。但其证明的生成过程极其耗时且需要被频繁调用,其中数论变换是证明生成过程的主要运算之一。然而现有的通用数论变换硬件加速方法难以满足其在简洁非交互式零知识证明中大规模、高位宽的要求。针对该问题,提出一种数论变换多级流水硬件计算架构。针对高位宽计算需求对高位模运算进行优化,设计了低时延蒙哥马利模乘单元;为了加速大规模计算,通过二维子任务划分将大规模数论变换任务划分为小规模独立子任务,并通过消除数据依赖实现了子任务间计算流水;在子任务多轮蝶形运算之间采用数据重排机制,有效缓解了访存需求并实现了不同步长蝶形运算间的计算流水。所提出的数论变换计算架构可以根据现场可编程门阵列(FPGA)片上资源灵活扩展,方便部署在不同规模的FPGA上以获得最大加速效果。所提出的硬件架构使用高层次综合(HLS)开发并基于OpenCL框架在AMD Xilinx Alveo U50实现了整套异构加速系统。实验结果表明,相比于PipeZK中的数论变换加速模块,该方法获得了1.95倍的加速比;在运行当前主流的简洁非交互式零知识证明开源项目bellman时,相比于AMD Ryzen 95900X单核及12核分别获得了27.98倍和1.74倍的加速比,并分别获得了6.9倍、6倍的能效提升。

NTRU格上高效紧凑密钥封装方案

基于NTRU格设计后量子密钥封装方案是格密码领域主流方向之一.为降低密文尺寸,现有方案会引入额外的困难性假设和使用纠错码来辅助压缩密文,但这会导致方案的假设过强和实现更复杂.为克服这些障碍,提出了一个仅基于NTRU单向困难性假设、不使用纠错码也能压缩密文的高效紧凑的密钥封装方案LTRU.给出一套性能均衡的LTRU参数集:具有128 b量子安全强度、与之匹配且可忽略的错误率、较小的公钥尺寸和密文尺寸.LTRU基于NTT友好环构造,给出一种高效的混合基数论变换算法来计算该环上多项式运算还给出了LTRU的C实现和AVX2实现.与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%;在AVX2实现的密钥生成和解封装算法上分别快了10.9倍和1.7倍.

基于Cortex-M4的CNTR/CTRU密钥封装高效实现

量子计算技术的迅猛发展对现有的公钥密码体制造成了极大的威胁,为了抵抗量子计算的攻击,后量子密码成为当前密码学界的研究热点.目前,物联网的安全问题备受关注,ARM Cortex-M4作为低功耗嵌入式处理器,被广泛应用于物联网设备中,在其上部署后量子密码算法将为物联网设备的安全提供更加可靠的保障.CNTR和CTRU是我国学者提出的NTRU格基密钥封装方案,相比于基于LWE技术路线的格基密钥封装方案在安全性和其他性能上具有综合优势,并在我国密标委得到立项.本文工作首次在ARM Cortex-M4平台上高效紧凑地实现了CNTR和CTRU方案,充分利用单指令多数据(Single Instruction Multiple Data,SIMD)指令,调整运算结构和指令安排,优化核心的多项式运算,从而在算法实现速度和堆栈空间上进行全面优化升级.本文主要工作如下:本文首次在ARM Cortex-M4上实现耗时模块多项式中心二项分布采样,采样速度提升32.49%;使用混合基数论变换(Number Theoretic Transform,NTT)加速非NTT友好多项式乘法运算,充分利用浮点单元(Floating-Point Unit,FPU)寄存器,在NTT实现中采用层融合技术,最大化减少加载和存储等耗时指令使用,使得正向NTT和逆向NTT的速度分别提升84.24%、81.15%;通过NTT过程系数范围分析进行延迟约减,进而减少约减次数,并使用改进的Barrett约减和Montgomery约减技术实现降低约减汇编指令条数;使用循环展开技术实现多项式求逆,优化多项式求逆这一耗时过程,速度优化率为68.85%;针对解密过程中的非NTT友好素数模数多项式环乘法,采用多模数NTT和中国剩余定理(Chinese Remainder Theorem,CRT)结合的方法进行加速,完成解密过程96.26%的速度提升;使用空间复用的方法优化堆栈空间,CNTR和CTRU的堆栈空间分别减少了29.86%、28.17%.实验结果表明:提出的优化技术大幅提升了算法实现效率,与C参考实现相比,CNTR和CTRU的整体速度优化率分别为85.54%、85.56%.与其他格基密钥封装方案最新ARM Cortex-M4实现相比,本文的优化实现在速度、空间和安全性上具有综合性的优势.

面向格基后量子密码算法的可重构多项式乘法架构

针对基于不同困难问题格基密码算法中的多项式乘法参数各异且实现架构不统一的现状,该文提出一种基于预处理型数论变换(PtNTT)算法的可重构架构。首先进行多项式乘法运算特征分析,综合了多项式参数(项数、模数及模多项式)对可重构架构的影响。其次,针对不同项数和模多项式设计了4×4串并行可转换型运算单元架构,可满足实现不同位宽基k-数论变换的可扩展设计。其中具体针对不同模数设计了可扩展实现16 bit模乘和32 bit乘法的可重构单元。在数据需求分析过程中,通过构建以系数地址生成、Bank划分以及实际与虚拟地址对应逻辑为主体的分配机制,设计了一种满足基k-数论变换的多Bank存储结构。实验结果表明,该文支持实现Kyber,Saber,Dilithium与NTRU等4种类型算法中的多项式乘法,与其余可重构架构相比,可采用统一架构实现4种算法中的多项式乘法。基于Xilinx Artix-7 FPGA 1.599μs完成一组项数为256,模数为3329的多项式乘法运算,花费243个时钟。

基于理想格的公钥加密方案快速实现技术研究

在基于理想格和模格的公钥加密方案中,多项式环上的乘法运算是影响方案实现效率的重要模块,而该模块通常可通过数论变换(number theoretic transform,NTT)来快速实现.本文采用结合Karatsuba算法的带预处理的NTT(preprocess-then-NTT with Karatsuba,KNTT),提升格公钥加密方案的实现效率.在使用KNTT前,通过改进采样和密文打(解)包结果的存储方式来调整多项式环元素的数据结构,使之直接适用KNTT,从而省去KNTT算法中的预处理和组合环节.改进了KNTT中的NTT变换的实现方式,进一步提高格公钥加密方案的实现效率.KYBER是NIST在第三轮评选中决定标准化的格公钥密码算法,本文将上述改进技术应用于KYBER类加密方案,得到了KNTT-based KYBER算法,与KYBER.CPAPKE相比,密钥生成实现效率提高了5%–8%,加密实现效率提高了7%–10%,解密实现效率提高了9%–10%.

一种新的多项式环上的数论变换算法

得益于易并行、速度快、方案平均意义下的安全性可建立在最坏情况的底层困难问题上等特点,格密码被认为是最有希望成为后量子密码标准的方案.在基于多项式环上格困难问题构造的密码方案中,数论变换算法是加速多项式乘法、提升密码方案运行效率的关键技术手段之一.目前已有的方法只对形如Zq[x]/(x^(n)±1)的多项式环适用,且安全参数n被限制为2的方幂.本文给出新多项式环n Zq[x]/(x^(n)-xn/2+1)上的数论变换及其上元素相乘的公式,并借助蝶形算法给出了变换公式的计算复杂度.结合Karatsuba算法,扩展了n=c·2^(k)情形下数论变换的参数选取范围,并优化了计算复杂度.

针对AKCN-MLWE算法的故障攻击

随着量子计算技术的飞速发展以及Shor算法的提出,未来成型的量子计算机将轻易求解大整数分解问题以及离散对数求解问题.由于传统公钥算法如RSA、椭圆曲线问题等其安全性均基于这些数学问题,因此该类算法面临的安全威胁也日益突出.后量子密码算法是为对抗量子计算破解而设计的一类加密算法,在近年来成为密码学研究热点.其中,基于格的后量子密码算法最为学术界广泛研究与评估.目前,密码学已经达成共识,密码算法不仅仅需要考虑算法理论安全性,同时需要考虑实现安全性,包括旁路攻击和故障攻击安全性.本文针对中国密码学会征集的第二轮后量子密码算法AKCN-MLWE提出了一种嵌入式环境下的故障攻击方法.AKCN-MLWE算法是一种基于格的公钥密码算法.本文提出的故障攻击向该算法中使用的数论转换模块(NTT)中的旋转因子注入故障并影响其输出结果.在分别针对密钥生成环节和加密环节进行故障注入后,利用有效的错误输出结果可以分别进行私钥的还原以及密文的解密.同时该故障注入并不会影响生成的公私钥对在后续通信中的使用.但是在对加密环节进行故障注入后,攻击者需要使用中间人攻击方法来维持该次通信.本文也对如何在真实环境下进行故障注入进行了讨论与实用性评估.本文所提出的故障攻击方法,在算法执行过程中仅需一次故障注入即可恢复整体私钥.最后,本文同时提出一种针对性的防御方法,在不影响实现效率的情况下可有效防止该类故障攻击的生效.

抗量子密码中快速数论变换的硬件设计与实现

快速数论变换(Number Theoretic Transform,NTT)是抗量子密码算法的关键部分,其计算性能对系统的运行速度至关重要。相比经典的NTT算法,高基NTT算法可以达到更好的计算性能。针对高基NTT硬件实现过程中计算流程冗长、控制逻辑复杂的问题,文章基于流水线结构提出一种高性能的基-4 NTT硬件架构。首先,基于经典NTT算法,推导出利于硬件实现的基-4递归NTT,简化了高基算法的计算流程;然后,提出一种单路延迟反馈结构,对计算流程进行有效的流水线分割,降低了硬件架构的复杂度;最后,利用两级蝶形运算耦合实现基-4蝶形单元,并使用移位与加法优化约简计算过程,节省了硬件资源开销。文章以抗量子密码方案Falcon为例,在Xilinx Artix-7 FPGA上实现了所提出的NTT硬件架构。实验结果表明,与其他相关的设计相比,文章提出的设计方案在计算性能和硬件开销等方面表现更好。

一种新的数字图像置乱方法

常见的基于位置空间的数字图像置乱方法存在不能改变图像统计特性的缺陷,同时置乱过程缺乏随机性,保密性不高。针对以上问题,提出了一种新的数字图像色彩空间置乱方法。该方法基于快速数论变换,置乱速度快,变换矩阵形式不固定,逆变换矩阵求解简单,恢复图像完全无损,且通过选取合适的参数,经过一次迭代就可以达到满意的置乱效果。实验结果表明,置乱后的图像接近白噪声,提高了保密信息的迷惑性,同时还原图像易于实现,有较好的实用性。

应用于格密码的可重构多通道数论变换硬件设计

针对不同格密码体制带来的数论变换参数多样性,以及数论变换的性能优化设计,该文提出一种基于随机存取存储器(RAM)的可重构多通道数论变换单元。在数论变换单元设计中,在按时间抽取的基础上改进多通道架构,并提出一种优化地址分配方法。最后基于Xilinx Artix-7现场可编程逻辑门阵列(FPGA)平台进行原型实现,结果显示,所设计的数论变换单元消耗的资源为1744 Slices, 16 DSP,完成1次多项式乘法的时间为2.01μs(n=256), 3.57μs(n=512), 6.71μs(n=1024)和13.43μs(n=2048),支持256~2048的不同参数n和13~32 bit模q的可重构配置,工作频率最高可达232 MHz。

计算二维数字卷积的二维重叠保留法

设ｈｋ２，ｋ２代表滤波器的系数（ｋ１＝０，１，…，ｌ２－１，ｋ２＝０，１，…，ｍ２－１），ｘｎ１，ｎ２和ｎ１，ｎ２（ｎ１＝０，１，…，ｌ１－１，ｎ２＝０，１，…，ｍ１－１）分别代表滤波器的输入和输出，本文给出了计算ｙｎ１，ｎ２（它是ｘｎ１，ｎ２和ｈｎ１，ｎ２的线性卷积）的二维重叠保留法，这是一维重叠保留法的推广和发展．在许多应用中，输入和输出的长度很长，相比之下，滤波器的系数长度较短．如果用直接的方法计算ｙｎ１，ｎ２，其乘法运算的个数将很大．本文指出在数字信号处理领域中用重叠保留法计算ｙｎ１，ｎ２是有效的．这一方法通过计算一系列长为Ｎ和Ｍ的循环卷积来计算ｙｎ１，ｎ２（ｎ１＝０，１，…，ｌ１－１，ｎ２＝０，１，…，ｍ１－１），这里Ｎ＝２ｄ，Ｍ＝２ｄ′，Ｎ＝Ｎ′＋ｌ２－１＜ｌ１，Ｍ＝Ｍ′＋ｍ２－１＜ｍ１．所以能够用快速数论变换（ＦＮＴＴ）或快速付里叶变换（ＦＦＴ）计算循环卷积．这有可能使我们用这一方法处理一个无限输入序列ｘｎ１，ｎ２和有限滤波器系数ｈｋ１。

数论变换在异步保密机中的应用

本文讨论了数论变换在异步保密系统中的应用。首先对数论变换应用后系统所出现的问题进行了描述，然后分析，讨论了这些问题产生的原因，并针对输入信号动态范围的扩展，数论变换非线性控制等提出了相应的解决方法。

数论变换与周期性序列关系在图像压缩中应用

利用数论变换的性质、整型变换的特点、变换速度快和算法简单的优势,结合图像数据的特点以及二维序列与变换系数之间的关系,提出并证明了数论变换转置定理和周期性二维序列与变换系数关系定理.该定理为用于二值图像压缩奠定了理论基础,特别是利用周期性二维序列与变换系数间的关系来判断图像是否具有周期性,进而确定其行列周期,以达到提高压缩比的目的.使用国际电报电话咨询委员会(CCITT)推荐的8幅二值图像进行验证,结果表明:数论变换快速算法及证明的两个定理,用于对图像数据的压缩是可行的,若分块适当可提高运算速度,减少存储空间,提高压缩比.提出的算法在图像压缩中应用具有较大的理论意义和应用价值.

长序列线性卷积的数论变换算法

本文提出一种利用数论变换计算长序列线性卷积的算法。它利用较短的数论变换对长序列卷积进行分段计算,减少了数论变换处理中移位操作的位数;用适当的字长就能完成较长的卷积计算,因而显著缩短了卷积执行时间。

数论变换算法的拓展与在图像压缩中应用

本文研究并利用了数论变换的性质、特点以及快速算法的优势,结合图象数据的特点以及二维序列与变换系数之间的关系,拓展了数论变换算法,提出了数论变换转置定理和周期性二维序列与变换系数关系定理并给予证明。使用CCITT推荐的8幅二值图像进行验证和分析,结果表明,数论变换快速算法及提出的两个定理,用于对图像数据的压缩是可行的,且分块适当可提高运算速度,减少存储空间,提高压缩比。本文算法在图象压缩中应用具有较大的理论意义和应用价值,为数论变换在图像压缩中的应用迈出了实际应用的第一步。

基于MLWE的格密码高效硬件实现

后量子密码的发展已经引起各界的广泛关注,硬件实现效率是后量子密码最终标准的重要衡量指标之一。其中基于模误差学习问题(Module Learning With Errors,MLWE)的CRYSTALS-Kyber格密码是NIST第三轮后量子密码标准中最有希望的一种加密方案,可变的公钥矩阵维度参数k将基于MLWE的公钥加密方案的安全性扩展到不同级别,相较于其他格密码方案更具灵活性和安全性。本文首先分析了基于NIST第三轮最新参数q=3329的MLWE的格密码公钥加密方案的算法理论,并针对其中的核心模块—多项式乘法模块提出了两种不同的硬件实现方式。两种多项式乘法硬件实现方式都是采用基于频率抽取的数论变换(Number Theoretic Transform,NTT)算法,使用NTT算法实现多项式乘法降低了传统算法实现的线性复杂度,在硬件结构上能够面对不同应用场景进行优化,因此本文针对NTT算法中循环计算的核心模块提出了两种不同的优化硬件结构。一是面积和执行时间折中的迭代型NTT硬件结构,二是高性能低时延的多路延时转接(Multi-path Delay Commutator)的流水型NTT硬件结构;并且针对于面积时间均衡的迭代型NTT模块设计了一种整体MLWE硬件实现结构。与已有的先进设计相比,本文的流水型NTT结构具备更好的速度性能,在速度上相较于之前的设计分别提升11.64%和59.43%。而对于使用迭代型NTT的MLWE整体实现方案,本文的设计使用了最少的周期和最小的面积时间乘积(Area-Time-Product,ATP),其效率比最新发表的工作的硬件效率实现高2倍左右。

基于FPGA的格密码关键运算模块的设计与实现

格密码是后量子密码中的一项重要技术,为提高格密码运算效率,提出了一种格密码中多项式乘法的硬件实现方法。该方法利用现场可编程门阵列(Field Program Gate Array,FPGA)内部存储器存放多项式系数,采用乒乓结构提高存储器并行读写速度,并通过预计算和预缩放简化计算过程,降低计算复杂度。同时,采用多级流水线技术,减少存取时间和蝶形运算等待时间,提升整体编译频率,提高运算性能。评估结果表明,该方法最大工作频率达到了320 MHz,完成一次1 024项多项式乘法运算的时间为41μs。

用于全同态加密的数论变换乘法蝶形运算优化及实现

全同态加密(FHE)可以真正从根本上解决云计算时将数据及其操作委托给第三方时的数据安全问题。针对全同态加密中占较大比例的大整数乘法运算优化需求,该文提出一种数论变换乘法蝶形运算的操作数合并算法,利用取模操作的快速算法,分别可将基16和基32运算单元的操作数减少到43.8%和39.1%。在此基础上,设计并实现了数论变换基32运算单元的硬件设计架构,在SMIC 90 nm工艺下的综合结果显示,电路的最高工作频率为600 MHz,面积1.714 mm^(2)。实验结果表明,该优化算法提升了数论变换乘法蝶形运算的计算效率。