密钥交换方法、密钥交换系统、密钥分发装置、通信装置、及程序

摘要

在允许动态的成员变更的同时，多个用户共享公共密钥，降低密钥交换所需的计算量。第一密钥生成单元(212)使用扭曲伪随机函数计算R

说明书

技术领域

本发明涉及信息安全技术的应用，特别是涉及形成组的多个用户共享公共密钥的密钥交换技术。

背景技术

目前，提出有形成组的多个用户共享公共密钥的密钥交换技术(例如，参照非专利文献1、2)。非专利文献1中记载有实现这种密钥交换技术的信息系统的构架。非专利文献2中记载有这种密钥交换技术的算法。

现有技术文献

非专利文献

非专利文献1：Suvo Mittra,“Iolus:a framework for scalable securemulticasting”,SIGCOMM'97,pp.277-288

非专利文献2：“Scalable Multicast Key Distribution”、[online]、[平成27年6月5日检索]、因特网<URL:https://tools.ietf.org/html/rfc1949>

发明所要解决的课题

非专利文献1、2所记载的现有技术中，需要预先注册共享公共密钥的用户，因此，不能在允许动态成员变更的同时，多个用户共享公共密钥。另外，因为将用户数设为n，作为整体，密钥交换所需的计算量成为O(log n)，所以存在随着用户数的增大而密钥交换的计算量增加的问题。

发明内容

本发明的目的是，鉴于这一点，提供能够在允许动态成员变更的同时，多个用户共享公共密钥，能够降低密钥交换所需的计算量的密钥交换技术。

用于解决课题的技术方案

为了解决所述的课题，本发明提供一种密钥交换方法，将n设为2以上的整数，将i设为1至n的各整数，将j设为2至n的各整数，将S设为密钥分发装置，将U_i设为n台的通信装置，将U₁设为从所述通信装置U_i选择的1台代表通信装置，将U_j设为从所述通信装置U_i除去了所述代表通信装置U₁的n-1台的普通通信装置，将||设为连结运算符，将α,β设为由下式定义的整数，

在密钥分发装置S的存储单元存储有密钥分发装置S的公开密钥密码的秘密密钥sk_S及秘密字符串st_S,st'_S，在通信装置U_i的存储单元存储有通信装置U_i的公开密钥密码的秘密密钥sk_i及秘密字符串st_i,st'_i，密钥交换方法包含：通信装置U_i通过扭曲伪随机函数，使用秘密字符串st_i,st'_i生成r_i,k_i,s_i，计算R_i＝g^ri及c_i＝g^kih^si，将(R_i,c_i)发送到密钥分发装置S的第一密钥生成步骤；密钥分发装置S通过目标碰撞困难散列函数，使用c₁,…,c_n生成sid，对于各i，将(sid,R_α,R_β)发送到通信装置U_i的会话ID生成步骤；代表通信装置U₁通过伪随机函数，使用(sid,R_n^r1)生成K₁^l，通过K₁^l和k₁||s₁的“异或”计算T₁，并将T₁发送到密钥分发装置S的代表第二密钥生成步骤；普通通信装置U_j通过伪随机函数，使用(sid,R_α^rj)生成K_j^l，通过伪随机函数，使用(sid,R_β^rj)生成K_j^r，通过K_j^l和K_j^r的“异或”计算T_j，并将(k_j,s_j,T_j)发送到密钥分发装置S的普通第二密钥生成步骤；密钥分发装置S通过扭曲伪随机函数，使用秘密字符串st_S,st'_S生成k_s，通过k₂,…,k_n,k_s的“异或”计算k'，对于各j，通过T₁,…,T_j-1的“异或”计算T'_j，并将k'发送到代表通信装置U₁，将(k',T'_j,T₁)发送到普通通信装置U_j的第三密钥生成步骤；普通通信装置U_j通过T'_j和K_j^r的“异或”计算K_j^l，并通过T₁和K_j^l的“异或”计算k₁||s₁的第一会话密钥生成步骤；通信装置U_i通过伪随机函数，使用sid及k'和k₁的“异或”生成公共密钥K₂的第二会话密钥生成步骤。

发明效果

根据本发明，能够在允许动态成员变更的同时，多个用户共享公共密钥。密钥交换所需的计算量成为用户数的常数次、即O(1)，与以往相比被消减。

附图说明

图1是示例密钥交换系统的功能结构的图。

图2(A)是示例密钥分发装置的功能结构的图，图2(B)是示例通信装置的功能结构的图。

图3是表示密钥交换方法的处理流程的图。

图4是示例密钥交换方法的处理流程的图。

具体实施方式

在说明实施方式之前，说明该说明书的表述方法。

关于某集合Set，将从Set随机选择要素m表述为m∈_RSet。

关于某算法ALG，将ALG对于输入x和随机数r输出y表述为y←ALG(x；r)。此外，ALG为确定的算法的情况下，随机数r为空。

|·|为值·的位长。

将к设为安全参数。

将F＝{F_к:Dom_к×FS_к→Rng_к}_к设为具有定义域{Dom_к}_к、密钥空间{FS_к}_к、值域{Rng_к}_к的函数族。此时，如果相对于任意的多项式时间的识别者D不能分辨函数F_к和真正随机函数RF_к:Dom_к→Rng_к，则将F＝{F_к}_к称作伪随机函数族。伪随机函数的具体例例如记载于下述参考文献1。

〔参考文献1〕O.ゴールドライヒ著、“現代暗号·確立証明·擬似乱数”、シュプリンガー·フェアラーク東京、2001年

将H＝{H_к:Dom_к→Rng_к}_к设为具有定义域{Dom_к}_к、值域{Rng_к}_к的散列函数族。此时，如果对于任意的多项式时间的攻击者A，在赋予了x∈_RDom_к之后未发现成为H_к(x)＝H_к(x')那种的x'(≠x)，则将H＝{H_к}_к称作目标碰撞困难散列函数族。目标碰撞困难散列函数的具体例例如记载于下述参考文献2。

〔参考文献2〕J.A.ブーフマン著、“暗号理論入門原書第3版”、丸善出版、2007年

将公开密钥密码算法设为(Gen,Enc,Dec)。密钥生成算法Gen以安全参数к为输入，以公开密钥pk和秘密密钥sk为输出。加密算法Enc以公开密钥pk和明文m为输入，以密文CT为输出。解密算法Dec以秘密密钥sk和密文CT为输入，以明文m为输出。公开密钥密码算法的具体例例如记载于上述参考文献2。

将消息认证码算法设为(MGen,Tag,Ver)。MAC密钥生成算法MGen以安全参数к为输入，以MAC密钥mk为输出。标志生成算法Tag以MAC密钥mk和明文m为输入，以认证标志σ为输出。验证算法Ver以MAC密钥mk、明文m、认证标志σ为输入，如果认证标志σ正确，则输出1，如果不正确，则输出0。消息认证码算法的具体例例如记载于上述参考文献2。

将函数加密算法设为(Setup,Der,FEnc,FDec)。设置算法Setup以安全参数к为输入，输出主秘密密钥msk和公开参数Params。密钥导出算法Der以公开参数Params、主秘密密钥msk、属性A为输入，输出用户秘密密钥usk。加密算法FEnc以公开参数Params、访问结构P、明文m为输入，输出密文CT。解密算法FDec以用户秘密密钥usk和密文CT为输入，如果属性A满足访问结构P，则输出明文m。函数加密算法的具体例例如记载于下述参考文献3。

〔参考文献3〕D.Boneh,A.Sahai,and B.Waters,“Functional encryption:definitions and challenges”,TCC,Lecture Notes in Computer Science,vol.6597,pp.253-273,2011.

将函数tPRF:{0,1}^к×FS_к×{0,1}^к×FS_к→Rng_к称作扭曲伪随机函数，使用伪随机函数F_к，定义为：

其中，a,b'∈{0,1}^к，a',b∈FS_к。扭曲伪随机函数的具体例例如记载于下述参考文献4。

〔参考文献4〕Kazuki Yoneyama,“One-Round Authenticated Key Exchange withStrong Forward Secrecy in the Standard Model against Constrained Adversary”,IEICE Transactions,vol.E96-A,no.6,pp.1124-1138,2013.

以下，详细说明本发明的实施方式。此外，图中具有相同功能的结构单元标注同一编号，省略重复说明。

实施方式的密钥交换系统如图1所示例，包含密钥分发装置1及N(≧2)台通信装置2₁,…,2_N。该实施方式中，密钥分发装置1及通信装置2₁,…,2_N分别连接到通信网3。通信网3为以密钥分发装置1与通信装置2₁,…,2_N可分别进行通信的方式构成的回路交换方式或分组交换方式的通信网。该实施方式中，通信装置2₁,…,2_N彼此之间也可以不能通信。通信网3不需要是确保安全的通信线路，例如能够使用因特网等。

密钥分发装置1如图2(A)所示例，包含存储单元100、设置单元101、公开密钥生成单元102、秘密字符串生成单元103、用户密钥发送单元111、会话ID生成单元113、认证标志验证单元114、第三密钥生成单元115、及认证标志生成单元116。通信装置2如图2(B)所示例的那样，包含存储单元200、公开密钥生成单元202、秘密字符串生成单元203、用户密钥接收单元211、第一密钥生成单元212、第二密钥生成单元214、认证标志生成单元215、认证标志验证单元216、及会话密钥生成单元217。该密钥分发装置1及通信装置2₁,…,2_N通过进行图3及图4所示例的各步骤的处理，实现实施方式的密钥交换方法。

密钥分发装置1及通信装置2₁,…,2_N例如为在具有中央运算处理装置(CPU:Central>

密钥分发装置1具备的存储单元100及通信装置2₁,…,2_N具备的存储单元200例如能够通过RAM(Random>

参照图3，说明实施方式的密钥交换方法的系统设置的处理步骤。

在以后的说明中，如下定义记号。S表示密钥分发装置1，U_i(i∈{1,…,N})表示N台通信装置2₁,…,2_N。将G设为к位的素数位数p的乘法循环群。将g,h分别设为群G的生成元。将H:{0,1}^*→{0,1}^к设为目标碰撞困难散列函数。将tPRF:{0,1}^к×FS_к×{0,1}^к×FS_к→Z_p、tPRF':{0,1}^к×FS_к×{0,1}^к×FS_к→FS_к设为扭曲伪随机函数。将F:{0,1}^к×G→Z_p²、F':{0,1}^к×Z_p→FS_к、F":{0,1}^к×FS_к→{0,1}^к设为伪随机函数。

在步骤S101，密钥分发装置S的设置单元101通过函数加密的设置算法Setup生成公开参数Params及主秘密密钥msk。设置单元101将公开参数Params分别发送到通信装置U₁,…,U_N。主秘密密钥msk被存储到存储单元100。

在步骤S102，密钥分发装置S的公开密钥生成单元102通过公开密钥密码的密钥生成算法Gen生成密钥分发装置S的公开密钥pk_S及秘密密钥sk_S的对。密钥分发装置S的公开密钥pk_S使用例如公开密钥基础等来公开。密钥分发装置S的秘密密钥sk_S被存储到存储单元100。

在步骤S202，通信装置U_i的公开密钥生成单元202通过公开密钥密码的密钥生成算法Gen生成通信装置U_i的公开密钥pk_i及秘密密钥sk_i的对。通信装置U_i的公开密钥pk_i使用例如公开密钥基础等来公开。通信装置U_i的秘密密钥sk_i被存储到存储单元200。

在步骤S103，密钥分发装置S的秘密字符串生成单元103生成扭曲伪随机函数中使用的秘密字符串(st_S,st'_S)作为st_S∈_RFS_к、st'_S∈{0,1}_к。秘密字符串(st_S,st'_S)被存储到存储单元100。

在步骤S203，通信装置U_i的秘密字符串生成单元203生成扭曲伪随机函数中使用的秘密字符串(st_i,st'_i)作为st_i∈_RFS_к、st'_i∈{0,1}_к。秘密字符串(st_i,st'_i)被存储到存储单元200。

在步骤S104，密钥分发装置S从例如公开密钥基础等取得各通信装置U₁,…,U_N的公开密钥pk₁,…,pk_N，并将其存储到存储单元100。

在步骤S204，通信装置U_i从例如公开密钥基础等取得密钥分发装置S的公开密钥pk_S，并将其存储到存储单元200。另外，将从密钥分发装置S接收到的公开参数Params存储到存储单元200。

参照图4，说明实施方式的密钥交换方法的会话密钥分发的处理步骤。

以下，设为N台通信装置2₁,…,2_N中的任意的n(≦N)台通信装置U_i(i∈{1,…,n})进行会话密钥SK的共享。另外，在将S,U_i作为各算法的输入的情况下，表示唯一地特定各装置的标识符。

在步骤S111，密钥分发装置S的用户密钥发送单元111在通信装置U_i开始会话时，在该会话为通信装置U_i的时帧TF的最初的会话的情况下，将当前时刻设为time，将属性设为A_i＝(U_i,time)，通过函数加密的密钥导出算法Der，生成通信装置U_i的用户秘密密钥usk_i←Der(Params,msk,A_i)。另外，通过消息认证码的密钥生成算法MGen，生成通信装置U_i的MAC密钥mk_i←MGen。而且，通过公开密钥密码的加密算法Enc，使用通信装置U_i的公开密钥pk_i将用户秘密密钥usk_i及MAC密钥mk_i加密，生成密文CT_i←Enc_pki(usk_i,mk_i)。用户密钥发送单元111将密文CT_i分别发送到通信装置U_i。

在步骤S211，通信装置U_i的用户密钥接收单元211通过公开密钥密码的解密算法Dec，使用通信装置U_i的秘密密钥sk_i将从密钥分发装置S接收到的密文CT_i解密，得到用户秘密密钥及MAC密钥(usk_i,mk_i)←Dec_ski(CT_i)。用户密钥接收单元211将用户秘密密钥usk_i及MAC密钥mk_i存储到存储单元200。

在步骤S212，通信装置U_i的第一密钥生成单元212生成^～r_i∈_R{0,1}^к,^～r'_i∈_RFS_к,^～k_i∈_R{0,1}^к,^～k'_i∈_RFS_к,^～s_i∈_R{0,1}^к,^～s'_i∈_RFS_к，通过扭曲伪随机函数tPRF计算r_i＝tPRF(^～r_i,^～r'_i,st_i,st'_i),k_i＝tPRF(^～k_i,^～k'_i,st_i,st'_i),s_i＝tPRF(^～s_i,^～s'_i,st_i,st'_i)。另外，计算R_i＝g^ri,c_i＝g^kih^si。而且，第一密钥生成单元212将(R_i,c_i)发送到密钥分发装置S。

在步骤S112，密钥分发装置S从通信装置U_i接收(R_i,c_i)。此时，等待至从所有的通信装置U₁,…,U_n接收到(R₁,c₁),…,(R_n,c_n)为止。

在步骤S113，密钥分发装置S的会话ID生成单元113通过目标碰撞困难散列函数H，使用从通信装置U₁,…,U_n接收到的c₁,…,c_n，生成sid＝H(c₁,…,c_n)。另外，从n台通信装置U₁,…,U_n选择1台通信装置作为代表者。代表者的选择方法是任意的，例如，可以选择预定的优先级最高的通信装置，也可以选择最近开始会话的通信装置。在此，通信装置U₁作为被选择者，将U₁称作代表通信装置。另外，将代表通信装置U₁以外的n-1台通信装置U_j(j∈{2,…,n})称作普通通信装置。会话ID生成单元113如下式那样计算α、β，将(sid,R_α,R_β)分别发送到通信装置U_i。

在步骤S213，通信装置U_i从密钥分发装置S分别接收(sid,R_α,R_β)。通信装置U_i随着接收(sid,R_α,R_β)，执行以后的处理。在i＝2,…,n的情况下，即如果通信装置U_i为通信装置U_j(i＝j)，则处理进入步骤S214_j。在i＝1的情况下，即如果通信装置U_i为代表通信装置U₁，则处理进入步骤S214₁。

在步骤S214_j，普通通信装置U_j的第二密钥生成单元214如下式那样，通过伪随机函数F，使用(sid,R_α^rj)生成K_j^l，通过伪随机函数F，使用(sid,R_β^rj)生成K_j^r，通过K_j^l和K_j^r的“异或”计算T_j。

在步骤S215_j中，普通通信装置U_j的认证标志生成单元215通过消息认证码的标志生成算法Tag，使用MAC密钥mk_j生成认证标志σ_j＝Tag_mkj(R_j,c_j,R_α,R_β,k_j,s_j,T_j,U_j,sid)。认证标志生成单元215将(k_j,s_j,T_j,σ_j)发送到密钥分发装置S。

在步骤S214₁，代表通信装置U₁的第二密钥生成单元214如下式那样，通过伪随机函数F，使用(sid,R_n^r1)生成K₁^l，通过K₁^l和k₁||s₁的“异或”计算T₁。其中，||为连结运算符。

在步骤S215₁，代表通信装置U₁的认证标志生成单元215通过消息认证码的标志生成算法Tag，使用MAC密钥mk₁生成认证标志σ₁＝Tag_mk1(R₁,c₁,R_n,R₂,T₁,U₁,sid)。认证标志生成单元215将(T₁,σ₁)发送到密钥分发装置S。

在步骤S114_j，密钥分发装置S的认证标志验证单元114对于j＝2,…,n，从普通通信装置U_j接收(k_j,s_j,T_j,σ_j)，通过消息认证码的验证算法Ver，使用普通通信装置U_j的MAC密钥mk_j验证Ver_mkj(R_j,c_j,R_α,R_β,k_j,s_j,T_j,U_j,sid,σ_j)。如果认证标志σ_j为不正当，则结束普通通信装置U_j的会话。另外，关于j＝2,…,n，验证c_j＝g^kjh^sj是否成立。如果不成立，则结束普通通信装置U_j的会话。

在步骤S114₁，密钥分发装置S的认证标志验证单元114从代表通信装置U₁接收(T₁,σ₁)，通过消息认证码的验证算法Ver，使用代表通信装置U₁的MAC密钥mk₁验证Ver_mk1(R₁,c₁,R_n,R₂,T₁,U₁,sid,σ₁)。如果认证标志σ₁为不正当，则结束代表通信装置U₁的会话。

在步骤S115a，密钥分发装置S的第三密钥生成单元115生成^～k_S∈_R{0,1}^к,^～k'_S∈_RFS_к,^～K₁∈_R{0,1}^к,^～K'₁∈_RFS_к，通过扭曲伪随机函数tPRF来计算k_S＝tPRF(^～k_S,^～k'_S,st_S,st'_S),K₁＝tPRF(^～K₁,^～K'₁,st_S,st'_S)。另外，通过下式来计算k'。

在步骤S115b，密钥分发装置S的第三密钥生成单元115对于j＝2,…,n，通过下式计算T'_j。

在步骤S115c，密钥分发装置S的第三密钥生成单元115对于i＝1,…,n，作为访问结构P_i＝(ID＝U_i)∧(time∈TF)，通过函数加密的加密算法FEnc将公共密钥K₁加密，生成密文CT'_i＝FEnc(Params,P_i,K₁)。在此，ID是表示通信装置的谓词变量，TF为表示通信装置的时帧的谓词变量。

在步骤S116_i，密钥分发装置S的认证标志生成单元116对于j＝2,…,n，通过消息认证码的标志生成算法Tag，使用普通通信装置U_j的MAC密钥mk_j生成认证标志σ'_j＝Tag_mkj(R_j,c_j,R_α,R_β,k_j,s_j,T_j,U_j,sid,c₁,k',T'_j,T₁,CT'_j)。认证标志生成单元116将(c₁,k',T'_j,T₁,CT'_j,σ'_j)发送到普通通信装置U_j。

在步骤S116₁，密钥分发装置S的认证标志生成单元116通过消息认证码的标志生成算法Tag，使用代表通信装置U₁的MAC密钥mk₁生成认证标志σ'₁＝Tag_mk1(R₁,c₁,R_n,R₂,T₁,U₁,sid,k',CT'₁)。认证标志生成单元116将(k',CT'₁,σ'₁)发送到代表通信装置U₁。

在步骤S216_j，普通通信装置U_j的认证标志验证单元216从密钥分发装置S接收(c₁,k',T'_j,T₁,CT'_j,σ'_j)，通过消息认证码的验证算法Ver，使用普通通信装置U_j的MAC密钥mk_j验证Ver_mkj(R_j,c_j,R_α,R_β,k_j,s_j,T_j,U_j,sid,c₁,k',T'_j,T₁,CT'_j,σ'_j)。如果认证标志σ'_j为不正当，则结束普通通信装置U_j的会话。另外，如下式，通过T'_j和K_j^r的“异或”计算K_j^l，且通过T₁和K_j^l的“异或”计算k₁||s₁。

然后，验证c₁＝g^k1h^s1是否成立。如果不成立，则结束普通通信装置U_j的会话。

在步骤S216₁，代表通信装置U₁的认证标志验证单元216从密钥分发装置S接收(k',CT'₁,σ'₁)，通过消息认证码的验证算法Ver，使用代表通信装置U₁的MAC密钥mk₁验证Ver_mk1(R₁,c₁,R_n,R₂,T₁,U₁,sid,k',CT'₁,σ'₁)。如果认证标志σ'₁为不正当，则结束代表通信装置U₁的会话。

在步骤S217，通信装置U_i的会话密钥生成单元217通过函数加密的解密算法FDec，使用通信装置U_i的用户秘密密钥usk_i将公共密钥K₁←FDec_uski(CT'_i,P_i)解密。另外，如下式，通过伪随机函数F'来计算公共密钥K₂。

然后，如下式，通过伪随机函数F"来计算会话密钥SK。

通过如上那样构成，根据本发明的密钥交换技术，不需要如以往那样预先注册进行密钥交换的用户的信息，能够在允许动态的成员变更的同时，多个用户共享公共密钥。另外，以往，将用户数设为n，密钥交换所需的整体的计算量成为O(log n)，但根据本发明，成为用户数的常数次、即O(1)，所以与以往相比，能够以少的计算量进行密钥交换。

本发明不限于上述的实施方式，不用说，在不脱离本发明的宗旨的范围内可以进行适宜变更。上述实施方式中说明的各种处理不仅按照记载的顺序以时间序列执行，而且还可以根据执行处理的装置的处理能力或根据需要并行或单独地执行。

[程序、记录介质]

在通过计算机实现上述实施方式中说明的各装置中的各种处理功能的情况下，各装置应有的功能的处理内容通过程序记述。而且，通过由计算机执行该程序，在计算机上实现上述各装置中的各种处理功能。

记述有该处理内容的程序能够记录在由计算机可读取的记录介质中。作为计算机可读取的记录介质，例如也可以为磁记录装置、光盘、光磁记录介质、半导体存储器等任何记录介质。

另外，该程序的流通例如通过销售、转让、出租记录有该程序的DVD、CD-ROM等可移动型记录介质等来进行。进而，也可以为将该程序存储于服务器计算机的存储装置，经由网络从服务器计算机向其它计算机转发该程序，由此使该程序流通的结构。

执行这种程序的计算机，例如，首先将存储于可移动型记录介质的程序或从服务器计算机转发来的程序暂时存储于自己的存储装置。然后，在执行处理时，该计算机读取存储于自己的记录介质的程序，执行根据读取的程序的处理。另外，作为该程序的其它执行方式，计算机可以从可移动型记录介质直接读取程序，执行按照该程序的处理，进而，也可以每次从服务器计算机向该计算机转发程序时，依次执行按照接收到的程序的处理。另外，也可以为下述结构，即，从服务器计算机，利用不进行程序向该计算机的转发而仅通过该执行指示和结果取得来实现处理功能的、所谓的ASP(Application Service Provider，应用服务提供商)型的服务，执行上述的处理。此外，本方式的程序中包含供电子计算机进行的处理用的信息、即基于程序的信息(虽然不是相对于计算机的直接的指令，但为具有规定计算机的处理的性质的数据等)。

另外，该方式中，通过在计算机上执行规定的程序，构成本装置，但是，也可以硬件上实现这些处理内容的至少一部分。