非延展水银承诺方案_英文_

非延展水银承诺_英文_ 第 24 卷第 6 期Vol . 24 No . 6 中 国 科 学 院 研 究 生 院 学 报 2007 年 11 月 Journal of the Graduate School of the Chinese Academy of Sciences November 2007 () Article ID :100221175 20070620778210 3 Non2mallea ble mercurial commitment scheme L I Bao XU Hai2Xia L I Hong2Da ( )State Key L aboratory of Inf ormation Security Graduate School of Chinese Academy of Sciences , Beijing 100049 , China ( )Received 30 December 2006 ; Revised 20 April 2007 Xu HX, Li HD , Li B. Non2mallea ble mercurial commitment scheme . J our nal of t he Graduate School of t he Chi nese Academy of Sciences ,2007 ,24( 6) :778,787 Abstract Mercurial commitment scheme is an interesting variation of regular commitment scheme , which additionally allows for a soft decommit stage . The soft decommitments are not required to binding but can () not conflict with the true decommmitments if the true decommmitments exist. In our paper , we consider reusable non2malleable mercurial commitment schemes. Reusable non2malleability is that the adversary accesses to an arbitrary number of commitments , which is a strictly stronger security notion than general non2malleability in which the adversary has access to only one commitment . We adopt the reusability mainly due to the inherent property of mercurial commitment scheme . We introduce the notion of reusable non2malleable mercurial commitment scheme and give a construction based on the multi2trapdoor mercurial commitment scheme . Key words commitment , non2malleable , mercurial , multi2trapdoor CL C TP309 1 Introduction The notion of commitment scheme is one of the most important primitive in cryptography. A commitment scheme involves two probabilistic polynomial time players : the committer and the receiver . It consists of two stages , a commitment stage and an open stage . In the commit stage , the committer sends some string which is called commitment related to a secret input m to the receiver . Later the committer during the open stage may choose to open the commitment thereby revealing m . The commitment scheme must be hiding , i . e . , the receiver access to the commitment cannot compute anything about m . It must also be binding , i . e . , the committer cannot produce a commitment that can be revealed to different messages m and m . To meet various requirements , extra security properties are needed. One of such properties is non2malleability () a concept introduced in Ref . 1 . As a classical example for non2malleable commitments , consider the fair contract bidding. Parties who want to bid on an item commit to their bids first , then commitments revealed and the winner determined. The security goal of non2malleability is to prevent parties from producing bids which related to the bits of others. However , the basic hiding and binding properties cannot ensure to reach the goal . It is well known that many existing commitment schemes are malleable . Naturally , a commitment scheme is non2malleable if ( ) ( ) 3 supported by the National Nature Science Foundation of China 60673073, National 863 project 2006AA01Z427, and Foundation of Graduate ()University of Chinese Academy of Sciences 065001 G †E2mail : hxxu @gucas. ac . cn such an attack is infeasible . Several constructions for non2malleable commitment schemes have been proposed in Refs. 1 ,4 etc .5 Mercurial commitment , proposed by Chase et al . is an interesting variation of regular commitments. The notion is distilled out of the zero2knowledge set constructions of Ref . 6 . A zero 2knowledge set allows a prover to commit to a secret set S and can prove statements of the form x ?S or x | S without information about S leaking. Compared to the conventional commitment schemes , the mercurial commitment schemes admit a relaxation of the binding property. They change the regular open phase into a two2stage opening protocol . One is the soft2open stage which is not binding but cannot conflict with the true decommitment . The other is the hard2open stage which is same as the usual commitments. Any committed value c can either be soft2 and hard2opened only to one message m , or can be soft2opened to arbitrary messages , but it cannot hard2opened at all . Namely , in the first phase , i . e . commitment phase , the committer must decide to soft2commit to nothing or hard2commit to only one value . Moreover the receiver cannot tell apart which kind of commit the sender chose by the hiding property. At TCCπ06 , Catalano et al . in Ref . 9 solved the minimal assumptions of mercurial commitment scheme and proposed efficient constructions for string mercurial commitment . In our paper , we propose the notion of non2malleable mercurial commitments. Here , we adopt the definition in which the adversary sees many commitments , and tries to output a commitment to some related messages , i . e . reusable non2malleable commitment introduced in Ref . 3 . There are two reasons we consider the strictly stronger notion other than the notion where the adversary sees one commitment and tries to produce his own related commitment . First , it is more natural to require non2malleability if the adversary gets any polynomial number of commitments as input . Second , the original applications of mercurial commitment to zero2knowledge sets in which commits to every element in a set implies that the adversary can access to many commitments. In addition to the notion , based on the multi2trapdoor mercurial commitment scheme which discussed in Ref . 7 and one 2time signature scheme , we give a construction of non2malleable mercurial commitments. 2 Preliminaries Notations 211 μ( ) () Negligible functions. A function nis negligible if for every polynomial p ?, there exists an N such that 1 μ( ) for all n > N , n? . ( ) p n Efficient algorithms. In our paper , an efficient algorithm is a probabilistic polynomial time Turing machine . Probabilistic assignments. If S is a probability space , then“x ?S ”denotes choosing an element x at random () () according to S . If A ?is a probabilistic algorithm , then“ a ?A ?”denotes that A outputs the string a . Probabilistic experiments. If A, A and B are events , then Pr[ A; , A : B denotes the probability of ; 1 k 1 k event B happening after events A, , A . 1 k 2time signature scheme One212 A main tool in our construction is one2time signature scheme which is against chosen message attack. The following definition is adapted from Ref . 8 . ( ) Def inition 2 . 1 S G ; Sig ; Veris a one2time secure signature if for every probabilistic polynomial time forger F , the following k ) () ) ( ( Prob [ sk ; vk? S G ; m ? F vk;1 ( ) ( ) ( ) si g ? S i g m ; sk; F m ; si g ; vk= m , si g : ( ) Ver m , si g , vk= 1 and m ? m ] is negligible in k . 中国科学院研究生院学报第 24 卷780 3 Correlative commitment Before proposing our non2malleable mercurial commitments , in this section we first review the relevant ( ) definitions such as trapdoor mercurial commitment , multi2trapdoor mercurial commitment and non2malleable commitment respectively. 311 ( Tra pdoor) mercurial commitment Mercurial commitment was originally introduced in Ref . 5 , here we adopt the definition in Ref . 9 . It consists of the following seven efficient algorithms : )( C = M Com2Gen , HCom , HOpen , HVer , S Com , SOpen , SVer ( ) The first four algorithms MCom2Gen , HCom , HOpen , HVerare same as in regular commitment schemes. k k ? ( ) Mcom2Gen 1 . Key generation algorithm. On input the security parameter 1 , it outputs a public commitment key pk . ? ( ) HComm ; r. The hard2commitment algorithm. On input pk , a message m from the associated message pk space and a random string r , it computes a commitment string c for the message m . ? ( ) HOpenm ; r. The hard2opening algorithm. On input pk , m and r which is the same as used in the pk commitment algorithm , it produces a decommitment value d for the commitment string c . ? ( ) HVerm , c , d. The hard2verification algorithm. On input pk and a message m and two strings c , d , pk ( ) it outputs 1 if it thinks the pair c , dis a valid hard2commitmentΠdecommitment pair for m . ? ( ) S Com; r. The soft2commitment algorithm. On input pk and a random string r , it computes a soft2 pk commitment string c relative to no message m . ? ( ) SOpenm , FLAG ; r. The soft2opening algorithm where m ?M and FLAG ?{ H , S } . It outputs a pk τ τ soft2decommitment to m . If FLAG = H then the soft2decommitment is obtained according to the hard2 ( ) τ commitment c = HComm ; r; If FLAG = S then the soft2decommitment is obtained according to the soft2 pk ( ) commitment c = S Com; r. pk ? ( τ) τ SVerm , c ,. The soft2verification algorithm. It accepts if is a valid proof that c is a hard or soft pk ( ) m . depends on its flagcommitment to For a mercurial commitment , the following requirements must be satisfied : Correctness. For all m ?M ,the following equations : ( ( ) ( ) ) HVerm , HComm ; r, HOpenm ; r= 1 pk pk pk ( ( ) ( ) ) SVerm , HComm ; r, S Openm , H ; r= 1 pk pk pk ( ( ) ( ) ) SVerm , S Com; r, S Openm , S ; r= 1 pk pk pk holds with all but negligible probability. Mercurial Hiding. No PPT adversary can distinguish ( ( ) ( ) ) m , HComm ; r, SOpenm , H ; rfrom pk pk ( ( ) ( ) ) m , S Com; r, SOpenm , S ; r. pk pk ( ππ )Mercurial Binding. It is computationally hard for a PPT adversary A to come up with c , m ,, m , ( τπ ) ) π( τ) ( ) π( resp. c , m ,, m ,such that resp.is a valid hard resp . softdecommitment of c to m and ′is a valid hard2decommitment of c to m′, but m ?m . Namely , it is infeasible to produce a commitment value c can hard or soft open in one way and then hard open in a different way. 10 Trapdoor mercurial commitment scheme is similar to the traditional trapdoor commitment, where the knowledge of the trapdoor enables one to open a commitment in different ways. As to the trapdoor mercurial commitments , the knowledge of the trapdoor enables one to soft and hard open a committed value to arbitrary values. It consists of the following ten efficient algorithms : )( C = TrMCom2Gen , HCom , HOpen , HVer , S Com , S Open , SVer , M Fake , HEquiv , S Equiv Here we omit the detailed definition of trapdoor mercurial commitment scheme which can be found in Ref . 9 . Multi2tra pdoor mercurial commitments 312 A multi2trapdoor commitment scheme firstly introduced in Ref . 4 . We propose the notion of multi 2trapdoor mercurial commitment scheme in Ref . 7 which is a combination of multi 2trapdoor and mercurial commitments. A multi2trapdoor mercurial commitment scheme consists of a family of trapdoor mercurial commitments. Every scheme in the family is trapdoor mercurial commitment as discussed in subsection 311 . The family must have a master trapdoor which can equivocate all the trapdoor mercurial commitment schemes. Every trapdoor mercurial commitment has its own trapdoor which can only equivocate the scheme itself but not any other scheme . Remark that here mentioned equivocation means the mercurial equivocation , Namely the HH equivocation , HS equivocation and SS equivocation. In following , we propose the notion of multi2trapdoor mercurial commitment formally : 7 Def inition 3 . 1 A multi2trapdoor mercurial commitment consists of twelve algorithms: )( Tk g , HCom , HOpen , HVer , S Com , SOpen , SVer , M Fake , HEquiv , S Equiv C = Key2Gen , S el , ? Key2Gen , Sel and Tkg are the same as in multi2trapdoor commitments. ? HCom , HOpen , HVer , S Com , SOpen , SVer are similar to that in mercurial commitment except that the public key is a pair of master public key PK and specific public key pk . The trapdoor key T which can either be master trapdoor TK or specific trapdoor tk is used in the algorithms M Fake , HEquiv , S Equiv to break the binding of multi2trapdoor mercurial commitments. ? ( ) M Fake ; r. The“fake”commitment algorithm. On input PK , pk , T and a random string r , if T PK , pk , T = TK or T = tk it computes“fake”commitment string c which is not associated to any message m . ? ( ) HEquivm ; r. The equivocation algorithm. For any message m , on input PK , pk , T , m and r , if PK , pk , T ( ) T = TK or T = tk it produces a fake decommitment value d for the fake string c = M Fake; r. PK , pk , T ? ( ) S Equiv m ; r. The soft equivocation algorithm. For any message m , on input PK , pk , T , m and r , PK , pk , T τ( ) if T = TK or T = tk it produces a soft2fake decommitment value for the fake string c = M Fake; r. PK , pk , T The requirements of multi2trapdoor mercurial commitments scheme is similar to trapdoor mercurial commitment scheme except that the original mercurial binding is strengthen into the following binding property. ) ( MMBinding. For any PPT adversary A , it firstly selects l strings pk, , pkas the specific keys and 1 l then given a master public key PK generated with the same distribution as generated by Key2Gen and the ( ) ( ) corresponding specific trapdoors tk, tkfor pk, , pkrespectively. Namely , A using the trapdoor , 1 l 1 l information can open ( ( ) ( ) ) m , Hcom m , r, HOpenm , ras PK , pk PK , pk i i ( ( ) ( ) ) m , Hcom m , r, HEquivm , r and PK , pk PK , pk , T i i ( ( ) ( ) ) m , Hcom m , r, S Equivm , r such that PK , pk PK , pk , T i i ( ( ) ( ) )Hver m , Hcom m , r, HOpenm , r PK , pk PK , pk i i ) )( ( ) ( , r = HVer m , Hcom m , r, HEquivm PK , pk PK , pk , T i i ( ( ) ( ) )= SVer m , Hcom m , r, S Equivm , r PK , pk PK , pk , T i i = 1 The probability 中国科学院研究生院学报第 24 卷782 ππ )( Pr[ c , m ,, m ,, pk ? A PK , tk , , tk1 l ( π) ( π ) s . t . HVerm , c ,= HVerm , c ,= 1 PK , pk PK , pk ( πτ )? A ? c , m ,, m ,, pk PK , tk , , tk1 l τ ) ( )( , c ,= 1 , s . t . HVerm , c , d = SVerm PK , pk PK , pk μ( ) m ? m , and pk ? pk,l ] < n , i = 1 , i Remark 1 . The difference between the multi2trapdoor commitment scheme and general commitment scheme focus on the binding property. The secure binding of multi2trapdoor commitment illuminates that for any PPT adversary with trapdoors of some commitment schemes it is still infeasible to equivocate other commitment schemes in the family. 313 Non2mallea ble commitment In this section , we review the reusable non2malleable commitment introduced in Ref . 3 . Non 2malleability is a secure notion concerned with man2in2the2middle attack. Informally , non2malleability means that the adversary cannot obtain an advantage from having access to the execution of commitment protocols compared with the adversary without such access. The notion of reusability implies that the adversary sees many commitments and tries to output a commitment to a related message . We consider two games. In the first game , the adversary outputs his own tuple of committed values after receiving commitments produced by honest party. When receiving openings of the original commitments , the adversary tries to open his own commitments in a way that his messages are related to the original messages. We call the adversary wins if the messages are indeed related. In the second game , the adversary not given the commitments , must try to output related messages without knowing anything about the original ones. We say that a commitment scheme is non2malleable if for any adversary in the first game there exists an adversary induced almost same result in the second game . Now describe the two games more formally. There is a publicly known distribution M on the message space and a randomly chosen public key pk . Define Game 1 as follows. We separate the adversary A into two efficient algorithms A and A . A receives 1 2 1 a tuple of commitments to t messages according to this distribution and outputs a vector of u commitments except that he cannot copy any of the received commitments. A will open the u commitments given t openings of the 2 received t commitments. We denote with S ucc1the probability that a distinguisher D outputs 1 when the two D , A , M vectors of messages are indeed related. k ) () ( S ucc1= Prob [ pk , tk? KG 1 ; m, , m? M ; D , A , M 1 t k r, ) ( ) ( 1 , r?{0 , 1} ; c, d? Comm, r; t i i pk i i ) ( ) ( cwhere ^c , , ^c, ^c? A pk , c, ? c; 1 u 1 1 i t j ) ( ( m^ , ^d, ) , m^ , ^d ? A pk , m, d, , m, d; 1 1 u u 2 1 1 t t ( ) s . t . Ver pk , m^ , ^c, ^d= 1 or m^ = ?: i i i i ( ) D m, , m^ = 1 ] , m, m^ , 1 u t 1 Define Game 2 as follows. Here the adversary A′receives nothing but the public key pk . Namely , the adversary must come up with u messages on its own. We denote with the probability that a S ucc2 D , A ′, M distinguisher D outputs 1 when the two vectors of messages are indeed related. k ) () ( S ucc2= Prob [ pk , tk? KG 1 ; m, , m? M ; D , A ′, M1 t ( ) ) ( m^ , m^ ? A pk; , 1 u m^ ? M ?{ ?} :s . t . i ) ( D m, m^ = 1 ] , , m, m^ , 1 u t 1 ( ) Note that a distinguisher D is admissible if for any input m, , m, m^ , , m^ , its probability of u 1 t 1 outputting 1 does not increase if any message m^ is changed into ?. This means that it is not beneficial the i adversary to refusing open its commitments. ( ) Def inition 3 . 2 A commitment scheme is t , ureusable non2malleable if for every message space distribution M , every efficient admissible distinguisher D , and for every efficient adversary A , there exists an efficient adversary A′such that | S ucc1- S ucc2| D , A , M D , A ′, M 3 is negligible. 4 Non2mallea ble mercurial commitment In this section , we give the definition of non2malleable mercurial commitment and a construction based on multi2trapdoor mercurial commitment . 411 Def inition of non2mallea ble mercurial commitment Compared to general non2malleable commitment , the main distinguishing feature of non2malleable mercurial commitment comes from the novel“soft algorithms”. First , the vector of commitments given to the adversary in Game1 can be formed in two ways. Namely , hard commitment or soft commitment . Accordingly , the opening vector consists of“soft2open”or“hard2open”. Second , consider the special adversary A . A opens all the u commitments he produced as“soft2open”m m only. Namely , A executes the soft2open stage only and refuses to provide“hard2open”of the commitments he m produced. Due to the definition of mercurial commitment any committed value c can be soft2opened to arbitrary messages but then it cannot hard2opened at all . In other words for such kind of adversary A can open the m commitment he produced in any way as desired , specifically , related to the given messages m, , mfor any 1 t relation . Hence it is implausible that A can increase his success probability by refusing hard2open the commitment m he produced. Namely , we view the adversary not providing hard2open as failure . Therefore , for mercurial commitment , the non2malleability changes into the following form : Def inition 411 Define Game1 as follows. We separate the adversary A into two efficient algorithms A , A . A 1 2 1 receives a tuple of commitments to t messages according to this distribution and outputs a vector of u commitments except that he cannot copy any of the received commitments. A will open the u commitments given t openings of 2 the received t commitments. We denote with S ucc1the probability that a distinguisher D outputs 1 when the D , A , M τ π two vectors of messages are indeed related. We denote as the“soft2open”and as the“hard2open”. k ) () ( S ucc1= Prob [ pk , m? M ;, tk? KG 1 , m, D , A , M t 1 k r, )( ) ( d 1 , r?{0 , 1} ; c, ? Comm, r; t i i pk i i ) ( ) ( cwhere ^c, ^c, , ^c? A pk , c, ? c;t j 1 u 1 1 i ) ττ) ( ( , m, d; m^ , ^ , m^ , ^ ? A pk , m, d, , t t 1 1 u u 2 1 1 ( ππ) ( m^ , ^ ,, m^ , ^ ? A pk , m, d,) , m, d; 1 1 u u 2 1 1 t t τπwhere d= or ; i i i ( π) ( τ) s . t . HVer pk , m^ , ^c, ^ = SVer pk , m^ , ^c, ^ = 1 i i i i i i or m^ = ?: i ) ( m^ = 1 ] , D m, m, m^ , , t 1 u 1 Game2 is the same as in definition 3 . 中国科学院研究生院学报第 24 卷784 k ) () ( S ucc2= Prob [ pk , t? KG 1 ; m, , m? M ; D , A ′, Mk 1 t ( )) ( m^ , m^ , ? A pk; 1 u s . t . m^ ? M ?{ ?} :i ( ) D m, , m, m^ , , m^ = 1 ] 1 t 1 u ( ) A mercurial commitment scheme is t , ureusable non2malleable if for every message space distribution M , every efficient admissible distinguisher D , and for efficient adversary A , there exists an efficient adversary A ′ such that | S ucc1- S ucc2| D , A , M D , A ′, M is negligible . Remark 2 . We focus on Game1 . The commitments c, cgiven to A can be formed in hard2commit or soft2 , 1 t 1 commit. As a result , the openings given to A may τ π be or accordingly. In non2malleable mercurial 2 commitment , the adversary A must open the commitments he produced twice , i . e . soft2open and hard2open. 2 ^ ^ ^ ^ ) ( ( ) ( ) ( ) For every message m^ , there are four cases ?, ?, m, ?, ?, m, m, m, where the first i i i i i element is the soft2open and the second is hard2open. In first case , we set m^ = ?. In second case , we set m^ = i i ? due to the illustration in the beginning of the section. In third case , the adversary cannot provide the soft2open. This case happens with negligible probability for proper mercurial commitment which means that the soft2open is part () of hard2open introduced in Ref . 9 . Although almost all the known construction are“proper”, for completeness , ^ we still consider this case in which we set m^ = m. Intuitively , hard2commit and hard2open consist a regular i i commit algorithm , regardless of soft algorithm , our definition must coincide with the normal non2malleability. In ^ forth case , we set m^ = m. Note that duo to the definition of mercurial commitment , the two results of soft2open i i and hard2open must equal . 412 Construction of non2mallea ble mercurial commitment scheme In this subsection we construct a reusable non2malleable mercurial commitment scheme NMMCom based on multi2trapdoor mercurial commitment scheme and one2time signature scheme . Construction 1 Key2Gen : The public key of the non2malleable scheme includes three elements. ()1 the master public key PK for a multi2trapdoor mercurial commitment scheme ; ()2 the description of a one2time signature scheme ; () 3a collision2resistant hash function H from the set of verification keys vk of the one2time signature scheme , to the set of specific public keys pk in the multi2trapdoor mercurial commitment scheme . ( ) Hard2Comm : the committer selects a key pair sk ; vk for a one2time signature scheme and computes the ( ) ( ) public key pk = H vkand computes HCom m ; r, where HCom denotes the hard2commit algorithm in the PK , pk multi2trapdoor mercurial commitment scheme , the following algorithms HOpen , HVer , S Com , SOpen , SVer have the ( ) ) ( same meaning. The hard2commitment string is vk , HCom m ; r. PK , pk ) ( Soft2Comm : the committer uses the key pair sk , vkselected in Hard2Comm , the soft2commitment string is ( ( ) ) vk , S Com ; r. PK , pk ( ) ( ( ) ) ) ( Hard2Open : outputs HOpen m ; r, Sig HCom m ; r. The hard2open consists of two parts , PK , pk PK , pk one is hard2open information in multi2trapdoor mercurial commitment scheme and the other is a signature on ( ) HCom m ; r. PK , pk ( ) ( ( ) ) ) ( Soft2Open : outputs SOpen m ; r, Sig S Com ; r. The soft2open consists of two parts , one is PK , pk PK , pk ( soft2open information in multi2trapdoor mercurial commitment scheme and the other is a signature on S Com ; PK , pk ) r. ( ) ) ( ) ( ( Hard2Ver : accept vk ; HCom m ; rif and only if pk = H vk , the signature is valid and HVer m , PK , pk ( ) ( ) ) HCom m ; r, HOpen m ; r= 1. PK , pk PK , pk ( ) ) ( ) ( ( Soft2Ver : accept vk , S Com ; rif and only if pk = H vk , the signature is valid and SVer m , PK , pk ( ) ( ) ) S Com ; r, SOpen m ; r= 1. PK , pk PK , pk To prove the above construction is non2malleable mercurial commitment , we need the following lemma1 which states that the adversary A cannot hard2open and soft2open the commitments he produced in two different ways even when seeing equivocations of other commitments. Lemma 1 For any adversary A who attacks the above non2malleable mercurial commitment : k O ) () ( τ τ π π ) ( ) ( Prob [ PK , T K? KG 1 ; c ,,,,? A PK; 1 2 1 2 ( τ) ( π) m? S of t2Open c ,; m? Hard2Open c ,; 1 1 1 1 ( τ) ( π) m? S of t2Open c ,; m? Hard2Open c ,:2 2 2 2 m??? m??? m? m]1 2 1 2 is negligible . Here O is an oracle acts like the following : ( ) ( ) ( ) On query , answer or ; where chosen m , rHcom m ; rScom rHcom or Scom depends on the honest committerπs algorithm. ( ) ( ) ( ) ( ) On query HEquiv , c , m, answer HEquiv c , m; On query S Equiv , c , m, answer S Equiv c , m. The adversary A cannot copy any commitment produced by O as his output . Proof . The lemma shows that a commitment c produced by A , which is different from any commitments produced by O , cannot open to two distinct and correct messages even given different equivocate messages vector of some commitment vector produced by O. Our proof is by reduction to the security of multi2trapdoor mercurial binding and unforgeability of one2time signature scheme . ^) ( Assume that A has a non2negligible probability of opening c = vk , ^c in two different ways , there are two cases : ^() t , where vkis produced by O. Because of the collision2resistance of H , we obtain , 1vk ?vk, i = 1 ,i i ^ that pk ?pk; for i = 1 , 2 ,, t . Hence using algorithm A , we can hard2equivocate and soft2equivocate the i commitment of a new scheme different from the schemes whose specific trapdoors are accessed to O. Contradiction to the MM secure binding property of multi2trapdoor mercurial commitment . ^() 2vk = vk. Note that c is not produced by O , so it must be ^c ?c. By assumption that A can open c = j j ^( ) vk , ^c successfully , thus A can provide a signature on ^c different from the signature on cincluded in Oπs j answer . Contradiction to the unforgeability of one2time signature scheme . Now we turn to our main result stated in Theorem 1 . Theorem 1 NMMCom in construction 1 is a non2malleable mercurial commitment scheme . Proof. To show NMMCom is non2malleable what we need is for any adversary A in Game1 , construct an ( ) adversary A′in Game2 such that | S ucc1- S ucc2| is negligible . Let t kbe an upper bound on its D , A , M D , A ′, M A running time . For any adversary A , construct algorithm A ′as follows : () 1A′selects a public key for NMMCom , and stores the secret key. Thus A′knows TK and can equivocate any commitments. () A′selects t messages according to the distribution M and computes the commitments c,2 , c. 1 t 中国科学院研究生院学报第 24 卷786 Without loss of generality , we assume A′can access to commit oracle . Namely the commitments c,, care 1 t hard2com or soft2com depends on the action of honest committer . For simplicity , we can also assume that every message in M with an identity flag“H”or“S”. () ) ( cto A , which outputs ^c, , ^c. Notice that up to this point , by the , 3A′feeds PK and c, t 1 1 u 1 hiding property , i . e . hard2com and soft2com are computational indistinguishable , the view of A′is identical to that of A . Thus the distribution of A πs output will be the same in both games. 1 - 1 () ( )ε ( ) 4A′runs kt kkcopies of A in order to open as many of A πs commitments as possible . On A 2 1 each copy , A′samples t messages from M and uses TK to equivocate the commitments c,, c. A′sets m^ to 1 t i th the first opening different from ?. If in all the copies , the iposition is ?, A′sets m^ = ?. i - 1 ε( ) ( ) A commitment is bad , if the probability that A opens it is less than k ?t k ; otherwise it is good. 2 A ( ) Since t kis an upper bound on the number of commitments A can produce , the probability that any bad A 1 - 1 ε( ) ( )ε ( )commitment will be correctly opened by A bounds by k. On the other hand since A′runs kt k k 2 A copies of A , the probability that A opens all good commitments is overwhelming. 2 2 () () Thus except than with negligible probability : 1A does not open any bad commitment in Game1 ; 2A′ 2 opens all good commitments in Game2 . Hence , the only way that A′could do worse than A is if D outputs 1 with 2 significantly larger probability in Game1 than in Game2 . This means that for at least good commitment m? contains 3 33 3 m′, and m? contains such that m ?m and m , m ? ?. By Lemma1 , this occurs with negligible m probability. Thus we conclude our proof . Remark 3 In fact our proof reaches the stronger result that the algorithm A′does not depend on the distinguisher D . Namely , for any adversary A , there exists an algorithm A′, such that for any D the result is obtainable . However , for generality , our definition adopts the regular form. 5 Concl usions Non2malleability is an particular security requirement and have many applications. For the new primitive , mercurial commitment , we propose the non2malleable notion in this paper . The main difference from regular non2 malleability lies in the soft algorithm which complicate our notion. Based on multi2trapdoor mercurial commitment and one2time signature scheme , we present a construction which can be proved satisfying the notion of non2malleable mercurial commitment . References () 1 ] Dolev D , Dwork C , Naor M. Non2malleable Cryptography. SIAM J ournal on Computing , 2000 , 30 2: 391,437 Crescenzo GD , Ishai Y , Ostrovsky R. Non2interactive and non2Malleable Commitment . In : Proceedings of the 30th ACM Symposium on Theory of 2 ] Computing. ACM Press , 1998 . 141,150 Damgard I , Groth J . Non2interactive and reusable non2malleable commitment schemes. In : Proceedings of the 35th ACM Symposium on Theory of 3 ] Computing. ACM Press , 2003 . 426,437 Gennaro R. Multi2trapdoor commitments and their applications to non2malleable protocols. In : Advances in Cryptology2CRYPTO 2004 . Springer2 4 ] verlag , 2004 . 220,236 Chase M et al . Mercurial commitment with applications to zero2knowledge sets. In : Advances in Cryptology2EUROCRYPT 2005 . Springer2verlag , 5 ] 2005 . 422,439 Micali S , Rabin M , Killian J . Zero2knowledge sets. In : Proceedings of the 44th IEEE Symposium on Foundations of Computer Science . IEEE 6 ] Computer Society , 2003 . 80,91 ( )Xu H , Li H , Li B. Multi2trapdoor mercurial commitment scheme submitted 7 ] Goldwasser S , Micali S , Rivest R. A digital signature scheme secure against adaptive chosen2message attacks. SIAM J ournal on Computing , 8 ] () 1988 , 17 2: 281,308 Catalano D , Dodis Y , Visconti I. Mercurial commitments : minimal assumptions and efficient constructions. In : The third Theory of Cryptography 9 ] conferenceTCC , Spinger2verlag , 2006 . 120,144 () Brassard G , Chaum D , Crepeau C. Minimum disclosure proofs of knowledge . J ournal of Computer and System Sciences , 1988 , 37 2:156,18910 非延展水银承诺方案 徐海霞李红达李宝 ( ( ) )信息安全国家重点实验室 中国科学院研究生院,北京 100049 摘 要 水银承诺方案是一般承诺方案的一种有趣变形 . 水银承诺方案中增加了 soft 解承诺阶段 , soft 解承诺阶段所公开的解承诺值不要求绑定性但是不能与真实的解承诺值冲突. 讨论了多重非延展水银 承诺方案 . 通常意义的非延展性是指敌手只允许存取一个承诺值 ,多重非延展性是指敌手可以存取任意 数量的承诺值 . 已有结论说明多重非延展性是严格强于通常非延展性的安全性概念. 采用多重非延展 性的概念在于水银承诺方案本身固有的性质 ,给出多重非延展水银承诺方案的概念 ,以及基于多陷门水 银承诺方案的一个具体构造. 关键词 承诺 ,非延展 ,水银 ,多陷门