基于线性方程组的可验证随机数生成的方法

技术领域

本发明涉及密码学领域，尤其涉及一种可由参与者共同生成一个 随机数，并且参与者可以验证此随机数是否被操控的方法。

背景技术

在密码学中随机数扮演着极其重要的角色，很多方案虽能生成随 机数，但是用户很难验证随机数的真实性。

在以密码学为核心的信息安全的领域中，随机序列扮演着非常重 要的角色，随机序列的安全性就确定了整个安全系统的安全性。密码 学领域中对随机序列的要求是很高的，从安全的角度来说，真正的随 机序列是完全不可预测的，只有真正意义上的随机序列最可靠。但是 在实际的应用中通常使用伪随机序列或不可预测序列。

随着对信息安全要求的提高，对随机数或者伪随机数提出了新的 要求，很多情况下，不仅要求数据是随机或者是伪随机的，并且要求 能够使用户确信该随机数是真正随机的，而不是被别人操控的。但目 前来看，很多随机数生成方案都不能达到可验证这个要求。

比如，在电子彩票的协议设计中，关键的环节是中奖数字的产生， 如何产生不受人为因素控制的随机数，已经不是难题，但是要让彩票 购买者完全相信中奖数字是随机的，还需要可信任的第三方存在。在 现行的电子彩票摇奖系统中，中奖数字的产生由发行者产生，彩票的 购买者无法参与。如果彩票发行者造假或者摇奖系统被人为破坏，则 产生的中奖数字不具有公平性。比如武汉的经济适用房“六连号事件” 与深圳福彩摇奖系统被植入木马病毒以实施诈骗，以及最近发生的对 3.6亿的彩票中奖公正性的质疑等，都属于此例。在此情况下，摇奖 系统的公平性受到严重破坏，造成了严重的信任危机，影响了行业的 正常发展以及政府的公信力。

在文献“基于Fp上插值多项式的可验证随机数（四川大学学报 (工程科学版),2010,42(6):105-108.）”和文献“有限域上可验证随 机数的快速构造及安全性分析（计算机工程与科学，2012,34(5): 35-39）”中，给出了一种基于插值多项式的可验证随机数方案，但 是该方案存在一定的漏洞，可能造成一些用户给出的数据在随机数的 生成过程中没有起到作用，但是仍然能通过验证。

例如：U1给出点（1，6），U2给出点（2，11）,U3给出点（3， 18），U4给出点（4，27），其中U1，U2，U3，U4为相互独立的参 与者。

根据上述文献的方法可以构成插值多项式y=3+2x+x²

但是由U1，U2，U3给出的数据就能得到此二次插值多项式，可 以说明U4的数据在此次计算中并未起作用。

针对以上问题，能否研发一种提供在多方参与的情况下，由参与 者共同生成一个随机数，并且参与者可以验证此随机数是否被操控的 方法呢？

发明内容

鉴于现有技术的不足，本发明旨在于提供一种基于线性方程组的 可验证随机数生成的方法，利用所述方法让每个用户给出的数据都能 参与到随机数的生成过程中，并且同时使得随机数是不可预测、不可 操控的。

为了实现上述目的，本发明采用的技术方案如下：

本发明为基于线性方程组的可验证随机数生成的方法，包括计算 中心，以及具有U₁,U₂,…,U_n个参与者，U_i(i=1,2,…,n)为所述参与者中 的一个，所述参与者U₁,U₂,…,U_n在与所述计算中心通信时，将共享一 个随机数r，且所述参与者U₁,U₂,…,U_n可以验证是否参与了所述随机 数r的生成；其中，所述随机数r是所述参与者U₁,U₂,…,U_n之间共享并 由所述计算中心帮助参与者U₁,U₂,…,U_n计算所生成的，所述方法包括 以下步骤：

（1）所述参与者U₁,U₂,…,U_n分别选择一个随机向量与一个随机 数发送至所述计算中心；

（2）所述计算中心运接收并使用所述参与者U₁,U₂,…,U_n所给的 随机向量与随机数来构造可验证随机数；

（3）所述参与者U₁,U₂,…,U_n对可验证随机数进行验证。

需要进一步说明的是，所述参与者U₁,U₂,…,U_n任选向量 α_i=(α_i1,α_i2,…α_in)与一个随机数α_i(n+1)(α_ij∈Z_p)发送至计算中心，当所 述计算中心收到所述任选向量α_i=(α_i1,α_i2,…α_in)(i=1,2,…,n)后，验证 这n个向量是否线性无关，如验证结果显示为线性相关，则让所述结 果相关的U_i重新选择向量，直至n个向量线性无关为止；其中，Z_p为 一有限域，p为素数。

需要进一步说明的是，在构造可验证随机数时，所述计算中心将 n个随机数α_i(n+1)(i=1,2,…,n)构成一个新的向量：

$y=\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right),$

然后建立线性方程组：

$\left(\begin{array}{cccccc}{\alpha }_{11}& & {\alpha }_{12}& & ···& {\alpha }_{1n}\\ {\alpha }_{21}& & {\alpha }_{22}& & ···& {\alpha }_{2n}\\ & ···& & ···& & ···\\ {\alpha }_{n1}& & {\alpha }_{n2}& & ···& {\alpha }_{\mathrm{nn}}\end{array}\right)a=\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right)\mathrm{mod}p,$

并求解出以下向量：

$a={\left(\begin{array}{cccccc}{\alpha }_{11}& & {\alpha }_{12}& & ···& {\alpha }_{1n}\\ {\alpha }_{21}& & {\alpha }_{22}& & ···& {\alpha }_{2n}\\ & ···& & ···& & ···\\ {\alpha }_{n1}& & {\alpha }_{n2}& & ···& {\alpha }_{\mathrm{nn}}\end{array}\right)}^{-1}\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right)\mathrm{mod}p=\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right),$

再令r=a₀||a₁||…||a_n，||表示连接符；当所述计算中心公布r时， 并公布向量$a=\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right)$作为验证，其中此时的r为可验证随机数。

需要进一步说明的是，所述参与者U₁,U₂,…,U_n可以验证下式是否 成立：

${\alpha }_{i}a=({\alpha }_{i1},{\alpha }_{i2},···{\alpha }_{\mathrm{in}})\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right)={\alpha }_{i(n+1)},(i=\mathrm{1,2},···,n);$

如成立，证明随机数r未被操控；否则，随机数r被操控。

进一步地，根据本发明的方法，可应用于电子摇号系统或电子彩 票系统中。

本发明有益效果在于，让每个用户给出的数据都能参与到随机数 的生成过程中，并且同时使得随机数是不可预测、不可操控的。在效 率方面，本发明的效率高于基于差值多项式的随机数方案。能够克服 基于插值多项式的可验证随机数方案的漏洞。

附图说明

图1为本发明的流程示意图；

图2为本发明一种实施方式流程示意图。

具体实施方式

下面将结合附图对本发明做进一步的描述。需要说明的是，本实 施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式 和具体的操作过程，但本发明的保护范围不限于下述的实施例。

本发明为基于线性方程组的可验证随机数生成的方法，包括计算 中心，以及具有U₁,U₂,…,U_n个参与者，U_i(i=1,2,…,n)为所述参与者中 的一个，所述参与者U₁,U₂,…,U_n在与所述计算中心通信时，将共享一 个随机数r，且所述参与者U₁,U₂,…,U_n可以验证是否参与了所述随机 数r的生成；其中，所述随机数r是所述参与者U₁,U₂,…,U_n之间共享并 由所述计算中心帮助参与者U₁,U₂,…,U_n计算所生成的，所述方法包括 以下步骤：

步骤一，所述参与者U₁,U₂,…,U_n选择一个随机向量与一个随机数 发送至所述计算中心；

（1）所述参与者U₁,U₂,…,U_n分别任选向量α_i=(α_i1,α_i2,…α_in)与一 个随机数α_i(n+1)(α_ij∈Z_p)发送至计算中心；

（2）当所述计算中心收到所述任选向量α_i=(α_i1,α_i2,…α_in)后，验 证这n个向量是否线性无关，如验证结果显示为线性相关，则让所述 结果相关的U_i重新选择向量，直至n个向量线性无关为止；

需要说明的是，Z_p为一有限域，p为素数。

步骤二，所述计算中心运接收并使用所述参与者U₁,U₂,…,U_n所给 的随机向量与随机数来构造可验证随机数；

（1）所述计算中心将n个随机数α_i(n+1)(i=1,2,…,n)构成一个新的 向量：

$y=\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right);$

（2）然后建立线性方程组：

$\left(\begin{array}{cccccc}{\alpha }_{11}& & {\alpha }_{12}& & ···& {\alpha }_{1n}\\ {\alpha }_{21}& & {\alpha }_{22}& & ···& {\alpha }_{2n}\\ & ···& & ···& & ···\\ {\alpha }_{n1}& & {\alpha }_{n2}& & ···& {\alpha }_{\mathrm{nn}}\end{array}\right)a=\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right)\mathrm{mod}p;$

（3）并求解出以下向量：

$a={\left(\begin{array}{cccccc}{\alpha }_{11}& & {\alpha }_{12}& & ···& {\alpha }_{1n}\\ {\alpha }_{21}& & {\alpha }_{22}& & ···& {\alpha }_{2n}\\ & ···& & ···& & ···\\ {\alpha }_{n1}& & {\alpha }_{n2}& & ···& {\alpha }_{\mathrm{nn}}\end{array}\right)}^{-1}\left(\begin{array}{c}{\alpha }_{1(n+1)}\\ {\alpha }_{2(n+1)}\\ .\\ .\\ .\\ {\alpha }_{n(n+1)}\end{array}\right)\mathrm{mod}p=\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right);$

（4）再令r=a₀||a₁||…||a_n，||表示连接符；当所述计算中心公布r 时，并公布向量$a=\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right)$作为验证，其中此时的r为可验证随机数；

步骤三，所述参与者U₁,U₂,…,U_n对可验证随机数进行验证；

参与者U₁,U₂,…,U_n可以验证下式是否成立：

${\alpha }_{i}a=({\alpha }_{i1},{\alpha }_{i2},···{\alpha }_{\mathrm{in}})\left(\begin{array}{c}{a}_1\\ a_2\\ .\\ .\\ .\\ a_n\end{array}\right)={\alpha }_{i(n+1)},(i=\mathrm{1,2},···,n)$

如成立，证明随机数r未被操控；否则，随机数r被操控。

为了更好的理解本发明，下面将结合具体实施例对本发明做详细 的描述。

实施例一

假设具有4个不同的参与者U₁,U₂,U₃,U₄，其有限域为Z₁₁

步骤一：

所述4个不同参与者U₁,U₂,U₃,U₄分别将向量与随机数， {(1,2,1,0),7}、{(0,1,6,3),7}、{(5,4,3,1),0}、{(4,0,1,2),3}， 其组成方式为{(向量),随机数}，发送至计算中心；

步骤二：

所述计算中心接收所述向量与随机数后求解如下线性方程组并 计算可验证随机数；

$\left(\begin{array}{cccc}1& 2& 1& 0\\ 0& 1& 6& 3\\ 5& 4& 3& 1\\ 4& 0& 1& 2\end{array}\right)a=\left(\begin{array}{c}7\\ 7\\ 0\\ 3\end{array}\right)\mathrm{mod}11.$

求解可得：

$a=\left(\begin{array}{c}1\\ 3\\ 0\\ 5\end{array}\right)$

根据求解则可验证随机数r＝1||3||0||5＝1305.，其中||表示连接 符；

步骤三：

参与者U₁,U₂,U₃,U₄验证可验证随机数；

以参与者U₁为例，参与者只需验证：

$\left(\mathrm{1,2,1,0}\right)\left(\begin{array}{c}1\\ 3\\ 0\\ 5\end{array}\right)=7$是否成立；

如此式成立，U₁则认为1305没有被操控。

以此类推，其他参与者的验证也是如此。

如图2所示，以电子摇号为例，当发生对摇号结果存在质疑时， 利用本发明的方法可以对结果进行验证，而且该验证是实现了每个参 与摇号的用户均可验证摇号结果是否被操控。从而最大限度的保证了 公平性。

对于本领域的技术人员来说，可根据以上描述的技术方案以及构 思，做出其它各种相应的改变以及变形，而所有的这些改变以及变形 都应该属于本发明权利要求的保护范围之内。