基于椭圆曲线的乘法三元组生成方法、装置、设备及介质

摘要

本发明提供一种基于椭圆曲线的乘法三元组生成方法、装置、设备及介质，该方法适用于第一参与节点，包括：选取随机非负整数x(1)和y(1)，对x(1)进行基于椭圆曲线的同态加密处理得到第一密文，将第一密文发送至预先选取有随机非负整数x(2)和y(2)的另一参与节点，以使另一参与节点将y(2)与所述第一密文进行同态数乘运算后再与预先选取的第二随机数r(2)相加，得到第一随机化结果后返回至所述第一参与节点；对所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第一解密结果，而后根据第一解密结果计算第一乘积z(1)，并根据第一乘积生成第一三元组(x(1),y(1),z(1))。本发明能够在椭圆曲线密码体系上生成乘法三元组，并且不会浪费乘法三元组的取值空间。

说明书

技术领域

本发明涉及加密技术领域，尤其涉及一种基于椭圆曲线的乘法三元组生成方法、装置、设备及介质。

背景技术

在一些业务场景中，每个业务平台均收集有各自的业务数据。例如，浏览器平台收集用户的网页浏览数据，网购平台收集用户的网购数据。这些业务 数据很有价值，通常作为业务平台的隐私信息保存。各业务平台不期望与其 他业务平台共享原始形式的业务数据。但在一些需求中，多个业务平台期望 在不公开各方的业务数据的情况下进行协同计算，以提高业务处理能力。例如，浏览器平台与网购平台期望利用网页搜索数据和网购数据构建更准确的推荐模型，从而基于该推荐模型，浏览器平台为用户更精准的推荐网页或广告，网购平台为用户更精准的推荐商品。

安全多方计算（Secure Multi-Party Computation，SMC）用于解决一组互不信任的参与方之间保护隐私的协同计算问题。多个业务平台可以作为参与 方，在不公开各自业务数据的情况下，利用安全多方计算来实现对业务数据 的协同计算。

当前较为成熟可实施的安全多方计算的实现方法主要包括基于秘密分享的安全多方计算方法和基于混淆电路的安全多方计算方法。其中基于秘密分享的安全多方计算方法具有算法简洁、计算方易于扩充等特点，成为落地安全多方计算的首选。秘密分享分为分享和恢复两个阶段。在分享阶段，将秘密以一定的方式分拆成多份碎片，并分发给不同的参与者；在恢复阶段，多个参与者根据自己所掌握碎片，共同协作恢复出原始秘密。秘密分享要求只有足够多的参与方才能恢复出原始秘密，如果参与方不够，将无法恢复原始秘密。

在实现基于秘密分享的安全多方计算中，需要使用Beaver乘法三元组（简称乘法三元组）来辅助和加速乘法的实现。乘法三元组是安全乘法计算甚至是所有安全多方计算的重要资源，是计算各方对于两个乘数x、y和乘积z=xy这三个数的秘密分享的总称。以两方为例，x=x1+x2，y=y1+y2，z=z1+z2，两方分别掌握(x1,y1,z1)和(x2,y2,z2)。乘法三元组的生成可以通过多种密码学方法来实现。

当前较为成熟的乘法三元组生成方法有基于TEE（Trusted ExecutionEnvironmen，可信执行环境）的方法、基于OLE（Oblivious Linear function Evaluation，不经意线性函数取值）的方法以及基于HE（Homomorphic Encryption，同态加密）的方法等。

在基于同态加密的方法中，多采用较为成熟的Paillier（帕耶）同态加密。基于Paillier同态加密的三元组生成方法是基于复合剩余假设并且计算方法主要是模指数运算，如果需要保持Paillier同态加密方案的安全性，要求明文空间需要与密钥空间长度相仿，这样使得产生出来的三元组的取值空间也较大，当安全多方计算的客体数据范围较小时，这种大范围的取值空间将会是一种浪费。此外，安全多方计算系统作为用户的信息系统的一部分，需基于已有的系统和密码体系，在某些特殊领域和行业，需求方已经有较为成熟的椭圆曲线密码体系，并且替换这一体系的成本较高。在为此类用户提供安全多方计算建设方案时，需要提供基于椭圆曲线的乘法三元组生成方法。

发明内容

针对上述现有技术中的问题，本发明提供一种基于椭圆曲线的乘法三元组生成方法、装置、设备及介质，以在椭圆曲线密码体系上生成乘法三元组，并且生成的乘法三元组不会浪费取值空间。

为了实现上述目的，本发明提供一种基于椭圆曲线的乘法三元组生成方法，适用于第一参与节点，该方法包括：

选取比特长度小于等于预设长度阈值的第一随机非负整数x

对所述第一随机非负整数x

当接收到所述第一随机化结果后，对所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第一解密结果w

当接收到所述第二参与节点发送的第二密文，且所述第二密文是通过对所述第三随机非负整数x

在本发明一个优选实施例中，所述对所述第一随机非负整数x

对所述第一随机非负整数x

利用基于椭圆曲线的厄格玛尔算法，对编码至所述椭圆曲线上的点进行加密，得到所述第一密文。

在本发明一个优选实施例中，所述对所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第一解密结果，包括：

利用基于椭圆曲线的厄格玛尔算法，将所述第一随机化结果解密为所述椭圆曲线上的点；

对解密得到的所述椭圆曲线上的点进行译码，得到所述第一解密结果。

为了实现上述目的，本发明还提供一种基于椭圆曲线的乘法三元组生成方法，适用于第一参与节点，该方法包括：

选取比特长度大于预设长度阈值的第一随机非负整数x

将所述第一随机非负整数x

针对每个所述第一随机非负整数x

对第i个所述第一随机非负整数x

当接收到第i个所述第一随机化结果后，对第i个所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第i个第一解密结果 w

对N个所述第一乘积分量进行聚合处理，得到第一乘积z

当接收到所述第二参与节点发送的第i个第二密文，且第i个所述第二密文是通过对第i个所述第三随机非负整数x

在本发明一个优选实施例中，所述将所述第一随机非负整数x

根据中国剩余定理，将所述第一随机非负整数x

所述对N个所述第一乘积分量进行聚合处理，得到第一乘积 z

根据中国剩余定理，对N个所述第一乘积分量进行聚合处理，得到第一乘积z

为了实现上述目的，本发明还提供一种基于椭圆曲线的乘法三元组生成装置，适用于第一参与节点，该装置包括：

选取模块，用于选取比特长度小于等于预设长度阈值的第一随机非负整数x

同态加密模块，用于对所述第一随机非负整数x

同态解密模块，用于在接收到所述第一随机化结果后，对所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第一解密结果w

计算模块，用于根据如下公式计算第一乘积z

三元组生成模块，用于生成第一三元组(x

同态数乘模块，用于在接收到所述第二参与节点发送的第二密文，且所述第二密文是通过对所述第三随机非负整数x

随机化模块，用于将所述同态数乘模块输出的结果与所述第一随机数r

在本发明一个优选实施例中，所述同态加密模块具体用于：

对所述第一随机非负整数x

利用基于椭圆曲线的厄格玛尔算法，对编码至所述椭圆曲线上的点进行加密，得到所述第一密文。

为了实现上述目的，本发明还提供一种基于椭圆曲线的乘法三元组生成装置，适用于第一参与节点，该装置包括：

选取模块，用于选取比特长度大于预设长度阈值的第一随机非负整数x

分解模块，用于将所述第一随机非负整数x

N个同态加密模块，第i个所述同态加密模块用于对第i个所述第一随机非负整数x

N个同态解密模块，第i个所述同态解密模块用于在接收到第i个所述第一随机化结果后，对第i个所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第i个第一解密结果w

N个计算模块，第i个所述计算模块用于根据以下公式计算第i个第一乘积分量z

聚合模块，用于对N个所述第一乘积分量z

三元组生成模块，用于生成第一三元组(x

N个同态数乘模块，第i个所述同态数乘模块用于在接收到所述第二参与节点发送的第i个第二密文，且第i个所述第二密文是通过对第i个所述第三随机非负整数x

N个随机化模块，第i个所述随机化模块用于将第i个所述同态数乘模块输出的结果与第i个所述第一随机数r

为了实现上述目的，本发明还提供一种电子设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现前述方法的步骤。

为了实现上述目的，本发明还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现前述方法的步骤。

通过采用上述技术方案，本发明具有如下有益效果：

本发明可以复用现有的椭圆曲线加密基础设施，减少改造和信任成本，支持任意比特长度的乘法三元组；可以接口式的方式接入到用户的安全多方计算体系内，与更底层和更上层的结构耦合度低，不影响用户系统底层模块和上层应用的技术方案实现；可以根据安全多方计算的客体数据规模来灵活选择乘法三元组的取值空间大小，避免产生过长比特的乘法三元组导致的资源浪费。

附图说明

图1为本发明实施例1的基于椭圆曲线的乘法三元组生成方法的流程图；

图2为本发明实施例2的基于椭圆曲线的乘法三元组生成方法的流程图；

图3为本发明实施例2中短比特三元组生成步骤的流程图；

图4为本发明实施例3的基于椭圆曲线的乘法三元组生成装置的结构框图；

图5为本发明实施例4的基于椭圆曲线的乘法三元组生成装置的结构框图；

图6为本发明实施例5的电子设备的硬件架构图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前 提下所获得的所有其他实施例，都属于本发明保护的范围。

在本发明使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本公开。在本公开和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。

实施例1

本实施例提供一种基于椭圆曲线的乘法三元组生成方法，如图1所示，该方法具体包括以下步骤：

S1011，参与节点P1选取第一随机数r

S1012，参与节点P2选取第二随机数r

例如，预设长度阈值可以设置为8，且选取x

S102，参与节点P1对所述第一随机非负整数x

在本实施列中，对所述第一随机非负整数x

S1021，对所述第一随机非负整数x

S1022，利用基于椭圆曲线的厄格玛尔算法，对编码至所述椭圆曲线上的点进行加密，得到所述第一密文。

S103，参与节点P2在接收到所述第一密文后，将所述第四随机非负整数y

S104，参与节点P2将步骤S103得到的同态数乘运算结果与预先选取的第二随机数r

S105，参与节点P1接收到所述第一随机化结果后，对所述第一随机化结果进行基于椭圆曲线的同态解密处理，基于同态加密同性，可以得到第一解密结果w

S106，参与节点P1根据如下公式计算第一乘积z

S107，参与节点P2对所述第三随机非负整数x

在本实施列中，对第三随机非负整数x

S108，参与节点P1接收到参与节点P2发送的第二密文后，将所述第二随机非负整数y

S109，参与节点P1将步骤S108得到的同态数乘运算结果与第一随机数r

S110，参与节点P2对所述第二随机化结果进行基于椭圆曲线的同态解密处理，得到第二解密结果w

S111，参与节点P2根据如下公式计算第二乘积z

本实施例中的步骤S102-S111可以概括为短比特三元组生成步骤。

本实施例适用于三元组取值空间要求较小的应用场景，基于短比特的随机非负整数生成的三元组不会造成取值空间的浪费；同时，本实施例可以复用现有的椭圆曲线加密基础设施，减少改造和信任成本，可以接口式的方式接入到用户的安全多方计算体系内，与更底层和更上层的结构耦合度低，不影响用户系统底层模块和上层应用的技术方案实现。

实施例2

本实施例提供一种基于椭圆曲线的乘法三元组生成方法，如图2和3所示，该方法包括以下步骤：

S2011，参与节点P1选取比特长度大于预设长度阈值的第一随机非负整数x

S2012，参与节点P2选取比特长度大于所述预设长度阈值的第三随机非负整数x

例如，预设长度阈值可以设置为8，且选取的x

S2021，参与节点P1将所述第一随机非负整数x

S2022，参与节点P2将所述第一随机非负整数x

在本实施例中，参与节点P1可以采用N维中国剩余定理（CRT）分解器，根据中国剩余定理，以公共模数p

参与节点P2同样可以采用N维中国剩余定理（CRT）分解器，根据中国剩余定理，以公共模数p

例如，如图2所示，预设长度阈值可以设置为8，当x

而后，可以参考实施例1的短比特三元组生成步骤依次对第i（i=1,…,N）个短比特（图2中示出为8比特）随机非负整数x

S203，参与节点P1对第i个所述第一随机非负整数x

S204，参与节点P2在接收到第i个所述第一密文后，将第i个所述第四随机非负整数y

S205，参与节点P2将步骤S204得到的结果与预先选取的第i个第二随机数r

S206，参与节点P1在接收到第i个所述第一随机化结果后，对第i个所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第i个第一解密结果w

S207，参与节点P1根据如下公式计算第i个第一乘积分量z

S208，参与节点P2对第i个所述第三随机非负整数x

S209，参与节点P1接收到参与节点P2发送的第i个第二密文后，将第i个所述第二随机非负整数y

S210，参与节点P1将步骤S210得到的结果与预先选取的第i个所述第一随机数r

S211，参与节点P2对第i个所述第二随机化结果进行基于椭圆曲线的同态解密处理，得到第i个第二解密结果w

S212，参与节点P2根据如下公式计算第i个第二乘积分量z

S213，参与节点P1对N个所述第一乘积分量z

在本实施例中，参与节点P1可以采用N维中国剩余定理（CRT）聚合器，以公共模数p

S214，参与节点P2对N个第二乘积分量z

在本实施例中，参与节点P2同样可以采用N维中国剩余定理（CRT）聚合器，以公共模数p

本实施例通过运用对随机非负整数的同态加密方案来构建随机非负整数的乘法三元组，并运用中国剩余定理来分解随机非负整数，将随机非负整数空间分解成多个较小的随机非负整数子空间，从而可以支持任意比特长度的乘法三元组，同时可以根据具体需要，灵活调节乘法三元组的数值范围，避免生成的乘法三元组浪费取值空间。此外，本实施例可以复用现有的椭圆曲线加密基础设施，减少改造和信任成本，可以接口式的方式接入到用户的安全多方计算体系内，与更底层和更上层的结构耦合度低，不影响用户系统底层模块和上层应用的技术方案实现。

在本实施例中，对于基于椭圆曲线同态加密方案的数乘运算的应用，仅使用了随机非负整数数乘作用于短随机非负整数空间，并且在每次使用时，密文的同态数乘运算仅使用一次，不会出现计算出来的新密文不可解密的情况，确保解密成功。

实施例3

本实施例提供一种基于椭圆曲线的乘法三元组生成装置，适用于第一参与节点，如图4所示，该装置包括：

选取模块11，用于选取比特长度小于等于预设长度阈值的第一随机非负整数x

同态加密模块12，用于对所述第一随机非负整数x

同态解密模块13，用于在接收到所述第一随机化结果后，对所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第一解密结果w

计算模块14，用于根据如下公式计算第一乘积z

三元组生成模块15，用于生成第一三元组(x

同态数乘模块16，用于在接收到所述第二参与节点发送的第二密文，且所述第二密文是通过对所述第三随机非负整数x

随机化模块17，用于将所述第一同态数乘模块输出的结果与所述第一随机数r

在本实施例中，所述同态加密模块12具体用于：

对所述第一随机非负整数x

利用基于椭圆曲线的厄格玛尔算法，对编码至所述椭圆曲线上的点进行加密，得到所述第一密文。

在本实施例中，所述同态解密模块13具体用于：

利用基于椭圆曲线的厄格玛尔算法，将所述第一随机化结果解密为所述椭圆曲线上的点；

对解密得到的所述椭圆曲线上的点进行译码，得到所述第一解密结果。

实施例4

本实施例提供一种基于椭圆曲线的乘法三元组生成装置，适用于第一参与节点，如图5所示，该装置包括：

选取模块21，用于选取比特长度大于预设长度阈值的第一随机非负整数x(1)和第二随机非负整数y

分解模块22，用于将所述第一随机非负整数x

N个同态加密模块23，第i个所述同态加密模块用于对第i个所述第一随机非负整数x

N个同态解密模块24，第i个所述同态解密模块用于在接收到第i个所述第一随机化结果后，对第i个所述第一随机化结果进行基于椭圆曲线的同态解密处理，得到第i个第一解密结果w

N个计算模块25，第i个计算模块用于计算第i个第一乘积分量z

聚合模块26，用于对N个所述第一乘积分量z

三元组生成模块27，用于生成第一三元组(x

N个同态数乘模块28，第i个所述同态数乘模块用于在接收到所述第二参与节点发送的第i个第二密文，且第i个所述第二密文是通过对第i个所述第三随机非负整数x

N个随机化模块29，第i个所述随机化模块用于将第i个所述同态数乘模块输出的结果与第i个所述第一随机数r

在本实施例中，所述分解模块根据中国剩余定理，将所述第一随机非负整数x

实施例5

本实施例提供一种电子设备，电子设备可以通过计算设备的形式表现（例如可以为服务器设备），包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其中处理器执行计算机程序时可以实现实施例1或2提供的基于椭圆曲线的数乘三元组生成方法。

图6示出了本实施例的硬件结构示意图，如图6所示，电子设备9具体包括：

至少一个处理器91、至少一个存储器92以及用于连接不同系统组件（包括处理器91和存储器92）的总线93，其中：

总线93包括数据总线、地址总线和控制总线。

存储器92包括易失性存储器，例如随机存取存储器（RAM）921和/或高速缓存存储器922，还可以进一步包括只读存储器（ROM）923。

存储器92还包括具有一组（至少一个）程序器924的程序/实用工具925，这样的程序器924包括但不限于：操作系统、一个或者多个应用程序、其它程序器以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。

处理器91通过运行存储在存储器92中的计算机程序，从而执行各种功能应用以及数据处理，例如本发明实施例1或2所提供的基于椭圆曲线的数乘三元组生成方法。

电子设备9进一步可以与一个或多个外部设备94（例如键盘、指向设备等）通信。这种通信可以通过输入/输出（I/O）接口95进行。并且，电子设备9还可以通过网络适配器96与一个或者多个网络（例如局域网（LAN），广域网（WAN）和/或公共网络，例如因特网）通信。网络适配器96通过总线93与电子设备9的其它器通信。应当明白，尽管图中未示出，可以结合电子设备9使用其它硬件和/或软件器，包括但不限于：微代码、设备驱动器、冗余处理器、外部磁盘驱动阵列、RAID（磁盘阵列）系统、磁带驱动器以及数据备份存储系统等。

应当注意，尽管在上文详细描述中提及了电子设备的若干单元/器或子单元/器，但是这种划分仅仅是示例性的并非强制性的。实际上，根据本申请的实施方式，上文描述的两个或更多单元/器的特征和功能可以在一个单元/器中具体化。反之，上文描述的一个单元/器的特征和功能可以进一步划分为由多个单元/器来具体化。

实施例6

本实施例提供了一种计算机可读存储介质，其上存储有计算机程序，所述程序被处理器执行时实现实施例1或2所提供的基于椭圆曲线的数乘三元组生成方法的步骤。

其中，可读存储介质可以采用的更具体可以包括但不限于：便携式盘、硬盘、随机存取存储器、只读存储器、可擦拭可编程只读存储器、光存储器件、磁存储器件或上述的任意合适的组合。

在可能的实施方式中，本发明还可以实现为一种程序产品的形式，其包括程序代码，当所述程序产品在终端设备上运行时，所述程序代码用于使所述终端设备执行实现实施例1或2所述的基于椭圆曲线的数乘三元组生成方法的步骤。

其中，可以以一种或多种程序设计语言的任意组合来编写用于执行本发明的程序代码，所述程序代码可以完全地在用户设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户设备上部分在远程设备上执行或完全在远程设备上执行。

虽然以上描述了本发明的具体实施方式，但是本领域的技术人员应当理解，这仅是举例说明，本发明的保护范围是由所附权利要求书限定的。本领域的技术人员在不背离本发明的原理和实质的前提下，可以对这些实施方式做出多种变更或修改，但这些变更和修改均落入本发明的保护范围。