加密通信系统、其密钥分发服务器、终端设备和密钥共亨方法

摘要

一种用于提供高度安全和高速度的组密钥更新的方法。该方法包括在组密钥分发之前在用户终端执行用于译码用于信息译码的加密的组密钥的一部分译码处理的步骤；分发组密钥和用于让每个终端设备执行组密钥的译码处理的其余部分的一部分的各个译码信息的步骤；以及在用户终端通过使用分发的译码信息和事先执行的一部分译码处理的结果而执行组密钥译码处理的步骤。

说明书

技术领域

本发明涉及用于分发用来解密加密的信息的密钥给用户终端的密码技术，具体地涉及用于以安全和快速方式更新密钥的技术。

背景技术

通常遇到许多情形，其中为了建立用于把信息提供给以前确定的组的系统，密钥(组密钥)只分发给登记为组成员的用户，然后执行通过密钥的密码通信。密码技术在许多应用中是有用的，诸如把内容分发到便携式电话、DVD播放器的解密器/重现器、通过CD-ROM接口分发软件、警察无线通信，和在P2P业务中在组之间的本地通信。

在上述的系统中，在终端设备的部件(译码器)被取走，例如被偷窃的情况下，存在有组密钥泄漏给组成员以外的未授权的个人的危险。为此，使用的组密钥必须被更新来创建新的密钥，以及新的密钥必须尽可能快地由组成员共享。

更新密钥的技术在利用一次建立的、用于很长一段时间期间的基础结构的系统中起到极其重要的作用。

假设在这种包含多个用户终端的系统(此后，称为广播型密码通信系统)中，消息被分发到排除单个用户终端或多个用户终端的所有的用户终端。应当注意，术语“排除”是指从组中排除某个用户终端(或某些用户终端)的操作，以及被排除的用户终端被称为“要被排除的终端”(此后，称为排除目标终端)。通常，当排除一个排除目标终端时，需要分发新的密钥给除了该排除目标终端以外的每个单独的用户终端。为此，当组的规模增加时，对于完成使得所有的用户终端共享新的组密钥的操作所需要的通信量和时延量也增加。

传统上，为了减小上述的对于更新组密钥所需要的时延量，设想了各种各样的技术。在日本专利申请2000-196581中公开的一种技术(第一传统技术)将作为上述的类型的传统的技术被示例地说明。

在上述的公布中公开的第一传统技术采用一种算法：它使得在确定排除目标终端后的通信量与时延量不正比于作为组成员的用户的数目”n”。当采用上述的算法和假设要被排除的终端的最大数目是”k”时，每个用户终端必须执行正比于”k”的次数的模指数运算，以计算组密钥。因此，如果”k”远小于”n”(k＜＜n)，则按照该技术的密钥分发可以比起通常的组密钥分发进行得有效得多。例如，当假设系统(n＝10000)包括10000个用户终端以及要排除的终端的数目是100(k＝100)时，虽然通常的组密钥分发需要执行正比于数目”10000”的次数的处理，但按照在该公布中公开的第一传统技术的密钥分发需要执行正比于数目”100”的次数的处理。

然而，在包括多达数百万的用户终端的系统(例如，如便携式电话的用于提供业务给移动终端的系统)和类似的系统中，需要使得代表要被排除的终端的最大数目的数目”k”放大(例如，几千到几万)，以满足组的规模。这使得其计算能力很差的终端上的计算负荷变为相当大，该负荷是由解密加上的，它正比于数目”k”。所以，希望执行组密钥分发，该组密钥分发需要执行解密的次数不正比于数目”k”，或如果可能的话，是恒定的次数。

日本专利申请2001-203682将作为解决上述的问题的一种传统技术(第二传统技术)被示例地说明。

在上述的公布中公开的第二传统技术通过执行模指数运算仅仅”2”次，而不取决于数目”n”和数目”k”来实现解密，数目”n”代表用户终端的总数，以及数目”k”代表要被排除的终端的最大数目。因此，第二传统技术允许包括非常大的数目的用户终端的系统进行快速分发组密钥。

在广播型密码通信系统中，协议的成员被定义为如下：

密钥分发服务器：用于在建立和分发个人密钥到单独的用户终端时，确定系统参数的可靠的代理。当将要分发组密钥时，服务器确定哪些用户终端是要被排除的，然后通过广播分发组密钥。密钥分发服务器用”S”表示。

用户终端：用于从密钥分发服务器接收广播材料的终端。用户终端”i”在建立时间时从密钥分发服务器接收个人密钥”Si”。一组用户终端被定义为一个集合Φ＝{1，...，n}(n＝|Φ|代表用户终端的总数)。

被排除的用户终端：被密钥分发服务器排除的用户终端。当密钥分发服务器在第一轮分发组密钥时要被排除的一组”d”(＜k)个用户终端被定义为一个子集Λ_l(∈Φ)。一旦被排除，在终端被排除的该轮以后，用户终端就不能解密组密钥，在多轮中，它决不重复地被排除。也就是，两个子集的交集为Λ_l∩Λ_l’＝{0}(l≠l’)。而且，假设代表被排除的用户终端的总数的数目在所有的轮中决不超过数目”k”(即，|∪Λ_l|≤k)。

有效的用户终端：未被排除的用户终端。假设在第一轮组密钥分发中有效的一组用户终端被定义为一个集合Ω_l(＝Φ\U^l_j＝lΛ_j)。

在这样定义的广播型密码通信系统中，U_l在第一轮被分发到在整个用户终端Φ中间的有效的用户终端Ω_l。使用U_l来加密消息允许这种类型的密码通信被使用于组Ω_l内的广播。也就是，密码通信如下地执行：

1.令Ω₀＝Φ。密钥分发服务器通过点对点和密钥分发协议连接，把组密钥”U₀”个人密钥key_i分发到每个用户”i”(i∈Φ)。

2对于每个l≥1，重复执行以下的处理(此后，执行以下的处理一次，称为“1轮”)：

(a)密钥分发服务器确定A₁CΩ_l-1。

(b)如果k≥∑^l_j＝1|Λ_j|，Φ：＝Ω_l-1，U₀：＝U_l-1，则返回到l。

(c)密钥分发服务器把报头H_l分发到Ω_l，使得Ω_l计算U_l。

(d)v∈Ω_l通过使用H_l和key_v计算U_l。

(e)密钥分发服务器和Ω_l通过使用U_l执行广播型密码通信。

而且，在此后阐述的说明中，利用以下的参数。”p”和”q”是满足q|p-1的大的质数，以及”g”是在有限区Z_p上阶数”q”的单元。”p”和”q”的大小被确定成使得关于组GF(q)的离散对数问题在计算上是很困难的，该组包含”g”作为生成单元。在以下的解释中，除非另外提出，计算都是使用模p算术进行的。应当注意，虽然未详细描述，除了不同于定义在组GF(q)上的质数的阶数”p”时使用的定义，阶数“p”可以被定义在任何组GF(p)上，这样，求解离散对数问题在计算上是很困难的。例如，通过(1)对于阶数”p”的单元进行乘法运算相应于在诸如椭圆曲线的曲线上对于任意有限的区的加法运算，或(2)通过令质数“p’”代替质数”p”作为指数，然后对扩展区GF(p’)进行算术运算，代替使用质数“p’”作为模数执行剩余运算，而构建组。

E(密钥，消息)表示使用对称密钥加密的消息加密。“n”表示用户终端的总数以及“k”(k＜n)表示要被排除的终端的最大数目。

在上述的假设下，在保密性和有效性方面，需要广播型密码通信系统满足以下四项要求。

1.有效的用户终端v∈Ω_l能够独立地解密组密钥(以多项式次数)。

2.即使当使用“k”个排除的用户终端的每一个拥有的个人密钥时，任何个人在用户终端被排除的轮以后也不能解密组密钥(以概率多项式次数)。

3.在分发组密钥时使用的报头的长度和每个用户终端拥有的个人密钥的尺寸不依赖于代表用户终端的总数的数目。

4.当在接收报头以计算组密钥的时间间隔内执行多次模指数运算和完成组密钥的解密(解密)时，该次数不取决于“n”和“k”。

要求1是需要用户终端能够有效地独立地执行解密的要求。在广播型密码通信系统中，当用户终端在解密后不需要与其他终端通信时在网络上不放置附加业务是重要的。

要求2是为阻止排除的用户终端尝试与其他排除的终端协同作用解密会话密钥所必须满足的要求。

要求3是为阻止在系统包括非常大量的用户终端时处理量的重大的增加所必须满足的要求。

要求4是必须满足以解密需要处理量的组密钥的要求，当“k”需要被确定为大小正比于大组的规模时，该处理量不取决于“n”和“k”。

所谓的“准备暗处攻击”和“r公开攻击”被包括在要求2中。使用时间阈值的协议实际上不能解决由“公开攻击”引起的问题。应当注意，当假设揭示秘密的攻击者的数目是“w”时，如果未授权的个人的数目不大于“k-w”，则秘密可被保持。因此，在与其他未授权的用户终端协同作用的未授权的用户终端的总数不大于“k”的条件下，评估协议的安全性允许讨论在与要求2相同的领域内的安全性。

上述的传统技术1满足上述的要求1，2和3。要被分发的加密消息的长度相应于恒定的时间间隔O(k)以及要被分发的个人密钥的尺寸相应于O(l)，意味着这些因素产生极高的效率。然而，由于代表为解密组密钥而要执行的模指数运算次数的数目等于O(k)，以及另外，模指数运算不能在接收组密钥之前施加到预计算，传统技术1不满足要求4。

传统技术2注意力集中在要求4的必要性上，然后提供满足要求4的算法。然而，传统技术2并不满足要求2，要求2是对于安全性最重要的，这是从以下的分析得出的理由。也就是，当组密钥被分发有限的次数时，未被排除的用户终端能够要求关于整个系统的秘密信息以及在密钥被分发有限次数后取消要执行的排除的操作(例如，如果k≥5，则在组密钥被分发三次后，对系统的攻击是可能的)。

下面将显示传统技术2如何不满足要求2。首先，将解释对于广播型密码通信传统技术2采用的算法。

1.建立

密钥分发服务器确定代表要被排除的终端的最大数目的数目“k”，以及随机地选择由以下的数字表示式1代表的k阶多项式Z_q。

[数字表示式1]

$>>F>>(>x>)>>=>>\Sigma >>j>=>0>>k>>>a>j>>>x>j>>>s>$

$>>G>>(>x>)>>=>>\Sigma >>j>=>0>>k>>>b>j>>>x>j>>>s>$

F(0)＝S和G(0)＝T(mod q)是只有密钥分发服务器知道的秘密密钥。密钥分发服务器把key_i＝(s_i，f_i)＝(F(i)，g^G(i)/F(i))(i＝1，...，n)经由秘密通信路径分发到每个用户终端“i”。另外，密钥分发服务器随机地选择单元U₀∈GF(q)以及广播它。

2.组密钥的加密

在第“l”(≥1)轮分发的组密钥U_l以以下的方式被分发。随机选择单元r_l∈Z_q和确定X_l＝g^rl。然后，确定对于要被排除的“d”用户终端的集Λ_l。从“n+k(R-1)”与“n+kR”中间选择“(k-d)”个整数，以及确定包含“(k-d)”个整数的集Θ_l。密钥分发服务器根据以下的数字表示式2确定M_l1，...，M_lk。

[数字表示式2]

M_ij＝r_lF(j)+G(j) modq(j∈Λ_lYΘ_l)

最后，密钥分发服务器确定E(U_l-1，B_l)＝E(U_l-1，X_l||[(j，M_lj)|j∈Λ_l∪Θ_l])，然后广播它。在第“l”轮中被共享的组密钥是U_l＝g^rlS+T。

3.组密钥的解密

由于在“l”轮中有效的用户终端，即，单元v∈Ω_l是单元v∈Ω_l-1，用户终端包含在“l-1”轮中的U_l-1。用户终端“v”通过使用U_l-1解密在接收的加密的消息E(U_l-1，B_l)中的B_l。然后，通过使用有关B_l的信息，终端根据数字表示式3计算组密钥U_l。

[数字表示式3]

$>>>U>l>>=>>>(>>X>l>>>f>v>>)>>>W>>l>1>>>>>g>>W>>l>2>>>>>s>$

其中，

[数字表示式4]

W_l1＝s_vL(v) mod q

$>>>W>>l>2>>>=>>\Sigma >>j>\in >>\Lambda >l>>>\Theta >l>>>>>(>>M>lj>>L>>(>j>)>>)>>mod>\; q>>s>$

而且，L(j)是由以下的数字表示式5代表的Lagrange多项式给出的插入系数。

[数字表示式5]

$>>L>>(>j>)>>=>>\Pi >>t>\in >>\Lambda >l>>Y>>\Theta >l>>Y>\{>v>\}>\backslash >\{>j>\}>>>>t>/>>(>t>->j>)>>mod>q>>s>$

随后，将显示在传统技术2中利用的算法如何不满足要求2。下面将详细地显示在“R”轮中有效的和任选的用户终端∨_v，即单元∨_v∈Ω_R如何计算和确定只有密钥分发服务器应当知道的秘密信息“S”和“T”。终端“v”在轮1到R，得到(j，M_lj)(l＝1，...，R，j＝1，...，k)，以及所得到的(j，M_lj)满足由以下的数字表示式6代表的关系。

[数字表示式6]

$>>>M>lj>>=>>r>l>over>>\Sigma >>t>=>0>>kover>>>a>t>>>j>t>>+over>>\Sigma >>t>=>0>>kover>>>b>t>>>j>t>>mod>q>>(>l>=>1>,>K>,>R>,>j>\in >>\Lambda >l>>Y>>\Theta >l>>,>|>>\Lambda >l>>Y>>\Theta >l>>|>=>k>)>>>s>$

应当注意，由于“j”是已知的，对于“2k+2+R”个变量，a₀，...，a_k，b₀，...，b_k，r₁，...，r_R，得到“kR”个方程。也就是，当“R”满足以下的数字表示式7，可以计算密钥分发服务器拥有的所有的秘密密钥，即，“S”(＝a₀)和“T”(＝b_l0)。

[数字表示式7]

$>>2>k>+>2>+>R>\le >kR>\iff >R>\ge >>>2>>(>k>+>1>)>>>>k>->1>\; >>s>$

例如，如果k≥5，所有的有效的用户终端在第3轮可以计算密钥分发服务器拥有的秘密密钥(诸如“S”和“T”)。这表示传统技术2不满足要求2。

发明内容

因此，本发明的目的是提供一种以高度安全和足够快速的方式更新组密钥而同时满足上述的四个要求的方法。

而且，除了上述的目的以外，本发明设想提供高度安全和高度有效的广播型密码通信。

为了达到上述目的，本发明被实现为密码通信系统，包括用于分发被使用来解密加密的信息的密钥的密钥分发服务器，和特定数目的、利用该信息的用户终端。按照本发明的第一方面的密码通信系统其特征在于，密钥分发服务器被构建成使得密钥分发服务器分发：被使用来解密信息的加密的第一组密钥；相应于特定数目的用户终端的、和被使用来执行所述第一组密钥的解密的各个解密信息；和相应于特定数目的用户终端的、和被使用来执行第二组密钥的一部分解密的各个密钥更新信息，该第二组密钥是在组密钥被更新后被更新的，以及特定数目的用户终端被构建成使得特定数目的用户终端通过利用由根据以前得到的和被使用来解密第一组密钥的密钥更新信息执行的处理操作得到的结果以及还利用从密钥分发服务器分发的解密信息，而解密从密钥分发服务器分发的第一组密钥。在时域上用于解密组密钥的分发操作减小了在更新组密钥时的处理量。

特定数目的用户终端在分发组密钥之前，实施组密钥的一部分解密。在用户终端中在分发组密钥之前预先实施组密钥的一部分解密，使得有可能减小对于在更新组密钥时不失去安全性的条件下分发新的组密钥后执行处理所需要的时间间隔。

优选地，在密码通信系统中，密钥分发服务器把被使用来解密第一组密钥的密钥更新信息连同处在第三组密钥被更新到第一组密钥之前的状态的第三组密钥一起分发到特定数目的用户终端。

而且，在密钥分发服务器更新组密钥的情况下，密钥分发服务器确定在特定数目的用户终端中间哪些用户终端要被排除，以及把被除了排除目标用户终端以外的其余的用户终端使用的解密信息连同被更新的组密钥一起分发到特定数目的用户终端，以使得其余用户终端能够解密被更新的组密钥。

为了达到上述目的，本发明还被实现为如下所述地构成的、用于分发用来解密加密的信息的密钥的密钥分发服务器。密钥分发服务器其特征在于包括：用于生成用来解密信息的第一组密钥和加密第一组密钥的装置；用于生成用来执行第一组密钥的解密的且相应于用户终端的各个解密信息的装置；用于生成用来执行第二组密钥的一部分解密的、和相应于用户终端的各个解密更新信息的装置，该第二组密钥是在一个组密钥更新后被更新的；以及用于分发第一组密钥、解密信息、与密钥更新信息给用户终端的装置。

为了达到上述目的，本发明还被实现为如下所述地构成的终端设备。该终端设备其特征在于包括：用于从特定的密钥分发服务器检索被加密以解密加密的信息的组密钥和用来解密组密钥的解密信息的装置；用于在组密钥分发之前执行组密钥的一部分解密的装置；以及用于通过利用根据组密钥的一部分解密执行处理操作得到的结果和从密钥分发服务器检索的解密信息而解密组密钥的装置。

而且，本发明还被实现为用于控制计算机和然后使得计算机作为上述的密钥分发服务器和/或终端设备运行的程序。该程序可被提供成使得程序被存储在磁盘、光盘和/或其他存储介质，诸如半导体存储器，然后，那些介质通过网络进行传递或分发。

此外，本发明被实现为如下所述地构建的、用于使得使用信息的特定数目的终端共享被使用来解密加密的信息的密钥的密钥共享方法。也就是，密钥共享方法其特征在于，该方法包括：使得特定数目的终端在组密钥分发之前执行被使用来解密信息的加密的组密钥的一部分解密的步骤；把组密钥和被使用来执行除了组密钥的一部分解密以外的一部分其余解密的、和相应于特定数目的终端的各个解密密钥分发到特定数目的终端的步骤；以及使得特定数目的终端使用被分发的解密信息和通过执行组密钥的一部分解密得到的结果——该一部分解密是以前执行的——来执行组密钥的解密的步骤。

附图说明

图1是说明按照实施例的广播型密码通信系统的总体结构的图。

图2是说明按照实施例如何执行密码通信的流程图。

图3是说明采用实施例的对等网络系统的结构的图。

图4是说明采用实施例的实时内容分发系统的结构的图。

图5是说明采用实施例的、用于为便携式电话提供业务的系统的结构的图。

图6是说明采用实施例的、用于分发多媒体内容的系统的结构的图。

图7是说明采用实施例的秘密广播系统的结构的图。

具体实施方式

下面根据附图上显示的实施例，详细地说明本发明。

图1是说明按照实施例的广播型密码通信系统的总体结构的图。

参照图1，按照实施例的广播型密码通信系统包括：密钥分发服务器10，用于生成用来进行密码通信的组密钥和分发该密钥；以及用户终端20，用于得到从密钥分发服务器10分发的组密钥，以及使用该密钥进行密码通信。

密钥分发服务器10是通过采用具有联网功能的工作站、个人计算机或其他计算设备实现的，以及在建立时确定系统参数，然后把个人密钥分发到每个用户终端20。当分发组密钥时，服务器确定哪些用户终端20是要排除的，然后解密该组密钥，此后，分发该密钥作为广播材料。诸如个人密钥和组密钥的生成、分发等等的处理，例如被实现为程序控制的CPU的功能。

用户终端20是通过采用具有联网功能的工作站、个人计算机、便携式电话、个人数字助理(PDA)或其他信息终端设备实现的，以及接收来自密钥分发服务器10的广播材料。用户终端“i”(第i个用户终端20)在建立时接收来自密钥分发服务器10的个人密钥S_i。然后，该终端使用个人密钥S_i解密加密的组密钥，而且，使用组密钥解密特定的消息，然后利用该消息。这些处理是通过采用例如程序控制的处理器实现的。假设一组用户终端20被定义为一个集合Φ＝{1，...，n}(n＝|Φ|，代表用户终端20的总数)。

整个用户终端20构成一个组Φ，它使用由密钥分发服务器10分发的组密钥执行密码通信。虽然构成该组的各个用户终端20初始地是能够参加密码通信的“有效的用户终端”，但在一个或多个用户终端由于某种原因成为“被排除的用户终端”后，被排除的终端决不能参加密码通信。也就是，被排除的终端决不能使用个人密钥来解密组密钥。

在实施例中采用的通信配置可以是其中在密钥分发服务器10或特定的服务器与用户终端20之间传送信息的是客户机/服务器系统，或其中在用户终端20之间传送信息的对等系统。也就是，提供被用户终端20使用的消息(内容)的供应商可以存在于与密钥分发服务器10分开的位置。

使用组密钥和在广播型密码通信系统内进行的密码通信包括四个阶段，即组密钥建立，使用组密钥的信息加密，使用组密钥的信息解密，以及密钥更新。

图2是说明按照本发明的如何执行密码通信的流程图。

在该实施例中，取决于代表排除目标终端的最大数目的数目“k”的一部分计算被分开，作为在加密的组密钥的解密期间的预计算(密钥更新)。这允许以鉴权的方式保持保密性，以及还许可除密钥更新以外通过执行模指数运算两次以高速度执行组密钥的解密。下面将说明按照实施例如何构建密码通信协议。应当注意，在以下的说明中，接收机是指使用用户终端20的用户和用户自己。

1.建立

在由以下的数字表示式8表示的Z_q中随机选择具有一个变量的”k”阶多项式。

[数字表示式8]

$>>F>>(>x>)>>=>S>+>>\Sigma >>j>=>1>>k>>>a>j>>>x>j>>>s>$

$>>>G>1>>>(>x>)>>=>>T>1>>+>>\Sigma >>j>=>1>>k>>>b>>1>j>>>>x>j>>>s>$

F(0)＝S和G_l(0)＝T_l被密钥分发服务器10制成秘密密钥。密钥分发服务器10把key_i＝(s_i，f_li)＝(F(i)，g^Gl(i)/F(i))作为在第一轮中用于接收机“i”的解密密钥分发到每个用户终端i∈(1，...，n)。并把组密钥U₀∈GF(q)分发到所有的用户终端20(步骤201)。

2.在第l轮中组密钥的加密

密钥分发服务器10随机地选择单元r_l∈Z_q和确定X_l：＝g^rl。然后，服务器确定要被排除的“d”用户终端的集合Λ_l(步骤202)。服务器从“n+k(R-1)”与“n+kR”中间选择“(k-d)”个整数，以及确定包含“(k-d)”个整数的集合Θ_l。密钥分发服务器10根据以下的数字表示式9确定M_l1，...，M_lk。

[数字表示式9]

M_lj＝r_lF(j)+G_l(j) modq(j∈Λ_lYΘ_l)

而且，作为有效的用户终端20的Ω_l(此后，称为用户终端Ω_l)通过使用以下的数字表示式10计算对于在“l”轮中计算分发密钥U_l所需要的报头信息H_l(步骤203)。

[数字表示式10]

B_l＝<X_l||{(j，M_lj)|j∈Λ_lYΘ_l}>

H_l＝E(U_l-1，B_l)

应当注意，在“l”轮中由有效的用户终端“Ω_l”共享的组密钥被表示为U_l＝g^rS+Tl。

随后，服务器生成密钥更新信息，以便在”l+1”轮中分发组密钥(也就是，用户终端20在“1+1”轮中解密组密钥后使用信息来更新密钥)。密钥分发服务器10随机地选择单元b_l+1，j∈Z_q(j＝0，...，k)和确定方程(u_l0，...，u_lk)＝(g^b1+l，0，...，g^b1+l，k)，以及根据以下的数字表示式11，使用组密钥U_l加密该方程，以确定C_l(步骤204)。

[数字表示式11]

C_l＝E(U_l，u_l0||K||u_lk)

然后，密钥分发服务器10把(H_l，C_l)作为广播材料分发到所有的用户终端20(即，Φ)(步骤205)。

3.在“l”轮中组密钥的解密

作为能够在“l”轮中进行解密的用户终端20的用户终端“v”，即单元v(∈Ω_l)，根据以下的数字表示式12在第“1”轮中进行解密(步骤206)。

[数字表示式12]

$>>U>=>>>(>>X>l>>>f>lv>>)>>>W>>l>1>>>>>g>>W>>l>2>>>>>s>$

W_l1＝s_vL(v) modq

$>>>W>>l>2>>>=>>\Sigma >>j>\in >\Lambda Y\Theta >>>>M>lj>>L>>(>j>)>>mod>q>>s>$

其中，

$>>L>>(>j>)>>=>>\Pi >>t>\in >\Lambda Y\Theta Y>\{>v>\}>\backslash >\{>j>\}>>>t>/>>(>t>->j>)>>mod>q>>s>$

也就是，在这轮中，用户终端“v”使用先前根据在“l-1”轮中分发的信息计算的f_lv和通过使用在步骤205分发的H_l被解密的“B_l”在”l”轮中解密组密钥“U_l”。

4.对于“l+1”轮的密钥更新(预计算)

根据以下的数字表示式13，用户终端“v”，即，单元v∈Ω_l，通过使用被包含在从密钥分发服务器10分发的C_l中的密钥更新信息，执行密钥更新作为预计算(即，在“l+1”轮中分发组密钥之前的处理)(步骤207)。

[数字表示式13]

$>>>f>>l>+>1>,>v>>>=>>>(over>>\Pi >>j>=>0>>kover>>>>u>lj>>>v>j>>>)>>>1>/>>s>v>>>>>s>$

另外，密钥分发服务器10在“l+1”轮中生成组密钥之前，执行以下数字表示式14的预计算。

[数字表示式14]

T_l+1＝b_l+1，0 modq

$>>>G>>l>+>1>>>>(>x>)>>=over>>\Sigma >>j>=>0>>kover>>>b>>l>+>1>,>j>>>>x>j>>mod>q>>s>$

密钥更新(预计算)应当由用户终端20和密钥分发服务器10在“l+1”轮中分发组密钥之前通过使用在“l”轮中连同组密钥一起分发的信息而被执行。

下面将识别如上所述按照实施例构建的广播型密码通信系统是否满足在安全性和效率方面的四个要求。

首先，显然，本实施例满足要求1，因为它不需要用户终端20之间进行通信。

而且，本实施例被构建成使得要被分发的加密的消息的长度等于O(k)以及要被分发的个人密钥的尺寸等于O(1)，还满足要求3。

另外，本实施例被构建成使得通过执行模指数运算两次而进行解密，还满足要求4。

随后，将说明本实施例如何还满足剩余的要求2。

首先，建立在要求2中“使用“k”个排除的用户终端拥有的个人密钥”的攻击者模型。攻击者的行为被建模为算法M₁，该算法根据由直至”R”轮之前被排除的“k”个成员拥有的解密密钥和直至“R”轮之前接收的信息确定在多项式时间在“R”轮中的组密钥。假设该(“k”)个排除的用户终端20被规定为用户终端“i”(i＝1，...，k)，而不失一般性。加到M_l的输入是＜g，p，q，k，U₀，(s₁，...，s_k)，(f_l1，...，f_lk)，(H₁，C₁)，...，(H_R，C_R)＞。

当攻击者的行为被如上所述地建模时，要求2可以替换地通过使用判决Diffie-Hellman(DDH)问题被描述为如下。

(命题)

“只要不存在解决DDH问题的多项式时间算法，M_l就不存在。”

DDH问题是判断问题，当随机从集合GF(q)选择单元g，h和单元a，b∈Z_q时，D＝＜g，n，g^a，h^a＞(这种形式被称为“Diffie-Hellman对”)和R＝＜g，h，g^a，h^a＞在GF(q)上以相当大的概率被鉴别。以多项式时间解决DDH问题的算法现在还不知道。也就是，这个问题是数学问题，可以认为求解这个问题在计算复杂性上是很困难的，以及根据上述的命题不存在M_l。因此，本实施例满足要求2。

如上所述，通过使用按照本实施例的在广播型密码通信系统中共享组密钥的方法，当组密钥被更新时安全性可以以鉴权的方式被保持，以及通过在分发组密钥之前对于实施组密钥的一部分解密作为预计算和在更新的组密钥分发后还执行模指数运算仅仅两次，而不取决于代表用户终端数目的数目“n”和代表排除的终端的最大数目的数目“k”，可以执行解密。因此，本方法在其中包括非常大数目的用户终端20的网络系统中是特别有效的。

随后，下面说明通过把按照本实施例的广播型密码通信系统应用到各种各样的网络系统而构成的例子。

[对等系统中组成员的管理]

在对等(P2P)网络系统中可以采用本实施例，以安全方式和高速地执行组内的通信。也就是，在网络系统中的组内所有的对等成员共享一个密钥(组密钥)以及进行广播型密码通信。

图3是说明采用本实施例的对等网络系统的结构的图。如图3所示，网络系统问题中的组管理器构成本实施例的密钥分发服务器10，以及组内的各个对等成员构成用户终端20。

在上述的网络系统中，当特定的对等成员以与在成员通过使用“离开”命令离开“jxta”的情形下的相同的方式离开该组，以便在对等成员离开该组后执行组内的保密通信时，需要剩余的对等成员再次尽可能快速地共享新的组密钥。同时，由于各种终端在对等网络系统中能够是对等的，系统需要被构建成使得即使其计算能力是极其有限的终端也能够容易地得到组密钥。本实施例可以在这样的对等网络系统中被采用来管理组内的成员。

当采用本实施例时，由于组密钥的解密可以通过执行模指数乘法两次而被全部完成，在组内的终端不需要具有大的计算能力。而且，即使当把本发明应用到大规模的网络时，组密钥仍可以高速地更新，而不失去可获得的效率。

[实时内容分发系统]

由于游戏机变得越来越复杂，出现通过配置对等网络的先进的在线游戏，每个游戏机被定义为一个对等成员。也就是，相应于组管理器的服务器提供游戏内容给各个游戏机，然后，用户通过游戏机进行对等通信而玩游戏。

图4是说明采用本实施例的实时内容分发系统的结构的图。如图4所示，用于分发游戏内容的服务器构成本实施例的密钥分发服务器10，以及各个游戏机构成用户终端20。

在这样的环境下，虽然预期需要经常在组内执行广播型密码通信，但也预期经常出现脱离组的成员关系。例如，拖欠他/她的会员费的用户必须与该组分离开。因此，当成员离开该组时所需要的为了与其余成员共享组密钥而执行解密的时间的减小，确保应用的高的可用性。

按照本实施例的广播型密码通信系统达到高速解密能力，和可供使用于大规模网络中，所以，可被应用来在图4所示的系统中分发内容。也就是，本实施例的系统允许高速地共享组密钥，以及许可由组密钥加密的内容，在内容接收的同时，即，实时地被解密。而且，费时的密钥更新也可以在内容接收后通过使用在执行内容时的过大的处理能力而被执行。应当注意，虽然说明了其中进行通信以使得内容被分发以执行在线游戏的例子，但不用说，按照本实施例的广播型密码通信系统可被应用于其中分发要实时执行的、不包括游戏内容的各种内容的情形。

[分发数据到便携式电话用户]

近年来，便携式电话大大地传播，现在已被国内一半以上的人口拥有和使用。然后，假设为几百万便携式电话用户提供密码组通信业务的情形。例如，该情形包括其中把特定的业务提供给构成一个组的终端的情形。

图5是说明本实施例应用到的用于便携式电话的业务提供系统的结构的图。如图5所示，用于提供业务的服务器构成密钥分发服务器10，以及登记该业务的便携式电话构成用户终端20。

在这样构建的网络系统中，当用户拖欠他/她的会员费或他/她的终端丢失或被盗窃时，必须破坏给予特定的终端的接入该组的许可。按照本实施例，即使具有很差的计算能力的便携式电话也能够通过应用本发明到该电话，而执行广播型密码通信。

[多媒体内容分发系统]

近年来，使用DVD的多媒体内容分发系统爆发性地传播。

图6是说明按照本实施例构建的多媒体内容分发系统的结构的图。如图6所示，提供多媒体内容的内容提供商构成密钥分发服务器10，以及用于重现多媒体内容的重现机构成用户终端20。

在该系统中，其中存储加密的数字内容(例如，电影，音乐和软件)的DVD媒体被分发。加密的内容通过使用在重现机中包含的解密器/重现器中存储的解密密钥被解密。解密密钥是随各个制造者而不同的，以及被存储在解密器/重现器的安全的存储器区域。然而，有解密密钥泄漏的危险，当闯入者分析加密密钥或制造者无法正确地组成该密钥时将观察到这一点。在这种情形下，需要提供密码算法，它使得某些加密密钥是不可用的。

当利用本实施例时，可以以鉴权的方式保持安全性，以及可以进行解密密钥更新，以使得某些加密密钥是不可用的。[解决警察无线收发信机的丢失/偷窃问题的秘密广播系统]

警察无线电是在组内保密通信的典型的例子。在这种情形下，被使用于保密通信的系统需要被构建成使得即使当使用除了警官拥有的收发信机外的无线接收机时，通信不能被监视。

图7是说明采用本实施例的秘密广播系统的结构的图。如图7所示，用于秘密广播的广播站构成密钥分发服务器10，以及各个无线接收机构成用户终端20。

如上所述，秘密广播，诸如警察无线通信，应当被执行成使得即使当使用除了警官拥有的收发信机外无线接收机时，通信不能被监视。然而，在警官的收发信机丢失或被盗窃的情况下，丢失的或被盗窃的收发信机从包含用户终端20的组(Φ)中被排除，然后按照本实施例，新的组密钥由其余用户终端共享，由此，使得丢失的收发信机是不可用的。

工业应用性

正如到此所描述的，按照本发明可以提供以高度安全的方式和高速地更新组密钥的方法。

而且，按照本发明可以达到高度安全的和高度有效的广播型密码通信。