矩阵与增广矩阵秩相等问题的保密计算及应用*

杜润萌,刘旭红,李顺东,魏 琼

1.陕西师范大学 计算机科学学院,西安 710119

2.陕西师范大学 数学与信息科学学院,西安 710119

1 引言

矩阵是现代科技领域必不可少的工具,在自然科学、工程和社会科学的各个领域都有着重要的应用价值,矩阵是图像处理、线性规划、各种网络研究的关键工具和手段.矩阵的秩是反映矩阵固有特性的一个重要参数[1],用矩阵方法解决问题的核心手段是利用矩阵的秩,所以科学计算中的许多与矩阵相关的问题都可以归约到矩阵秩的计算,许多保密的科学计算问题也都可用矩阵秩的保密计算协议解决.因此,矩阵秩的保密计算是安全多方计算的一个基本问题,有着重要的意义.

安全多方计算(secure multiparty computation,SMC)是指在不泄露自己隐私数据的情况下,多个参与者利用他们的私有数据进行合作计算,计算结束后没有参与方能获得多于规定输出的信息,是近年来国际密码学界的研究热点[2].SMC 最初是由姚期智教授提出来的,Goldreich 等人[3,4]对安全多方计算的理论进行了深入研究,证明了在一定的条件下,任意函数f(x1,···,xn)的安全多方计算都是可以实现的,并且给出了基于不经意传输的解决方案.这样的通用解决方案有重要的理论意义,奠定了安全多方计算的理论基础,但是用通用解决方案解决实际的安全多方计算问题是不合理的,对具体的问题应该研究具体的解决方案.同时Goldreich 利用比特承诺[5]和零知识证明[6]设计了一个编译器,借助这个编译器,可以自动生成一个对于半诚实参与者和恶意参与者都安全的多方计算协议,该协议可以强迫恶意参与者以半诚实的方式参与协议的执行过程,否则将被发现.

安全多方计算的研究在计算科学中占有重要的地位和广泛的应用前景,这激励着人们研究各种具体的安全多方计算问题[7].所研究的问题可以总结为以下几类:保密的科学计算问题[8];保密的统计分析问题[9];保密的数据挖掘问题[10];其他安全多方计算问题.关于科学计算的两方安全计算问题,美国普渡大学的Du 博士在其论文中还指出了科学计算其他值得研究的问题[11]:矩阵特征值、特征向量、行列式、矩阵因子分解等.Cramer 和Damgård 在线性秘密共享下首次研究了线性代数中各种各样的安全计算问题:如矩阵的行列式、矩阵的秩、线性方程组、特征多项式等问题,并给出了解决方案[12].

文献[13]给出了一个判定加密矩阵的奇异性的协议.基于此协议,解决了计算加密矩阵的秩和线性方程组解的问题.但该文利用矩阵的奇异性去判断矩阵的秩,要求矩阵必须为n×n的方阵,因而解决方案不具有普遍意义.此外,方案采用同态加密体制,计算复杂性较高.在国内,线性代数问题同样得到了广泛深入的研究.文献[14]将Du 的工作推广到多方的情形.方案需要多次调用两矩阵乘积协议以及不经意传输协议,计算复杂性与通信复杂性都很高.文献[15]提出的保密计算矩阵秩的协议,需要Alice 和Bob 两个人合作计算一个m×n矩阵的秩,但计算复杂性是O(mn2).文献[16]基于安全点积协议设计了个多方向量组秩的协议.但求矩阵秩的时候需要调用mn次点积协议,计算复杂性是O(m2n),其中m表示参与者个数,n表示每个参与者所拥向量的维数,这个方案的计算复杂性也较高.

综上所述,现有的关于矩阵秩的保密计算协议存在几个方面的不足:解决方案的适用性有限;基于公钥加密算法设计的方案计算复杂性较高;用矩阵的秩解决的实际问题有限.针对这些问题,本文假设Alice拥有一个矩阵Am×n,Bob 拥有一个矩阵Bm×1,设计了一个安全高效的计算增广矩阵(A|B)秩的协议.将矩阵秩的计算推广到一般的矩阵,提出了不需要加密运算的高效保密计算协议,并以此判断矩阵与增广矩阵秩是否相等.判断矩阵与增广矩阵秩是否相等的保密计算可以作为一个基本建筑模块,用于构建许多安全多方计算问题的协议,包括保密判定空间直线与直线(平面与直线、平面与平面)的位置关系、保密判断多项式整除、保密判断集合包含问题和任意数整除问题、保密判断线性方程组解的数目等应用,拓宽了矩阵秩的保密计算的应用领域.

空间两直线位置关系问题的多方保密计算方案在实际应用场景中具有重要的研究意义.例如:航空公司A 和航空公司B 在同样的两个国家之间分别设计了一条航线图L1和L2,他们想在不泄露自己航线图的情况下保密地判定L1和L2是否相交,确保航线的安全性.所以他们需要合作计算两条空间航线是否相交.现实中很多问题都可以归约到空间位置关系的保密判定,因此研究这个问题有着重要的应用价值.由于平面和直线在直角坐标系下可分别用三元线性方程和三元线性方程组来表示,而线性方程组解的数目和系数矩阵关系密切,因此可用保密判定矩阵与其增广矩阵的秩是否相等的方法来判断空间直线与直线(平面与直线、平面与平面)的位置关系.

本文研究矩阵与增广矩阵秩的相等问题的保密计算,主要贡献如下:

(1)研究了矩阵与增广矩阵的秩是否相等的安全多方计算问题,提出了一种新的、不需要加密运算的、适用于一般矩阵的高效解决方案,为解决其他多方保密计算问题提供一种新的方法.

(2)在保密判断矩阵和增广矩阵秩是否相等协议的基础上,提出了保密判断空间两条直线位置关系的协议,方案安全且高效.

(3)在保密判断矩阵和增广矩阵秩是否相等协议的基础上,提出了保密判断两个多项式是否可以整除的协议,也为解决其他多方保密计算问题提供一种新的途径.

本文第2 节介绍了协议相关预备知识;第3–5 节设计了三种协议;第6 节分析了方案的效率;第7 节给出了文章的总结.

2 预备知识

2.1 安全性定义

半诚实参与者[17]本文方案的安全性均假设安全多方计算的参与者为半诚实参与者.半诚实参与者是指参与者在协议执行过程中将完全按照协议忠实地执行协议,但他们也会保留计算的中间结果试图推导出其他参与者的输入.

隐私的模拟范例[18]如果对于任意一个半诚实的参与者,在执行协议的过程中,参与者所获得信息都可以通过他自己的输入和输出进行模拟,而且得到的消息序列与实际过程得到的消息序列不可区分,就说明协议是安全的.如果一个多方计算协议能够进行这样的模拟,即说明所有参与者都不可能从协议的执行过程中得到其他参与者任何有价值的信息.这就是研究安全多方计算问题时普遍接受的模拟范例.

一些记号假设双方计算的参与者分别是Alice 和Bob.

(1)设f=(f1,f2)是一个概率多项式时间函数,π表示计算f的双方计算协议.

(2)当输入为(x,y)时,Alice(Bob)在执行协议π的过程中所得到的信息序列记为其中r1(r2)表示Alice(Bob)选择的随机数;表示Alice(Bob)第i次收到的信息.

(3)输入为(x,y)时,执行协议π以后,Alice(Bob)的输出结果记为

定义1(半诚实参与者的保密性)对于一个函数f,如果存在概率多项式时间算法S1与S2(也称这样的多项式时间算法为模拟器)使得

其中表示计算上不可区分,则认为π保密地计算f.

2.2 矩阵相关知识

矩阵的秩在m×n矩阵A中任取k行、k列(1kmin{m,n}),位于这k行、k列交叉点处的元素按原来次序组成的k阶行列式称为A的一个k阶子式.矩阵A中不等于零的子式的最高阶数称为A的秩,记为R(A).

初等行变换设A为m×n矩阵,可对A实施以下三类初等行变换,将A化为行阶梯矩阵或最简行阶梯矩阵.

(1)第一类初等行变换:将A的第i行与第j行交换位置;

(2)第二类初等行变换:将A的第i行乘以非零常数λ;

(3)第三类初等行变换:将A的第i行的λ倍加到第j行.初等变换不会改变矩阵的秩.

初等矩阵[19]由单位矩阵E经过一次初等变换得到的矩阵称为初等矩阵.

从初等矩阵的定义可以看出,初等矩阵是方阵,并且每次进行初等变换都会有一个与之相对应的初等矩阵.共有三类初等矩阵,如图1 所示.

图1 三类初等矩阵Figure 1 3 kinds of primary matrix

其中,P(i,j)表示互换矩阵E的第i行与第j行,P(i(c))表示用数域中非零数c乘E的第i行,P(i,j(k))表示把矩阵E的第j行的k倍加到第i行.由于本文中全部用的初等行变换,所以与列变换相应的初等矩阵不做讨论.

用初等变换化矩阵为行阶梯矩阵任意矩阵Am×n经过有限步的初等行变换,可将矩阵化为行阶梯矩阵A′,特点是:可画出一条阶梯线,线的下方全为0,阶梯线的竖线后面的第一个元素为非零元.例如矩阵

即为一个行阶梯矩阵.因此存在初等矩阵P1,P2,···,Ps,使得下式

成立,记P=Ps···P2P1.

2.3 多项式整除与矩阵秩的关系

命题1有两个多项式f(x)=anxn+an−1xn−1+···+a0x0,q(x)=cmxm+cm−1xm−1+···+c0x0,令g(x)=f(x)q(x).利用f(x)的系数并且每一列扩展m个0 构造矩阵A(m+n+1)×(m+1),利用g(x)的系数构造矩阵B(m+n+1)×1.f(x)整除g(x)的充分必要条件是其对应的系数矩阵满足R(A)=R(A|B).

证明:必要性:g(x)=f(x)q(x)=a0c0x0+(a1c0+a0c1)x1+···+(asc0+as−1c1+···+a1cs−1+a0cs)xs+···+(am+nc0+am+n−1c1+···+a0cm+n)xm+n

从上式可以得出

其中in,jm.

利用f(x)的系数并且每一列扩展m个0 构造矩阵A(m+n+1)×(m+1),利用q(x)的系数构造矩阵C(m+1)×1.令A与C作相乘的运算,可以得到矩阵B,如图2 所示.

图2 AC =BFigure 2 AC =B

从图2 中比较A,B,C中的元素可以得出:

因此f(x)q(x)=g(x)等价于AC=B.f(x)整除g(x),而且有唯一的商q(x),等价于AC=B对应的线性方程组有解,而线性方程组有解的条件是矩阵A与增广矩阵(A|B)同秩,也就是R(A)=R(A|B).同理可证充分性.

综上所述,f(x)整除g(x)的充分必要条件是其对应的系数矩阵满足R(A)=R(A|B).

3 矩阵与增广矩阵秩相等问题

3.1 问题描述

Alice 有一个矩阵Am×n,Bob 有一个矩阵Bm×1,利用A,B构造增广矩阵(A|B),其中

Alice 和Bob 都想在不暴露自己私有数据的情况下,判断矩阵A和增广矩阵(A|B)的秩是否相等.

协议的基本原理Alice 计算初等变换矩阵Pm×m发送给Bob,其中矩阵A′=PA.Bob 收到P后,计算PB得到矩阵B′发送给Alice.Alice 判断矩阵A的秩与增广矩阵(A|B)的秩是否相等.为方便表达,定义如下谓词:

例如,Alice 有一个矩阵A3×3,Bob 有一个矩阵B3×1,Alice 计算出初等变换矩阵P3×3发送给Bob,其中

Bob 收到P后,计算PB得到矩阵B′,其中

Bob 将矩阵B′发送给Alice.Alice 比较矩阵A′与增广矩阵(A′|B′)秩的大小,其中

由此可知,R(A′)=R(A′|B′)=3,输出P(A,(A|B))=2.上述原理是我们计算矩阵与增广矩阵秩是否相等的基本思路,不涉及任何保密问题,保密计算矩阵秩的具体协议参看协议1.

3.2 矩阵与增广矩阵秩相等问题保密计算方案

协议1保密的计算矩阵与增广矩阵秩相等问题.

输入:Alice 有一个矩阵Am×n,Bob 有一个矩阵Bm×1.

输出:P(A,(A|B)).

(1)Alice 计算初等变换矩阵Pm×m.Alice 对矩阵P随机化处理得到矩阵P′,其中

其中,ri是Alice 选取的有理数随机数.Alice 将P′发送给Bob.

(2)Bob 计算P′B得到矩阵B′,其中

Bob 统计从以上紧挨并连续等于的个数和从开始以下0 的个数,分别记为p,q.Bob 将p,q发送给Alice.

(3)Alice 根据p,q进行判断.若R(A)=R(A|B)

定理1在半诚实模型下,协议1 是正确的.

证明:(1)Alice 计算初等变换矩阵P和P′=P(r1,...,rm),其正确性是由对矩阵进行初等行变换不会改变的矩阵的秩保证的.

(2)Bob 计算B′=P′B,这样就可以保证Bob 与Alice 做的是同样的初等变换.

(3)Bob 统计从以上紧挨并连续等于的个数和从开始以下0 的个数,分别记为p,q.Bob将p,q发送给Alice.根据矩阵的秩的定义,Alice 根据p,q进行判断即可得到增广矩阵(A|B)的秩.

因此,协议1 是正确的.

协议1 的安全性分析为了分析协议1 的安全性,需要详细分析在协议执行后可能推断出的潜在信息.

首先考虑Alice 矩阵的安全性.Alice 对矩阵进行随机化处理,Bob 在整个协议的执行过程中仅得到Alice 发送给他的矩阵P′.由于P′原本不是最简矩阵,并且有r1,r2,···,rm为Alice 的保密数据,均可随机选取(也可选择有理数),即使Bob 有无限的计算能力,也无法推出矩阵P,更无法推出矩阵A.

同样的,Alice 只知道p,q,所以Alice 也无法推断出矩阵B.

定理2在半诚实模型下,协议1 是安全的.

证明:我们通过构造使得(1)和(2)成立的模拟器S1和S2来证明本定理,首先构造S1.

(1)S1接受输入(A,P(A,(A|B))),根据P(A,(A|B))的值构造矩阵B′,用A,B′进行模拟.

(2)S1计算矩阵A的初等变换矩阵P,按照协议1 对P进行随机化处理得到矩阵P′.

(3)S1计算P′B′得到矩阵B′′.S1统计从以上紧挨并连续等于的个数和从开始以下0的个数,分别记为p′,q′.

(4)S1比较R(A|B′)和R(A|B)是否相等.

在本协议中view1(A,B)={A,P,R(B),P(A,(A|B))}.令S1(A,P(A,(A|B)))={A,P,R(B′),P(A,(A|B′))},由于P(A,(A|B))=P(A,(A|B′)),则R(B)=R(B′),所以可以推出

类似地,还可以构造S2使下式成立

4 空间两条直线的位置关系

4.1 问题描述

Alice 有一条空间直线L1,Bob 有一条空间直线L2,方程分别为

Alice 和Bob 都想在不暴露自己私有数据的情况下,判断这两条空间直线的位置关系.

协议的基本原理Bob 利用平面方程l22的参数构造矩阵B1,矩阵B2以及矩阵B,其中

Bob 将平面方程l21的参数a31,a32,a33,a34发送给Alice(由于经过一条直线的平面有无限多个,所以将其中一个平面参数发送给Alice,Alice 也无法推断出直线方程).Alice 利用L1,l21的系数构造矩阵A1、矩阵A2以及矩阵A,其中

Alice 和Bob 利用矩阵A1,A2,B1,B2构造矩阵(A1B1)、矩阵(A2B2)以及增广矩阵(AB),其中

因此,判定空间两条直线间的位置关系的问题就转化为矩阵(A1B1)与增广矩阵(AB)秩的关系.当R(A1B1)=R(AB)=3 时,L1与L2相交于一点;当R(A1B1)=R(AB)=2 时,L1与L2重合;当R(A1B1)=2 且R(AB)=3 时,L1与L2平行;当R(A1B1)=3 且R(AB)=4 时,L1与L2为两条异面直线.为方便表达,定义如下谓词:

例如,Alice 有一条空间直线L1,Bob 有一条空间直线L2,方程分别为

Alice 和Bob 利用矩阵A1,A2,B1,B2构造矩阵(A1B1)、矩阵(A2B2)以及增广矩阵(AB),其中

对矩阵(A1B1)和增广矩阵(AB)进行初等行变换,将矩阵(A1B1)和增广矩阵(AB)化为行阶梯矩阵(A1B1)′,(AB)′,其中

由此可知,R(A1B1)=2 且R(AB)=3,所以L1与L2平行,输出P(L1,L2)=2.

4.2 空间两条直线的位置关系保密计算方案

协议2保密的计算空间两条直线间的位置关系.

输入:Alice 有一条空间直线L1,Bob 有一条空间直线L2.

输出:P(L1,L2).

(1)Bob 将l21的参数a31,a32,a33,a34发送给Alice.Alice 和Bob 调用协议1 中的(1)–(2).

(2)Alice 比较R(AB)与R(A1B1)的大小.若R(AB)=4,输出P(L1,L2)=3;若R(A1B1)=R(AB)=3,输出P(L1,L2)=0;若R(A1B1)=R(AB)=2,输出P(L1,L2)=1;若R(A1B1)=2 且R(AB)=3,输出P(L1,L2)=2.

定理3在半诚实模型下,协议2 是正确的.

证明:证明方法与定理1 的证明类似,是根据矩阵秩的定义和初等变换不改变矩阵的秩保证其正确性.

协议2 的安全性分析协议2 的安全性分析与协议1 的安全性分析类似.

定理4在半诚实模型下,协议2 是安全的.

证明:证明方法与定理1 的证明类似,也可采用构造模拟器的方法.

5 多项式整除问题

5.1 问题描述

Alice 有一个多项式f(x)=anxn+an−1xn−1+···+a0x0,Bob 有一个多项式g(x)=bmxm+bm−1xm−1+···+b0x0.Alice 和Bob 都想在不暴露自己私有数据的情况下,判断多项式f(x)是否可以整除g(x).若f(x)可以整除g(x),记f(x)|g(x);若f(x)不可以整除g(x),记f(x)∤g(x).

协议的基本原理Alice 利用多项式f(x)中的系数,每一列扩展(m−n)个 0,构造矩阵A(m+1)×(m−n+1),Bob 利用多项式g(x)中的系数构造矩阵B(m+1)×1,如图3 所示.

因此,多项式整除问题就转换为矩阵A与增广矩阵(A|B)秩的关系.若R(A)=R(A|B),则f(x)|g(x);若R(A)R(A|B),则f(x)∤g(x).为方便表达,定义如下谓词:

图3 矩阵A 和矩阵BFigure 3 Matrix A and B

例如,Alice 有一个多项式f(x)=x−2,Bob 有一个多项式g(x)=x2−5x+6.Alice 利用f(x)中的系数,每一列扩展1 个0,构造矩阵A,Bob 利用g(x)的系数构造矩阵B,Alice 计算出初等变换矩阵P3×3发送给Bob,其中

Bob 收到P后,计算PB得到矩阵B′,其中

Bob 将矩阵B′发送给Alice.Alice 比较矩阵A′与增广矩阵(A′|B′)秩的大小,其中

由此可知,R(A′)=R(A′|B′)=2,所以f(x)|g(x),输出P(f(x),g(x))=1.

5.2 多项式整除问题保密计算方案

协议3保密的计算多项式整除问题

输入:Alice 有一个多项式f(x)=anxn+an−1xn−1+ ··· +a0x0,Bob 有一个多项式g(x)=bmxm+bm−1xm−1+···+b0x0.

输出:P(f(x),g(x)).

(1)Bob 构造矩阵B(m+1)×1,将m发送给Alice.

(2)若m

(3)Alice 和Bob 调用协议1 中(1)–(2).

(4)Alice 进行判断.若R(A′)=R(A′|B′′),输出P(f(x),g(x))=1;否则输出P(f(x),g(x))=0.

定理5在半诚实模型下,协议3 是正确的.

证明:证明方法与定理1 的证明类似,是根据矩阵秩的定义和初等变换不改变矩阵的秩保证其正确性.

协议3 的安全性分析协议3 的安全性分析与协议1 的安全性分析类似.

定理6在半诚实模型下,协议3 是安全的.

证明:证明方法与定理1 的证明类似,也可采用构造模拟器的方法.

5.3 多项式整除问题的应用

集合包含问题Alice 有一个集合A={a1,a2,···,an},Bob 有一个集合B={b1,b2,···,bm}.Alice和Bob 都想在不暴露自己私有数据的情况下,判断一个集合是否包含另一个集合.若一个集合不包含另一个集合,记(A⊈B)∩(B⊈A);若一个集合包含另一个集合,记(A⊆B)∪(B⊆A).Alice和Bob 都将集合中的数据用多项式的形式表达出来[20].例如,集合A={1,,3,2},即多项式f(x)=(x−1)(2x−1)(x−3)(x−2).因此,集合包含问题就转换为多项式整除问题.若(f(x)|g(x))∪(f(x)|g(x)),就是一个集合包含另一个集合;否则不是.具体协议与协议3 类似,本文不予给出.

整除问题Alice 有一个机密数x(x0),Bob 有一个机密数y(y0).Alice 和Bob 都想在不暴露自己私有数据的情况下,判断一个数是否整除另一个数.若两个数据不具有整除关系,记(x∤y)∧(y∤x);若两个数据具有整除关系,记(x|y)∨(y|x).根据算术基本定理,任一整数z都可以表示为

pi表示第i个素数,即p1=2,p2=3,···,令[p]=Alice 和Bob 利用x,y,[p]构造集合[pA],[pB].例如,数据z=24,即[p]={2,4,8,3}.因此,数的整除判定问题就转换为多项式整除问题.若(f(x)|g(x))∨(f(x)|g(x)),就是两个数据具有整除关系;否则不是.具体协议与协议3 类似,本文不予给出.

6 性能分析

6.1 效率分析

本文的基础协议(协议1)本质是通过保密计算增广矩阵的秩,以此保密判断矩阵的秩和增广矩阵的秩是否相等.因此在与其他文献做对比时,为了统一标准,均以求解矩阵的秩来比较方案的计算复杂性和通信复杂性.

计算复杂性分析文献[15]求矩阵秩的时候调用了向量比等协议,其计算开销是n·(mn+2m+2)Me,m,n表示Alice 和Bob 两个人合作计算一个m维n列矩阵的秩,Me是模指数运算(下同).文献[16]求矩阵秩的时候需要调用mn次点积协议,计算开销是m2nMe,m表示参与者个数,n表示每个参与者所拥有向量的维数.在计算复杂性理论中,当模指数运算与普通的运算数量差不多的时候,普通的基本运算所消耗的时间一般可以忽略不计.文献[15,16]均有复杂的模指数运算,而我们的协议只有简单的初等变换运算,因此与文献[15,16]中的协议相比,我们的协议计算复杂性可以忽略.

本文的方案主要利用了矩阵的初等行变换运算,所以分析计算复杂性时,只考虑协议执行中最费时的初等行变换运算,其他运算忽略不计.现以3×3 维的矩阵为例,在我们的实验条件下求矩阵的初等变换矩阵的计算开销约3 毫秒,对矩阵进行一次随机化处理的计算开销约1 毫秒,总共耗时约4 毫秒.4×4维矩阵求一次初等变换矩阵和随机化处理的计算开销约6 毫秒,依次类推,实验数据显示求一次初等变换矩阵和随机化处理的计算开销是随着矩阵维数的增长大致线性增长.由于计算开销与计算设备和计算软件密切相关,本文假设求一次初等变换矩阵是x毫秒,执行一次m×n维矩阵随机化处理是h毫秒.本文协议1–3 均需要求一次初等变换矩阵和执行一次矩阵随机化处理,计算开销均为(x+h)毫秒.

通信复杂性分析衡量通信复杂度的指标是用协议交换信息的比特数,或者用通信轮数,在安全多方计算研究中通常用轮数.文献[15]通信轮数是n·(mn+2m+)轮.文献[16]通信复杂度主要产生在调用点积协议时产生的信息交互,通信轮数为mn2轮.本文中协议1 的通信复杂性是3 轮,协议2 的通信复杂性是4 轮,协议3 的通信复杂性是4 轮,所以本文协议的计算复杂性和通信复杂度都比较低.矩阵的秩计算方案的计算复杂性和通信复杂性比较见表1.

表1 矩阵的秩计算方案的效率对比Table 1 Comparison of all solutions on matrix rank calculation

另外给出本文在应用部分的协议2(空间两条直线的位置关系)与文献[21]在效率和安全性方面的分析与比较(见表2).文献[21]调用了内积协议,其中方案中调用的内积协议总次数和用户需要进行的模指数运算的次数作为衡量计算复杂性的指标,其它运算忽略不计.模指数运算记为Me.

表2 直线与直线位置关系判定方案的效率对比Table 2 Comparison of solutions on location relation between line and line

实验仿真由于协议2 和协议3 与协议1 类似,所以实验仿真只模拟协议1.

操作系统:Windows7(64 位).操作软件:MATLAB R2014a.语言:MATLAB.协议1:保密的计算矩阵与增广矩阵秩相等问题.设定:矩阵为方阵,方阵内每一个数据为8 位大随机数,方阵的维数间隔为1.图4 描述了协议1 的执行时间随着方阵维数增长的变化规律.

图4 协议1 的执行时间随着方阵维数增长的变化规律Figure 4 Consume time of protocol increases with the dimension of square matrix

由图4 可知,以毫秒为单位测出的执行时间随方阵维数的增长大致呈线性增长.综上所述,协议1–3不仅具有较高的安全性,而且计算双方的通信代价及计算复杂度都比较低.

7 结论

本文研究矩阵与增广矩阵的秩是否相等的问题,设计了一个不需要借助密码学原语、具有信息论安全、计算复杂性低且通信效率高的安全多方保密计算协议.在保密判断矩阵和增广矩阵秩是否相等协议的基础上,提出了保密判断两个多项式是否可以整除的协议,利用该协议可以解决有理数集合包含问题、数的整除问题.本文还提出可以利用矩阵和增广矩阵秩是否相等保密高效的解决空间直线与直线的位置关系.本文研究的这些问题都是基于半诚实模型的,对于多方保密计算的研究与应用有重要的理论意义,对其他密码学应用也有一定意义,未来将研究恶意模型下的保密计算矩阵与增广矩阵的秩是否相等的问题.