密钥生成设备、加密设备、接收设备、密钥生成方法、加密方法、密钥处理方法以及程序

摘要

密钥生成设备构建分配了n个接收设备的分级Y分支树结构。使用存在于该Y分支树结构的树叶和根之间的中间节点作为父节点将新参数分别提供至每个子群，以便于可以灵活地配置该子群。当不存在或存在少量待排除的合同者时，可以减小待分布的首标大小以及该合同者将要执行的运算的计算量。

说明书

技术领域

本发明涉及密钥生成设备、加密设备、接收设备、密钥生成方法、加密方法、密钥处理方法以及程序。

背景技术

近年来，不仅由于个人计算机(PC)的普遍使用，而且由于便携式电话、数字家用电器等的普遍使用，针对音乐、图像等的内容传递业务(deliverybusiness)已经变得越来越重要。例如，作为内容传递业务，存在使用有线电视、卫星广播或因特网的付费广播，使用诸如CD或DVD之类的物理介质的内容的销售等。在任意这些情况下，均需要配置仅有客户才可获取内容的机制。

通常，在这种内容传递系统中，系统的管理员(在下文中，称为中心)预先仅向客户提供密钥，并且在内容传递时，传递已经通过使用会话密钥s对内容M加密而生成的加密文本C，以及用于仅允许该客户获取会话密钥s的首标h。因此，只有该客户可获取内容M。

作为用于实现上述情形的内容传递方法，例如，使用公钥的方法是可用的(例如，见非专利文献1)。

非专利文献1：D.Boneh，C.Gentry，B.Waters，＂Collusion ResistantBroadcast Encryption With Short Ciphertexts and Private Keys＂，CRYPTO′05，Proceedings of 25th Annual International Cryptology Conference on Advances inCryptology，London，UK，Springer Verlag，2005，58-75页。

发明内容

技术问题

然而，在上述非专利文献1描述的公钥加密方法中，即使在对其取消传递的排除用户的数量很少的情况下，也总是需要传递恒定大小的首标h。因此在实际可能的情形(诸如，排除客户的数量为零的情况或者排除用户的数量相对于用户的总数的百分比很小的情况)下，不能降低首标大小。因此，存在在传递已加密内容时数据冗余度增大的问题。

因此，鉴于上述问题作出本发明。本发明的目的是提供：即使在排除用户的数量很小的情况下也能够降低首标大小的、新颖的并且改进的密钥生成设备、加密设备、接收设备、密钥生成方法、加密方法、密钥处理方法以及程序。

技术方案

为了实现上述目的，根据本发明的第一方面，提供密钥生成设备，其包含：树结构构造单元，其分级地构造将n个接收设备分配给树叶并且由logYn表示高度的Y元树结构，并且形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群；叶密钥分配单元，其将叶密钥gy分配给各树叶以及各中间节点；参数分配单元，其向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……YX)及节点参数γ_x，y(x：层，y：1，2，……YX)；以及密钥计算单元，其识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

上述密钥生成设备可配置为进一步包含传递单元，其向相应接收设备传递密钥计算单元计算出的该路径中的多组密钥。

上述密钥生成设备可配置为进一步包含：随机数判定单元，其随机地选择素数p以确定将该素数p作为阶的双线性群G，随机地选择用作G的生成元的g，并且随机地选择保密随机数α(α是整数)。上述叶密钥分配单元可计算满足以下表达式A的叶密钥g_y。这里，在以下表达式A中，设置y＝1、2、……、Y、Y+2、……、2Y。

[算式1]

$g_y=g^{{\left(\alpha \right)}^y}$ ……表达式A

上述参数分配单元可为根及除了树叶之外的所有各节点随机地选择节点参数γ_x，y(γ_x，y是整数)，并且可计算以下表达式B中所示的参数ν_x，y。

[算式2]

$v_{x,y}=g^{\left({\gamma }_{x,y}\right)}$……表达式B

密钥计算单元将通过把分配给中间节点或树叶的叶密钥g_y提高至分配给该中间节点或该树叶的父节点的参数γ_x，y的幂所得到的值设置为保密密钥。即，在将分配给中间节点或树叶的的叶密钥g_y简写为K并且将分配给该中间节点或该树叶的父节点的参数γ_x，y简写为T的情况下，可以将通过K^T获得的值设置到保密密钥。

上述密钥计算单元可基于叶密钥g_y和参数ν_x，y来计算公钥。上述传递单元可包含公布该公钥的公钥公布部分。

上述传递单元可进一步包含将密钥计算单元计算出的保密密钥传送至相应接收设备的传输部分。

为了取得上述目的，根据本发明的第二方面，提供包括排除接收设备识别单元的加密设备，其中，所述排除接收设备识别单元识别n个接收设备之中的排除接收设备，并且确定非排除接收设备的组S。

上述加密设备可进一步包括会话密钥确定单元，其随机地选择整数t，并且确定会话密钥s＝e(g_y，g₁)^t。

这里，上述e(g_y，g₁)表示关于双线性群的两个元素g_y和g₁的双线性映射。

上述加密设备可进一步包括加密单元，其通过使用会话密钥s对待传递的内容加密。

在分级树结构中，上述会话密钥确定单元可进一步包含首标元素计算部分，其标记在从树叶延伸至向其分配了排除接收设备的树叶的路径中存在的所有各节点，并且基于分配给已标记节点的参数ν_x，y以及分配给该已标记节点用作其父节点的中间节点的叶密钥g_y，通过使用以下表达式C来计算首标元素。这里，S_x，y表示属于已标记节点用作父节点的每个子群的一组未标记子节点。

[算式3]

$c_{x,y}={(v_{x,y}·\underset{j\in S_{x,y}}{\Pi }{g}_{Y+1-j})}^t$……表达式C

上述会话密钥确定单元可进一步包含首标信息生成部分，其将所述首标元素计算部分得到的c_x，y和g_y设置为首标信息。

为了取得上述目的，根据本发明的第三方面，提供能够与密钥生成设备及加密设备通信的接收设备，该接收设备包括接收密钥生成设备得到的密钥的接收单元，其中，该密钥生成设备分级地构造其中将n个接收设备分配给树叶并且由log_Yn表示高度的Y元树结构，形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群，将叶密钥g_y分配给各树叶以及各中间节点，向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……Y^X)及节点参数γ_x，y(x：层，y：1，2，……Y^X)，识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

上述接收设备可进一步包括解密单元，其通过使用会话密钥s来对经加密的内容进行解密。

上述接收单元可进一步接收作为用于识别排除接收设备的信息的、关于非排除接收设备的组S的信息。上述接收设备可进一步包括确定单元，其确定该组S中是否包含该接收设备。

在确定单元确定组S中包含上述接收设备的情况下，上述解密单元可通过基于以下的表达式D计算会话密钥s并且使用计算出的会话密钥s来对经加密的内容进行解密。

[算式4]

$s=\frac{e(g_{i_{x\prime }},c_{x,y})}{e({g_{i_{x\prime }}}^{{\gamma }_{i_{x\prime }-1}}·\underset{j\ne i_{x\prime }}{\underset{j\in S_{x,y}}{\Pi }}{g}_{Y+1-j+i_{x\prime }},g^t)}$……表达式D

为了取得上述目的，根据本发明的第四方面，提供密钥生成方法，其包含：树结构构造步骤，其分级地构造将n个接收设备分配给树叶并且由log_Yn表示高度的Y元树结构，并且形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群；叶密钥分配步骤，其将叶密钥g_y分配给各树叶以及各中间节点；参数分配步骤，其向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……Y^X)及节点参数γ_x，y(x：层，y：1，2，……Y^X)；以及密钥计算步骤，其识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

为了取得上述目的，根据本发明的第五方面，提供包括排除接收设备识别步骤的加密方法，其中，所述排除接收设备识别步骤识别n个接收设备之中的排除接收设备，并且确定非排除接收设备的组S。

为了取得上述目的，根据本发明的第六方面，提供包括接收通过如下处理得到的密钥的步骤的密钥处理方法，所述处理包含：分级地构造将n个接收设备分配给树叶并且由log_Yn表示高度的Y元树结构，形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群，将叶密钥g_y分配给各树叶以及各中间节点，向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……Y^X)及节点参数γ_x，y(x：层，y：1，2，……Y^X)，识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

为了取得上述目的，根据本发明的第七方面，提供用于促使计算机实现以下功能的程序：树结构构造功能，其分级地构造将n个接收设备分配给树叶并且由log_Yn表示高度的Y元树结构，并且形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群；叶密钥分配功能，其将叶密钥g_y分配给各树叶以及各中间节点；参数分配功能，其向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……Y^X)及节点参数γ_x，y(x：层，y：1，2，……Y^X)；以及密钥计算功能，其识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

根据该配置，通过将计算机程序存储在计算机中提供的存储单元中并且由计算机中提供的CPU来读取和执行该计算机程序，该计算机程序促使计算机用作上述的密钥生成设备。另外，也可提供具有记录在其上的计算机程序的计算机可读记录介质。例如，该记录介质是磁盘、光盘、磁光盘、闪存等。另外，例如，可以经由网络传递上述计算机程序，而无需使用所述记录介质。

为了取得上述目的，根据本发明的第八方面，提供用于促使计算机实现排除接收设备识别功能的程序，该排除接收设备识别功能识别n个接收设备之中的排除接收设备，并且确定非排除接收设备的组S。

根据该配置，通过将计算机程序存储在计算机中提供的存储单元中并且由计算机中提供的CPU来读取和执行该计算机程序，该计算机程序促使计算机用作上述的加密设备。另外，也可提供具有记录在其上的计算机程序的计算机可读记录介质。例如，该记录介质是磁盘、光盘、磁光盘、闪存等。另外，例如，可以经由网络传递上述计算机程序，而无需使用所述记录介质。

为了取得上述目的，根据本发明的第九方面，提供用于促使计算机实现接收通过如下处理得到的加密密钥的接收功能的程序，所述处理包含：分级地构造将n个接收设备分配给树叶并且由log_Yn表示高度的Y元树结构，形成由比树叶和根之间存在的中间节点更低的层中存在的多个树叶构成的子群，将叶密钥g_y分配给各树叶以及各中间节点，向所述各中间节点及所述根分配不同的参数ν_x，y(x：层，y：1，2，……Y^X)及节点参数γ_x，y(x：层，y：1，2，……Y^X)，识别从所述根延伸至所述树叶的路径，并且基于向所述路径中存在的中间节点或树叶分配的叶密钥g_y以及向该中间节点或该树叶的父节点分配的参数ν_x，y和节点参数γ_x，y来计算密钥。

根据该配置，通过将计算机程序存储在计算机中提供的存储单元中并且由计算机中提供的CPU来读取和执行该计算机程序，该计算机程序促使计算机用作上述接收设备。另外，也可提供具有记录在其上的计算机程序的计算机可读记录介质。例如，该记录介质是磁盘、光盘、磁光盘、闪存等。另外，例如，可以经由网络传递上述计算机程序，而无需使用所述记录介质。

有益效果

根据本发明，即使在排除客户的数量很小的情况下，也可以减小首标大小。

附图说明

图1是用于根据本发明的优选实施例说明加密密钥生成系统的说明图。

图2是用于根据实施例说明密钥生成设备的硬件配置的框图。

图3是用于根据本发明的基础技术的基本方法说明密钥生成的概况的说明图。

图4是用于根据本发明的基础技术的一般化方法说明密钥生成的概况的流程图。

图5是用于根据本发明的基础技术的一般化方法说明密钥生成阶段的流程图。

图6是用于根据本发明的基础技术的一般化方法说明加密的概况的说明图。

图7是用于根据本发明的基础技术的一般化方法说明加密阶段的说明图。

图8是用于根据本发明的基础技术的一般化方法说明解密阶段的说明图。

图9是用于根据本发明的优选实施例说明密钥生成设备的配置的框图。

图10是用于根据实施例说明加密设备的配置的框图。

图11是用于根据实施例说明接收设备的配置的框图。

图12是用于根据实施例说明逻辑树的具体示例的说明图。

图13是用于根据实施例说明密钥生成的概况的说明图。

图14是用于根据实施例说明密钥生成阶段的流程图。

图15是用于根据实施例说明密钥生成的具体示例的说明图。

图16是用于根据实施例说明加密的概况的说明图。

图17是用于根据实施例说明加密阶段的流程图。

图18是用于根据实施例说明加密的具体示例的说明图。

图19是用于根据实施例说明加密的具体示例的说明图。

图20是用于根据实施例说明加密的具体示例的说明图。

图21是用于根据实施例说明解密阶段的流程图。

图22是用于根据实施例说明解密的具体示例的说明图。

图23是执行传递给客户的首标的首标大小方面的比较的曲线图。

图24是执行双线性群上的乘法的数量方面的比较的曲线图。

图25是执行传递给客户的首标的首标大小方面的比较的曲线图。

图26是执行双线性群上的乘法的数量方面的比较的曲线图。

具体实施方式

在下文中，参考附图详细描述本发明的优选实施例。注意，在说明书和附图中，通过将相同的符号提供给具有基本上相同功能配置的组件，冗余说明将被省略。

(第一实施例)

在下文中，详细描述根据本发明第一实施例的加密密钥传递系统。

图1是示出根据本实施例的加密密钥传递系统10的说明图。例如，加密密钥传递系统10包含：通信网络12、密钥生成设备20、加密设备30、接收设备40A以及接收设备40B。

通信网络12是用于连接密钥生成设备20、加密设备30以及接收设备40以便于可以实现双向通信或单向通信的通信线网络。例如，该通信网络由公共线路网络(诸如因特网、电话网络、卫星通信网络或广播通信信道)、专用线路网络(诸如WAN(广域网，Wide Area Network)、LAN(局域网，Local AreaNetwork)、IP-VPN(因特网协议虚拟专用网，Internet Protocol-Virtual PrivateNetwork)或无线LAN)等构成。该通信网络可以是有线的或无线的。

密钥生成设备20生成公钥(public key)以及对于多个接收设备中的每一个均唯一的保密密钥。密钥生成设备20公布公钥，并且将各保密密钥经由安全通信信道传递给相应接收设备。注意，执行公钥和保密密钥的生成及管理的中心拥有密钥生成设备20。

加密设备30通过使用密钥生成设备20生成并公布的公钥来对任何内容加密，并且将经加密的内容经由通信网络12传递给每个接收设备。加密设备30可由任意第三方拥有。另外，加密设备30可由密钥生成设备20的拥有者或接收设备40的拥有者拥有。

每一个接收设备40均能够通过使用唯一的保密密钥来对从加密设备30传递的经加密内容进行解密，并且能够使用经解密的内容。注意，接收设备40A和接收设备40B可以经由通信网络12或线(wire)来彼此连接。注意，接收设备40由各客户拥有。

注意，虽然在图解实施例中将诸如个人计算机(Personal Computer：PC)之类的计算机设备(无论是笔记本型设备或台式型设备)显示为接收设备40，但是接收设备40并不限于本示例。只要接收设备40是具有经由网络的通信功能的设备，那么就可以将其配置为例如用于电视广播的信息装置(诸如PDA(个人数字助理)、家用游戏机、DVD/HDD记录器或电视接收器)、调谐器或解码器等。可替换地，接收设备40可以是客户可携带的便携式设备(Portable Device)，诸如，例如便携式游戏机、便携式电话、便携式视频/音频播放器、PDA或PHS。

接下来参考图2简要说明根据本实施例的密钥生成设备20的硬件配置。

图2是示出密钥生成设备20的硬件配置的框图。例如，密钥生成设备20包含：CPU(中央处理单元)201、ROM(只读存储器)203、RAM(随机存取存储器)205、HDD(硬盘驱动器)207、加密处理单元209以及存储器(安全模块)211。

CPU 201用作运算处理设备以及控制设备。CPU 201根据各种程序控制密钥生成设备20内的一般运算。ROM 203存储CPU 201使用的程序、运算参数等。RAM 205临时存储CPU 201执行中使用的程序，在该程序的执行中适当变化的参数等。

HDD207是用于被配置为根据本实施例的密钥生成设备20的存储单元的示例的数据存储的设备。HDD 207驱动硬盘，并且存储CPU 201执行的程序以及各种数据。加密处理单元209在CPU 201的控制下，执行根据本实施例的密钥生成设备20所执行的各种类型的加密处理。存储器(安全模块)211主要用于安全地存储需要隐藏的信息，诸如私钥(private secret key)以及中心保密随机数。存储在存储器211内部的信息具有从外界不可查阅该信息的特性。另外，例如，存储器(安全模块)211可由具有防止篡改(tamper-resistant)性质的存储设备构成。注意，虽然给出了指示安全模块为存储器的描述，但是，根据本发明的安全模块不限于存储器。例如，安全模块可以是磁盘、光盘或磁光盘。可替代地，安全模块可以是诸如半导体存储器之类的存储介质。

CPU 201、ROM 203、RAM 205、HDD 207、加密处理单元209以及存储器211通过由CPU总线等构成的总线213而相互连接。

总线213通过桥接器与诸如PCI(外围组件互连/接口)总线之类的输入/输出接口215相连接。

输入单元217例如由用户操作的操作部件(诸如鼠标、键盘、触摸板、按钮、开关以及控制杆)、输入控制电路(用于基于用户的操作生成输入信号并且将该输入信号输出至CPU 201)等构成。通过操作输入单元217，密钥生成设备20的用户能够将各种数据输入至密钥生成设备20，并且能够指令密钥生成设备20执行处理操作。

输出单元219例如由显示设备(诸如CRT(阴极射线管)显示设备或液晶显示(LCD)设备以及灯)、音频输出设备(诸如扬声器和听筒)等构成。输出单元219例如能够输出再现内容。具体地，显示设备以文本或图像的形式显示诸如再现的视频数据之类的各种类型信息。同时，音频输出设备将再现的音乐数据等转换为声音，并且输出该声音。

通信单元221是例如由用于允许与通信网络12的连接的通信设备等构成的通信接口。通信单元221经由通信网络12，将诸如关于加密密钥的信息以及内容信息之类的各种数据传送至例如加密设备30，以及从接收设备40A和40B接收诸如关于加密密钥的信息以及内容信息之类的各种数据。

驱动器223是存储介质的读取器/写入器。驱动器223包含在密钥生成设备20中，或者外部地提供。驱动器223读取所加载的可拆卸记录介质14(诸如磁盘、光盘、磁光盘或半导体存储器)上记录的信息，并且将该信息输出至RAM 205。

注意，由于加密设备30和接收设备40的硬件配置与密钥生成设备20的硬件配置基本相同，因此省略加密设备30和接收设备40的硬件配置的描述。

以上已经描述了能够实施根据本实施例的密钥生成设备20、加密设备30和接收设备40的功能的硬件配置的示例。每个上述组件可以由通用构件构成，或者可以由专用于该组件功能的硬件构成。因此，可以根据关于本实施例的每种实施场合的技术水平(technical level)，以适当的方式改变将要使用的硬件配置。另外，显而易见，上述硬件配置仅是示例，并且本发明不限于此。例如，HDD 207和存储器(安全模块)211可以由相同的存储设备构成。另外，依据使用方式，省略了总线213、输入/输出接口215等的配置是可用的。在下文中，详细描述通过上述硬件配置可以实现的加密密钥生成方法。

关于基础技术的说明

在提供本发明的优选实施例的详细描述之前，首先描述构成用于实现该实施例的基础的技术问题。注意，通过对于下面所述基础技术的改善，以可取得更显著效果的方式形成了本实施例。因此，与该改善有关的技术是形成本实施例特征的真正的部分。即，应该注意，尽管本实施例遵循此处所述技术问题的基本构思，但是，本实施例真正的实质总结在改善部分中，本实施例的配置明显不同于基础技术的配置，另外，在本实施例与基础技术之间就优点方面进行了划界。

在使用公钥的传统内容传递方法中，中心判定内容传递系统的系统参数k，并且基于该系统参数k形成k阶中心保密多项式。然后，通过使用该k阶保密多项式，中心生成公钥PK以及对于客户i唯一的保密密钥d_i(在下文中，称为私钥)。中心公布公钥PK，并且通过使用安全通信信道将私钥传递给客户i。另外，在内容的传递时，中心传递加密文本C以及首标h。由于首标h是通过使用公钥PK生成的，因此任何传递者均可以生成首标h。在使用公钥的传统内容传递方法中，客户i应该仅持有一个保密密钥d_i。另外，由于公布了公钥PK，因此非中心传递者能够传递内容。

然而，为了生成私钥，使用基于保密参数k的k阶多项式。在k+1或更多个客户相互合谋的情况下，存在不能保持系统的安全性的合谋问题。

因此，上述非专利文献1中建议了公钥内容传递方法，其中，即使在任何数量的客户彼此合谋的情况下，也可以保持系统的安全性。

在Boneh、Gentry、Waters等人的非专利文献1所述的方法中，通过使用称作双线性群的一种循环乘法群(而不使用k阶多项式)生成私钥，并且将对于群中客户i唯一的元素提供为私钥d_i。另外，通过由每个客户使用用于首标h的生成以及会话密钥s的获取的、称作双线性映射的运算，可以解决使用公钥的传统内容传递系统中一直以来存在的巨大问题：合谋问题。

在非专利文献1中，作为基本方法，首先描述用于将一组用户处理为一个群的方法。在下文中，参考图3描述该基本方法。在该基本方法中，中心51生成双线性群的生成元g与中心保密数α，并且通过使用它们来向客户i(i＝1、……、n)分配以下参数：

[算式5]

$g_i=g^{{\alpha }^i}$

另外，生成用于将一组客户55处理为一个群的参数υ＝g^γ，并且将生成元g和参数υ公开为公钥PK＝(g、g₁、……、g_n、g_n+2、……、g_2n、υ)。此外，对于客户i，通过使用分配给i的以下参数：

[算式6]

$g_i=g^{{\alpha }^i}$

经由安全一对一通信信道53预先提供以下私钥：

[算式7]

$d_i=g_i^{\gamma }$

传递者根据分配给所有非排除客户的以下参数：

[算式8]

$g_i=g^{{\alpha }^i}$

以及用于将一组客户处理为一个群的参数υ＝g^γ，从公钥PK＝(g、g₁、……、g_n、g_n+2、……、g_2n、υ)创建与所有非排除客户相对应的公用首标元素。然后，传递者通过使用包含公用首标元素的首标元素以及在会话密钥生成时使用的随机数元素，生成首标h，并且连同加密文本C一起传递该首标h。

如上所述，在基本方法中，通过将一组客户处理为一个群，并且形成与该群对应的首标元素，最小化了首标h的大小(在下文中，称为首标大小)。

然而，由于将所有的客户处理为一个群，因此需要将不同的参数g₁、……、gn分配给各客户。因此，公钥的大小等于或大于客户数量的两倍。另外，在每个客户均从首标h获取会话密钥s的情况下，需要计算与除了客户之外的所有非排除客户相对应的参数g₁、……、g_n的乘积。因此，如果表示客户的总数的值n非常大，那么强加给客户关于计算量方面的负担非常大。在实际的内容传递中，需要将内容经由付费广播、诸如DVD、因特网之类的物理介质等传递至巨大数量的客户。因此，考虑到上述问题，可以说实际中不能使用该基本方法。

作为用于解决上述问题的方法，在非专利文献1中建议了一般化方法，其中，可以通过将一组客户分组为多个子群来降低公钥的大小。在该一般化方法中，一组客户被分组为多个子群，并且对每个分组后的子群执行如在所述基本方法中那样的运算。因此，增加了需要为各个子群生成的不同首标元素以及首标大小。然而，可以降低公钥的大小。另外，每个客户需要计算分配给属于分组后子群的各客户的参数的乘积。然而，与所述基本方法相比，由于将一组客户分组为子群，因而可以降低需要计算的参数数量。因此，可以解决所述基本方法的问题。

在下文中，参考图4～8详细描述非专利文献1中所述的一般化方法。首先定义说明上述一般化方法所需的符号，以及描述非专利文献1中使用的双线性群以及双线性映射。然后，通过利用这些定义，描述非专利文献1中所述一般化的细节、问题等。

<符号的定义>

用于说明非专利文献1中所述一般化方法的每个符号如以下所列那样来定义。

n：客户的总数

A：当将客户群分组为多个子群时的分组数

B：属于分组后的子群的客户数

PK：系统的公钥

d_i：第i个客户的私钥

r：排除客户的总数

p：用作双线性群的阶的大素数

G、G₁：具有阶p的双线性群

g：G的生成元

M：未加密的内容(纯文本)

s：会话密钥

C：通过使用会话密钥s对纯文本M加密得到的加密文本

E_S(M)：通过使用密钥s对纯文本M的加密

D_S(C)：通过使用密钥s对加密文本C的解密

e(u、v)：关于双线性群G的两个元素u和v的双线性映射。

<双线性群的双线性映射>

现在描述非专利文献1中使用的双线性群的双线性映射。双线性映射e(u、v)是将循环乘法群G的两个元素u和v映射至循环乘法群G₁的元素并且满足以下所列性质的映射。

1.双线性性质：对于任意u、v∈G以及a、b∈Z，满足e(u^a，v^b)＝e(u，v)^ab。

2.非退化(Non-degenerate)性质：e(g，g)≠1。

现在详细描述与非专利文献1中所述一般化方法有关的每个步骤。该一般化方法主要由三个阶段构成，即，密钥生成阶段、加密阶段以及解密阶段。密钥生成阶段仅由中心在系统的配置之时执行一次。加密阶段和解密阶段分别由传递者和客户每次进行传递时执行。在下文中描述每个阶段。

<密钥生成阶段>

在下文中，参考图4和图5描述密钥生成阶段。图4是用于说明非专利文献1的一般化方法中的密钥生成阶段的说明图。图5是非专利文献1的一般化方法中的密钥生成阶段的流程图。

中心51根据下面所述过程生成各客户55的私钥以及公钥。首先，中心51随机地选择大素数p，并且判定将所选p作为其阶的双线性群G(步骤S11)。

然后，中心51各自随机地选择在步骤S11中确定的双线性群G的生成元g以及中心保密随机数α(α是整数)(步骤S13)。

接下来，中心51判定属于分组后子群的客户数B，并且使用以下表达式确定与计算相一致的分组数A。然后，中心51将客户分组为A个子群(步骤S15)。

[算式9]

  ……(表达式1)

这里，上面表达式右侧指示的符号是表示“大于等于(n/B)的最小整数”的符号。

然后，中心51如以下那样为i(i＝1、……、B、B+2、……、2B)计算叶密钥gi(步骤S17)。

[算式10]

$g_i=g^{{\left(\alpha \right)}^i}$             ……(表达式2)

接下来，中心51随机选择与子群数A相对应的A个随机数γ(γ₁、……、γ_A，γ是整数)。然后，如以下那样计算属于双线性群G的v₁……、v_A(步骤S19)。

[算式11]

$v_i=g^{{\gamma }_i}\in G(i=1,......,A)$   ……(表达式3)

然后，中心51基于在上述步骤S13中选择的g、在步骤S17中计算出的g_i以及在步骤S19中计算出的v_i，确定下面所示的公钥PK，并且公布该公钥PK(步骤S21)。

PK＝(g、g₁、……、g_B、g_B+2、……、g_2B、v₁、……、v_A)……(表达式4)

然后，中心51选择与客户i属于的子群S_a(a是大于等于i/B的最小整数)以及作为子群中客户i的索引(index)的b＝imodB(这里，i是大于等于1并且小于等于B的整数)相对应的参数g_b和γ_a，并且为下面表达式中计算出的客户i生成私钥d_i(步骤S23)。

[算式12]

$d_i=g_b^{{\gamma }_a}={v_a}^{{\alpha }^b}\in G$         ……(表达式5)

然后，中心51经由安全的一对一通信信道53将如上述那样生成的私钥d_i秘密地传递至各客户i(步骤S23)。

如上所述，在非专利文献1的密钥生成阶段中，在步骤S15中，中心51将由n个客户构成的一组客户分组为每一个均包含B个客户的A个子群。然后，在步骤S11、步骤S13、步骤S17以及步骤S19中，中心51设置内容传递系统管理所需的各种参数。

另外，在步骤S21中，中心51通过使用已生成的参数来生成公钥PK。在随后的步骤S23中，中心51基于表示在步骤S15中确定的子群分组数的A以及表示属于一个子群的客户数的B，为各客户生成私钥。

在这种场合下，对于每个客户，基于分配给该客户的客户唯一编号，确定该客户所属子群以及该子群中的索引。如上所述，由于在私钥生成中不使用k阶多项式，因此即使任意数量的客户相互合谋，也不可执行对于另一客户的私钥伪造(fabrication)以及允许排除用户从首标获取会话密钥的未授权密钥的形成。

<加密阶段>

在下文中，参考图6和图7描述加密阶段。图6是用于说明非专利文献1一般化方法中的加密阶段的说明图。图7是非专利文献1的一般化方法中的加密阶段的流程图。

传递者57根据以下所述过程对将要传递的内容加密，并且将经加密的内容经由广播通信信道59共同传递给非客户61以及客户63。

首先，传递者57随机选择整数t，并且如下面那样计算会话密钥s(步骤S31)。

s＝e(g_B+1，g)¹＝e(g_B1，g₁)¹     ……(表达式6)

然后，传递者57确定可对内容解密的用户组S，并且对于l＝1、……、A，如下面那样确定各子群(步骤S33)。

[算式13]

${\hat{S}}_l=S\cap \{(l-1)B+1,......,\mathrm{lB}\}$         ……(表达式7)

$S_l=\{x-\mathrm{lB}+B|x\in {\hat{S}}_l\}\subseteq \{l,......,B\}$      ……(表达式8)

这里，下标1是表示子群的参数。以上表达式7表示的组是参数1表示的子群中所包含的客户和非客户的组。以上表达式8表示的组是表示参数1所表示的子群中的客户的位置的组。

然后，传递者57如下面那样形成客户63计算会话密钥s所需的首标h(步骤S35)。

[算式14]

$h=(g^t,{(v_1·\underset{j\in S_1}{\Pi }{g}_{B+1-j})}^t,...,{(v_A·\underset{j\in S_A}{\Pi }{g}_{B+1-j})}^t)\in G^{A+1}$       ……(表达式9)

接下来，传递者57基于步骤S31中计算出的会话密钥s，如表达式10所示那样加密待传送的内容。然后，传递者57经由广播通信信道59，连同关于在步骤S33中确定的组S信息以及在步骤S35中计算出的首标h，传送经加密的内容C，而不管是非客户61还是客户63(步骤S37)。

C＝E_S(M)          ……(表达式10)

如上所述，在传递之时，在加密阶段步骤S31中生成会话密钥之后，传递者57在步骤S33中确定可以对属于每个子群的内容进行解密的一组客户。然后，在步骤S35中，传递者57创建包含与各子群对应的元素的首标。这里，首标h的每个元素仅由与可在每个子群中执行解密的客户相对应的参数g_b形成，而不包含与排除客户对应的g_b。因此，在稍后所述解密之时，可以实现非客户(non-customer)的排除。

<解密阶段>

在下文中，参考图8描述解密阶段。图8是非专利文献1一般化方法中的解密阶段的流程图。

接收到经加密内容等的传递的客户i根据下面所述过程，对经加密的内容执行解密处理。

首先，客户63检查传递者传递的组S中是否包含其自身索引i(步骤S51)。在组S中不包含其自身索引i的情况下，客户63判定该客户63是被排除的，并且终止解密处理。在组S中包含其自身索引i的情况下，客户63继续执行以下所述处理。

接下来，客户63从所传送的首标h中选择与客户63属于的子群S_a相对应的首标元素，并且计算会话密钥s(步骤S53)。即，如h＝(C₀、C₁、……、C_A)所表示，首标h由与各子群对应的首标元素构成。客户63基于该首标元素，如以下计算那样，选择与客户63属于的子群S_a相对应的元素C₀和C_a，并且获取会话密钥s。

[算式15]

$s=\frac{e(g_b,C_a)}{e(d_i·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b},C_0)}$        ……(表达式11-1)

$=\frac{e(g_b,{(v_a·\underset{j\in S_a}{\Pi }{g}_{B+1-j})}^t)}{e({v_a}^{\left({\alpha }^b\right)}·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b},g^t)}$      ……(表达式11-2)

$=\frac{e(g_b,{g_{B+1-b}}^t)·e(g_b,{(v_a·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j})}^t)}{e({v_a}^{\left({\alpha }^b\right)}·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b},g^t)}$ ……(表达式11-3)

$=\frac{e{(g,g_{B+1})}^t·e(g^t,{({v_a}^{\left({\alpha }^b\right)}·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b})}^t)}{e({v_a}^{\left({\alpha }^b\right)}·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b},g^t)}$……(表达式11-4)

$=e{(g,g_{B+1})}^t$              ……(表达式11-5)

从以上表达式11-5以及表达式6中可清楚地看到，通过使用从传递者57传送的首标h、公钥PK、以及客户63自己持有的私钥d_i，客户63能够计算与传递者57为加密所使用的内容密钥s相同的一个。

然后，客户63通过使用上面步骤S53中计算出的会话密钥s，将已传递的经加密的内容C解密为纯文本M(步骤S55)。

M＝D_S(C)     ……(表达式12)

如上所述，在解密的时候，客户63首先在步骤S51中检查该客户63是否是被排除的。在该客户63是否是被排除的情况下，由于客户63因为稍后描述的原因而不可获取会话密钥s，因此客户63终止解密处理。根据步骤S51的判定知道其未被排除的客户从已传送的首标中提取与该客户所属子群相对应的首标元素，并且在步骤S53中，基于该首标元素、该客户的私钥以及公钥，通过使用表达式11-1～11-5所示的双线性映射来执行解密运算，从而可以获取会话密钥。然后，通过使用计算出的会话密钥s，客户执行加密文本的

解密。

这里，即使排除客户通过使用表达式11-1～11-5所示的双线性映射来执行解密运算，由于与其自身g_b对应的值g_B+1-b未包含在步骤S53中的表达式11-2的以下部分之中：

[算式16]

${(v_a·\underset{j\in S_a}{\Pi }{g}_{B+1-j})}^t$        ......(表达式13)

因此由于作为非专利文献1中安全性基础的BDHEP(Bilinear Diffie-HellmanExponential Problem，双线性Diffie-Hellman指数问题)的困难，因而不可实现至表达式11-3的转换。因此，不能计算出正确的会话密钥s。

如上所述，非专利文献1的方法解决了使用k阶多项式的传统公钥内容传递方法中一直以来存在的问题：合谋问题。另外，由于中心在密钥加密阶段的步骤S15中预先将一组客户分组为A个子群，因此可以将传递者需要生成的首标配置为总具有A+1个元素。因此，无论排除客户的数量如何，均可以将首标大小保持恒定。

如上所述，在非专利文献1的方法中，必须总是传送具有恒定大小的首标。因此，在不存在排除客户或存在少数排除客户的情况下，存在不可实现高效内容传递的问题。在实际的内容传递系统中，客户数量经常是很大的值。因此，相对于客户的总数，排除客户的数量经常是很小的值。另外，如果排除客户的数量很大，那么内容传递系统自身可能会崩溃。因此，作为内容传递系统，在不存在排除客户或排除客户的数量相对于客户的总数保持很小的情况下，需要高效地传递内容。

然而，如上所述，非专利文献1中难于满足这种条件。此外，在非专利文献1中，为了在解密阶段的步骤S53中执行使用表达式11-1中双线性映射的运算，如以下表达式14中所示那样，需要预先计算分配给客户所属子群内存在的非排除客户的参数与该客户所持有的私钥的乘积。

[算式17]

$d_i·\underset{j\ne b}{\underset{j\in S_a}{\Pi }}{g}_{B+1-j+b}$     ......(表达式14)

这里，在由PAIR表示使用双线性映射的运算、由INV表示关于双线性群G₁的逆运算、由MUL表示关于双线性群G的乘法、而由r_a表示客户i所属子群S_a中排除客户的数量的情况下，可以将客户在解密阶段需要执行的运算的计算量表示为“2PAIR+INV+(B-1-r_a)MUL”。

如据此清楚看到的那样，在属于分组后子群的客户的数量B很大的情况下或者客户所属子群中排除客户的数量r_a很小的情况下，存在每个客户在解密时需要执行的计算量增大的问题。

如上所述，即使在使用非专利文献1的一般化方法的情况下，当一组客户的分组数增多时，也可以减小每个客户在内容解密时执行的计算量。然而，增大了首标大小。另外，相反，当一组客户的分组数减少时，可以减小首标大小。然而，存在计算量增大的问题。另外，即使在排除客户的数量很少的情况下，也总是需要传递具有恒定大小的首标h。因此，在实际非常可能发生的情形下(诸如，不存在排除客户或排除客户的数量相对于客户的总数的百分比很小的情况下)存在不能减小首标大小以及内容传递时数据冗余度增大的问题。

因此，为了解决上述问题，本申请的发明人在已专心致志于认真研究之后，开发了如下面所述那样的根据本发明实施例的加密密钥传递系统。在根据本实施例的密钥生成设备中，通过配置向非专利文献1的方法添加某些参数的逻辑树，即使在排除客户的数量很少的情况下，与专利文献1中所述的方法相比，也可以减小首标大小。另外，通过提供这种配置，可以将客户在解密时需要执行的运算的计算量降低至等效量或更低。因此，可以实现高效内容传递。

本实施例的描述

在下文中，根据上述基础技术，详细描述根据本实施例的密钥生成设备、加密设备和接收设备。根据本实施例的密钥生成设备20通过采用非专利文献1的方法构造逻辑树。与非专利文献1的方法相比，根据本实施例的密钥生成设备20通过逻辑树的使用实现了在不存在排除客户或排除客户的数量很少的情况下的高效内容传递。

首先参考图9描述根据本实施例的密钥生成设备20的配置。图9是示出根据本实施例的密钥生成设备20的配置的框图。

例如，密钥生成设备20包含树结构构造单元231、随机数确定单元233、叶密钥分配单元235、参数分配单元237、密钥计算单元239、存储单元241以及传递单元252。

树结构构造单元231构造作为根据本实施例的密钥生成设备的重要元素的逻辑树。即，树结构构造单元231分级地构造Y元树，其中，将n个目标接收设备分配给树叶，并且由(log_Yn)表示高度。此外，形成每一个均具有Y元树的子群，在该Y元树中，将树叶和根之间存在的每个中间节点定义为父节点。即，通过树结构构造单元231，Y个分支总是从一个节点向下生成的Y元树结构分级地层叠。当浏览所构造的整个分级Y元树结构时，在最上层(在下文中，称为第0层)仅存在一个根，并且在该根的下面，将该根作为父节点的Y个子节点构造为第一层。另外，在第二层中，进一步存在将第一层中存在的Y个子节点作为父节点的Y²个子节点。通过重复这种结构，在最底层(即，第log_Yn层)中总共存在n个树叶。

这里，在一个分支从一个节点向下生长并且在该分支的末端存在一个节点的情况下，将上方节点相对地称作父节点，而将下方节点相对地称作子节点。关于父节点和子节点的这种概念是基于相对思想的。例如，在通过分支上下链接三个节点的情况下，如果将最上方的节点称为父节点，那么位于中间位置的节点称为子节点。另外，当关注于最下方节点时，对于位于用作父节点的中间位置的节点来说，最下方节点用作子节点。

另外，在分级的树结构中，将最上层中存在的根与最下层中存在的n个树叶之间存在的每个节点称作中间节点。

随机数确定单元233确定根据本实施例的密钥生成设备以及双线性群所使用的各种随机数。即，随机数确定单元233随机地选择素数p，并且确定将素数p作为其阶的双线性群G。另外，随机数确定单元233随机地选择表示G的生成元的g，并且随机地选择表示保密随机数的整数α。

叶密钥分配单元235向树结构构造单元231构造的分级Y元树结构中的n个终端树叶以及不是树叶和根的所有中间节点分配叶密钥g_y。

参数分配单元237向树结构构造单元231构造的分级Y元树结构中的除了n个终端树叶之外的所有节点(即，最上层中的根以及在该根和树叶之间存在的所有中间节点)分配任意的参数ν_x，y。这里，每个x和y是表示节点位置的下标，x表示层，而y表示该节点在层x中的位置。

密钥计算单元239基于双线性群G以及随机数确定单元233确定的随机数、叶密钥分配单元235分配的叶密钥、参数分配单元237分配的参数等来计算公钥和私钥。

例如，存储单元241包含树结构存储部分243、随机数存储部分245、叶密钥存储部分247、参数存储部分249、密钥存储部分251等。在这些存储部分中存储着每个处理单元执行的、在处理的中间所需的变量和计算结果或者根据该处理获得的结果。诸如树结构构造单元231、随机数确定单元233、叶密钥分配单元235、参数分配单元237以及密钥计算单元239之类的各处理单元能够自由地将数据写至存储单元241以及从存储单元241读取数据。

另外，可以将存储单元241中的各种数据存储在不同于上述存储部分243、245、247、249以及251的部分中。注意，虽然图9中示出了各种存储部分独立地存在于存储单元241之内的状态，但是各种存储部分并不是必须单独存在，而是可以将各种数据作为一个整体存储在存储部分中。另外，可以使用配有安全模块的存储介质作为存储单元241。

根据本实施例的密钥生成设备中的传递单元252例如包括传输部分253和公钥公布部分255。传输部分253向每个接收设备传送由密钥计算单元239计算出的且存储在密钥存储部分251中的私钥。另外，公钥公布部分255向每个接收设备公布由密钥计算单元239计算出的且存储在密钥存储部分251中的公钥。

现在参考图10描述根据本实施例的加密设备30的配置。图10是示出根据本实施例的加密设备30的配置的框图。

如图10中所示，加密设备30包括例如接收单元301、存储单元303、排除接收设备识别单元305、会话密钥确定单元307、内容存储单元313、加密单元315以及内容传输单元317。

接收单元301接收密钥生成设备20生成并公布的公钥。另外，接收单元301能够进一步接收密钥生成设备20生成的素数p以及作为识别排除接收设备的信息的、关于非排除接收设备的组S的信息和公钥。

存储单元303例如存储密钥生成设备20生成的公钥。另外，存储单元303能够存储关于素数p的信息、关于非排除接收设备的信息等和公钥。

排除接收设备识别单元305在经由通信网络12连接至加密设备30的多个接收设备40之中识别对其取消了内容的传递的排除接收设备，并且确定非排除接收设备的组S。在确定组S的时候，排除接收设备识别单元305能够查阅存储单元303中存储的各种数据。

会话密钥确定单元307确定用于待传递内容的加密的会话密钥。会话密钥确定单元307可进一步包含例如首标元素计算部分309以及首标信息生成部分311。

在确定会话密钥s的时候，会话密钥确定单元307随机地选择整数t，并且通过使用已公布的公钥来执行双线性映射的运算。

首标元素计算部分309标记如下路径中存在的所有各节点，所述路径是：在密钥生成设备20构造的分级树结构中从对其分配了排除接收设备的树叶延伸至根的路径；并且首标元素计算部分309基于分配给已标记节点的参数以及分配给将所述已标识节点用作其父节点的中间节点的叶密钥来计算首标元素。

首标信息生成部分311基于首标元素计算部分309得到的首标元素以及公钥来生成首标信息。

内容存储单元313存储未加密的内容。另外，内容存储单元313可存储从诸如CD(光盘)、DVD(数字多功能盘)或存储卡之类的介质获取的内容。这里，上述内容可以是任何内容数据，例如，通过移动图像或静态图像所构成的视频内容(诸如电影、电视节目、视频节目或图)、音频内容(诸如音乐、演讲或无线电节目)、游戏内容、文献内容或软件。视频内容可包含音频数据和视频数据。

加密单元315从内容存储单元313选择待传递的内容，并且通过使用会话密钥确定单元307计算出的会话密钥s来对该内容加密。

内容传输单元317经由通信网络12向每个接收设备传送加密单元315加密的已加密内容、首标信息生成部分311确定的首标以及排除接收设备识别单元305识别的组S。

现在，参考图11描述根据本实施例的接收设备40的配置。图11是示出接收设备40的配置的框图。

如图11中所示，接收设备40例如包含接收单元401、存储单元403、确定单元405以及解密单元407。

接收单元401接收密钥生成设备20生成的私钥。另外，接收单元401能够进一步接收密钥生成设备20生成的公钥以及作为识别排除接收设备的信息的、关于非排除接收设备的组S的信息和私钥。另外，接收单元401还能够接收加密设备30加密的内容。

存储单元403例如存储密钥生成设备20生成的公钥以及私钥。另外，存储单元403能够存储关于非排除接收设备的组S的信息以及关于已传递的经加密内容、经解密内容等的内容信息和加密密钥。

确定单元405确定接收到的组S中是否包含接收设备自身。根据确定单元405的确定结果，解密单元407对已加密的内容执行解密处理。

解密单元407通过使用接收单元401接收到的首标h以及存储在存储单元403中的公钥和私钥，计算已加密内容的解密所需的会话密钥s。在计算出会话密钥s之后，解密单元407继续执行已加密内容的解密。

以上已经描述了根据本实施例的密钥生成设备20、加密设备30以及接收设备40的功能的示例。上述每个组件均可以通过使用通用构件或电路来构成，或通过该组件功能所专用的硬件来构成。另外，各组件的所有功能均可由CPU等执行。因此，根据本实施例实施时的技术水平(level)，可以以适当的方式改变将要使用的配置。

如非专利文献中那样，根据本实施例的加密密钥传递系统10由三个阶段构成，即，密钥生成阶段、加密阶段和解密阶段。密钥生成阶段仅由中心在系统配置时执行一次。另外，加密阶段和解密阶段分别由传递者和客户每次进行传递时执行。注意，如基础技术的描述中那样定义根据本实施例的加密密钥传递系统10的说明所使用的各符号及运算。在下文中，首先给出本实施例中配置的逻辑树的定义和描述。然后详细描述每个阶段。

<逻辑树的结构和定义>

首先给出对于根据本实施例的密钥生成设备20的说明所需的逻辑树的描述和定义。在根据本实施例的密钥生成设备20中，通过将每个客户分配给树叶并且将非专利文献1中客户的分组分配给逻辑树，实现了高效的内容传递。该逻辑树由根据本实施例的密钥生成设备20中的树结构构造单元231来构造。

注意，为了简化，在本实施例中使用了Y元树。另外，由于需要将所有的客户都分配给树叶，因此假设客户的总数n是可表示为Y的幂的值。然而，在实际内容传递中经常发生不能将n表示为Y的幂的情况。尽管如此，通过预先准备其数量(其远大于n)可表示为Y的幂的树叶，可容易地处理这种情况。在下文中关于逻辑树的结构给出每个定义。

对于本实施例中使用的Y元树，由n表示树叶的数量。因此，假设由H表示除了根之外的Y元树的高度，得到H＝log_Yn。另外，假设由N表示除了树叶之外的节点的总数，得到N＝(n-1)/(Y-1)。因此，除了根之外，Y元树中存在H层。这里，将这些层定义为Layer(层)。即，以将根的一组子节点定义为Layer1以及将Layer1中所有节点的一组子节点(即，该根的孙节点)定义为Layer2的形式，将Y元树的各层定义为Layer x(x＝0、……、H)。这里，x是表示层的下标。另外，通过假设将包含在Layer x中的各个节点的索引表示为节点索引，给出定义(x，y)(y＝1、……、Y^X)。这里，根是Layer0中的节点，根的索引是(0，1)。

作为上述定义的Y元树的示例，在图12中示出客户数n为9且分支数Y为3的情况。

由于客户数n为9，因此将除了根之外的三叉树(ternary tree)的高度表示为log₃9＝2。因此在该三叉树中存在着包含该根的三层。即，将包含根的层501定义为Layer0，并且将包含作为根的子节点的三个节点的层503定义为Layer1。将Layer1中存在的三个节点单独地用作其父节点情况下的子节点的层505定义为Layer2。由于根据Layer1中存在的三个节点中的每一个都形成三个子节点，因此在Layer2中总共存在9个树叶。

另外，除了树叶之外的节点数N(即，根的数量与中间节点的数量之和)被表示为(9-1)/(3-1)＝4。

例如，分配给包含树叶的各节点的节点索引是：对于根的(0，1)，以及对于Layer1中从左端起的三个节点的(1，1)、(1，2)和(1，3)。另外，将节点索引(2，1)、(2，2)、……、(2，9)提供给Layer2中从左端起单独的9个节点(即树叶)。

另外，在根据本实施例的密钥生成设备20中，将接收设备40(即，用于内容传递的客户507)分配给树叶。即，分别将客户1(507A)、客户2(507B)、……、客户9(507I)分配给Layer2中的树叶(2，1)、(2，2)、……、(2，9)。

现在，在下文中通过使用逻辑树的上述定义给出根据本实施例的加密密钥传递系统的具体描述。

<密钥生成设备20的运算：加密密钥生成阶段>

中心操作该中心拥有的密钥生成设备20，并且根据以下过程为各客户生成公钥和私钥。在下文中，参考图12、图13和图14详细描述根据本实施例的密钥生成设备20的操作。图13是用于说明密钥生成设备20的密钥生成的概况的说明图。图14是密钥生成设备20的加密密钥生成阶段的流程图。

首先，密钥生成设备20的随机数确定单元233随机地选择素数p(其为很大的值)，并且确定将所选择的p作为其阶的双线性群G(步骤S101)。这里，很大值的素数p意味着具有很大数字的素数。通过选择具有对于其离散算法问题不易求解的大量数字的素数，随机数确定单元233确保了根据本实施例的加密密钥的安全。

然后，随机数确定单元233随机地选择双线性群G的生成元g，以及中心保密随机数α(α是整数)(步骤S103)。

与素数p、双线性群G、生成元g以及随机数α有关的数据被存储在例如存储单元241内的随机数存储单元245中，并且由叶密钥分配单元235、参数分配单元237、加密密钥计算单元239等查阅。

然后，密钥生成设备20的树结构构造单元231确定属于分组后子群的客户数Y。在根据以下计算确定了分组数X之后，树结构构造单元231将客户分组为X个子群。此外，树结构构造单元231构造将每一个客户都作为树叶来分配的Y元树(步骤S105)。这里，以下表达式101内的n表示客户的总数。

[算式18]

      ……(表达式101)

例如，如图12中所示，在客户的总数n为9并且Y＝3(即，构造三叉数)的情况下，根据表达式101，分组数X为3。

树结构构造单元231使得将如上所述那样构造的Y元树结构存储在存储单元241内的树结构存储部分243中。

接下来，密钥生成设备20的叶密钥分配单元235如以下那样对i(i＝1、……、Y、Y+2、……、2Y)计算叶密钥g_i(步骤S107)。

[算式19]

$g_i=g^{{\left(\alpha \right)}^i}$       ……(表达式102)

从上面的表达式102可清楚地看到，对于叶密钥g_i的计算，使用了随机数确定单元233确定的生成元g以及中心保密随机数α。因此，叶密钥分配单元235访问存储单元241内的随机数存储部分245以读取数据。在计算出叶密钥之后，叶密钥部分单元235将计算出的叶密钥g_i存储在存储单元241内的叶密钥存储部分247中。

注意，在步骤S107中，不仅计算出了Y个叶密钥g_i(其中，Y表示属于子群的客户数)，而且通过将i变化到2Y(除了Y+1)计算出了叶密钥g_i。不执行g_Y+1的计算的原因是为了确保根据本实施例的加密密钥传递系统10的安全。另外，这是由于从g_Y+2至g_2Y的叶密钥g_i是在稍后所述解密阶段中执行解密所需要的。

然后，加密密钥创建设备20的参数分配单元237随机地选择与除了树叶之外的所有节点(x，y)相对应的随机数γ_x，y(γ_x，y是整数)。然后，参数分配单元237如下面那样计算参数ν_x，y，并且将参数ν_x，y分配给Y元树的除了树叶之外的各节点(步骤S109)。这里，x＝0、……、H-1(H是Y元树结构的高度)，而y＝1、……、Y^X。

[算式20]

$v_{x,y}=g^{{\gamma }_{x,y}}\in G$       ……(表达式103)

例如，如图12中所示，在对九个客户构造三叉树结构的情况下，由于三叉树结构的高度H是2，因此x是0或1。另外，y是1、2或3。即，在图12的情况下，参数分配单元237一共分配了四个参数ν_x，y：ν_0，1、ν_1，1、ν_1，2和ν_1，3。因此，对于γ_x，y，同样随机地选择了四个整数。基于如上述那样确定的值，根据表达式103将参数分配给各节点。

另外，将参数分配单元237计算出的参数ν_x，y、节点参数γ_x，y等存储在存储单元241内的参数存储部分249中。

然后，叶密钥分配单元235将g_x，y分配给除了根之外的所有节点(步骤S111)。这里，y＝1、……、Y^X，而g_x，y表示由g₁、……、g_Y构成的组{g₁、……、g_Y}元素。如上所述，叶密钥分配单元235具有计算叶密钥g_y的功能以及将计算出的叶密钥分配给除了根之外的所有节点的功能。分配结果与树结构相关联地存储在存储单元241内的叶密钥存储部分247中。

作为示例，考虑图12中所示的情况。在这种情况下，在Layer1(503)中存在根用作其父节点的三个子节点以形成子群。因此，将g₁作为g_1，1分配给节点(1，1)，将g₂作为g_1，2分配给节点(1，2)，并且将g₃作为g_1，3分配给节点(1，3)。

另外，当考虑Layer2(505)时，共存在三个子群：即，节点(1，1)用作其父节点的三个节点(2，1)、(2，2)和(2，3)所构成的子群，节点(1，2)用作其父节点的三个节点(2，4)、(2，5)和(2，6)所构成的子群，以及节点(1，3)用作其父节点的三个节点(2，7)、(2，8)和(2，9)所构成的子群。在这种情况下，将g₁作为g_2，1分配给节点(2，1)，将g₂作为g_2，2分配给节点(2，2)，并且将g₃作为g_2，3分配给节点(2，3)。类似地，将g₁作为g_2，4分配给节点(2，4)，将g₂作为g_2，5分配给节点(2，5)，并且将g₃作为g_2，6分配给节点(2，6)。另外，将g₁作为g_2，7分配给节点(2，7)，将g₂作为g_2，8分配给节点(2，8)，并且将g₃作为g_2，9分配给节点(2，9)。

然后，密钥生成设备20的密钥计算单元239如以下那样形成公钥，并且经由公钥公布部分255公布公钥PK(步骤S113)。

PK＝(g、g₁、……、g_Y、g_Y+2，……、g_2Y、ν_0，1、……、ν_H-1，X)……(表达式104)

从上面的表达式104可清楚地看到，公钥PK由随机数确定单元233确定的生成元g、叶密钥分配单元235计算出的叶密钥g_i以及参数分配单元237计算出的参数ν_x，y构成。因此，叶密钥计算单元239通过查阅存储单元241内的每个存储部分245、247和249来形成公钥PK。密钥计算单元239将所形成的公钥PK存储在存储单元241内的密钥存储部分251中。公钥公布部分255查阅密钥存储部分251以公布公钥。注意，密钥计算单元239可直接将形成的公钥PK传送至公钥公布部分255。

作为示例，考虑图12中所示的情况。在这种情况下，将(g、g₁、g₂、g₃、g₅、g₆、ν_0，1、ν_1，1、ν_1，2、ν_1，3)公布为公钥PK。

然后，密钥计算单元239为客户i(i＝1、……、n)识别从根延伸至分配给客户i的树叶的路径，并且对于该路径中Layer x中的节点，将客户i的索引设置为i_x。即，i₀＝(0，1)以及i_H＝(H，i)。中心为分配给客户i的除了根之外的所有节点i₁、……、i_H识别分配给这些节点的参数g_ix。另外，中心识别分配给除了树叶之外的所有节点i₀、……、i_H-1的参数γ_ix。并且如下面那样为客户i计算私钥d_i。然后，传输部分253通过使用安全通信信道将私钥d_i传递至客户i(步骤S115)。

[算式21]

$d_i=\{g_{i_1}^{{\gamma }_{i_0}},...,g_{i_H}^{{\gamma }_{i_{H-1}}}\}=\{{v_{i_0}}^{{\alpha }^{i_1}},...,{v_{i_{H-1}}}^{{\alpha }^{i_H}}\}\in G^H$     ……(表达式105)

从表达式105可清楚地看到，基于分配给已识别路径中的节点i_x的叶密钥g_ix以及分配给用作该节点i_x的父节点的节点的参数γ_ix-1来计算私钥d_i的各元素。即，可以说每个私钥d_i都是基于分配给每个节点的叶密钥而计算出的一组密钥。注意，在下文中参考图15详细描述上述步骤S115的具体示例。

注意，当在密钥计算单元239中计算出对于各客户唯一的私钥d_i时，密钥计算单元239将这些私钥存储在存储单元241内的密钥存储部分251中。在传输部分253向每个客户传送私钥d_i的情况下，传输部分253通过查阅存储单元241内的密钥存储部分251来获取必要的信息。另外，密钥计算单元239可直接将生成的私钥传至传输部分253。

现在参考图15举例说明上述步骤S115的具体示例。在图15中，对九个客户构造了三叉树结构。这里，考虑向被分配给树叶(2，3)的客户3传送私钥d₃的情况。

从根(0，1)延伸至表示客户3的树叶(2，3)的路径是从根(0，1)经由中间节点(1，1)延伸至树叶(2，3)的路径。在这种情况下，分别由i₁和i₂表示该路径中除了根(0，1)之外的节点(1，1)和(2，3)。这里，考虑分配给各节点(0，1)、(1，1)和(2，3)的参数。对于节点(0，1)，将γ_0，1分配为γ_i0。对于节点(1，1)，将γ_1，1分配为γ_i1，并且将g_1，1表示的g₁分配为g_i，1。另外，对于树叶(2，3)，将g_2，3表示的g₃分配为g_i2。

根据表达式105，待由客户3持有的私钥d₃是通过将分配给节点(1，1)的叶密钥g1提高至分配给作为节点(1，1)的父节点的根(0，1)的γ_0，1的幂所得到的一组结果，以及通过将分配给树叶(2，3)的叶密钥g3提高至分配给作为树叶(2，3)的父节点的根(1，1)的γ_1，1的幂所得到的一组结果。

如上所述，如图13中所示，关于根据本实施例的密钥生成设备20，中心509拥有的密钥生成设备20选择双线性群G以及各种参数，并且生成公钥PK以及对于客户唯一的私钥d_i。然后，中心509公布公钥PK以及通过使用安全一对一通信信道511向每个客户507传递私钥d_i。

<加密设备30的运算：加密阶段>

现在参考图16和图17详细描述根据本实施例的加密设备30的运算(即，加密阶段)。图16是用于说明加密设备30的加密的概况的说明图。图17是加密设备30的加密的概况的流程图。注意，可以由拥有加密设备30的任意第三方执行下面所述的加密阶段。另外，只要密钥生成设备20的拥有者或接收设备40的拥有者是加密设备30的拥有者，那么即使密钥生成设备20的拥有者或接收设备40的拥有者也能够执行下面的加密阶段。

在执行下面描述的加密阶段之前，加密设备30的接收单元301接收密钥生成设备20生成和公布的公钥、素数p、关于树结构的信息以及关于非排除接收设备的组S的信息中的每一个。接收设备301接收到的这种信息存储在存储单元303中。存储在存储单元303中的这种信息可随意地由加密设备30的每个处理单元读取。

首先，排除接收设备识别单元305标记从分配给期望将其排除的所有客户的树叶延伸至根的路径中的所有节点，并且将非排除客户所使用的、用于根据首标h识别分配给非排除客户的首标元素的节点索引的组S初始化为S＝φ(φ表示空集)(步骤S301)。

然后，会话密钥确定单元307随机地选择任意的整数t，并且如下面中那样计算会话密钥s(步骤S303)。

s＝e(g_Y+1，g)^t＝e(g_Y，g₁)^t　　……(表达式106)

然后，首标元素计算部分309将表示层的参数x设置为-1(步骤S305)。即，步骤S305是初始化表示层的参数x的步骤。

然后，首标元素计算部分309将x替换为x+1以将x的值增大1(步骤S307)。

接下来，首标元素计算部分309将y设置为0以初始化参数(步骤S309)。

然后，首标元素计算部分309将y(其是表示每层中节点的位置的参数)替换为y+1以将y的值增大1(步骤S311)。

接下来，首标元素计算部分309将与节点(x，y)对应的首标元素c_x，y初始化为c_x，y＝0(步骤S313)。

根据下面所述的步骤，首标元素计算部分309执行用于计算首标元素的特定处理。

然后，首标元素计算部分309判定是否标记了节点(x，y)的所有子节点(步骤S315)。作为该判定的结果，在标记了所有子节点的情况下，首标元素计算部分309进入下面所述的步骤S321。同时，在存在未标记子节点的情况下，首标元素计算部分309进入下面所述的步骤S317。

接下来，首标元素计算部分309将一组未标记子节点定义为S_x，y，并且如以下那样计算与属于S_x，y的各元素用作根的子树(子群)的客户相对应的首标元素(步骤S317)。

[算式22]

$c_{x,y}={(v_{x,y}·\underset{j\in S_{x,y}}{\Pi }{g}_{Y+1-j})}^t\in G$      ……(表达式107)

另外，首标元素计算部分309如以下那样设置组S(步骤S317)。

[算式23]

S∪S_x，y……(表达式108)

接下来，首标元素计算部分309标记属于S_x，y的各元素用作根的子树的所有节点(包含树叶)(步骤S319)。

然后，首标元素计算部分309判定当前关注的参数y是否对应于Y^X(步骤S321)。作为该判定的结果，在y是Y^X的情况下，首标元素计算部分309进入下述步骤S323。同时，在y不是Y^X的情况下，首标元素计算部分309返回步骤S311以将参数y增大1。

接下来，首标元素计算部分309判定当前关注的参数x是否是H-1(步骤S323)。作为该判定的结果，在x是H-1的情况下，首标元素计算部分309进入下述步骤S325。同时，在x不是H-1的情况下，首标元素计算部分309返回步骤S307以将参数x增大1。

如上所述，通过重复步骤S307～S323直至满足了步骤S321和步骤S323两者的条件为止，首标元素计算部分309能够计算出首标的生成所需的所有首标元素。

即，由于在对于首标元素的具体计算之前，在步骤S313中将与关注的节点(x，y)相对应的首标元素c_x，y初始化为0，因此在步骤S315中标记了关注的节点(x，y)的所有子节点的情况下，节点(x，y)的首标元素c_x，y被保持为0并被存储。同时，在未标记关注的节点(x，y)的所有子节点的情况下，在步骤S317中将c_x，y替换为新值。因此，c_x，y具有不为0的值。

首标元素计算部分309将通过上述步骤的重复所获得的所有首标元素传给首标信息生成部分311。另外，首标元素计算部分309可将计算出的首标元素存储在存储单元303中。

然后，首标信息生成部分311通过使用生成元g和步骤S303中选择的t来计算g^t。另外，首标信息生成部分311通过仅使用具有非0值的首标元素c_x，y，如以下那样形成首标h(步骤S325)。

h＝(g^t、c_0，1、……、c_H-1，X)(c_x，y≠0)……(表达式109)

在生成首标信息之后，首标信息生成部分311将生成的首标h传给加密单元315。另外，首标信息生成部分311可将生成的h存储在存储单元303中。

然后，加密单元315从存储单元313接收待传递的未加密内容M，并且通过使用会话密钥确定单元307确定的会话密钥s，如下面那样对内容M加密。然后，内容传输单元317将经加密的内容C连同首标信息生成部分311生成的首标h以及节点索引的组S传送至客户(步骤S327)。

C＝E_S(M)……(表达式110)

现在参考图18～图20具体描述根据本实施例的加密阶段。图18～图20是用于具体说明根据本实施例的加密阶段的说明图。在图18～图20中示出了构造三叉树结构并且将九个客户分配给树叶的情况。

在下面的示例中描述期望排除的客户是客户2和客户3的情况。如图18中所示，将树叶(2，2)分配给客户2，并且将树叶(2，3)分配给客户3。在这种情况下，从期望排除的客户2延伸至根的路径是图18中虚线所示的、从树叶(2，2)经由节点(1，1)延伸至根(0，1)的路径。类似地，从期望排除的客户3延伸至根的路径是图18中虚线所示的、从树叶(2，3)经由节点(1，1)延伸至根(0，1)的路径。在这种情况下，排除接收设备识别单元261标记根(0，1)、节点(1，1)、树叶(2，2)和树叶(2，3)。注意在图18中，以使用虚线环绕被标记节点的方式示出了被标记的节点。然后，通过会话密钥确定单元307执行步骤S303，并且确定会话密钥s。

然后，首标元素计算部分309执行步骤S305～S311。作为结果，用0替换参数x，并且用1替换参数y。然后，首标元素计算部分S309执行步骤S313。在这种情况下，将对应于节点(0，1)的首标元素c_0，1初始化为0。然后，首标元素计算部分S309执行步骤S315以确定是否标记了根(0，1)的所有子节点。从图19中可清楚的看到，存在根(0，1)的三个子节点(1，1)、(1，2)和(1，3)，并且节点(1，2)和(1，3)未标记。因此，首标元素计算部分309执行步骤S317。

在图19的情况下，未标记子节点的组S_0，1是{(1，2)、(1，3)}。另外，由于分别将g₂和g₃分配给节点(1，2)和(1，3)，因此将首标元素c_0，1计算为(ν_0，1·g₂·g₁)^t。

然后，首标元素计算部分309执行步骤S319。通过步骤S319，标记了作为节点(1，2)(其为S_0，1的一元素)用作根的子树的所有节点：节点(1，2)、树叶(2，4)、树叶(2，5)以及树叶(2，6)。类似地，对于作为S_0，1的另一元素的节点(1，3)，标记了节点(1，3)、树叶(2，7)、树叶(2，8)以及树叶(2，8)。

由于首标元素计算部分309在步骤S321中的判定是y＝1，因而满足了条件。因此，随后首标元素计算部分309执行步骤S323中的判定。在这种情况下，由于x＝0≠1，因此不满足分支条件。因此，通过设置到x＝1，首标元素计算部分309返回步骤S307以重复处理。

从返回的步骤S307至S311的处理被顺序地再次执行。此时，已经用1替换了x，并且用1替换了y。因此，接下来对节点(1，1)执行类似的处理。

在这种情况下，节点(1，1)的未标记子节点的组S_1，1仅是{(2，1)}。类似地，执行首标元素的计算，并且将(ν_1，1·g₃)^t计算为首标元素c_1，1。然后，由于标记了节点(1，1)用作根的子树的所有节点，因此现在标记了尚未被标记的树叶(2，1)。

结果，标记了包含根和树叶的三叉树结构的所有节点。因此，在步骤S323的判定中，满足了分支条件。

通过上述处理，首标信息生成部分311通过使用具有非0值的首标元素c_x，y(即，c_0，1和c_1，1)，形成了首标h。因此，形成了(g^t，c_0，1，c_1，1)作为首标h。另外，表示能够通过上述处理解密已传递内容的客户的组的S为{(1，2)，(1，3)，(2，1)}。

如上所述，在根据本实施例的加密内容传递块中，传递者513如图16中所示那样通过使用公钥PK以及传递者513选择的随机数t来计算会话密钥s和首标h。同时，传递者513还判定能够解密内容的客户的组S。然后，传递者513经由广播通信信道515传递经加密的内容C、首标h以及组S，而不管是客户507还是非客户517。

<接收设备40的运算：解密阶段>

现在参考图21详细描述根据本实施例的接收设备40的运算(即，解密阶段)。图21是作为接收设备40的密钥处理方法的解密阶段的流程图。

首先，由接收单元401接收经加密内容C、首标h以及组S的接收设备40将信息临时地存在存储单元403中。然后，执行经加密内容C的解密处理。

首先，接收设备40的判定单元405查阅存储在存储单元403中的组S以判定组S中包含的节点是否存在于从分配给接收设备40的树叶至根的各节点之中(步骤S501)。作为判定的结果，在不存在组S中包含的节点的情况下，判定单元405判定接收设备40被排除，并且终止下面所述的解密处理。同时，作为判定的结果，在存在组S中包含的节点的情况下，接收设备40将组S中包含的节点的节点索引设置为(x′，y′)，并且执行下面的步骤S503。

接收设备40的解密单元407在接收单元401接收到的并且在存储单元403中存储的首标h的各元素之中选择与节点(x′，y′)的父节点(x，y)和g^t相对应的首标元素c_x，y(步骤S503)。这里，由下面的表达式表示节点(x′，y′)的父节点(x，y)。

[算式24]

      ……(表达式111)

另外，如下面那样，解密单元407通过使用公钥以及来自于接收设备40的私钥d_i的、与节点(x′，y′)相对应的元素来获取会话密钥s(步骤S503)。

[算式25]

$s=\frac{e(g_{i_{x\prime }},c_{x,y})}{e({g_{i_{x\prime }}}^{{\gamma }_{i_{x\prime }-1}}·\underset{j\ne i_{x\prime }}{\underset{j\in S_{x,y}}{\Pi }}{g}_{Y+1-j+i_{x\prime }},g^t)}$……(表达式112-1)

……(表达式112-2)

……(表达式112-3)

……(表达式112-4)

$=e{(g,g_{Y+1})}^t$……(表达式112-5)

然后，解密单元407通过使用所获取的会话密钥s，对经加密的内容C解密以获得纯文本M(步骤S505)。

M＝D_S(C)……(表达式113)

然后，参考图22具体描述根据本实施例的解密阶段。图22是用于具体说明根据本实施例的解密阶段的说明图。在图22中，示出构造了三叉树结构并且向树叶分配九个客户的情况。

在下面的示例中，假设如下的情况：期望排除的客户是客户2和客户3，并且向客户1～9传递经加密的内容C、首标h以及组S。在下文中详细描述被分配给树叶(2，4)的客户4解密所传递内容的情况。

在图22的情况下，从分配给客户4的树叶(2，4)延伸至根(0，1)的路径中包含的节点是上述的树叶(2，4)、节点(1，2)以及根(0，1)。这里，客户4使用的接收设备40的判定单元405判定接收单元401接收到的关于组S的信息中是否包含上述三个节点。

在图22的情况下，由于客户2和客户3是期望排除的客户，因此组S是{(1，2)，(1，3)，(2，1)}。如据此清楚看到的那样，组S中包含节点(1，2)，该节点(1，2)是向其分配了客户4的树叶(2，4)的父节点。因此，判定单元405判定满足了步骤S501的分支条件。解密单元407继续执行解密处理。

在这种情况下，步骤S503中的节点(x′，y′)对应于节点(1，2)。因此，节点(x′，y′)的父节点(x，y)是根(0，1)。解密单元407选择与节点(0，1)以及g^t相对应的首标元素c_0，1。另外，解密单元407通过使用与ν_0，1有关的元素(其为来自于客户4的私钥d₄的、与节点(0，1)相对应的元素)以及公钥PK来计算会话密钥s。具体地，由下面的表达式表示用于获得会话密钥s的双线性映射。

[算式26]

$s=\frac{e(g_{4_1},c_{\mathrm{0,1}})}{e({g_{4_1}}^{{\gamma }_{4_0}}·\underset{j\ne 4_1}{\underset{j\in S_{\mathrm{0,1}}}{\Pi }}{g}_{Y+1-j+4_1},g^t)}$

以上已详细描述了根据本实施例的加密密钥传递系统10中的三个阶段(密钥生成、加密以及解密)的示例。

注意，可以创建用于促使计算机用作根据上述实施例的密钥生成设备20、加密设备30以及接收设备40的计算机程序。通过将计算机程序存储在计算机中提供的存储单元中并且由计算机中提供的CPU来读取和执行该计算机程序，其促使计算机用作上述的密钥生成设备20、加密设备30以及接收设备40。另外，也可提供具有记录在其上的计算机程序的计算机可读记录介质。例如，该记录介质是磁盘、光盘、磁光盘、闪存等。另外，例如，可以经由网络传递上述计算机程序，而无需使用所述记录介质。

现在，在下文中将根据本实施例的加密密钥传递系统10与作为基础技术的、非专利文献1中所述的内容传递系统相比较。

作为基础技术的、非专利文献1的方法是在使用公钥的内容传递系统中通过使用双线性映射来解决合谋程序的方法。在该方法中，预先将客户分组为多个子群，并且在传递内容时，传递包含依据子群而不同的所有首标元素的首标。因此，即使在排除客户的数量增大的情况下，也可以将首标大小保持恒定。然而，即使在为实际内容传递系统所假设的情况下(诸如不存在排除客户的情况或者排除客户的数量很少的情况)，也总是必须传递具有恒定大小的首标。因此，存在传递效率被降低的问题。

另外，存在另一问题：在属于分组后子群的客户的数量B很大的情况下，或者客户所属子群中的排除客户的数量很少的情况下，客户在解密时需要执行的运算的计算量增大。

同时，在根据本实施例的密钥生成设备中，通过使用基础技术的方法来构造逻辑树并且使得参数的数量略微增加，可以灵活地配置子群。具体地，在不存在排除客户或者排除客户的数量很少的情况下，可以减小所传递首标的大小，并且可以将客户需要执行的运算的计算量减小至小于等于基础技术中所述方法的计算量。在下文中描述基础技术和本实施例之间的主要差异，同时将注意力放在各阶段的差异中。另外，通过使用数值的具体示例，就解密所需的首标大小以及计算量进行比较。

<密钥生成阶段的差异>

首先描述密钥生成阶段的差异。在基础技术的方法中，在步骤S11和步骤S13中设置了各种参数之后，在步骤S15中，客户被分组为每一个均包含B个客户的A个子群。类似地，在本实施例中，在步骤S101和步骤S103中设置了各种参数，并且将客户分组为每一个均包含Y个客户的X个子群。

然而，在本实施例中，在步骤S105中，进一步构造将客户分配给树叶的Y元树结构。因此，在基础技术中，在步骤S19中需要用于为每个子群合并(intergrate)首标元素的A个中心保密γ₁、……、γ_A以及与这些中心保密相对应的A个公共值ν₁、……、ν_A(其中A表示子群的分组数)，而在本实施例中，由于可以为步骤S105中构造的Y元树的除了树叶之外的所有节点形成子群，因此，需要N个值(其中，N表示除了树叶之外的节点总数)。

另外，在基础技术中，客户i仅属于由下面的表达式表示的子群S_a。

[算式27]

因此，中心向客户i秘密地传递私钥：

[算式28]

$d_i=g_b^{{\gamma }_a}={v_a}^{{\alpha }^b}\in G$

然而，在本实施例中，在步骤S105中构造了逻辑树之后，在步骤S109中，该逻辑树的每个节点均可用于子群的重构。因此，客户i需要属于由从分配给客户i的树叶至根的所有节点所构成的多个子群。

因此，在本实施例的步骤S115中，必须为客户i保留多个私钥。如上所述，在密钥生成阶段中，由于在本实施例中构造了逻辑树，因此与基础技术相比较，所需参数的数量略微增加。然而，在不存在排除客户的情况下或者排除客户的数量很少的情况下，与传统技术相比较，可以减小接下来所述的加密阶段中生成的首标的首标大小。

<加密阶段的差异>

接下来描述加密阶段。在基础技术中，在步骤S31中生成会话密钥。然后，在步骤S33中，为各子群选择非排除客户，并且确定分配给各客户的子群中客户索引的组S1(1＝1、……、A)。然后，在步骤S35中，计算仅各子群中非排除客户可通过其获得会话密钥的首标元素，并且配置首标。因此，除非排除了属于子群的所有客户，否则必须计算与所有子群相对应的首标元素。因此，无论排除客户的数量r很大或很小，都将首标大小保持恒定。

同时，在本实施例中，在步骤S301中标记了从分配给排除客户的树叶至根的所有节点，并且将非排除客户通过其从首标h中识别分配给非排除客户的首标元素的一组节点索引设置为S。然后，在步骤S303中，根据如基础技术中那样的过程在步骤S303中生成会话密钥s。在步骤S305～S325中，计算仅分配给未标记节点的客户可通过其获取会话密钥s的首标元素，并且配置首标h。

更详细地，在本实施例的步骤S317中，为属于Layer x的节点之中的未标记节点生成首标元素。这是与基础技术中步骤S35的运算相类似的运算。然而，由于已存在A个子群，因此在基础技术的步骤S35中必须生成A个首标元素，而在本实施例中，仅对特定节点的一组子节点执行步骤S317，并且在步骤S307～S323中重复该处理。

这里，如步骤S315～S319中所示，对于一旦已经生成其首标元素的节点来说，通过标记属于将该节点作为其顶点的子树的所有节点，不需要生成与这些节点相对应的首标元素。因此，出现如下优点：可以将用于包含节点的所有非排除客户的首标元素一起合并在路径中。因此，在排除客户的数量较少的情况下，可以将更大数量的节点合并在一起。因此，可以减小首标尺寸。

<解密阶段的差异>

最后描述解密阶段。在基础技术中，非排除客户在步骤S53中获取与客户属于的子群相对应的首标元素，并且通过使用该首标元素、公钥和私钥来取得会话密钥。同时，在本实施例中，在步骤S503中，非排除客户在从分配给客户的树叶延伸至根的路径中存在的节点之中获取与包含在S中的节点的父节点相对应的首标元素，并且通过使用该首标元素、公钥和私钥来取得会话密钥。

其区别仅在于所使用的相应首标元素和私钥，并且执行如基础技术中那样的运算。然而，客户在基础技术的解密阶段中需要执行的运算的计算量是2PAIR+INV+(B-1-r_a)MUL，而本实施例中的计算量是2PAIR+INV+(Y-1-r_a)MUL。

<关于首标大小和计算量的比较>

在基础技术中，将一组客户分组为每一个均具有B个客户的A个子群。生成与各子群相对应的首标元素，并且作为首标共同地传递所有的首标元素。因此，无论排除客户的数量很大还是很小，首标大小总是A+1。无论排除客户的数量多少，这均具有可将首标大小保持恒定的优点，然而这具有不可减小首标大小的缺点。在实际的内容传递系统中，在排除客户的数量相对于客户的总数的百分比很小的范围内需要高效传递内容的能力。因此，即使通过更加强调安全和便利来使用基础技术的方法，在内容传递时也存在增大了首标大小冗余度的问题。

为了减小基础技术中的问题，可以设想通过减少一组客户的分组数A来减小其首标大小。然而，在这种情况下，存在如下问题：增大了表示属于分组后子群的客户数的B值，并且增大了表示每个客户需要执行的运算的计算量的值2PAIR+INV+(B-1-r_a)MUL。

同时，如在基础技术中那样，在本实施例中，将一组客户分组为每一个均包含Y个客户的A个子群。然而，此外通过添加一些参数构造了将分组后子群中的各客户设置为树叶的Y元树。因此，虽然无论是否存在排除客户，基础技术中的首标大小都是A+1，但是在将根定义为最上层的情况下，可以将属于不存在排除客户的子群的每个客户看作上层的成员。从而，可以将多个子群看作为一个子群，并且可以减小首标大小。另外，如上所述，虽然将每个客户需要执行的运算的计算量表示为2PAIR+INV+(Y-1-r_a)MUL，但是通过将Y设置为B或更小，可以将计算量减小为小于等于基础技术方法中的计算量。

如上所述，与基础技术相比较，本发明是使用公钥的内容传递方法中的一种。与基础技术相比，本发明具有下面所述的特征。

第一，在本实施例中，通过向基础技术的方法添加参数构造了逻辑树，并且将所添加的参数分配给逻辑树的各节点。

第二，用作中心的密钥生成设备预先向各客户传递与分配给逻辑树的参数有关的信息，作为附加私钥。

第三，已加密内容的传递者操作加密设备。在排除了客户的情况下，如使用公共密钥的内容传递方法中那样，传递者生成已对每个节点执行了排除的首标h。

第四，每个客户操作接收设备以通过使用如基础技术中那样的方法，根据公钥PK、首标h以及私钥d_i来计算会话密钥s。

第五，通过如上述第一至第四特征那样配置基础技术的方法，可以将客户解密所需的计算量减小至小于等于基础技术方法中的计算量。

第六，通过如上述第一至第四特征那样配置基础技术的方法，在排除客户数量很少的情况下，与基础技术相比，可以减小首标大小。

示例

为了更详细地描述本实施例的优点，如图23～26中具体示例，示出在将参数n、A、B、X和Y设置为很小的值的情况下，首标大小方面以及解密所需计算量方面的比较。

在基础技术中，建议将与客户数n有关的分组后子群中包含的客户数B的值设置为B＝(n)^1/2。同时，在本实施例中，通过将逻辑树的分支数Y(其为与基础技术中的B相对应的参数)设置为小于等于B，可以增大首标大小和计算量方面的效率。

因此，在下面为了比较，将客户数n设置为相同，并且设置Y<B。图23和图24中分别示出基础技术和本实施例之间就首标大小方面和解密所需运算的计算量方面的比较。另外，图25和26中分别示出在设置Y＝B的情况下的首标大小方面以及解密所需计算量方面的比较。

在图23和24中，作为具体数值，将基础技术方法中的各参数设置为n＝64、A＝8且B＝8，而将本实施例中各参数设置为n＝64、X＝16且Y＝4。另外，在图25和26中，将各参数设置为n＝64、X＝8且B＝Y＝8。然而，为了简化，将所使用的双线性群以及双线性群的大小设置为相同。

(关于设置Y<B的情况)

首先说明图23和24。在图23中，横坐标轴表示排除客户的数量，而纵坐标表示首标大小(首标元素的总数)。另外，在图24中，横坐标轴表示排除客户的数量，而纵坐标表示解密所需运算的计算量。然而，关于解密所需运算的计算量，由于仅有双线性群G上的乘法部分影响基础技术与本实施例之间的差异，因此图24中的纵坐标表示双线性群G上的乘法的数量。另外，在图23中，实线表示传统技术方法中的首标大小，而虚线表示本实施例中的首标大小。另外，在图24中，实线表示传统技术方法中的计算量，而虚线表示本实施例中的计算量。

关于首标大小方面的比较，如从图23中可清楚看到的那样，在排除客户的数量r小于4的情况下，根据本实施例的方法中的首标大小小于基础技术的方法中的首标大小。即，这种情况表明：即使在大约上至6％的总客户被排除的情况下，在根据本实施例的方法中也可以更高效地传递内容。

关于解密所需计算量方面的比较，如从图24中可清楚看到的那样，在排除客户的数量r小于60的情况下，根据本实施例的方法中的计算量小于基础技术的方法中的计算量。这表明：在根据本实施例的方法中可以更高效地解密内容。另外，在排除客户的数量超过60的情况下，也可以看到：可以获得与基础技术方法中的计算量相等的计算量。因此，在如上述那样设置参数的情况下，当不存在排除客户或排除客户的数量很少的时候，根据本实施例的方法能够获得减小的首标大小并且获得每个客户在解密时需要执行运算的减小的计算量。所以，可以说：与根据基础技术的方法相比，根据本实施例的方法能够实现内容的高效传递。

(关于设置Y＝B的情况)

接下来说明图25和26。由于在图25和26中仅改变了上述图23和24中X和Y的值，因此图25和26中的横坐标轴和纵坐标轴、实线以及虚线表示与图23和24中的那些相同。

在设置X＝A＝8且Y＝B＝8的情况下，关于首标大小方面的比较，如从图25中可清楚看到的那样，在排除客户的数量r小于7的情况下，根据本实施例的方法中的首标大小小于基础技术的方法中的首标大小。即，这种情况表明：即使在大约上至9％的总客户被排除的情况下，在根据本实施例的方法中也可以更高效地传递内容。此外，在排除客户的数量大于等于7的情况下，可以获得与基础技术的方法中的首标大小相等的首标大小。因此，无论排除客户的数量如何，均可以将首标大小减小至小于等于基础技术方法中的首标大小。

另外，关于解密所需计算量方面的比较，如从图26中可清楚看到的那样，无论排除客户的数量r如何，均可以获得与基础技术的方法中的计算量相等的计算量。因此，在将各参数设置为X＝A＝8且Y＝B＝8的情况下，可以看到，当不存在排除客户或排除客户的数量很少的时候，可以减小首标大小，并且解密仅需要与基础技术方法中的计算量相等的计算量。

如从上面清楚看到的那样，通过应用本实施例，与基础技术相比，可以在更实际的内容传递系统中实现高效的内容传递，同时保持如基础技术中那样的便利和安全。

如上所述，本发明是这样的方法：在用于通过使用公钥来安全传递内容的内容传递系统中，与传统方法相比，其用于实现待传递的数据量的减小以及解密所需的计算量的减小。通过本发明的实施，与使用公钥的传统内容传递方法相比，可以获得高效的内容传递。

以上已经参考附图描述了本发明的优选实施例。然而，不用说，本发明并不限于这些实施例。显而易见，本领域的技术人员可在权利要求书中所述的范围之内构思各种变化或修改，应该明白，所述各种变化或修改都必然地落在本发明的技术范围内。

例如，虽然上述树结构构造单元231假设了分支从顶部向底部生成的树`结构，但是三叉结构并不必然地受限于此。可以给出分支从底部向顶部、从左向右或从右向左生成的树结构。

另外，本说明书每个流程图中的各步骤并不必然地以根据如流程图所述次序的时间顺序方式来处理。各步骤可包含并行或单独执行的处理(例如，并行处理或基于对象的处理)。