用于多密钥同态加密的方法和设备

用于多密钥同态加密的方法和设备
1.本技术基于并要求2022年2月24日提交到韩国知识产权局的第10-2022-0024657号韩国专利申请和2022年11月17日提交到韩国知识产权局的第10-2022-0154691号韩国专利申请的优先权，其公开内容通过引用整体并入本文。
技术领域
2.一个或多个实施例涉及多密钥同态加密。更具体地，一个或多个实施例涉及一种通过重新使用多密钥同态加密中的误差来生成乘法密钥(multiplication key)的方法。


背景技术：

3.最近，已经开发了隐私保护机器学习方法，其中，可以通过在用户数据被加密的状态下执行运算操作来接收用户期望的操作结果。
4.隐私保护机器学习的示例是多密钥同态加密。在多密钥同态加密中，具有数据的每个用户生成他或她自己的秘密密钥，因此难以访问其他用户的数据。在应用多密钥同态加密方法的系统中，服务器拥有每个用户的公钥和乘法密钥，并通过使用这些密钥来执行密文操作。然而，当用户数量增加时，服务器必须拥有的公钥和乘法密钥的数量根据用户数量线性增加，需要长时间进行密文操作，并且还消耗大量的运算资源，诸如存储器。


技术实现要素：

5.一个或多个实施例包括一种用于通过在rerlwe环境中生成乘法密钥时使用基于环上带误差学习(rlwe，ring learning with error)生成的公钥的误差值来减少多密钥同态加密中乘法密钥的运算操作的方法。rerlwe环境是指修改的rlwe环境。
6.另外的方面将部分地在下面的描述中阐述，并且部分地将从描述中显而易见，或者可以通过实践本公开的所呈现的实施例来学习。
7.根据一个或多个实施例，一种用于执行多密钥同态加密的设备包括公钥生成器和乘法密钥生成器，公钥生成器被配置为通过使用针对每个客户端的秘密密钥来生成公钥，乘法密钥生成器被配置为通过重新使用在生成公钥时使用的公钥保护误差来生成乘法密钥。
8.用于执行多密钥同态加密的设备可以通过使用修改的rlwe样本来生成乘法密钥，并且修改的rlwe样本以(a，-as+x，ax+e)的形式定义，其中，a表示从rq上的均匀分布中选择的元素，s表示秘密密钥分布，并且x和e表示误差分布。
9.在用于执行多密钥同态加密的设备中，公钥可以以pki＝(a，bi＝-a
·
si+xi)的形式定义，其中，a表示从rq上的均匀分布中选择的元素，si表示秘密密钥，并且xi表示公钥保护误差。
10.在用于执行多密钥同态加密的设备中，公钥可以是mki＝a
·
xi+ei+p
·
si，其中，a表示从rq上的均匀分布中选择的元素，si表示秘密密钥，并且xi表示公钥保护误差，并且ei表示乘法密钥保护误差。
11.在用于执行多密钥同态加密的设备中，当客户端之间的先前通信可能时，可以针对所有乘法密钥生成共同乘法密钥mki＝a
·
xi+ei+p
·
si。
12.根据一个或多个实施例，一种用于执行多密钥同态加密的设备包括：秘密密钥生成器，被配置为生成秘密密钥；公钥保护误差选择器，被配置为从误差分布中选择公钥保护误差；公钥生成器，被配置为通过使用秘密密钥和公钥保护误差生成公钥；乘法密钥保护误差选择器，被配置为从误差分布中选择乘法密钥保护误差；以及乘法密钥生成器，被配置为通过使用秘密密钥、公钥保护误差和乘法密钥保护误差来生成乘法密钥。
13.根据一个或多个实施例，一种执行多密钥同态加密的方法包括：由公钥生成器通过使用针对每个客户端的秘密密钥来生成公钥，以及由乘法密钥生成器通过重新使用在生成公钥时使用的公钥保护误差来生成乘法密钥。
附图说明
14.通过以下结合附图的描述，本公开的某些实施例的上述和其他方面、特征和优点将更加明显，其中：
15.图1示出了当在基于环上带误差学习(rlwe)的多密钥同态加密系统中客户端之间的先前通信不可能时执行多密钥同态加密的示例；
16.图2示出根据实施例的用于执行多密钥同态加密的设备的内部配置；和
17.图3示出了根据实施例的当客户端之间的先前通信不可能时通过多密钥同态加密生成乘法密钥的示例。
具体实施方式
18.现在将详细参考实施例，其示例在附图中示出，其中，相同的附图标记始终表示相同的元件。在这方面，本实施例可以具有不同的形式，并且不应被解释为限于本文阐述的描述。因此，下面仅通过参考附图来描述实施例，以解释本说明书的各方面。如本文所使用的，术语“和/或”包括相关联的所列项目中的一个或多个的任何和所有组合。诸如
“……
中的至少一个”的表达当在元件列表之后时，修饰整个元件列表而不修饰列表的单个元件。
19.在下文中，参考附图描述本公开。
20.图1示出了当在基于环上带误差学习(rlwe)的多密钥同态加密系统100中用户之间的先前通信不可能时执行多密钥同态加密的示例。
21.多密钥同态加密系统100包括客户端110、112和114以及服务器120。客户端110、112和114以及服务器120均包括处理器和存储器。
22.服务器120可以根据基于带误差学习(lwe)的加密方法执行同态加密，并且可以通过使用根据基于环上带误差学习(rlwe)的加密方法的同态加密，通过同态加密操作单元122执行运算操作。
23.服务器120需要每个客户端的公钥和乘法密钥，以便对多密钥同态加密系统100的两个密文执行乘法操作。
24.当在基于rlwe的多密钥同态加密系统中客户端之间的先前通信可能时，使用共同
公钥和共同乘法密钥
[0025][0026][0027]
然而，如图1所示的示例，当客户端之间的先前通信不可能时，客户端110、112和114均将公钥pki、乘法密钥mki和密文cti发送到服务器120，并且服务器120的同态加密操作单元122执行同态加密操作并将生成的密文发送到客户端110、112和114中的每一个。然后，客户端110、112和114通过彼此协作来执行解密。
[0028]
这里，当客户端的数量增加时，服务器120必须拥有的客户端110、112和114的公钥pki和乘法密钥mki的数量增加，导致存储器使用的增加。另外，当客户端110、112和114之间的通信不可能时，所有同态操作将由服务器120执行，并且乘法操作的操作时间变长。
[0029]
参考图1，描述了当客户端之间的通信不可能时执行基于rlwe的多密钥同态加密的方法。
[0030]
为了执行多密钥同态加密，客户端110、112和114中的每一个生成密文模数q0、q1、...q
l
和特殊模数p0、p1、...、pk。在这种情况下，rlwe样本的格式定义如下。
[0031]
(a，-as+x)、a
←rq
、s
←
χ
key
、x
←
χ
err
[0032]
其中，a表示所有客户端需要共享的元素，并且从定义在rq*r
p
上的均匀分布中选择，s表示秘密密钥分布，e表示误差分布。这里，rq*r
p
＝并且，
[0033]
每个客户端通过rlwe样本生成秘密密钥si，并通过使用秘密密钥si生成公钥pki和乘法密钥mki。
[0034]
pki＝(a，bi＝-a
·
si+xi)、mki＝(mk
i，0
，mk
i，1
，mk
i，2
)
[0035]
乘法密钥mki的每个元素如下。
[0036]
mk
i,0
从在rq*r
p
上定义的均匀分布中选择。
[0037]
mk
i，1
＝-si·
mk
i，0
+e
i，1
+p
·ri
[0038]
mk
i，2
＝-ri·
a+e
i，2
+p
·
si[0039]ei，1
和e
i，2
表示rq上的误差分布，ri←
χ和ri从密钥分布中选择。例如，从秘密密钥分布中选择ri，并且ri在乘法运算期间被移除以用作用于执行乘法操作的临时秘密密钥。
[0040]
当客户端110、112和114之间的先前通信不可能时，如图1所示的示例所示，服务器120必须拥有的公钥pki＝(a,bi＝-asi+xi)和乘法密钥mki＝(mk
i，0
，mk
i，1
，mk
i，2
)变得庞大。另外，当客户端使用具有例如具有有限资源的存储器的电子设备，诸如移动电话时，生成用于同态操作的密钥会是繁重的。
[0041]
为了解决该问题，在实施例中，可以重新使用在生成rlwe样本时使用的公钥保护误差，以减小乘法密钥的尺寸并减少操作时间。这将参考图2进行描述。
[0042]
图2示出根据实施例的用于执行多密钥同态加密的设备200的内部配置。
[0043]
用于执行多密钥同态加密的设备200在re-rlwe环境中实现。re-rlwe环境是指修改的环境，其中，重新使用在生成rlwe样本时使用的误差。re-rlwe样本的格式定义如下。
[0044]
(a，-as+x，ax+e)、a
←rq
、s
←
χ
key
、x，e
←
χ
err
[0045]
其中，a是从rq上的均匀分布中选择的元素，s是秘密密钥分布，并且x和e表示rq上的误差分布，并且x表示公钥保护误差，并且e表示乘法密钥保护误差。从任意密钥分布中选择公钥保护误差和乘法密钥保护误差，并且任意密钥分布的示例包括离散高斯分布。
[0046]
用于执行多密钥同态加密的设备200包括秘密密钥生成器210、公钥生成器220、公钥保护误差选择器230、乘法密钥生成器240和乘法密钥保护误差选择器250。
[0047]
秘密密钥生成器210通过re-rlwe样本生成秘密密钥si。不同于rlwe样本，通过将ax+e添加到re-rlwe样本，可以减小乘法密钥的尺寸。
[0048]
例如，当客户端之间的通信困难时，为了执行rlwe多密钥同态加密的乘法，需要公钥pki＝(a，bi＝-a
·
si+xi)和乘法密钥mki＝(a'，b'，c')＝')＝(mk0，mk1，mk2)。然而，根据实施例，为了当客户端之间的通信困难时执行rlwe多密钥同态加密的乘法，需要公钥pki＝(a，bi＝-a
·
si+xi)和乘法密钥mki＝c＝ax+e。也就是说，在现有技术中，存在需要三个元素的乘法密钥(mk0，mk1，mk2)，但是在本公开中，乘法密钥被减小到一个元素mki，并且因此乘法密钥的尺寸被减小。
[0049]
公钥生成器220通过使用秘密密钥si和由公钥保护误差选择器230选择的公钥保护误差xi来生成公钥pki＝(a，bi＝-a
·
si+xi)。
[0050]
乘法密钥生成器240通过使用秘密密钥si、公钥保护误差xi和由乘法密钥保护误差选择器250选择的乘法密钥保护误差ei来生成乘法密钥mki＝a
·
xi+ei+p
·
si。换句话说，当生成乘法密钥时，重新使用在生成公钥pki＝(a，bi＝-α
·
si+xi)时使用的公钥保护误差xi，从而减小乘法密钥的尺寸。乘法密钥保护误差选择器250从e
←
χ
err
中选择乘法密钥保护误差ei。例如，可以从离散高斯分布中选择乘法密钥保护误差ei。
[0051]
在乘法密钥mki＝a
·
xi+ei+p
·
si中，a
·
xi和ei是构成re-rlwe样本的元素。ei表示乘法密钥保护误差，并且不容易通过ei找到公钥保护误差xi，使得整个分布表现为均匀分布。p是当在同态加密操作中执行乘法时防止误差值快速增加的变量。
[0052]
当客户端之间的先前通信可能时，乘法密钥生成器240针对所有乘法密钥生成共同乘法密钥k表示客户端的数量。
[0053]
图3示出了根据实施例的当客户端之间的先前通信不可能时rlwe环境和re-rlwe环境中的每一个中的乘法密钥。
[0054]
在现有技术中，当客户端之间的先前通信不可能时，客户端310生成秘密密钥、公钥a和b以及乘法密钥(mk0，mk1，mk2)。在实施例中，客户端320生成秘密密钥、公钥a和b以及修改的乘法密钥mki，并且相应地，相关技术的乘法密钥(mk0，mk1，mk2)被改变为mki，并且乘法密钥的尺寸被减小到1/3。
[0055]
即使客户端之间的先前通信可能，根据现有技术，客户端生成秘密密钥、公钥a和b以及乘法密钥在实施例中，客户端生成秘密密钥、公钥a和b以及乘法密钥mki，
因此，现有技术的乘法密钥被改变为mki，并且乘法密钥的尺寸被减小1/2。
[0056]
上述设备可以被实现为硬件组件、软件组件和/或硬件组件和软件组件的组合。例如，实施例中描述的设备和组件可以通过使用至少一个或多个通用计算机或专用计算机来实现，诸如处理器、控制器、算术逻辑单元(alu)、数字信号处理器、微计算机、现场可编程门阵列(fpga)、可编程逻辑单元(plu)、微处理器或可以执行并响应指令的任何其他设备。处理装置可以执行操作系统(os)和在os上运行的一个或多个软件应用。此外，处理装置可以响应于软件的执行而访问、存储、操纵、处理和生成数据。为了便于理解，可以描述使用单个处理装置，但是本领域普通技术人员将意识到处理装置可以包括多个处理元件和/或多种类型的处理元件。例如，处理装置可包括多个处理器或单个处理器以及控制器。处理装置也可以具有诸如并行处理器的其他处理配置。
[0057]
根据实施例的方法可以体现为可由各种计算机装置执行的程序命令，并且可以记录在计算机可读记录介质上。计算机可读记录介质可以单独地或组合地包括程序命令、数据文件、数据结构等。记录在计算机可读记录介质上的程序命令可以被专门设计和配置用于实施例，或者可以是计算机软件领域的普通技术人员公知和可用的。计算机可读记录介质的示例包括诸如硬盘、软盘或磁带的磁介质，诸如cd-rom或dvd的光介质，诸如光磁软盘的磁光介质，以及诸如rom、ram或闪存的专门配置为存储和执行程序命令的硬件设备。程序命令的示例包括可以由计算机通过使用解释器等执行的高级语言代码以及由编译器制作的机器语言代码。
[0058]
根据通过重新使用多密钥同态加密中的误差来生成乘法密钥的方法，作为实施例，可以减小乘法密钥的尺寸，从而减少客户端和服务器对存储器的使用量。
[0059]
此外，在不使用客户端间通信的多密钥同态加密中，在现有方法中，需要modup和moddown操作均两次以执行一个同态乘法。然而，根据实施例的多密钥同态加密方法，可以减小乘法密钥的尺寸，并且还仅需要一次modup操作和moddown操作，从而减少了整个乘法操作时间。
[0060]
虽然已经参考本公开的示例具体示出和描述了本公开，但是本领域普通技术人员将理解，在不脱离由所附权利要求限定的本公开的精神和范围的情况下，可以在其中进行形式和细节上的各种改变。例如，即使上述技术以与上述方法不同的顺序执行，和/或诸如上述系统、结构、设备和电路的组件以与上述方法不同的形式耦接或组合，或者由其他组件或其等同物代替或替换，也可以获得适当的结果。因此，权利要求的其他实现方式、其他实施例和等同物落入权利要求的范围内。
[0061]
应当理解，本文描述的实施例应当仅在描述性意义上考虑，而不是为了限制的目的。每个实施例内的特征或方面的描述通常应被认为可用于其他实施例中的其他类似特征或方面。虽然已经参考附图描述了一个或多个实施例，但是本领域普通技术人员将理解，在不脱离由所附权利要求限定的本公开的精神和范围的情况下，可以在其中进行形式和细节上的各种改变。

技术特征：
1.一种用于执行多密钥同态加密的设备，所述设备包括：公钥生成器，被配置为通过使用针对每个客户端的秘密密钥来生成公钥；以及乘法密钥生成器，被配置为通过重新使用在生成公钥时使用的公钥保护误差来生成乘法密钥。2.如权利要求1所述的设备，其中，所述乘法密钥使用修改的环上带误差学习(rlwe)样本来生成，并且修改的rlwe样本以(a，-as+x，ax+e)的形式定义，其中，a表示从rq上的均匀分布中选择的元素，s表示秘密密钥分布，并且x和e表示误差分布。3.如权利要求1所述的设备，其中，所述公钥以pk
i
＝(a，b
i
＝-a
·
s
i
+x
i
)的形式定义，其中，a表示从rq上的均匀分布中选择的元素，s
i
表示秘密密钥，并且x
i
表示公钥保护误差。4.如权利要求1所述的设备，其中，所述公钥是mk
i
＝a
·
x
i
+e
i
+p
·
s
i
，其中，a表示从rq上的均匀分布中选择的元素，s
i
表示秘密密钥，并且x
i
表示公钥保护误差，并且e
i
表示乘法密钥保护误差。5.如权利要求4所述的设备，其中，当客户端之间的先前通信可能时，针对所有乘法密钥生成共同乘法密钥mk
i
＝α
·
x
i
+e
i
+p
·
s
i
。6.一种用于执行多密钥同态加密的设备，所述设备包括：秘密密钥生成器，被配置为生成秘密密钥；公钥保护误差选择器，被配置为从误差分布中选择公钥保护误差；公钥生成器，被配置为通过使用秘密密钥和公钥保护误差来生成公钥；乘法密钥保护误差选择器，被配置为从误差分布中选择乘法密钥保护误差；以及乘法密钥生成器，被配置为通过使用秘密密钥、公钥保护误差和乘法密钥保护误差来生成乘法密钥。7.如权利要求6所述的设备，其中，所述秘密密钥使用修改的环上带误差学习(rlwe)样本来生成，并且修改的rlwe样本以(a，-as+x，ax+e)的形式定义并生成乘法密钥，其中，a表示从rq上的均匀分布中选择的元素，s表示秘密密钥分布，x表示公钥保护误差，并且e表示乘法密钥保护误差。8.一种执行多密钥同态加密的方法，所述方法包括：由公钥生成器通过使用针对每个客户端的秘密密钥来生成公钥；以及由乘法密钥生成器通过重新使用在生成公钥时使用的公钥保护误差来生成乘法密钥。9.如权利要求8所述的方法，其中，所述乘法密钥使用修改的环上带误差学习(rlwe)样本来生成，并且修改的rlwe样本以(a，-as+x，ax+e)的形式定义，其中，a表示从rq上的均匀分布中选择的元素，s表示秘密密钥分布，并且x和e表示误差分布。10.如权利要求8所述的方法，其中，所述公钥以pk
i
＝(a，b
i
＝-α
·
s
i
+x
i
)的形式定义，a表示从rq上的均匀分布中选择的元素，si表示秘密密钥，并且xi表示公钥保护误差。11.如权利要求8所述的方法，其中，所述公钥是mk
i
＝α
·
x
i
+e
i
+p
·
s
i
，并且，a表示从rq上的均匀分布中选择的元素，s
i
表示秘密密钥，并且x
i
表示公钥保护误差，并且e
i
表示乘法
密钥保护误差。12.如权利要求11所述的方法，其中，当客户端之间的先前通信可能时，针对所有乘法密钥生成共同乘法密钥mk
i
＝α
·
x
i
+e
i
+p
·
s
i
。13.一种计算机可读记录介质，其上记录有用于执行如权利要求8所述的方法的程序。

技术总结
一种用于执行多密钥同态加密的设备，包括：公钥生成器，被配置为通过使用针对每个客户端的秘密密钥来生成公钥；以及乘法密钥生成器，被配置为通过重新使用在生成公钥时使用的公钥保护误差来生成乘法密钥。通过重新使用公钥保护误差来减小乘法密钥的尺寸，可以减少操作时间和存储器。作时间和存储器。作时间和存储器。


技术研发人员：卢宗善 金荣植 具滋贤 李俊雨
受保护的技术使用者：朝鲜大学校产学协力团
技术研发日：2023.02.20
技术公布日：2023/8/28