通用可组合安全的门限签名协议.doc

第6期洪璇等：通用可组合安全的门限签名协议7通用可组合安全的门限签名协议洪璇1，陈克非2,3，李强2（1. 上海师范大学 计算机科学与技术系，上海 200234；2. 上海交通大学 密码与信息安全实验室，上海 200240；3. 现代通信国家重点实验室，四川 成都 610041）摘 要：门限签名协议使得签名团体中任何t个参与者合作可以生成某个消息的有效签名；而少于t个参与者就无法得到该消息的合法签名。目前关于门限签名协议的安全性研究只是专注于单一协议执行时的安全性，针对这点，引入通用可组合框架。利用该框架的通用可组合性可以模块化地设计与分析门限签名协议。首先定义了门限签名协议在通用可组合框架下的安全模型，并证明其等价于门限签名协议标准概念下的安全模型，然后以前摄门限签名协议为例描述如何应用这个安全模型。提出的门限签名协议和前摄性门限签名协议不仅满足可证明安全性，还具有通用可组合安全性。关键词：门限签名协议；UC框架；UC安全；前摄门限签名协议中图分类号：TP309.2 文献标识码：A 文章编号：1000-436X(2009)06-0001-06Universal composable threshold signatureHONG Xuan1, CHEN Ke-fei2,3, LI Qiang2(1.Department of Computer Science and Technology, Shanghai Normal University, Shanghai 200234, China;2.Cryptography and Information Security Lab, Shanghai 200240, China;3. National Laboratory of Modern Communication, Chengdu 610041, China)Abstract: Threshold signature allowed any subset of t parties generating a signature, but that disallowed the creation of a valid signature if fewer than t parties participate in the protocol. Since the security of threshold signature was only considered in a single instance before, the universal composability framework was introduced. The framework with its security preserving composition property allowed for modular design and analysis of the threshold signature. The defined ideal functionality of threshold signature is proved equals to the standard security notion of threshold signature. Furthermore, how to applying the ideal functionality is described. The proposed threshold signature protocol and proactive threshold signature protocol are not only provably secure, but also universally composable.Key words: threshold signature; UC framework; UC security; proactive threshold signature1 引言收稿日期：2008-06-02；修回日期：2009-03-17基金项目：国家自然科学基金资助项目（90704004）；国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311201）；现代通信国家重点实验室基金资助项目(9140C1103020803)Foundation Items: The National Natural Science Foundation of China (90704004); The National Basic Research Program of China (973 Program)(2007CB311201); The National Laboratory of Modern Communication (9140C1103020803)在现代密码协议研究中，门限密码体制是目前比较受关注的方向。一个(t,n)门限签名协议允许签名团体中任何t个或多于t个参与者合作生成某个消息的有效签名；而少于t个参与者就无法完成该消息的合法签名。任何一个验证者可以利用签名团体的公钥验证签名的正确性。门限签名体制中每个签名者都保留一份签名密钥，可以用于生成签名的一个“碎片”。在收集到足够的“碎片”后，就可以按指定的方式联合生成这个消息的门限签名。Desmedt1首次介绍了门限密码体制的概念。而第一个基于RSA密码体制的门限签名协议是由Boyd2和Frankel3分别提出的。此后几年，大家不断提出各种门限签名协议，然后又不断进行分析、改进28。现在一般认为最有效的RSA门限签名方案之一就是Shoup在2000年提出的门限签名方案5。在随机预言机模型下，已证明该协议的安全性等价于RSA困难问题的安全性。其后，大量的文章研究基于该协议的改进，但是基本思路并没有太大变化7。基于门限签名还有各种应用，如代理门限签名协议8、前摄门限签名协议6等，这些协议都可以由门限签名协议变形得到，但是其安全性证明则需要重新证明，这使得协议的设计证明存在许多冗余工作。为了能更好地利用已有工作成果，作者希望采用通用可组合框架(UC, universal composability framework)9来设计协议。本文定义了门限签名协议的UC框架，并证明该框架下的安全模型等价于门限签名协议标准概念的安全性，即强壮性和不可伪造性。相比于Almansa6等人在2006年欧密会上提出的门限签名理想功能FThSign066，FThSign不管在协议定义方面还是安全性证明方面都有一些改进。然后将说明如何利用这个安全模型进一步设计“高层的”协议。只要先设计好有安全部件FThSign的混合协议，并证明其安全性，然后用UC安全的Shoup方案直接替代FThSign插入到协议中即可。这样构造的协议可以根据UC定理直接推导出其安全性。对于UC框架的介绍将在第2节中详细介绍。在第3节中，将定义UC框架下的门限签名协议安全模型，并证明其与标准概念下安全性的等价。在第4节中，将说明如何利用这个安全模型进一步设计“高层的”协议。第5节是结束语。2 UC框架的基本知识近几年来，对于密码协议的安全性分析工作已取得了巨大的进展。以前甚至现在的绝大多数协议分析时都需要先确立正确的模型，实际上一个完整的模型要考虑的状态和情况非常多，难以考虑周全。于是为了简化起见，许多协议的设计都是简单地考虑单一协议的执行情况。当一个协议应用到其他环境中时，安全性就需要重新定义。从而产生了定义的指数爆炸性增长，对上层协议的安全性证明带来了无法估量的难度。因此有必要采用一种新的技术来分析和设计协议，UC框架正是适用于这样一个要求的设计分析密码协议的框架。UC框架最初是由Ran Canetti9,10提出的。它的最优秀的性质就是一种模块化设计思想：可以单独设计协议。只要协议满足了UC安全，就能保证其与其他协议并行运行时的安全。协议设计者可以按照如下步骤来构造更为复杂的协议。1) 设计一个“高层的”协议能安全地解决某个复杂任务，假设其中用到的子任务是物理安全的；2) 设计满足UC安全的协议能解决子任务；3) 通过将UC安全的子协议插入到“高层的”协议中来获得一个完整的协议。UC安全框架的核心由3个模型：现实模型、理想模型以及混合模型搭建而成，它的主要证明和技术手段是“仿真”。现实模型描述了协议执行的实际情况，它是由一些交互的运行协议的图灵机（简称ITM）集合（表示协议参与者），外加上一个表示攻击者的ITM构成。理想模型则描述了协议执行的理想情况，此模型可以通过定义理想功能（ideal functionality）F得到所需要的安全任务。混合模型则是以现实模型和理想模型作为基础的。所谓混合模型，因为该模型将现实模型和理想模型进行了一些混合，现实模型中协议可以访问理想模型的某些理想功能。建立起这3个模型之间的桥梁就是“仿真”，将现实模型的安全规约到理想模型的安全。如果协议A和协议B完成同样的功能，那么协议A至少和协议B一样安全。如果攻击者攻击现实模型下协议，不比攻击理想模型下的F获得更大的影响或更多的信息，那么至少是和F一样安全的。为了更好地描述仿真的结果，需要引入环境机Z的概念。环境机Z同样是一个ITM，它代表协议运行的整个外部环境（包括其他并行的协议等）。环境机Z提供给协议所有输入，并可以读取协议所有的输出。用REAL,A,Z(k,z)表示现实模型下环境机Z的输出，而IDEALF,S,Z(k,z)则表示理想模型下环境机Z的输出，其中k是安全参数，z是环境机Z的输入。因此，以上关于“仿真”的说法形式化地表述为：如果对于现实模型中的任何实际攻击者A，都存在一个理想模型中的仿真攻击者S，在任何输入下，现实模型中运行A和协议的环境机Z的输出，与理想模型中运行S和理想功能F的环境机Z的输出是不可区分的，那么至少是和F一样安全的。下面是仿真的形式化定义和UC定理。1) 协议安全仿真协议：如果对于任何实际攻击者A，都存在一个仿真攻击者S，使得等式REAL,S,Z(k,z) REAL,A,Z(k,z)成立，那么称协议安全仿真了协议。2) 协议安全实现理想功能F：如果对于任何实际攻击者A，都存在一个理想攻击者S，使得等式IDEALF,S,Z(k,z) REAL,A,Z(k,z)成立，那么称协议安全实现了理想功能F。3) UC定理：如果协议安全实现了理想功能F，且和F都是的子程序，则组合后的协议/F安全仿真了协议。其中，是F-混合模型下混合协议，/F则表示把中对F的调用都用替代后的协议。3 UC安全的门限签名协议3.1 门限签名理想功能FThSign在这一节，定义门限签名理想功能FThSign，已经描述了理想模型下如何得到所需的门限签名任务。在2006年的欧密会上，Almansa等人提出了一个满足UC安全的前摄门限签名理想功能6，但是在他们定义的功能FThSign06中有以下弱点。首先，FThSign06把签名者集合认为是一个诚实的整体，所以用一个诚实的“用户”替换整个签名者集合。虽然这样的处理使得FThSign06的描述变得简单，但是同时也使得FThSign06无法让每个签名人都得到他们的部分签名，也无法描述单个被攻破用户这些细节行为。其次，FThSign06中签名密钥和验证密钥是由攻击者提供，这样就限制了协议的灵活性。因为在协议执行过程中，应该允许签名密钥和验证密钥根据前面的执行结果变化。而且攻击者还能知道参与者何时签名消息，何时验证签名。最重要一点，Almansa等人并没有证明FThSign06与标准概念下安全性的等价，只是证明了若是不可伪造的，则安全实现了FThSign06，而且其证明中也没有包含门限签名的强壮性。安全实现了FThSign06的门限签名协议仍然不能容忍活跃的攻击者。门限签名理想功能FThSign与FThSign06相比：首先，细分了各个基本模块，这样有助于描述协议的细节行为；其次，FThSign中的攻击者提供子签名函数PS，子签名验证函数PV,子签名联合函数C和门限签名函数V。FThSign是运行存储在本地的算法计算结果，所以攻击者也不知道何时签名者签名消息，何时用户验证何消息。门限签名理想功能FThSign如下所述，基本想法如下。密钥生成。接收到签名者S的输入(KeyGen,sid)后，验证sid=(S,sid)，如果不成立，忽略该请求。否则，把(KeyGen,sid)交给攻击者，在接收到攻击者的输出(Algorithms,sid,PS,PV,C,V)后，其中PS、PV、C、V是多项式时间算法，再把(VerificationAlgorithms, sid,PV,V)输出给S。子签名生成。接收到S的输入(ThSign,sid,m)后，计算=PS(m)并验证PV(m,)=1。如果等式成立，把消息(ThSignature,sid,m,)输出给S并记录(m,PV)；否则，输出error给S并停止。子签名验证。接收到参与者V的输入(ThVerify, sid,m,PV)后，把(ThVerified,sid,m,f)输出给V，其中f按下面的规则计算：若PV=PV，存在记录(m,PV)且PV(m,)=1，令f=1。确保了若PV是注册的公钥，是合法的子签名，则一定通过验证。若PV=PV，不存在记录(m, , PV)，令f=0。确保了若PV是注册的公钥，不是合法的子签名，即这是个成功的伪造子签名，则一定不通过验证。若PVPV，令f=1。确保了如果是被攻破的用户，则他提供的子签名一定通过验证。子签名联合。接收到参与者C的输入(Combine,sid,m,1,PV1, t,PVt)后，若对于每个i都存在记录(m,i,PVi)，则计算=C( 1,t)，并验证PV(m,)=1。如果等式成立，把(Combine,m,V)输出给C并记录(m,V)；否则输出error给C并停止。门限签名验证。接收到参与者V的输入(Verify,sid,m,V)，把(Verified,sid,m,g)输出给V，其中g按照下面的规则计算。若V=V，存在记录(m,V)，且V(m,)=1，令g=1。确保了若V是注册的公钥，是合法的门限签名，则一定通过验证。若V=V，不存在记录(m,V)，令g=0。确保了若V是注册的公钥，不是合法的门限签名，即这是个成功的伪造门限签名，则一定不通过验证若VV，令g=0。确保了就算是被攻破的用户，他也不能注册一个用户集合的门限签名。简单来说，门限签名理想功能FThSign提供一个“注册机”，使得签名者S能注册子签名和门限签名。任何提供了正确验证密钥的用户能检验子签名或门限签名是否已经被注册。它有5类输入，这些输入对应5个基本模块：密钥生成、子签名生成、子签名验证、子签名联合、门限签名验证。3.2 与标准概念下安全性的等价Almansa等人定义的FThSign06并没有证明与标准概念下安全性的等价，他只是证明了等价的充分性，即证明了若协议是不可伪造的，则协议安全实现了FThSign06。而且，他证明时所采用的也是签名方案的安全性，并没有包含门限签名中的重要性质强壮性。本文对于标准概念的安全的定义采用Shoup的定义：一个安全的门限签名协议是指这个签名协议具有强壮性和不可伪造性。定理1 门限签名协议是强壮的和不可伪造的，当且仅当，安全实现了门限功能FThSign。证明 首先证充分性，即需要证明若安全实现了FThSign，则是强壮的和不合伪造的。假设不具有强壮性或不具有不可伪造性，就能构造环境机Z和实际攻击者A，对于任何理想攻击者S，Z都能分辨它是与A和交互，还是与S和FThSign交互。1) 假设不具有伪造性，即存在的一个成功的伪造者B。Z一开始就激活B，并输出从签名者S得到的子签名验证函数PV。一旦S请求签名消息m，Z用输入(Thsign,sid,m)激活S，并把S输出发给B。当B产生伪造的子签名(m,PV)时，Z执行如下：若消息m之前已经签过，Z输出0并停止；否则Z用输入(ThVerify,sid,m,PV)激活验证者V，Z的输出是验证结果。很明显，当Z与A和交互时，因为B能伪造一个子签名，所以Z能以不可忽略的概率输出1。但是，当Z与S和FThSign交互时，Z不可能输出1。2) 假设不具有强壮性。存在的某个被攻破的签名者S能参与门限签名的生成。环境机Z用输入(ThSign,sid,m)激活S，因为他是被攻击者控制，所有的签名都能通过子消息的验证。然后S用伪造的签名(m,PV)参与子签名的联合。从这里可以看出，当Z与A和交互时，因为S能参与联合签名的生成过程，所以Z能以某个不可忽略的概率输出1。但是，当Z与S和FThSign交互时，FThSign并没有记录被攻破的用户S的记录(m,)，Z是不可能输出1的。接下来证充分性。即需要证明若是强壮的和不可伪造的，则安全实现FThSign。同样采用反证法。假设不能安全实现FThSign，是存在Z能分辨它是与D（dummy adversary，完全按照Z的指令运行）和交互，还是与S和FThSign交互。即使具有强壮性，仍然能构造一个攻击者B伪造签名。B可以调用环境机Z，当Z用输入(KeyGen,sid,m)激活参与者S时，B把V传输给Z。当Z用输入(ThSign,sid,m)激活S时，B通过他的子签名生成算法计算出m的子签名。当Z用输入(ThVerify,sid,m,PV)激活参与者P时，B首先检查(m,)是否是伪造的子签名，若是伪造的，则B输出(m,)并停止，否则继续模拟。当Z用输入(Combine,sid,m,1,PV1, t,PVt)激活联合者C时，挑战者B用子签名联合算法计算出m的签名并交给Z。当Z用输入(Verify,sid,m,V)激活参与者P时，B首先检查(m,)是否是伪造的门限签名，若是伪造的，则B输出(m,)并停止。接下来分析B成功的概率。首先用事件X代表B成功伪造了一个子签名或门限签名。很显然，只要事件X不发生，则Z不能分辨它是与运行D的协议交互，还是与运行S的理想功能FThSign交互。但是已经假设Z能以一个不可忽略的概率分辨它是与运行D的协议交互，还是与运行S的理想功能FThSign交互。那么很显然事件X发生的概率也是不可忽略的。4 实现理想功能FThSign4.1 UC安全的门限签名协议已经证明如果Shoup方案中散列函数H()是一个随机预言机，则Shoup方案是一个安全的门限签名方案（即不可伪造的和强壮的）。该方案的安全性基于标准RSA签名方案的安全性。用Shoup方案来实现门限理想功能FThSign。首先把它转变成如下的协议。密钥生成。接收到输入(KeyGen,sid)，验证sid=(S,sid)，如果不成立，则忽略该请求。否则，签名者S调用Dealer以得到他的密钥SKi,和公钥VKi。输出(VerificationAlgorithm,sid,VKi,e)。Dealer的执行如下：随机选择2个大素数p,q，其中p=2p+1, q=2q+1，令N=pq, M=pq。选择RSA指数e，并计算d，使得ed1 mod M。选择Zm上的t维多项式函数aixi，和验证密钥VK=v，计算Ski=f(i) mod M, VKi=vski mod M。子签名生成。接收到输入(ThSign,sid,m)后，令x=H(m)，签名者S计算他的子签名i=x2SKi mod N，并计算这个子签名的证明(z,c)，其中r是随机数，z=Skic+r。输出(Thsignature,sid,m,i)。子签名验证。接收到输入(ThVerify,sid,m,(VKi,z,c)后，验证者V验证，如果成立，输出(ThVerified,sid,m,1)，否则输出(ThVerified,sid,m,0)。子签名联合。接收到输入(Combine,sid, m,1, PV1, t,PVt)，并验证这些子签名的正确性后，联合者C输出(Combined,sid,m,)。门限签名按以下方式计算：。可以很容易计算出a、b，使42a+eb=1，则。门限签名验证。接收到输入(Verify,sid,m,V)，验证y=e mod N。如果成立，输出(Verified, sid,m,1)，否则输出(Verified,sid,m,0)。与FThSign类似，门限签名协议也分为5部分，分别是密钥生成、子签名生成、子签名验证、子签名联合和门限签名验证。因为协议只是在方案的基础上加上sid等通信信息，所以协议与方案可以相互转换，且同样是不可伪造的和强壮的。根据定理1，很容易推出协议具有UC安全性。推论1 由Shoup门限签名方案转变的协议安全实现了门限签名理想功能FThSign。4.2 基于FThSign的应用在这一节中，将介绍如何应用UC框架下的门限签名理想函数FThSign设计 “高层的”的协议。这很好地体现了UC框架的优点：模块化设计思想。其基础就是UC定理：单独设计协议。只要协议满足了UC安全，那么就能保证其与其他协议并行执行时的安全性。对于门限签名理想功能FThSign，同样可以利用UC定理设计其他的“高层的”协议，如前摄门限签名协议。它可以把门限签名功能作为其子任务，因为FThSign假设是物理安全的，所以设计时不需要考虑其门限签名子任务的安全性。然后根据UC定理，把安全实现了FThSign的协议插入协议，替代协议中对FThSign的访问，最后得到的完整协议/F必定安全仿真了协议。而且，在协议的具体化过程中，还可以把满足UC安全的另一个协议插入协议来得到另一个完整协议/F。也就是说，同一个协议可以得到具有不同性质的完整协议，而且这2个实际协议的安全性都不需要重新证明。这就是模块化设计协议的一个十分吸引人的优点。以前摄门限签名协议为例说明上面的思路。首先定义安全的前摄门限签名混合协议，该协议的设计还需要理想更新功能FRefresh的帮助。FRefresh接收的输入是签名者S的消息(Refresh,sid)。验证会话标识sid的有效性后，FRefresh的输出是每个用户更新后的4个多项式时间算法PS、PV、C、V。(FThSign, FRefresh)-混合模型下的前摄门限签名协议PrThSign具体如下。子签名生成。接收到输入(ThSign,sid,m)后，签名者Si首先验证sid=(Si,sid)，如果等式不成立，忽略该请求，否则如下运行。如果是签名Si第一次激活，把(KeyGen,sid)输出给FThSign，并保存FThSign的输出(VerificationAlgo- rithms,sid,PV,V)。如果不是Si第一次激活，Si把(ThSign,sid,m)输出给FThSign，Si能得到FThSign的输出(ThSignature, sid,m,)。子签名验证。接收到输入(ThVerify,sid,m,PV)后，验证者V把(ThVerify,sid,m,PV)输出给FThSign，并输出FThSign给他的结果(ThVerified,sid,m,f)。子签名联合。接收到输入(Combine,sid, m,1, PV1, t,PVt)后，参与者C再把该消息输出给FThSign，并输出FThSign给他的结果(Combined, sid,m,)。门限签名验证。接收到输入(Verify,sid,m,V)，验证者V把(Verify,sid,m,V)输出给FThSign，并输出FThSign给他的结果(Verified,sid,m,g)。密钥更新。接收到输入(Refresh,sid)后，S把(Refresh,sid)输出给FThSign，并保存FThSign提供的结果(Refreshed, sid,PV,V)。PrThSign分为5部分，分别是子签名生成、子签名验证、子签名联合、门限签名验证和更新密钥。每次需要生成和验证子签名、子签名联合、门限签名验证时，协议PrThSign都调用功能FThSign，每次更新密钥时，协议PrThSign则调用FRefresh。因为篇幅的限制，协议PrThSign的安全性证明略去。根据UC定理，用替代协议FThSign后得到的完整协议/FPrThSign的安全性很容易推导。5 结束语本文定义了门限签名协议在UC框架下的安全模型，并证明该安全模型等价于门限签名协议标准概念下的安全性（即不可伪造性和强壮性）。如果方案满足了标准概念下的安全性就确保了该方案还具有UC安全性。相比于Almansa等人在2006年欧密会上提出的门限签名理想功能FThSign06，本文的FThSign不管在协议定义还是安全性证明方面都有一些改进。证明Shoup方案是满足UC安全的，可以很方便地用来设计其他的“高层的”协议，并以前摄门限签名协议为例描述这种设计思路。但是因为篇幅的限制，对于本文得到的前摄门限签名协议只是一个混合模型下的协议，还需要调用某些理想功能。本文提出了设计门限签名协议的模块化思路，但是还有一些不足，如本文考虑的是静态攻击者，攻击者必须在攻击一开始就选择被攻击的用户身份等。在以后的工作中，将继续研究如何完善门限签名协议的UC框架。参考文献：1DESMEDT Y. Society and group oriented cryptography: a new conceptA. CRYPTO87C. Santa Barbara, CA, USA, 1987. 20-127. 2BOYD C. Digital multisignaturesA. Cryptography and CodingC. 1989.241-246.3FRANKEL Y. A practical protocol for large group oriented networksA. EUROCRYPT89C. Houthalen, Belgium, 1989. 56-