英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

无可信第三方的可验证随机数生成

摘要

可验证随机数不仅要求随机性还要求其随机性可以验证.它在加密协议中有许多应用，如密钥管理，数字签名和认证.2010年，刘教授等人已经提出了一种通过插值多项式生成可验证随机数的有效方案.这个方案影响了近期的许多研究.在本文中,我们证明了将拉格朗日插值替换为重心插值法后,刘的协议的计算效率和灵活性可以进一步提高.此外,我们提出了一个基于可验证密钥共享的可验证随机数生成的新方式.与刘的方式相比,我们的研究已经去掉了对可信方的假设.因此,它适合于参与者无法全部赞同一个可信实体的情况.

关键词:可验证随机数,可验证密钥共享,多项式插值.

1引言

可验证随机数已在密码协议中起到了非常重要的作用.在许多情况下,一个数字不仅需要具有随机性,其随机性也需要是可验证的.目前,可验证随机数在许多应用中得到运用,比如密钥管理,数字签名和验证.

在文献中,可验证随机函数是由Micali,Rabin和Vadhanin率先提出的[12].该方案利用了Goldreich-Levin变换[6].然而计算效率十分低下,而且输出范围有限.为了解决这两个弊端,一些著作在接下来的几年里被提出.例如,Lysyanskaya[11]提出了一个基于Diffie-Hellman问题的方案.Dodis和Yampolskiyrsquo;s的方案[1]是基于双线性群的.此外,Naor,Pinkas和Reingold已经调查了如何通过分布式方式生成随机函数[13].可验证随机数的概念是衍生自可验证随机函数.2010年,刘等人提出了生成可验证随机数的有效方案[10].该方案影响了近期的其他著作[18,17].在本文的剩余部分,刘的协议将被称为LYC协议.

在本文中,我们证明了通过将拉格朗日插值替换为重心插值,LYC协议中的一些计算可以被预处理.这样使得实时计算可以由O(K²)减少到O(K),其中K是参与者数量.此外,在需要暂时添加或删除一些数据点的情况下,多项式插值可以通过现有数据更新,而不需要重新计算整个多项式.LYC协议需要采用一些可信方.在本文中,我们还探讨了这一假设如何能去除,从而得到一个利用可验证密钥共享的可验证随机数的生成方案.

本文的组织.本文的其余部分安排如下:在第二节中我们给出了一些与本工作相关的加密组件.LYC协议将在第三节中被描述和分析.第四节中,我们会提出一个方法来提升LYC协议的计算效率和灵活性.在第五节中我们提出一个无需可信第三方的生成可验证随机数的新协议.最后,在第六节中我们将会进行讨论和总结.

2组件

在本节中，我们将简要回顾一些与我们的研究相关的组件.

2.1拉格朗日插值

当给出K 1个x坐标都不同的数据点(时，我们可以唯一地拟合一个通过所有这些K 1个数据点的k阶多项函数,多项函数如下:

其中拉格朗日基础多项式是：

为了证明这为什么有效，当

否则，当,我们有

因此对于任何数据点(我们有`

换句话说，多项函数将会经过所有这些K 1个数据点(.

2.2 Shamir的秘钥共享

Shamir的密钥共享[16]是密钥共享和阈值技术的一个基本组件.一个庄家D能在n个参与者之间共享密钥,使其中任何包含K 1个参与者的子集可以共同恢复密钥,但是任何只包含k个参与者的子集无法得到密钥.庄家D先生成一个k阶多项式,其中常数项系数a₀=s是要被共享的密钥，而其他的系数a_i(i=1,2,hellip;,k)是随机选则的.然后D计算出n个满足多项式的数据点(,再将这些数据点通过私人频道交给不同的参与者.通过使用拉格朗日插值,任何包含k 1个参与者的子集可以共同插值得到唯一的多项式,然后恢复s=a₀.但是任何包含k个参与者的子集无法计算出的任何系数.值得注意的是Shamir密钥共享和拉格朗日插值法也工作在有限域.

2.3 Feldman的可验证密钥共享

在Shamir的密钥共享中,庄家D需要是可信的.否则,她可以分发不正确的数据给参与者,以致于密钥永远无法恢复.为了解决这个问题,Feldman[2]提出一些技术来允许密钥以可验证的方式被共享.设p,q为两个大素数q|p-1.我们用图G_p表示的q阶子组.令g为G_q的产生式.为了分享一个密钥,D先生成一个在上的k阶多项式,其中a₀=s和所有其他的系数a_i(i=1,2,hellip;,k)都是在中随机选择的.此外,D广播 mod p(i=0,1,hellip;,k).多亏了离散对数问题,A_i的公开不需要启用任何概率多项式时间实体学习相应的值a_i.具体如下,D计算n个满足的数据点(，然后将每个数据点通过私有频道交付给一个参与者.现在每一位参与者都能验证她的数据点是否确实满足多项式函数,方式如下：

2.4分布式密钥生成

在分布式密钥生成[15,5]，n个参与者可以一起生成一个均匀分布在上的私钥x，从而使k或更少的参与者没有x的信息，也无法预测x.相反,x只可以在存在k 1个以上的参与者的时候才能被恢复.在文献中,这种技术也被用来如在[4]中一样生成(r,s)-DSS签名中的r值,和如在[8,7,3]中一样,在积极密钥共享和签名方案中生成多项式.在本文中,我们证明了它也可以用来改善LYC协议使得:(1)在不需要可信方的情况下生成可验证随机数；(2)各参与者不需要透露她的随机部分.

3 概述LYC协议

LYC协议[10]的主要思路如下:

1. 假设有k个参与者.每个参与者随机选择一个数据点((i=1,2,hellip;,k且.之后通过私有频道将她的数据点送到计算中心;
2. 一旦接收所有这些数据点(I = 1,2,hellip;,k),CC首先检查他们的x坐标是否都不相同，然后它随机选择另一个数据点(();
3. 根据这k 1个数据点，CC可以利用拉格朗日插值计算一个在上的k阶多项式，这样，(i=0,1,hellip;,k);
4. 最后，随机数r被计算为,其中||是连接符号.

如果任何一个参与者怀疑他们的数据点是否对最后的随机数做出了贡献,她可以检查她的数据点是否满足多项函数.换句话说,就是方程是否成立.

3.1效率分析

每个参与者的计算成本非常低.当生成随机数r,每个参与者只需要随机选择两个值.当验证她的数据点是否对多项式有贡献时,一个参与者可以使用Horner算法[9]来验证是否成立,全部的操作仅仅要求k的乘法和加法.除了选择一个数据点(,数据中心CC需要将k 1个数据点插值如函数中.但是,当使用拉格朗日插值时,计算不能被预先处理,而且实时计算复杂度为O(k²),是参与者数量的平方.此外,当额外的数据点被添加,整个多现式需要重新计算.

3.2安全性分析

LYC协议的安全性证明在[18]中给出.然而,证明是基于计算中心CC是诚实的这样一个假设的.如果CC是不诚实的,他可以影响随机数而不被检测到.例如,CC可以用一个十分简单的策略,使随机数r的最后一位为0.CC首先随机选择一个数据点(和内插一个多项式.

如果r的最后一位是0,它公布这个数据点.否则,它随机选择一个不同的数据点和再次内插这个多项式.这个过程可以重复直到r的最后一位是0.此外,一个稍微先进的技术使得CC可以控制多项式的任何系数a_i(i=0,1,hellip;,k).k 1个数据点的拉格朗日插值法可以用范德蒙矩阵改写为:

由于CC已经知道(，如果它随机选择,范德蒙矩阵的逆可以计算出来.因此，我们有：

现在，CC可以使用它希望计算y₀特定的a_i值.然后，它公布数据点(.通过这种方式，CC可以控制随机数的许多连续位.因为这个问题，一个生成随机值的较好的方法是使用一些单向散列函数r=h(a₀||a₁||hellip;||a_k).

上述技术的一个特例是控制第一系数a₀为：

使用CC的一个原因是因为每个参与者需要揭示她的数据点。如果没有CC而且参与者异步揭示他们的数据点，那个揭示最后一个数据点的参与者将会对随机数产生更大的影响.此外，CC需要确保x坐标都不相同.因此，LYC协议需要采用CC作为可信方.

4 LYC协议的效率提高

在本节中，我们们将介绍如何通过使用重心插值替换拉格朗日插值来提高LYC协议的效率：(1)一些计算可以提前进行，而且计算中心CC的实时计算花费从O(k²)减少到O(k),其中k是参与者的数量; (2) 如果一些数据点被添加或暂时移除，我们只需要更新现有的数据，而不是重新计算整个多项式。因此，我们的工作同时提高效率与LYC协议的灵活性。

正如在[2,15]，如果k 1个数据点的x坐标x_i提前固定，安全性不会受到影响,如设置x_j=j(j=1,2,hellip;,k 1).以这种方式，每个参与者只需要随机选择y坐标y_j.

指代. 拉格朗日基础多项式可以被重新写为：

接着，通过定义重心权

我们可以将重写为

现在，该内插多项式可以表示为重心形式

这种形式的一个优点是，如果x坐标都预先固定，所述重心加权的Wi可以预先计算.因此实时计算仅要求O(k)计算量而不是在拉格朗日中的O(k²)计算量.

另一个好处是，如果一个数据点需要被添加或暂时移除，也没有必要重新计算整个多项式。例如，增加一个额外的数据点(时，我们首先更新值和各重心权系数w_i(i=1,2,...,k 1)如下：

,

然后，计算后，k 1阶多项式可以被插值为：

5无可信方的可验证随机数的生成

如3.2节证明的，可信第三方是LYC协议的主要瓶颈.此外，这使得此协议无法在参与者们不赞同同一个可信实体的情况下使用.

为了解决这个问题，我们提出一个无可信第三方生成可验证的随机数的方法。我们的协议是基于Feldman的可验证秘钥共享[2]：每个参与者首先随机选择一个K阶多项式并在所有的参与者之中共享。以后，这些个体多项式将被用于构建生成多项式，但没有单独的多项式必须被揭露.最后,用生成多项式的系数生成随机值

通信模型：我们假设有n概率多项式时间参与者P₁,P₂,...,P_n它们通过成对的私人通道连接。此外，存在可以由每一个玩家可以访问的广播频道。

对手型号：我们假设一个对手A可以由概率多项式时间来模拟.图灵机，可以损坏k参与者，例如,A可导致损坏的玩家以任何方式从指定的协议转移。为了追求鲁棒性，我们假设k lt;N / 2.

设p,q为两个大素数,使得q|p-1. 我们用图G_p表示的q阶子组.令g为G_q的产生式. 目标为，如果没有一个可信的第三方,包含Q个诚实玩家的子集(|Q|ge;K 1)将定义一个唯一的多项式，其系数都均匀分布在. 而且随机数将使用这些系数被产生. 每个诚实的参与者可以确认她个人的随机多项式已经对最后的随机值作出了贡献。

1. 每个参与者P_i在上随机选择一个k阶多项式如下

P_i对多项式和广播承诺 mod p(i=0,1,hellip;,k).P_i也计算n个数据点其中(j= 1,2,hellip;,n)而且通过一个私有频道将发送给参与者P_i。

1. 每个参与者P_j验证从P_i接收到的数据点是否与多项式一致

如果验证失败，P_j广播一个对P_i的投诉.

3. 如果大于k次的参与者针对特定的参与者投诉，这个参与者将被取消资格，并立即删除.否则，如果k或更少的玩家（包括P_J）抱怨针对特定运动员P_i，然后P_i需要广播(J，S_IJ).

现在，任何人都可以验证如果验证失败，P_i将被取消资格并删除.我们定义集合Q作为设定的剩下的参与者.

4 每个参与者P_j计算并广播数据点. 现在，任何人都可以验证此数据点是否满足生成多项式函数

请注意，我们不要求参与者同步显示这些数据点，由于看到其他数据后点的参与者不能修改她的数据点.

5 最后，任何人都可以使用数据点在上插值一个生成多项式

然后，随机值将被生成为r=h(a₀||a₁||hellip;||a_k)，其中h表示一些单向散列函数，||是连接符.

5.1效率分析

在步骤1中，每个玩家需要随机选择了一个在上的k阶多项式，然后使用霍纳算法[9]计算n个数据点. 因此，用于该步骤中的所有操作为kn乘法和kn加法. 在步骤2和步骤4，验证分别需要O(k)和O(k²)操作量.在步骤5中，内插多项式时，我们也可以预先计算重心的权重。因此，实时计算需要O(k)的操作量.

5.2安全性分析

我们的协议可以被认为是Pedersen的分布式密钥生成协议[15

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[154181]，资料为PDF文档或Word文档，PDF文档可免费转换为Word