一种格密码中多项式压缩的并行实现方法

摘要

本发明涉及一种格密码中多项式压缩的并行实现方法，属于密码学领域，该方案包括以下步骤：首先通过格密码相关参数设置来预计算k、m等参数；基于设置的参数对待压缩或解压缩的多项式系数进行并行压缩或解压缩。本发明利用处理器提供的并行计算指令集在不修改参数的前提下实现更高效的格密码中多项式压缩的目的。

说明书

技术领域

本发明属于密码学领域。

背景技术

随着量子计算的快速发展，可以抵御量子计算攻击的后量子密码逐渐显示出优势。格密码是后量子密码中的一种类型，其中又包括了基于不同困难问题的类型，如基于环上容错学习等。当前以及未来越来越多的通信、数据加密需求使得密码算法的性能愈发重要，处理器架构差异、计算能力差距等都是密码算法实现中需要考虑的关键因素。格密码的性能仍有一定提升空间，原因在于格密码中的部分算子依旧可以针对特定平台进行优化。

基于上述问题，学术界和工业界已针对格密码进行很多相关的实现优化工作，例如在ARM平台、Intel平台、FPGA等对核心算子进行针对性优化。优化实现中的关键技术之一即提升并行度，对于格密码中的多项式乘法、多项式加法等算法使用特定平台的指令集进行处理。然而，在现有的并行优化实现中，均未对多项式压缩进行优化，多项式压缩耗时较长影响密码算法的整体性能，成为性能提升的瓶颈。

发明内容

发明目的：为了解决上述背景技术中存在的问题，本发明提供了一种格密码中多项式压缩的并行实现方法。

技术方案：本发明提供了一种格密码中多项式压缩的并行实现方法，该方法包括压缩计算和解压缩计算；

所述压缩计算具体包括如下步骤：

步骤1：根据格密码的模数q，计算用于进行多项式压缩计算的乘法参数m和移位参数k，所述q为小于等于2

步骤2：基于乘法参数m和移位参数k，对格密码中多项式的系数进行并行压缩计算。

进一步的，所述步骤1中基于如下公式计算k和m：

其中d为正整数，《为左移，

且k和m满足如下条件：

&表示与，＞＞为右移，x为单个多项式中的单个系数,

进一步的，所述步骤2中采用第一处理器进行压缩计算，该处理器中所有寄存器的位数均为l，进行压缩前将

进一步的，所述第一处理器根据如下公式对l/t个系数进行并行压缩计算：

其中，x

进一步的，在进行解压缩计算时采用第二处理器进行解压缩计算，该处理器中所有寄存器的位数均为l，解压缩计算前将q的值广播到第二处理器中的第一寄存器中，将压缩后任意一组中l/t个系数对齐输入到第二处理器中的第二寄存器中，第二处理器调用第一，二寄存器中的数据，对该组的l/t个系数进行并行解压缩计算。

进一步的，所述第二处理器根据如下公式对l/t个系数进行并行解压缩计算：

x″

其中，x'

有益效果：本发明计算了用于压缩计算的乘法参数m和移位参数k，并利用乘法和位移计算代替压缩计算中的除法计算，实现了压缩效率最大化；本发明大幅度提升了格密码压缩性能，本发明与现有方案相比，算法性能提升8倍到53倍左右。

附图说明

图1是本发明的流程图；

图2是采用本发明的方法在AKCN-MLWE中实现对3比特压缩与解压缩计算的AVX2算法图；

图3是采用本发明的方法在AKCN-MLWE中实现对10比特压缩与解压缩计算的AVX2算法图。

具体实施方式

构成本发明的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。

如图1所示，本实施例提供了一种格密码中多项式压缩的并行实现方法，该方法包括压缩计算和解压缩计算，

所述压缩计算具体包括如下步骤：

步骤1：根据格密码的模数q，计算用于进行多项式压缩计算的乘法参数m和移位参数k，所述q为小于等于2

步骤2：基于乘法参数m和移位参数k，对格密码中多项式的系数进行并行压缩计算。

优选的，步骤1具体为：首先，

记格密码中单个多项式为R

优选的，预计算

优选的，使用处理器所支持的并行计算指令集，如Intel处理器中的AVX2指令集，进行并行压缩计算

优选的，解压所前预计算2

x″

其中，x″

为进一步说明本实施列的技术方案及技术效果，在格密码AKCN-MLWE中，模数q＝7681，多项式维度n＝256，压缩系数d＝3或d＝10，具体压缩与解压缩的AVX2实现算法分别见图2和图3，图2中的a[i]表示作为算法输入的a中的第i个系数，图3中的vpmul{l|h}w表示vpmullw和vpmulhw两条指令，vpunpck{l|}wd表示vpunpcklwd和vpunpckwd两条指令，0xf5和mask表示算法中使用的运算掩码，a1、b和c表示算法中使用的临时寄存器，b[i]和c[i]分别表示b和c中的第i个系数。

本实施例在8核Intel Core i9-9880H处理器和16G内存的硬件环境下进行基准测试，将本实施例的性能结果与现有技术的性能结果进行比对，比对的结果如表1所示，从表1中可以看出，本实施例在同样参数设置下，性能提升是现有技术的8倍到53倍。

表1

上面对本发明作了详细的说明，但是本发明并不限于上述的实施方式，在本领域的技术人员可以根据自己所具备的知识，对本发明做各种变化以达到更优的效果。