基于中国剩余定理构造的无可信安装的多线性映射方法

摘要

本发明提供一种基于中国剩余定理构造的无可信安装的多线性映射方法，包括：每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布；每个参与方使用中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数；每个参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射。该方法使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

说明书

技术领域

本发明信息安全技术领域，具体涉及一种基于中国剩余定理构造的无可信安装的多线性映射方法、一种非临时性计算机可读存储介质和一种计算机设备。

背景技术

多线性映射是密码原语是双线性映射的一种推广，不仅能够用来构造非交互式密钥交换协议，三方Diffie-Hellman密钥交换协议和各种公钥加密方案，还广泛用于证据加密(WE：Witness Encryption)、不可区分模糊器(IO：Indistinguishability Obfuscation)和函数加密(FE：Function Encryption)等。随着多线性映射在密码学中的应用范围不断扩大，作为应用基础的构造方案将越来越重要。

现有的多线性映射算法都需要保密秘密元素，即在初始化阶段需要存在可信中心以产生方案的初始化参数，可信中心对初始化算法中选择和使用的秘密参数保密，仅仅发布构造方案初始化算法产生的公共参数。这种可信安装要求不仅会损害系统构造的安全性，而且在网络环境下有时无法获得一个可信中心。

发明内容

本发明为解决上述技术问题，提供了一种基于中国剩余定理构造的无可信安装的多线性映射方法，使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，则通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

本发明还提出一种非临时性计算机可读存储介质。

本发明还提出一种计算机设备。

本发明采用的技术方案如下：

本发明第一方面实施例提出了一种基于中国剩余定理构造的无可信安装的多线性映射方法，包括以下步骤：每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布；所述每个参与方使用所述中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数；每个所述参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射。

根据本发明的一个实施例，使用所述中国剩余定理将各方的公共参数进行组合时，利用NTL(一种高性能的可移植C++库，提供用于处理带符号的任意长度整数以及整数和有限域上的矢量，矩阵和多项式的数据结构和算法)函数库使用所述中国剩余定理将n个整数环上理想的构造组合在一起，将整数环上定义的中国剩余定理直接应用到多项式环。

根据本发明的一个实施例，所述每个参与方使用所述中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数，包括：计算模q，其中，

本发明第二方面实施例提出了一种非临时性计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现本发明第一方面实施例所述的基于中国剩余定理构造的无可信安装的多线性映射方法。

本发明第三方面实施例提出了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时，实现本发明第一方面实施例所述的基于中国剩余定理构造的无可信安装的多线性映射方法。

本发明的有益效果：

本发明使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

附图说明

图1是根据本发明一个实施例的基于中国剩余定理构造的无可信安装的多线性映射方法的流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

图1是根据本发明一个实施例的基于中国剩余定理构造的无可信安装的多线性映射方法的流程图。如图1所示，该方法包括以下步骤：

S1，每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布。

S2，每个参与方使用中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数。

S3，每个参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射。

具体地，使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，则通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射。为此，算法通过中国剩余定理(CRT：Chinese RemainderTheorem)将各方使用上述新随机化构造(所有参与方)产生的公共参数组合，后，各方自适应地产生无可信安装构造中的其它算法，例如，通用的加密算法，身份认证算法等，最终正确实现共用的公共参数环境下无可信安装的多线性映射。该方法是构造常用公钥加密算法的重要基础构件，其安全性基于新的困难问题假设——ext-GDDH/ext-GCDH。

在本发明的实施中，使用中国剩余定理将各方的公共参数进行组合时，利用NTL函数库使用中国剩余定理将n个整数环上理想的构造组合在一起，将整数环上定义的中国剩余定理直接应用到多项式环。

具体地，为使构造安全，使用中国剩余定理将n个整数环上理想的构造组合在一起；在整数环上定义的中国剩余定理，应用到多项式环的计算，以构造无可信安装的多线性映射。这种扩展不仅实现了无可信安装构造，而且构造方案中模的素因子不再需要保密。

本发明中的符号约定为：

设λ为安全参数。设符号

设n＝2

我们使用小写黑体字母表示列向量(如a)，大写黑体字母表示矩阵(如A)。向量或矩阵的转置使用上标符号T表示(如a

设

符号[a]

给定任意元素a∈R，符号MSB

本文使用标准渐近符号O(·)，Ω(·)，Θ(·)，ω(·)，o(·)。

可忽略量(Negligible Amount)是指对于任意正常数c，其渐近小于λ

基于中国剩余定理构造的无可信安装的多线性映射方法的具体实现过程为：

设q为N个不同素数的积，即

给定任意N个数(a

式中整数p

整数环

设

类似地，给定任意N个元素(a

其中整数p

设N＝κ+1为参与方个数。

为简单，符号

无可信安装构造的各个算法具体如下：

对于每个参与方

(1)第t方产生并发布公开参数{par

(1.1)选择足够大素数q

(1.2)随机抽样

(1.3)抽样素理想元素

(1.4)抽样素理想元素

(1.5)对于

(1.5.1)抽样选取元素

(1.5.2)计算

(1.5.3)产生明文元素e

(1.6)对于

(1.6.1)抽样选取元素

(1.6.2)计算h

(1.6.3)产生“0”测试参数

//p

(1.7)第t方发布公开参数

//这里假定素数q

(2)第t方使用CRT将所有方的公开参数{par

(2.1)计算模

(2.2)对于

(2.3)对于

(2.4)对于

(3)第t方输出所有方共用的公共参数：

其中，高斯抽样CRT编码算法d

(1)使用高斯抽样算法选取N个元素

(2)使用CRT计算产生R

1-级编码算法

(1)使用高斯抽样CRT编码算法产生d

(2)计算产生R

加法编码算法u←ADD(PAR，k，u

给定m个k-级编码

乘法编码算法u←MUL(PAR，1，u

给定k个1-级编码

“0”测试算法

(1)给定d

(2)给定一个κ-级编码u，计算“0”测试函数ISZero以判定u中明文元素是否为“0”，即

其中

提取算法

(1)给定d

(2)给定一个κ-级编码u，计算提取编码

(3)从v的每个系数中提取l＝(log q

由于无可信安装构造使用新随机化构造作为基本构件，因此在各方产生各自的公开参数par

λ：安全参数。

κ＝poly(λ)：多线性映射的次数。

n＝O(κλ log λ)：多项式环的维数。

σ＝O(n log n)：秘密素理想元素的抽样参数。

σ′＝O(n

产生0-级编码的高斯抽样参数。

q

τ＝2：公共参数中编码与“0”测试参数对的个数。

l

l＝(log q

所以，根据上述参数设置，构造中编码大小约为n|q|≈92κ N n log n，公共参数大小约为2τn|q|，其中|q|为q的比特长度。

本发明利用NTL函数库来实现使用中国剩余定理整数环上理想的构造多线性映射算法，并对算法的空间复杂性和执行时间复杂性进行评估。主要在整系数n阶多项式上进行操作，算法执行时间大部分用于多项式的乘法和加法。此外，公钥初始化过程中，随机选取向量和在高斯分布上采样也需要一定的时间。所以，对这两方面进行优化就非常必要。系统采用C++语言，采用NTL自带的函数库进行相关数学操作。计算机硬件配置为主机四核3.10GHZ，4GB RAM。

在计算中，计算复杂性最高的多项式乘法采用快速傅里叶变换(FFT)算法来提高计算速度。NTL库函数经过优化，所以运行速度较快。当安全参数λ取值不同时，对应的安全等级、编码加法、乘法和提取算法所需时间如表1所示。

表1：安全参数不同时的各项指标

本发明安全级单位以比特位计算，根据分析，在λ选取不同参数时，本方案能够达到的安全级别为2

对于本发明上述的基于中国剩余定理构造的无可信安装的多线性映射方法，下面给出安全性证明。

为给出构造安全性假设，首先引入无可信安装的难度假设问题wots-ext-GCDH/wots-ext-GDDH，然后给出无可信安装构造的已知攻击分析。

1.安全假设

为定义wots-ext-GCDH/wots-ext-GDDH难度问题，我们先考虑无可信安装构造的安全实验过程：

(1)产生公共参数PAR←INSTGen(1

(2)对于r＝0，1，L，κ：

(2.1)调用高斯抽样CRT编码算法抽样

d

r

(2.2)计算产生1-级编码：

(3)计算κ-级编码

(4)计算产生两个“0”测试参数

(4.1)计算与编码u

(4.2)计算随机的“0”测试参数

(5)产生提取比特串w

(6)产生随机提取比特串w

定义(wots-ext-GCDH/wots-ext-GDDH).根据上述安全实验，安全假设问题wots-ext-GCDH/wots-ext-GDDH定义如下：

无可信安装的κ-级提取CDH问题(wots-ext-GCDH)：给定{PAR，u

无可信安装的κ-级提取DDH问题(wots-ext-GDDH)：给定{PAR，u

D

D

评论.虽然难度问题wots-ext-GCDH/wots-ext-GDDH与问题ext-GCDH/ext-GDDH在形式上相似，但是并不能在它们之间建立多项式时间计算难度上的等价关系。因为虽然在公开参数par

由于无法建立wots-ext-GCDH/wots-ext-GDDH与ext-GCDH/ext-GDDH的提取比特串之间的关系，导致无法归约证明它们在计算难度上多项式时间等价。

假定任何概率多项式时间算法A攻击提取问题wots-ext-GCDH/wots-ext-GDDH的概率优势是可忽略的，即：

对于wots-ext-GCDH问题，我们有

Pr[A({PAR，u

对于wots-ext-GDDH问题，我们有

|Pr[A(w

其中算法A中省略了{PAR，u

评论.(1)本文给出安全假设也是为了便于证明基于无可信安装构造的应用安全性，否则基于构造的每个应用都要给出新的难度假设，容易导致应用的安全性不明确。(2)判定问题wots-ext-GDDH能够归约到计算求解问题wots-ext-GCDH。因为如果知道问题wots-ext-GCDH的提取比特串w

2.已知攻击分析

由于无可信安装构造使用新随机化构造作为基本组件，并运用多项式环上CRT将新随机化构造进行组合产生。因此，已知攻击分析主要包括二个方面：(1)针对新随机化构造的攻击分析；(2)“0”化攻击扩展分析。

(1)针对新随机化构造的攻击分析

因为各方都使用新随机化构造方法产生并发布各自的公开参数par

(2)“0”化攻击扩展分析

本节主要分析Cheon等人破解CLT13构造的“0”化攻击方法扩展对新随机化构造的安全影响。Cheon等人的“0”化攻击分为三个步骤：

第一步：计算产生一些“0”的κ-级编码，并乘以“0”测试参数，从而获得有理数

第二步：先计算两个矩阵方程的比以移除共同项，并产生特征值为有理数的矩阵；然后通过计算特征值以获得对应于明文的CRT中各成分的比，即在中国剩余定理中各个素数模下的余数比。

第三步：使用CRT中各成分的比，计算求解模的各个素因子，并进而直接计算求解CLT13构造中的其它秘密量。

现在具体分析“0”化攻击的扩展攻击无可信安装构造方案的不可行性。

第一步：这步攻击能够实行，但计算获得的矩阵方程是在域

设j，k，

其中，

h

w

-e

元素v

v

diag(h

其中符号diag(·，…，·)为对角矩阵。

类似于Cheon等人的“0”化攻击

第二步：这步攻击实行时存在问题。我们能够取i＝1，2，计算得到

这里假定w

这步攻击计算存在二个问题：一是目前不知道如何计算求解这种特征值，因为特征多项式定义在域K上，需要计算求解的元素也属于K，而不是在有理数域

第三步：这步攻击无需实行。因为本文构造中模的素因子公开，不需保密，然而CLT13构造中知道模的素因子就能求解所有秘密元素。也就是说，通过使用Cheon等人的“0”化攻击，攻击者获得的信息并不比直接使用基于交叉乘积的已知攻击方法得到的信息更多。

因此，“0”化攻击扩展不能用于攻击本文无可信安装的构造，证明本发明的无可信安装的构造安全等级较高。

综上所述，根据本发明实施例的基于中国剩余定理构造的无可信安装的多线性映射方法，每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布，每个参与方使用中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数，每个参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射。该方法使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

此外，本发明还提出一种非临时性计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述的基于中国剩余定理构造的无可信安装的多线性映射方法。

根据本发明实施例的非临时性计算机可读存储介质，存储在其上的计算机程序被处理器执行时，每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布；每个参与方使用中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数，每个参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射，由此，使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

此外，本发明还提出一种计算机设备，处理器运行存储在存储器上的计算机程序时，每个参与方使用新随机化构造的初始化算法产生各自的公共参数并发布；每个参与方使用中国剩余定理将各方的公共参数进行组合，以产生所有参与方共用的公共参数，每个参与方自适应地产生无可信安装构造中的算法，以实现共用的公共参数环境下无可信安装的多线性映射，由此，使用多线性映射的所有参与方各自保存一部分秘密信息，使得参与方的任何子集都不能获得构造的全部秘密信息，通过这种秘密信息分散保存的方式能够构造出无可信安装的多线性映射，提高了构造的安全性。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现定制逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，″计算机可读介质″可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。