一种基于块型编码的密文内积快速计算方法与流程

1.本发明属于数据加密技术领域，尤其涉及一种基于块型编码的密文内积快速计算方法。


背景技术：

2.内积运算是向量与向量之间最基本的运算方式之一，是向量间距离计算、向量相似性计算、矩阵乘法运算等的计算基础，被广泛应用于机器学习、计算机图形学等领域。向量内积运算作为基础运算，在大部分使用场景下，向量都是以明文数据的的形式进行计算，如果计算方是恶意的，那么向量中所包含的敏感信息就会泄露。此外，如果在计算过程中有恶意的第三方存在，那么恶意方也可通过直接窃取明文数据获取隐私信息。显然，明文下的内积计算方式存在隐私数据泄露的风险。
3.另一方面，简单使用同态加密等技术加密原始向量的方法，可以实现在向量内积计算过程中对隐私的保护，但是，当向量维度不高的时候，存在密文空间使用率不高的缺点，并且单次仅计算一个向量内积，效率并不高。


技术实现要素：

4.本发明的目的在于：为了克服现有技术问题，公开了一种基于块型编码的密文内积快速计算方法，通过本发明解决了当前向量内积运算过程存在的隐私泄露问题，防止恶意计算方或者恶意第三方在内积计算过程中，轻易获取到明文敏感数据，保障了隐私性。
5.本发明目的通过下述技术方案来实现：
6.一种基于块型编码的密文内积快速计算方法，所述密文内积快速计算方法包括如下步骤：
7.s1：向量扩展步骤，将各待求内积的明文向量进行补0扩展；
8.s2：块型编码步骤，基于块型编码，对向量进行两种形式的打包编码，包括：单个向量重复编码和若干个向量串联编码；
9.s3：同态加密步骤，采用同态加密方法对s2完成块型编码的明文多项式进行加密，得到密文多项式；
10.s4：密文内积快速计算步骤，基于两种形式的打包编码加密后的密文多项式，利用单个密文内部打包向量局部求和算法，实现密文域内向量内积的批量计算；
11.s5：密文内积矩阵解密步骤，对密文矩阵的每一个元素进行解密，得到明文多项式矩阵；
12.s6：密文内积矩阵解码步骤，对明文多项式矩阵中的每一个元素依次进行解码，得到明文的打包向量内积；
13.s7：向量卷积运算结果获取步骤，将s6获得的各向量内积值提取出来，得到所有向量的内积值矩阵。
14.根据一个优选的实施方式，步骤s2中，单个向量重复编码为：将若干重复的扩展后
向量打包编码为一个明文多项式。
15.根据一个优选的实施方式，步骤s2中，若干个向量串联编码为：将全部向量进行分组，如果最后一组向量数量不足，则使用零向量替代；并将每一组中扩展后的各向量进行串联，打包编码为一个明文多项式。
16.根据一个优选的实施方式，步骤s1中，各待求内积的明文向量为v1，v2，...，vs，各向量长度为d，即vi＝{v
i，1
，v
i，2
，...，u
i，d
}，1≤i≤s；令n表示明文槽的数量；令k是n的一个因子，即k|n，且k≥d；令t＝n/k，z＝k-d。
17.根据一个优选的实施方式，步骤s4具体包括：
18.s41：对s3获得的两种形式下的密文多项式ctxt和bctxt，于密文域计算并获得两密文多项式的差c
i，j
＝he.sub(ctxti，bctxtj)，i＝1，...，s，j＝1，2，...，r，其中，ctxt为：单个密文重复编码的密文多项式，bctxt为：若干个向量串联编码的密文多项式；
19.s42：对两密文多项式的差进行同态乘法计算，获得c
i，j
＝he.square(c
i，j
)，i＝1，...，s，j＝1，2，...，r；
20.s43：对密文计算其内部向量的局部和c
i，j
＝partialsum(c
i，j
，k)，其中k表示内部打包的单个向量长度；
21.s44：得到一个密文内积矩阵c，其中c
i，j
表示第i个向量与第j组打包向量的所有内积。
22.根据一个优选的实施方式，步骤s5包括：
23.对密文矩阵c的每一个元素c
i，j
，i＝1，...，s，j＝1，2，...，r进行解密，得到明文多项式矩阵p，即矩阵元素p
i，j
＝he，decrypt(c
i，j
)，i＝1，...，s，j＝1，2，...，r。
24.根据一个优选的实施方式，步骤s6包括：
25.对明文多项式矩阵p中的每一个元素依次进行解码，得到明文的打包向量内积vprod
i，j
＝he，decode(p
i，j
)，i＝1，...，s，j＝1，2，...，r，包含了向量vi，i＝1，...，s与第j组打包向量的内积值。
26.根据一个优选的实施方式，步骤s7包括：
27.将所有向量内积值提取出来，得到所有向量的内积值矩阵prod，即矩阵元素
28.前述本发明主方案及其各进一步选择方案可以自由组合以形成多个方案，均为本发明可采用并要求保护的方案。本领域技术人员在了解本发明方案后根据现有技术和公知常识可明了有多种组合，均为本发明所要保护的技术方案，在此不做穷举。
29.本发明的有益效果：
30.本发明公开了一种基于块型编码的密文内积快速计算方法，当不可信的计算方在计算向量内积时，无法获知向量的原始数据信息；此外，恶意的第三方在整个向量内积的密态计算过程中，也无法窃取密文中所包含的任何信息并实施恶意操作。本发明提出的密文内积快速计算方法可以应用于机器学习、计算机图形学等需要矩阵向量运算的场景，为向量内积的计算提供安全防护。
附图说明
31.图1是本发明基于块型编码的密文内积快速计算方法流程示意图。
具体实施方式
32.以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
33.应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。
34.实施例1：
35.参考图1所示，图中示出了一种基于块型编码的密文内积快速计算方法，所述密文内积快速计算方法包括如下步骤。
36.步骤s1：向量扩展步骤，将各待求内积的明文向量进行补0扩展。
37.步骤s1中，各待求内积的明文向量为v1，v2，...，vs，各向量长度为d，即vi＝{
vi，1
，v
i，2
，...，v
i，d
}，1≤i≤s；令n表示明文槽的数量(可设置为2的幂数)。令k是n的一个因子，即k|n，且k≥d；令t＝n/k，z＝k-d。
38.补0扩展具体包括：对于每一个vi＝{v
i，1
，v
i，2
，...，v
i，d
}，1≤i≤s，首先将其进行补零扩展，使其为度变为k，即
39.步骤s2：块型编码步骤，基于块型编码，对向量进行两种形式的打包编码，包括：单个向量重复编码和若干个向量串联编码。
40.优选地，步骤s2中，单个向量重复编码为：将若干重复的扩展后向量打包编码为一个明文多项式。
41.具体地，可以为将t个扩展后的向量v
′i打包编码为一个明文多项式ptxti，即ptxti＝he.encode(v
′i，v
′i，...，v
′i)，i＝1，...，s。
42.优选地，步骤s2中，若干个向量串联编码为：将全部向量进行分组，如果最后一组向量数量不足，则使用零向量替代；并将每一组中扩展后的各向量进行串联，打包编码为一个明文多项式。
43.具体地，可以为：将全部s个向量v1，v2，...，vs进行分组，每组t个，如果最后一组向量数量不足，则使用零向量替代则得到组向量。
44.将每一组中扩展后的t个向量进行串联，打包编码为一个明文多项式bptxtj，j＝1，2，...，r，如第一组向量串联编码，bptxt1＝he.encode(v
′1，v
′2，...，v
′
t
)。
45.基于块状编码对明文向量进行了两种方式的打包编码，即单个向量重复编码和多个向量串联编码，大大提升了明文槽的利用率，避免了空间的浪费，在实际应用中也可以大大减少内存开销。
46.且块状编码的模式，使得多个向量编码加密到一个密文中，因此在后续密文计算内积的过程中，完成一次计算操作，就等价于明文与多次的内积计算，达到批量计算内积的效果，大大提升了密文计算的效率。
47.步骤s3：同态加密步骤，采用同态加密方法对s2完成块型编码的明文多项式进行
加密，得到密文多项式。
48.具体地，针对单个向量重复编码加密为：对每一个明文多项式进行同态加密，得到对应的密文多项式ctxti，即ctxti＝he.encrypt(ptxti)，i＝1，...，s。
49.针对若干个向量串联编码加密为：对每一个明文多项式bptxtj，j＝1，2，...，r进行同态加密，得到密文多项式bctxtj，j＝1，2，...，r，即bctxtj＝he.encrypt(bptxtj)，j＝1，2，...，r。
50.同态加密允许在数据不解密的情况下完成同态加法以及同态乘法运算，可以保护数据在计算过程中的安全性，是防止隐私泄露的一种有潜力的解决方案。此外，一些同态加密方案(如bfv方案，ckks方案等)也支持多个明文数据进行批打包编码，转换为对应的密文，再完成密文域的计算，这大大提升了计算效率。同态加密方案包含的主要算法如下：
51.(1)he.keygen(λ)：密钥生成算法，选择算法参数λ，输出公钥pk，私钥sk，计算密钥evk。
52.(2)he.encode(v)：编码算法，将一个数值向量v打包编码，输出一个环上的明文多项式m。
53.(3)he.enc
pk
(m)：加密算法，使用公钥对明文m进行加密，输出密文c。
54.(4)he.dec
sk
(c)：解密算法，使用公钥对密文c进行加密，输出明文m。
55.(5)he.decode(m)：解码算法，将一个环上明文多项式m解码，输出为一个数值向量v。
56.(6)he.add
evk
(e1，c2)：同态加法运算，c1和c2分别是m1和m2的对应密文，输出c
add
是m1+m2的对应密文。
57.(7)he.mul
evk
(c1，c2)：同态乘法运算，c1和c2分别是m1和m2的对应密文，输出c
mul
是m1×
m2的对应密文。
58.(8)he.rotateleft(c，i)，对密文c中对应的明文槽元素向左移动i位。
59.(9)he.rotateright(c，i)，对密文c中对应的明文槽元素向右移动i位。
60.同态加密提供密文计算的优势，在整个密文向量内积的计算过程中，向量的原始数据始终不暴露给计算方或者恶意第三方，保证了数据拥有方的隐私性。
61.步骤s4：密文内积快速计算步骤，基于两种形式的打包编码加密后的密文多项式，利用单个密文内部打包向量局部求和算法，实现密文域内向量内积的批量计算。
62.具体地，如表2所示，步骤s4具体包括：
63.s41：对s3获得的两种形式下的密文多项式ctxt和bctxt，于密文域计算并获得两密文多项式的差c
i，j
＝he.sub(ctxti，bctxtj)，i＝1，...，s，j＝1，2，...，r，其中，ctxt为：单个密文重复编码的密文多项式，bctxt为：若干个向量串联编码的密文多项式。
64.s42：对两密文多项式的差进行同态乘法计算，获得c
i，j
＝he.square(c
i，j
)，i＝1，...，s，j＝1，2，...，r；
65.s43：对密文计算其内部向量的局部和c
i，j
＝partialsum(c
i，j
，k)，其中k表示内部打包的单个向量长度。
66.进一步地，密文所对应的打包向量局部求和的算法可以是：令一个密文c＝he.encrypt(v1，v2，...，v
t
)，其中vi表示维度为k的一个向量。对密文c所对应的打包向量局部求和，得到新的密文c
‘
＝he.encrypt(sv1，sv2，...，sv
t
)，其中
67.更进一步地，如表1所示，密文所对应的打包向量局部求和的算法具体步骤如下：
68.①
初始化一个辅助向量并编码为明文多项式表示t个长度为k的向量的串联，且初始化c
‘
＝c；
69.②
设置循环变量j＝logk-1；
70.③
利用同态移位、同态加法、同态乘法等运算依次计算tmp＝he.rotateright(init，2j)，s1＝he.mul(init，c
′
)，s2＝he.mul(tmp，c
′
)，s2＝he.rotateleft(s2，2j)，c
′
＝he.add(s1，s2)；
71.④
如果循环变量j＞0，那么计算tmp＝he.rotateleft(tmp，2j+2
j-1
)，init＝he.mul(tmp，init)；
72.⑤
循环变量j＝j-1，如果j≥0，则返回至第
③
步；
73.⑥
重新设置循环变量j＝0；
74.⑦
依次计算tmp＝he.rotateright(c’，2j)，c
′
＝he.add(c
′
，tmp)；
75.⑧
循环变量j＝j+1，如果j＜logk，则返回至第
⑦
步；
76.⑨
返回新密文c
‘
，表示密文打包向量局部求和的结果。
77.表1单个密文内部打包向量局部求和表
[0078][0079]
[0080]
s44：得到一个密文内积矩阵c，其中c
i，j
表示第i个向量与第j组打包向量的所有内积。
[0081]
表2密文域向量内积批量计算cinnerprod(ctxt，bctxt，s，r，k)
[0082][0083]
步骤s5：密文内积矩阵解密步骤，对密文矩阵的每一个元素进行解密，得到明文多项式矩阵。
[0084]
优选地，步骤s5包括：对密文矩阵c的每一个元素c
i，j
，i＝1，...，s，j＝1，2，...，r进行解密，得到明文多项式矩阵p，即矩阵元素p
i，j
＝he，decrypt(c
i，j
)，i＝1，...，s，j＝1，2，...，r。
[0085]
步骤s6：密文内积矩阵解码步骤，对明文多项式矩阵中的每一个元素依次进行解码，得到明文的打包向量内积。
[0086]
优选地，步骤s6包括：对明文多项式矩阵p中的每一个元素依次进行解码，得到明文的打包向量内积vprod
i，j
＝he，decode(p
i，j
)，i＝1，...，s，j＝1，2，...，r，包含了向量vi，i＝1，...，s与第j组打包向量的内积值。
[0087]
步骤s7：向量卷积运算结果获取步骤，将s6获得的各向量内积值提取出来，得到所有向量的内积值矩阵。
[0088]
优选地，步骤s7包括：将所有向量内积值提取出来，得到所有向量的内积值矩阵prod，即矩阵元素
[0089]
本发明公开了一种基于块型编码的密文内积快速计算方法，当不可信的计算方在计算向量内积时，无法获知向量的原始数据信息；此外，恶意的第三方在整个向量内积的密态计算过程中，也无法窃取密文中所包含的任何信息并实施恶意操作。本发明提出的密文内积快速计算方法可以应用于机器学习、计算机图形学等需要矩阵向量运算的场景，为向量内积的计算提供安全防护。
[0090]
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于块型编码的密文内积快速计算方法，其特征在于，所述密文内积快速计算方法包括如下步骤：s1：向量扩展步骤，将各待求内积的明文向量进行补0扩展；s2：块型编码步骤，基于块型编码，对向量进行两种形式的打包编码，包括：单个向量重复编码和若干个向量串联编码；s3：同态加密步骤，采用同态加密方法对s2完成块型编码的明文多项式进行加密，得到密文多项式；s4：密文内积快速计算步骤，基于两种形式的打包编码加密后的密文多项式，利用单个密文内部打包向量局部求和算法，实现密文域内向量内积的批量计算；s5：密文内积矩阵解密步骤，对密文矩阵的每一个元素进行解密，得到明文多项式矩阵；s6：密文内积矩阵解码步骤，对明文多项式矩阵中的每一个元素依次进行解码，得到明文的打包向量内积；s7：向量卷积运算结果获取步骤，将s6获得的各向量内积值提取出来，得到所有向量的内积值矩阵。2.如权利要求1所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s2中，单个向量重复编码为：将若干重复的扩展后向量打包编码为一个明文多项式。3.如权利要求1所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s2中，若干个向量串联编码为：将全部向量进行分组，如果最后一组向量数量不足，则使用零向量替代；并将每一组中扩展后的各向量进行串联，打包编码为一个明文多项式。4.如权利要求1所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s1中，各待求内积的明文向量为v1，v2，...，v
s
，各向量长度为d，即v
i
＝{v
i，1
，v
i，2
，...，v
i，d
}，1≤i≤s；令n表示明文槽的数量；令k是n的一个因子，即k|n，且k≥d；令t＝n/k，z＝k-d。5.如权利要求4所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s4具体包括：s41：对s3获得的两种形式下的密文多项式ctxt和bctxt，于密文域计算并获得两密文多项式的差c
i，j
＝he.sub(ctxt
i
，bctxt
j
)，i＝1，...，s，j＝1，2，...，r，其中，ctxt为：单个密文重复编码的密文多项式，bctxt为：若干个向量串联编码的密文多项式；s42：对两密文多项式的差进行同态乘法计算，获得c
i，j
＝he.square(c
i，j
)，i＝1，...，s，j＝1，2，...，r；s43：对密文计算其内部向量的局部和c
i，j
＝partialsum(c
i，j
，k)，其中k表示内部打包的单个向量长度；s44：得到一个密文内积矩阵c，其中c
i，j
表示第i个向量与第j组打包向量的所有内积。6.如权利要求5所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s5包括：对密文矩阵c的每一个元素c
i，j
，i＝1，...，s，j＝1，2，...，r进行解密，得到明文多项式矩阵p，即矩阵元素p
i，j
＝he，decrypt(c
i，j
)，i＝1，...，s，j＝1，2，...，r。7.如权利要求6所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s6包
括：对明文多项式矩阵p中的每一个元素依次进行解码，得到明文的打包向量内积vprod
i，j
＝he，decode(p
i，j
)，i＝1，...，s，j＝1，2，...，r，包含了向量v
i
，i＝1，...，s与第j组打包向量的内积值。8.如权利要求7所述的基于块型编码的密文内积快速计算方法，其特征在于，步骤s7包括：将所有向量内积值提取出来，得到所有向量的内积值矩阵prod，即矩阵元素prod
i，l
＝vprod
i，「l/t」
[(「l/t」-1)k+1]，i＝1，...，s，l＝1，2，...，s。

技术总结
本发明公开了一种基于块型编码的密文内积快速计算方法，包括：S1：向量扩展步骤；S2：块型编码步骤，基于块型编码，对向量进行两种形式的打包编码，包括：单个向量重复编码和若干个向量串联编码；S3：同态加密步骤；S4：密文内积快速计算步骤，基于两种形式的打包编码加密后的密文多项式，利用单个密文内部打包向量局部求和算法，实现密文域内向量内积的批量计算；S5：密文内积矩阵解密步骤，对密文矩阵的每一个元素进行解密，得到明文多项式矩阵；S6：密文内积矩阵解码步骤，对明文多项式矩阵中的每一个元素依次进行解码，得到明文的打包向量内积；S7：将S6获得的各向量内积值提取出来，得到所有向量的内积值矩阵。所有向量的内积值矩阵。所有向量的内积值矩阵。


技术研发人员：黄云帆 汤殿华 尉小鹏 徐温菊 赵伟
受保护的技术使用者：中国电子科技集团公司第三十研究所
技术研发日：2023.05.29
技术公布日：2023/8/9