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倍的能效提升。

PreNTT:面向zk-SNARK的数论变换计算并行加速方法

简洁非交互式零知识证明(zk-SNARK)由于具备证明验证过程简捷快速的优点,已在加密货币等众多领域得到广泛应用。但其证明生成过程所需计算仍复杂耗时,影响了进一步的应用拓展。针对zk-SNARK证明生成过程中的主要计算瓶颈——数论变换(NTT),提出了一种基于GPU的NTT计算加速方法PreNTT。首先,提出了基于预计算的NTT并行计算方法,利用预计算与旋转因子次幂算法优化,减少NTT并行计算开销,并结合动态预计算,进一步提高NTT计算效率。其次,通过“动态自适应计算核调度”,可以根据NTT输入规模自适应地分配GPU片上资源,提升了大规模NTT任务的计算能效。然后,通过核外整体数据混洗和核内局部数据混洗相结合的方式,避免了访存冲突。最后,使用CUDA多流技术执行数据传输和计算过程,对预计算时间进行了有效隐藏。实验结果表明:基于PreNTT实现的zk-SNARK系统,与目前业界最先进的系统Bellperson相比,NTT模块运行时间获得了全规模最低1.7倍的加速比,最高加速比为9倍。PreNTT能够有效提高NTT算法并行度,降低zk-SNARK运算时间开销。

快速小波变换,循环卷积和数论变换

证明了二维Mallat分解算法可通过二维循环卷积来计算 ,从而 ,快速计算循环卷积的方法 ,如快速数论变换 (FNTT) ,FFT等 ,均可用来实现二维Mallat分解算法 ,这也就提供了快速小波变换的一个新算法 .作者分别比较了直接用二维Mallat分解算法和用FNTT实现二维Mallat分解算法的乘法和加法运算的次数 ,分析表明 ,在通常情况下 ,新算法的乘、加法次数均会少一些 ,并在微机PC/ 5 86( 166MHz)上用FNTT通过二维Mallat分解算法对一个 2 5 6× 2 5 6的原始数字图像进行了分解 .

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

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

数论变换在图像压缩技术中的应用

在对用变换算法ＫＬ和ＤＣＴ 实现图像数据压缩技术的分析与评价的基础上，提出了一种新的图像数据压缩算法，即数论变换（ｎｕｍ ｂｅｒ ｔｈｅｏｒｅｔｉｃ ｔｒａｎｓｆｏｒｍ ｓ，ＮＴＴ）算法．对该算法进行了推证，证明了在以正整数ｐ 为模的整数环Ｚｐ 上ＮＴＴ是线性正交变换，以及在Ｚｐ 上具有卷积特性等．设计了具有ＦＦＴ 类型的快速算法，该算法可采用移位操作实现，其速度优于ＫＬ和ＤＣＴ变换．最后通过实例比较，说明了该算法在图像数据压缩中表现出运算速度快、精度高和压缩效果好等优点．ＮＴＴ算法的研究，为图像压缩技术开拓了新的方法．

数论变换算法(NTT)应用于图像压缩技术

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

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

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

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

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

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

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

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

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

剩余类环Z_M与Z_M上的数论变换

剩余ZM类环是一类特殊的环.数论变换是以正整数M为模的正整数环(域)ZM上定义的线性正交变换,所用的计算方法是数论中的同余运算.介绍了剩余类环ZM上的几个方面的知识点,以及ZM上的数论变换的有关理论,及其数论变换应注意的几个问题.

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

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

数论变换算法中的几个问题

本文讨论了数论变换的参数选取以及素数模在计算机上算法实现的问题，指出模取素数时数论变换（NTT）也可以保留FNT速度快、精度高的主要优点，同时也改进了其字长选取不灵活的缺憾，使得数论变换也可直接用于长序列卷积的快速计算。

用弗马数论变换作语音信号自相关分析

线性预测编码(LPC)是语音信号处理的一种强有力的分析技术.此时把信号看作非平稳随机过程,用自相关函数来计算短时预测参数.求解线性方程组的方法是简便的,但自相关系数的计算是十分繁重的,从而影响了处理的速度和实时性.为了提高计算速度,本文选用快速弗马数论变换(FFNT)计算自相关系数.计算机仿真表明,它快于和优于直接法.本文中的FNT具有与FFT相同的结构,因而很便于用硬件实现。

数论变换在图像压缩技术中的运用

近年来,伴随多媒体技术的不断发展,多媒体技术的出现,不仅推动了我国社会发展的速度,还带动了很多行业的发挥在那。但是在多媒体数据中,存在着大量的数据类型,为此怎样组织与压缩存储等这些数据已经成为多媒体计算机需要解决的重要问题。本文主要对数论变换在图像压缩技术中的应用展开相应的分析,旨在确保图像压缩技术能够得到更好的发展,并且在充分利用数论变换的基础之上,使得多媒体数据得到更好的处理。

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

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

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

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

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

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

基于FPGA的数论变换算法及应用的研究

本文介绍了数论变换及其一些基本特性;讨论了数论变换中的快速算法和较长序列变换等重要问题,并给出了解决方案。进一步论证了基于FPGA实现数论变换的可行性及其在数字信号处理应用中优势所在;最后设计出了基于FPGA的基本数论变换的实现并基于此实现了快速卷积运算器。