NTT——数论变换算法在图像压缩技术中的应用研究

提出了一种全新的图像数据压缩算法 ,即数论变换 (Number Theory Transformation,NTT)算法 .证明了在以正整数 p为模的整数环 Zp 上 NTT是线性正交变换 ,以及在 Zp 上具有卷积特性等 .设计了具有 FFT类型的快速算法 ,该算法可采用移位操作实现 ,其速度优于 DCT变换 .最后通过实例比较 ,说明了该算法在图像数据压缩中表现出运算速度快、精度高和压缩效果好等优点 .NTT算法的研究 。

一种用于小模数多项式乘法快速数论变换的扩域方法

在基于Ring-LWE体系的格密码算法中,快速数论变换是加速多项式环乘法的常见方法,但该方法对于系数域模数小于多项式长度的多项式环乘法不适用.本文通过对多项式系数域构造扩域,扩大系数域的阶数,使小模数的多项式环乘法也能够使用快速数论变换来加速.扩域上的有限域乘法会带来额外的计算开支,但快速NTT变换的使用可以带来指数级的加速效果,总体来说节省更多的计算复杂度.常见的快速数论变换使用与快速傅里叶变换相似的折半定理,进行基2的快速变换,而系数域构造扩域后由于其阶数无法满足基2变换的条件,本文通过将多项式长度进行质因子分解来推导复合基的快速数论变换,最终为小模数多项式环乘法提供可观的加速效果.

抗量子格密码体制的快速数论变换算法研究综述

量子计算机的迅速发展给传统的RSA密码、ECC等公钥密码体制带来严重的安全威胁。在抗量子公钥密码体制中,基于格的密码体制是重要的研究类型之一,对算法快速实现的研究具有重要意义。快速数论变换算法是格密码体制的核心运算,其运算效率是实现格密码算法的关键。文章主要对格密码体制中的快速数论变换算法的研究进展,特别是近年来在各种CPU平台上的软件实现方法的进展进行分析和综述,对快速数论变换算法在蝶形结构、负包卷积、取模运算等方面的改进算法进行分析和总结。

快速数论变换的原理与方法及应用

本文提出一种快速数论变换算法，这种算法是以数论为基础，对样本点为的数论变换，按时间抽取的方法，得到一组等价的迭代方程，对方程中对偶结点对的性质作了详细分析，有效高速简化了方程中的计算公式. 与直接计算相比，大大减少了运算次数。

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

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

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

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

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

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

基于NTT的高效多项式乘法器设计及其FPGA实现

基于快速数论变换(number theoretic transform,NTT)的多项式乘法运算是后量子密码(post-quantum cryptography,PQC)的重要组件,提高多项式乘法器的运算速度至关重要。文章基于现场可编程门阵列(field programmable gate array,FPGA)提出一种输入位宽为14位、长度为1024的高效多项式乘法器硬件加速方案,设计一种无冗余可重用的蝶形运算单元电路。通过提高部分运算的并行度,实现模乘器接近100%的利用率,降低整个多项式乘法运算的迭代周期,提高整体运算速度。该乘法器最终被部署在Xilinx Artix-7 FPGA开发板上,实验结果表明,电路的最高工作频率为238 MHz,多项式乘法运算的总体用时为35.59μs,对比现有的硬件设计,该文提出的电路运算效率提高36.9%。

一种面积高效的双态可配置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算法通用性的同时,在计算性能和硬件开销等方面表现更好。

基于稀疏相位和可调傅里叶变换的图像加密

针对光学图像加密的轮廓显现问题,提出了一种基于稀疏相位和可调傅里叶变换的图像加密方法。将可调傅里叶变换引入光学图像加密程序中,运用二维可调傅里叶变换实现像素混淆处理,相比基于复数或实数的变换域方案,计算复杂度较低;从加密函数提取相位值并获得加密数据的相位函数,再提取相位加密函数的稀疏数据,从而避免将密文相位信息主要集中在纯相位掩码内,以解决轮廓显现问题;完成了单图像加密实验和双图像加密实验,结果表明实现了较好的安全性,解决了光学图像加密的轮廓显现问题。

数论变换在NTRU公钥密码体制中的应用

文中概述了数论变换(NTT)及其应用。特别地,数论变换可通过类似快速傅里叶变换(FFT)算法来计算两个整系数多项式的乘积或计算它们两组整系数的循环卷积。作为实例,给出了实现快速Fermat数变换(FFNT)的流程图。笔者还讨论了NTRU公钥密码体制,并将计算循环卷积的快速算法应用到NTRU公钥密码体制,从而提高了该体制的实现速度。

紧凑的Aigis-sig数字签名方案软硬件协同实现方法

基于理想格构造的Aigis-sig数字签名方案具有实现效率高、签名长度短、抗量子攻击等优势。针对Aigis-sig方案,构造了一种改进的模乘计算元件,设计了一种基于快速数论变换(NTT)算法实现环上多项式运算的紧凑硬件架构;同时以此架构为基础,提出了Aigis-sig数字签名方案的FPGA软硬件协同实现方法。实验表明,在Xilinx Zynq-7000 SoC平台上,CPU频率和硬件频率分别设置为666.66 MHz和150 MHz时,该实现方案相较于纯软件实现,签名阶段和验签阶段分别取得约26%和17%的性能提升。

素阶数域上的高效格基数字签名方案

随着量子计算的快速发展,特别是Shor量子算法及其变体的优化进步,当前基于大整数分解和离散对数问题的经典公钥密码体制将面临颠覆性的影响.为了应对量子攻击,学界开始对后量子密码学的研究,其中基于格的后量子密码方案因其在安全、效率、带宽等方面的均衡表现和良好的可扩展性而成为后量子密码的主流技术路线.目前,基于格的后量子密码方案大多使用分圆环,尤其是二次幂分圆环作为底层代数结构.但分圆环中具有丰富的子域、自同构、环同态等代数结构,容易遭受针对性攻击.基于具有“高安全性、素数阶、大Galois群和惰性模数”特点的素阶数域,设计出后量子数字签名方案Dilithium-Prime,并给出推荐参数集.然而,素阶数域的一个显著缺点是无法直接使用快速数论变换(NTT)算法进行高效的多项式乘法,导致素阶数域上的密码方案性能较差.为此,设计素阶数域上的NTT算法和小多项式乘法,实现素阶数域上高效的多项式乘法.最后,为方案的关键算法设计常数时间无分支实现方法,给出方案的C语言实现,并与其他方案进行对比.实验结果表明,在同一安全等级下,与分圆环上的数字签名方案CRYSTALS-Dilithium推荐参数相比,Dilithium-Prime方案的公钥尺寸、私钥尺寸、签名尺寸分别降低1.8%、10.2%、1.8%,签名算法效率提高11.9%,密钥生成算法、验证算法所需时间分别为CRYSTALS-Dilithium方案的2.0倍和2.5倍,但不同于CRYSTALS-Dilithium,Dilithium-Prime方案具有抵抗针对分圆环的密码攻击的优越特性;与2023年韩国后量子密码算法竞赛中提出的基于素阶数域的签名方案NCC-Sign推荐参数相比,在相同的安全等级和带宽条件下,Dilithium-Prime方案的密钥生成算法、签名算法、验证算法的速度分别提升至4.2倍、35.3倍、7.2倍,实现兼顾高效性和安全性的素阶数域签名算法.

CRYSTALS-Dilithium算法实现的空间优化

量子计算机的高速发展给传统公钥密码带来了潜在的威胁,基于格的数字签名算法CRYSTALS-Dilithium,虽然实现效率较传统公钥密码要高效得多,但是需要较大的存储资源空间保存公钥、私钥以及中间变量。针对上述问题,提出了节省矩阵所需要的空间和减少临时变量的数量两种优化方法,减少签名过程中的中间变量所需空间大小。通过本文的方法,可以减少大量程序运行所需要的存储资源,以便能更好地应用于存储资源受限的物联网设备中。对于三种不同安全级别的Dilithium算法,节省空间分别为23.53%,32.00%和38.89%。