1、然后模拟者为敌手提供一个与实际环境不可区分的模拟环境,回答敌手的所有询问;最后利用敌手的攻击结果解决基础困难问题。本文基于文献7提出了一个基于椭圆曲线的签密方案,并在RO模型中给出了安全性证明。与文献8的可证明安全签密方案相比,本文的方案能够抵御攻击能力更强的敌手,并且采用了不同的思路对方案的安全性予以证明。1 预备知识 本章简单地介绍了椭圆曲线群中的GDH（gap Diffie-Hellman）问题。本文提出的签密方案的安全性依赖于GDH问题的困难性。问题描述:给定椭圆曲线群（P, + ）中的任意元素aP、bP,以及DDH（decisional Diffie-Hellman） Oracle
2、ODDH（?q,?q）,找到Diffie-Hellman密钥K=abP。其中ODDH的功能是: 对于输入（P, Pu, Pv, z） （P,P,P,P）, 判定是否有z=uvP 。如果GDH问题从计算上说不可解,则称GDH假设成立。确切地说,对于安全参数k和攻击者AGDH,定义下述游戏:GDHgame（k, AGDH） aRZ*q;bRZ*q KAGDH（P , aP, bP | ODDH（?q） if K=abP then return 1 else return 0 其中:R表示从集合中随机选取元素对变量赋值;AGDH（P, aP, bP | ODDH（?q）表示算法在执行过程中可以对符号
3、“|”之后的预言机作询问。定义SuccGDH=max PrGDHgame（k, AGDH）=1 这里max指对所有可能的敌手取最大值。如果SuccGDH是关于k的可忽略函数,则称GDH假设成立。2 签密方案的形式化定义 2.1 方案组成 签密方案由以下几个算法组成:a）GC系统初始化算法。输入安全参数k,输出系统公共参数cp 。b）GK密钥生成算法。输入系统参数cp,输出用户密钥对 （sk,pk） 。c）SC签密算法。输入系统参数cp,发送者的私钥skA,接收者的公钥pkB,明文m,输出签密C 。d）USC解签密算法。输入系统参数cp,接收者的私钥skB,发送者的公钥pkA,签密C,输出明文m
4、或符号“”表示解签密失败。2.2 敌手模型 假定敌手为第三方,即只考虑外部攻击,其目标是从签密信息中获取部分明文信息或伪造签密信息。假定敌手可以选择任意接收者身份和明文对发送者的签密预言机进行询问,也可以选择任意发送者身份和密文对接收者的解签密预言机进行询问。2.3 安全性定义 定义1 密文不可区分性。设SCR=（GC, GK, SC, USC）为签密方案,O为敌手。考虑以下游戏:game（k, O, SCR） cpGC（k）（skA, pkA） RGK（cp） （skB, pkB） RGK（cp） （m0, m1） O（k, cp, find, pkA, pkB | SC（cp, skA,?
5、q）, USC（cp, skB,? iR0, 1 C* SC（cp, skA, pkB,mi） i O（k, cp, guess, pkA, pkB , C* | SC（cp, skA,?if i=i （pkA, C*） was never queried to USC（cp, skB,?q） then return 1 else return 0 SC（cp, skA,?q）表示以任意接收者公钥和明文对A作签密询问;USC（cp, skB,?q）表示以任意发送者公钥和密文对B作解签密询问。（下同） O的优势定义为 AdvO=|2Prgame（k,O,SCR）=1-1| 以S0表示“game输
6、出为1”这一事件。如果没有任何PPT敌手能够以不可忽略的优势赢得游戏,则称签密方案SCR是密文不可区分的。定义2 不可伪造性。game-1（k,O,SCR） cpGC（k） （skA, pkA） RGK（cp） （C*, pkR） O（k, cp, pkA | SC（cp, skA,?if pkR is invalid then return 0 m* USC（cp, skR, pkA, C*） if m*“”（pkR, m*） was never queried by O to SC（cp, skA,?then return 1 else return 0?定义SuccO=Prgame-1（
7、k,O,SCR）=1 如果没有任何PPT敌手能够以不可忽略的优势赢得游戏,则称签密方案SCR是不可伪造的。3 方案构造 签密方案SCR=（GC, GK, SC, USC）的细节描述如下:GC（k） 随机选取长度为k的素数q,G1为由点P生成的阶为q的椭圆曲线循环乘法群,假定明文空间为0, 1k,选取两个安全hash函数G: G10, 1k , H: 0, 1*Zq ,cp=（ G1, P, G, H）。GK（cp） 对任意用户i, 随机选取秘密数siZ*q,令Pi=siP,用户的公钥pki=Pi,私钥ski=si SC（cp, skA, pkB, m） 设skA=sA, pkA=PA,pkB=
8、 PB 。xRZ*q, Kx PB, tG（K）, ct?m, rH（m, PA, PB, K）, sx/（r+ sA）, C（c, r, s） USC（cp, skB, pkA, C） 设skB= sB, pkA= PA,pkB= PB, C=（c, r, s） 。Ws（PA+rP）, KsBW, tG（K）, m t?c, if H（m, PA, PB, K）=r then return m else return “” 4 安全性分析 1）保密性 关于方案的保密性,有以下定理。定理1 如果GDH假设成立,则SCR在本文假定的安全模型下具有密文不可区分性。确切地说,有 Adv?SCR（qG
9、 , qH, qSC,qUSC）2 SuccGDH+（qH +qSC+qUSC）/2k-1+ （qSC+qUSC）/2k-1+ qSC（qG +qH+qSC+qUSC）/2k -1 其中qG、qH、qSC、qUSC分别表示各预言机被询问的次数。证明 不失一般性,本文假设信息的发送者为A,接收者为B。设有模拟者M模拟游戏game中的SCR与敌手O作游戏game-1,回答O所提出的询问。游戏规则修改如下:a）对于敌手O在find阶段之后所生成的两个长度相等的明文m0、m1,M执行下列操作:t+R0, 1k,iR0, 1,c+t+?mi , r+R Zq ,s+R Z*q 回答C+（c+, r+,
10、s+）。b）当G在K+=s+（r+sA）PB被询问时,直接返回t+之值。c）当H在（mi, PA, PB, K+=s+（r+sA）PB ）被询问时,直接返回r+之值。d）假定SC oracle和USC oracle 都是完备的,即对于签密询问,运用sA进行签密应答;对于解签密询问,运用sB进行解签密应答。以S1表示“game-1输出为1”这一事件。在敌手O看来,M所提供的模拟环境与实际环境类似,不同之处仅在于: 当H 在find阶段中在点（mi, PA, PB, K+ ）被询问时回答有区别（这是因为mi只有在find阶段结束时才确定）,H在该点被询问的次数最多为qH+qSC+qUSC。因此有
11、| PrS1-PrS0 | （qH+qSC+qUSC）/2k （1） 对game-1进行修改,得游戏game-2。规则a）和d）不变。b）G被询问时,直接返回G oracle之值;c）H被询问时,直接返回H oracle之值。注意到, t+仅在计算密文c+时使用。由于t+的随机性,仅有c+而区分m0和m1是不可能的,从而有 PrS2=1/2（2） 与game-1相比,不同之处在于:如果G在K+被询问或H在（mi, PA, PB, K+ ）被询问,回答可能有差别（game-1中分别以t+、r+应答而game-2中均以随机数应答）。从而有 | PrS2-PrS1 | PrG在K+被询问或H在（mi
12、, PA, PB, K+ ）被询问（3） 事件“G在K+被询问或H在（mi, PA, PB, K+ ）被询问”可以分为三种情形:由敌手O直接询问,用ask2表示该情形;通过SC oracle询问;通过USC oracle询问。则有 PrG在K+被询问或H在（mi,PA, PB, K+ ）被询问 Prask2+（qSC+qUSC）/2k（4） 进一步,用G Sim、H Sim分别代替游戏game-2中的G oracle、H oracle,得游戏game-3。此时,M需要维护四张表GL1、GL2、HL1、HL2,用于跟踪对各预言机的询问,各表的初始状态均为空表。模拟算法描述如下: G Sim（K）
13、 if ODDH（P, W, PR, K）=1 for some （PR |W|（?, t）GL2 then return t else if （K, t） GL1 then return t else tR0, 1k ;Add （K, t ） to GL1;return t H Sim（m, PS, PR, K） for some （PR |W|（m, PS, PR, ?）, r）HL2 then return r else if （m, PS, PR, K）, r） HL1 then return r else rRZq ;add （m, PS, PR, K）, r） to HL1;ret
14、urn r 注意到,在此游戏中,GL2、HL2均为空表。Prask3= Prask2（5） 进一步,用SCSim、USCSim分别代替游戏game-3中的SC oracle、USC oracle,得游戏game-4。SCSim（PA , PR , m） tR0, 1k ;c=t?m ;rRZq ;sR Z*q W=s（PA+rP） add （PR |W|（?, t） to GL2 add （PR |W|（m, PA, PR, ?）, r） to HL2 C （c, r, s） return C USCSim（PB, PS, C） W=s（PS+rP） ifODDH（P, W, PB, K）=1
15、 for some （K, t） GL1or ODDH（W, W, PR, PB）=1 for some （PR |W|（?, t）GL2 then m=t?c add （PB |W|（?, t） to GL2 ; m= t?c if ODDH（P, W, PB, K）=1 for some （m, PS, PB, K）, h）HL1 or ODDH（W, W, PR, PB）=1 for some （PR |W|（m, PS, PR, ?）, h）HL2 thenif h=r then return m else return “” else hRZq ;add （PB |W|（m, PS,
16、 PB,?）, h） to HL2;if h=r then return m 注意到,仅当SC oracle在点K+对G或H作过询问并且（K+, t） GL1 或 （m, PA, PR, K+）, h） HL1 时,模拟结果才会有误差。| Prask4-Prask3 |qSC（qG+qH+qSC+qUSC）/2k （6） 如果事件ask4发生,则说明表中有K+=s+（r+sA）PB 存在。有abP=sAPB=（K+- s+r+PB）1/s+。进一步,其值可以通过DDH oracle找到（即对于表中的分量K,首先计算（K- s+r+PB）1/s+）=v,然后借助ODDH（P, PA , PB,
17、v）找到正确的K值）。也就是说,如果ask4发生,则可以解决GDH问题。Prask4SuccGDH（7） 由式（1）（7）可得 AdvSCR（qG, qH, q?SC, qUSC）/2=| PrS0-1/2 | SuccGDH+（qH +qSC+qUSC）/2k+ （qSC+qUSC）/2k+ qSC（qG +qH+qSC+qUSC）/2k 从而得到定理的结论。关于算法的执行时间,通过直接计算不难得到,敌手攻破SCR与解决GDH问题的时间多项式等价。2）不可伪造性 关于方案的不可伪造性,有以下结论:如果CDH假设成立,则方案SCR在本文假定的安全模型下具有不可伪造性。运用与定理1的证明过程类似的方法,可以得到具体不可伪造性的度量结果。3）安全性比较 从安全性角度看,该方案能够抵御敌手的自适应选择明文/密文攻击。与文献8中的方案相比,本文基于不同的计算假设,采用了不同的安全性证明思路。5 结束语 本文提出了一个基于椭圆曲线的签密方案,并在RO模型中给出了安全性证明。在GDH问题难解的假设之下,该方案被证明是安全的。从安全性角度看,该方案能够抵御敌手的自适应选择明文/密文攻击。与文献8中的方案相比较,本文基于不同的计算假设,并且采用了不同的思路对方案的安全性予以证明。
