（基础数学专业论文）rsa+verifiable+signature+sharing+scheme+made+simple.pdf

摘要 由f r a n k l i n 和r e i t e r 在文献 3 1 中介绍的可验证签名分享( v s ) 是多方安全 计算的一个非常简单的方法，可被用于r s a 可验证签名分享v z s 可使 得数字签名的接收者( 并不一定是该签名原来的签名者) 在1 1 个参与者中分 享这个签名本篇文章用到了 1 j 1 中的方法，它几乎不基于任何的数学结构 和复杂的子协议它能生成在对付混合型敌手时是安全的协议 在我们新的r s av e s 方案中，签名的接收者将用门限加密系统将签名 s 加密然后他将消息m 和v s = e e k ( s ) 发送给这些参与者，其中e 为加 密方案的公钥而将私钥d k 用文献【1 】中的多方安全计算方法在这些参与 者中分享我们的方案在少数参与者的情况下效率很高，应用性很强 关键词数字签名，混合型敌手，可验证签名分享，多方安全计算 a b s t r a c t av e r ys i m p l ea p p r o a c ht os e c u r em u l t i - p a r t yc o m p u t a t i o ni su s e dt os h a r er s a v e r i f i a b l es i g n a t u r e v e r i f i a b l es i g n a t u r es h a r i n g ( v e s ) w a si n t r o d u c e db yf r a n k l i n a n dr e i t e r 3 】v z se n a b l e st h er e c i p i e n to fad i g i t a ls i g n a t u r ew h oi sn o tn e c e s s a r i l y t h eo r i g i n a ls i g n e r t os h a r et h a ts i g n a t u r ea m o n gnp l a y e r ss ot h a tas u b s e to ft h e m c a nl a t e rr e c o n s t r u c ti t t h ea p p r o a c ht os e c u r em u l t i p a r t yc o m p u t a t i o ni sb a s e do n e s s e n t i a l l yn om a t h e m a t i c a ls t r u c t u r eo rs o p h i s t i c a t e ds u b - p r o t o c o l s i tn a t u r a l l y y i e l d sp r o t o c o l ss e c u r ef o rm i x e d ( a c t i v ea n dp a s s i v e ) c o r r u p t i o no ng e n e r a l ( a s o p p o s e dt ot h r e s h o l d ) a d v e r s a r ys t r u c t u r e s i no u rn e wr s av e ss c h e m e ，t h er e c i p i e n to ft h es i g n a t u r ew i l le n c r y p ts u s i n gat h r e s h o l dc r y p t o s y s t e m t h e ns h eg i v e st ot h ep l a y e r st h ev a l u ema n d o s = 如耳( s ) ，w h e r eei sap u b l i ck e ye n c r y p t i o ns c h e m e sa n dt h ed e c r y p t i o nk e y d ki ss h a r e da m o n gt h ep l a y e r su s i n gt h ea p p r o a c ht om u l t i - p a r t yc o m p u t a t i o n 1 o u rs c h e m ei se f f i c i e n ta n dp r a c t i c a lf o ras m a l ln u m b e ro fp l a y e r s k e y w o r d s d i g i t a ls i g n a t u r e m i x e da d v e r s a r yv e r i f i a b l es i g n a t u r es h a r e m u l t i - p a r t yc o m p u t a t i o n 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：季融佛 日期：堋年乡月饼日 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交 论文的电子版和纸质版有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅有权将学位论文的内容 编入有关数据库进行检索有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 学位论文作者签名：置翮佛 日期：哪年号月垮日 c h a p t e r1 i n t r o d u c t i o n v e r i f i a b l es i g n a t u r es h a r i n g ( v e s ) w a si n t r o d u c e db yf r a n k h na n dr e i t e r 【3 】v e se n a b l e st h er e c i p i e n to fad i g i t a ls i g n a t u r ew h oi sn o tn e c e s s a r i l yt h e o r i g i n a ls i g n e r ，t os h a r et h a ts i g n a t u r ea m o n g 佗p l a y e r ss ot h a tas u b s e to ft h e mc a n l a t e rr e c o n s t r u c ti t i n 【3 1 ，e f f i c i e n tp r o t o c o l sw e r eg i v e nf o rr s a ，r a b i n ，e i g a m a l ， s c h n o r ra n dd s ss i g n a t u r e s h o w e v e rt h e kr s aa n dr a b i nv e sp r o t o c o l sw e r e s u b s e q u e n t l yb r o k e ni n 【4 】a l s ot h e kd s sv e sa c h i e v e so n l yah e u r i s t i cf o r mo f s e c u r i t y au n i f y i n ga p p r o a c ht ov e s ，b a s e do nh o m o m o r p h i s m so fs e c r e ts h a r i n g s c h e m e s ，i ss h o w nb yb u r m e s t e r 【6 】t h ea p p r o a c hi sv e r ye l e g a n ta n da l s os e c u r e ， h o w e v e ri t sg e n e r a l i t yd o e sn o ty i e l de x t r e m e l ye f f i c i e n tp r o t o c o l sw h e na p p h e dt o t y p i c a lr e a l - l i f es i g n a t u r es c h e m e s s e c u r ef u n c t i o ne v a l u a t i o nw a si n t r o d u c e db yy a oi n 5 】l e tp = 【只，r ) o f 佗p l a y e r st oc o m p u t ea na r b i t r a r ya g r e e df u n c t i o no ft h e i rp r i v a t ei n p u t s e v e ni f a l la d v e r s a r ym a yc o r r u p ta n dc o n t r o ls o m eo ft h ep l a y e r si nv a r i o u sw a y s s e c u r i t y i nm u l t i p a r t yc o m p u t a t i o nm e a u st h a tt h ep l a y e r s i n p u t sr e m a i ns e c r e t ( e x c e p t f o rw h a ti sr e v e a l e db yt h ei n t e n d e dr e s u l t so ft h ec o m p u t a t i o n ) a n dt h a tt h e r e s u l t so ft h ec o m p u t a t i o na r eg u a r a n t e e dt ob ec o r r e c t m o r ep r e c i s e l y , s e c u r i t yi s d e f i n e dr e l a t i v et oa ni d e a l - w o r l ds p e c i f i c a t i o ni n v o l v i n gat r u s t e dp a r t y ：a n y t h i n g t h ea d v e r s a r yc a na c h i e v e di nt h er e a lw o r l dh ec a l la l s oa c h i e vi nt h ei d e a lw o r l d 1 1r e v i e wt h ea d v e r s a r yc a p a b i l i t i e s t h ep o t e n t i a lm i s b e h a v i o ro fs o m eo ft h ep l a y e r si su s u a l l ym o d e l e db yc o u s i d - e r i n gac e n t r a la d v e r s a r yw i t ha no v e r a l lc h e a t i n gs t r a t e g yw h o c a nc o r r u p ts o m eo f t h ep l a y e r s t w od i f f e r e n tn o t i o n so fc o r r u p t i o n ，a c t i v ea n dp a s s i v ec o r r u p t i o n ，a r e u s u a l l yc o n s i d e r e d p a s s i v ec o r r u p t i o nm e a n st h a tt h ea d v e r s a r yl e a r n st h ee n t i r e i n t e r n a li n f o r m a t i o no ft h ec o r r u p t e dp l a y e r s ，b u tt h ep l a y e r sc o n t i n u et op e r f o r m t h ep r o t o c o lc o r r e c t l y s u c hp l a y e r sa r es o m e t i m e sa l s oc a l l e ds e m i - h o n e s t a c t i v e c o r r u p t i o nm e a n st h a tt h ea d v e r s a r yc a nt a k ef u l lc o n t r o lo ft h ec o r r u p t e dp l a y e r s a n dm a k et h e md e v i a t ea r b i t r a r i l yf r o mt h ep r o t o c 0 1 i fn oa c t i v ec o r r u p t i o n sa r e c o n s i d e r e d ，t h e nt h eo n l ys e c u r i t yi s s u ei st h es e c r e c yo fp l a y e r si n p u t s 2 硕士毕业生毕业论文2 0 0 8 年 as t a t i ca d v e r s a r ym u s td e c i d eb e f o r et h ee x e c u t i o no ft h ep r o t o c o lw h i c hp l a y - e r sh ec o r r u p t s ，w h i l ea na d a p t i v ea d v e r s a r yc a nc o r r u p tn e wp l a y e r sd u r i n gt h e p r o t o c o l ，a sl o n g8 8t h et o t a ls e to fc o r r u p t e dp l a y e r s 这s t i l la d m i s s i b l e 。i nt h i s p a p e rw ec o n s i d e rs t a t i ca d v e r s a r ya n dt h et h ea d v e r s a r y sc o r r u p t i o nc a p a b i l i t i e s c o u l db es p e c i f i e db ya d v e r s a r ys t r u c t u r ea si n 【1 1 am i x e da d v e r s a r yi s 髓a d v e r - s a r yw h oc a l lc o r r u p ts o m ep l a y e r sp a s s i v e l ya n ds o m ep l a y e r sa c t i v e l y t h en o t i o n i sd e s c r i b e di nd e t a i li ns e c t i o n2 t h er s av x ss c h e m e l e tb o bb et h es i g n e r ，a l i c eb et h er e c i p i e n to f t h es i g n a t u r ea n d 岛，rb et h ep l a y e r s l e t ( ，如) b eb o b sr s ap u b l i ck e y t h em a t c h i n gs i g n i n gk e yi s8 bs u c ht h a t8 b v b 一1r o o d 蛰( ) w e 硇q s u m et h e s t a n d a r d ”h a s h - a n d - s i g n p a r a d i g m a l i c er e c e i v eam e s s a g em f r o mb o ba n db o b s s i g n a t u r es = 仇8 口m o d n bo ni tw h e r em = h ( m 1 f o rs o m ec o l l i s i o n - r e s i s t a n th a s h f u n c t i o nh a l i c cw a n tt ov e r i f i a b l ys h a r et h ev a l u esa m o n gt h ep l a y e r s 最，最， t h a ti s a tt h ee n do ft h es h a r i n gp h a s et h ep l a y e r sm u s tb ea s s u r e dt h a tt h e yh o l d s h a r e so fb o b ss i g n a t u r eo nm i nt h i sp a p e rw ep r e s e n tan e wp r o t o c o lf o rr s av sb a s e do ns i m p l es e c u r e m u l t i - p a r t yc o m p u t a t i o n ，w h i c hi sp r o v a b l ys e c u r ea g a i n s tam i x e da d v e r s a r y i n o u rn e ws c h e m e ，t h er e c i p i e n to ft h es i g n a t u r ew i l le n c r y p tsu s i n gat h r e s h o l d c r y p t o s y s t e m t h e ns h eg i v e st ot h ep r o x i e st h ev a l u ema n d 岛= e e k ( s ) ，w h e r e ei sap u b l i ck e ye n c r y p t i o ns c h e m e sa n dt h ed e c r y p t i o nk e yd ki ss h a r e da m o n gt h e p r o x i e su s i n gt h ea p p r o a c ht om u l t i - p a r t yc o m p u t a t i o n o u rs c h e m ei se f f i c i e n t a n dp r a c t i c a lf o ras m a l ln u m b e ro fp l a y e r s 。 s e v e r a lc o m m u n i c a t i o nm o d e l sa r ec o n s i d e r e di nt h el i t e r a t u r e i nt h es t a n - d a r ds y n c h r o n o u sm o d e l ( f o ri n f o r m a t i o n - t h e o r e t i cs e c u r i t y ) ，a n yp a i ro fp l a y e r sc a n c o m m u n i c a t eo v e rab i l a t e r a ls e c u r ec h a n n e l 。s o m ep a p e r sa 鹬u m et h ea v a i l a b i l i t y o fab r o a d c a s tc h a n n e lw h i c hg u a r a n t e e st h ec o n s i s t e n c yo ft h er e c e i v e dv a l u e si fa s e n d e rs e n d sav a l u et os e v e r a lp l a y e r s ，b u ti np r a c t i c eab r o a d c a s tc h a n n e lm u s tb e s i m u l a t e db ya ( q u i t ei n e f f i c i e n t ) p r o t o c o la m o n gt h ep l a y e r s 羔2r e l a t e dw r o r k 。 s o m ei d e a si no u rn e wr s av z ss c h e m eh a v ea p p e a r e dp r e v i o u s l yi nt h el i t - 3 e r a t u r ea l t h o u g hi nd i f f e r e n tc o n t e x t sa n dw i t hd i f f e r e n tu s a g e p e r f o r m i n gs e c r e t s h a r i n gb ye n c r y p t i n gav a l u ew i t has y m m e t r i ck e yt h a ti ss h a r e da m o n gt h ep l a y e r s a p p e a r e df i r s ti n 7 】a 8aw a yt os h o r t e nt h es i z eo f s h a r e so nc o m p u t a t i o n a u ys e c u r e s e c r e ts h a r i n gs c h e m e s t h es p e c i f i ci d e ao fu s i n gt h r e s h o l dc r y p t o s y s t e mt o ”b o o t s t r a p ”s e c r e ts h a r i n ga p p e a r e di n 【8 】t h ei d e ae n c r y p t i n gas i g n a t u r ea n dt h e n p r o v i n gz kt h a tt h ee i p h e r t e x tc o n t a i n sav a l i ds i g n a t u r eh a sa p p e a r e di ns e v e r a l p l a c e s 【9 ，l o i n 【1 0 】i tw a sp r o p o s e da sag e n e r a lp a r a d i g mt oc o n s t r u c tu n d e n i a b l e s i g n a t u r e sb u tt h es p e c i f i ce f f i c i e n ts o l u t i o nw o r ko n l yf o re i g a m a l - l i k es i g n a t u r e s c h a p t e r2 p r e l i m i n a r i e s 2 1s t r u c t u r e s 。 d e f i n i t i o n1c o n s i d e raf i n i t es e tp w ec a l las u b s e t o yt h ep o w e rs e t2 尸o i p a ( m o n o t o n e ) s t r u c t u r e rp 万珏i sc l o s e du n d e rt a k i n gs u b s e t s i e ，黟s i i a n ds f si m p l i e sg 毫1 7 w ed e f i n ea ( c o m m u t a t i v ea n da s s o c i a t i v e ) o p e r a t i o no n s t r u c t u r e s , d e n o t e dh ：h lu 2i st h es t r u c t u r ec o n s i s t i n go fa l lu n i o n so f o t i , ee l e m e n t 蟛h la n do n ee l e m e n to y l - 1 2 ，i e ，蠢li j h 2 ：= & u 岛：曼i i ，岛珏 。s t r u c t u r e s w i l lb ed e s c r i b e db yl i s t i n go n l yt h em a x i m a ls e t s ，t h e i rs u b s e t sb e i n gu n d e r s t o o da s b e t o n 毋n gt ot h es t r u c t u r e 。 t h es i z e n o fas t r u c t u r ei ii st h en u m b e ro fm a x i m a le l e m e n t s 2 。2 s e c r e c ys t r u c t u r e s ，a d v e r s a r ys t r u c t u r e sa n dm o d e l as e c r e t s h a r i n gs c h e m ea l l o w sad e a l e rt os h a r eas e c r e ta m o n gas e tp2 只 。，只 鹾骼p l a y e r ss u c ht h a to n l yc e r t a i nq u a l i f i e ds u b s e t so fp l a y e r s 淞r e - c o n s t r u c tt h es e c r e t ，i e ，a r eq u a l i f i e d ，w h i l ec e r t a i no t h e rs u b s e to fp l a y e r so b t a i n n oi n f o r m a t i o na b o u tt h es e c r e t ，i e ，a x ei g n o r a n t as e c r e t - s h a x i n gs c h e m ei so b u - a l l ys p e c i f i e db yt h es o - c a l l e da c c e s ss t r u c t u r ei ，t h ec o l l e c t i o no fq u a l i f i e dp l a y e r s u b s e t i no u rc o n t e x t ，i ti sm o r en a t u r a lt oc h a r a c t e r i z eas e c r e t - s h a r i n gs c h e m e b yt h es e c r e c ys t r u c t u r e c o n s i s t i n go ft h ec o l l e c t i o no fi g n o r a n tp l a y e rs u b s e ta n d o b v i o u s l y 一2 v r a sm e n t i o n e de a r l i e r 箍ag e n e r a l i z a t i o no fs p e c i f y i n gt h ea d v e r s a r y sc a p a b i l i - t i e sb yac o r r u p t i o nt y p ea n da na d v e r s a r ys t r u c t u r eam e a n i n gt h a tt h ea d v e r s a r y c a l lc h o o s eo n eo ft h es e t si naa n dc o r r u p tt h e s ep l a y e r s 。f o rp a s s i v ec o r r u p t i o nw e c a l la l s oc a l lt h i ss t r u c t u r et h es e c r e c ys t r u c t u r er a t h e rt h a nt h ea d v e r s a r ys t r u c t u r e 。 d e f i n i t i o n 2c o n s i d e rap l a y e rs e tpa n dt w os t r u c t u r e sa 艺2 p a ( e ，) - a d v e r s a r yi sc a l l e dam i x e da d v e r s a r y 蘧t h ea d v e r s a r yc a nc o r r u p ts 撕ep l a y e r s p a s s i v e l ya n ds o m ep l a y e r sa c t i v e l y , 0 , 8l o n ga st h es e tao ya c t i v e l yc o r r u p t e dp l a y - e 孵a n d 挠es 8 嚣o yp a s s i v e l yc o r ru p t e dp l a y e r ss a t i s f yb o t ha aa n d ( a u b ) e w ea s s u m et h a ta l i c ea n dt h ep l a y e r sa r ec o n n e c t e db yaf u l ln e t w o r ko fp r i v a t e 5 c h a n n e l sa n dab r o a d c a s tc h a n n e l 。w e8 s s t l m et h ea d v e r s a r yi s 鑫p r o b a b i l i t yp o 妒 n o m i mt i m e da n ds t a t i c ( ，) * a d v e r s a r ya n dt h ec o m m u n i c a t i o ni ss y n c h r o n o u s 2 。3 b a s i ct o o l s 2 。3 。1v 积i f i a b l es e c r e ts h a r i n g a sm e n t i o n e da b o v e & s e c r e t s h a r i n gs c h e m ei su s e l e s si fn o ta l lp l a y e r sc a nb e a s s u m e dt ob e h a v ec o r r e c t l y af i r s tp r o b l e mi st h a ts o m ep l a y e r sm a yc o n t i b u t e f a l s es h a r e sd u r i n gr e c o n s t r u c t i o n t h i sc a l lb es o l v e db yd i s t r i b u t i n gt h es e c r e t i nar e d u n d a n tm a n n e r ，a l l o w i n gf o re r r o rc o r r e c t i o n 。s i n c et h i sr e q u i r e st h es e to f s h a r e st os a t i s f y 鑫c e r t a i nc o n s i s t e n c yc o n d i t i o n ，as e c o n dp r o b l e ma r i s e s ，n a m e l y t h a t 鑫c h e a t i n gd e a l e rc a l ld i s t r i b u t ei n c o n s i s t e n t s h a r e s v e r i f i a b l es e c r e t - s h a r i n g s o l v eb o t ht h e s ep r o b l e m e s ， d e f i n i t i o n3a 雠蝴a b l es e c r e t s h a r m g ( v s s ) s c h e m e o r 穗s e t 尹o lp l a y e r s 删弧 s e c r e c ys t r u c t u r e a n ds e c u r e 衔a d v e r s a r ys t r u c t u r eac o n s i s t sq | t w op r o t o c o l s , s h a r ea n dr e c o n s t r u c t , s u c h 绕蠢胡孵嚣gt h ea d v e r s a r yc o r r u p t sp l a y e r sa c c o r d i n g 协，t h ef o l l o w i n gc o n d i t i o n sh o 堀：。 1 。蓼s h a r et e n i n a 渤s n c 扰s s u u y , t h e nt h er e c o n s t r u e t 交mp r o t o c o l 菇赫 t h es a m ef i x e dv a l u e 供a l lp o s s i b l ea d v e r s a r ys t r a t e g i e s , i e - t h ed e a l e ri s c o m m i t t e dt oas i u g l ev a l u e 。 浮 凳堪t h ed e a l e ri sh o n e s td u r i n g8 h a r e - t h e nr e c o n s t r u c t i o na l w a y sy i e l d sh i s i n p u tv a l u e 魏可t h ed e a l e ri sh o n e s 南麟e nt h ea d v e r s a r yc a n n o to b t a i na n y 识如r m 穗锈d 住a b o u t t h es h a r e ds e c r e t i n 黥v s ss c h e m e ( s e ef i g u r e 圭a n d2 ) i s 黔v e n , w h i c hi ss e c u r ea g a i n s to f 攘( 鬈，盎) 一a d v e r s a r y , p r o v i d e dt h a t 嚣a n d s a t i 毋t h ef o l o w i n gc o n d i t i o n ： p 譬窆心a t j 王) l e t 奄b et h en u m b e ro fm a x i m a ls e t si n ，i e ，= 避”，噩 ，a n dl e t 夏辩 p 霉b et h ec o m p l e m e n to ft h es e t 墨+ t h ed e a l e rw i l ls h a r e 释s e c r e t 器a m o n gt h e p l a y e r sw h e r esi sar a n d o m d e m e n ti nad o m a i nd 。 6硬士毕业生毕业论文 2 0 0 8 拒 t h ef o l l o w i n gt h e o r e mg i v e st h es t r o n gc o n d i t i o n ( 1 ) f o rv e r i f i a b l es e c r e t - s h a r i n g 翅b ep o s s i b l e 。t h ee f f i c i e n c yo ft h ep r o t o c o li sp o l y n o m i a li n | l ，a n d | i n o t h e rw o r d s ，ac h e a t i n gp l a y e rs e tac a n n o tv i o l a t et h ec o r r e c t n e s s ，a n da l lc o r r u p t e d ? i p l a y e r st o g e t h e r ( aob ) o b t a i nn oi n f o r m a t i o nn o ts p e c i f i e db yt h ep r o t o c o l 。 t h e o r e ml p e r f e c tv s ss c h e m e ( s e ef i g u r ei a n d2 ) s e c u r ea g a i n s ta 僻- 剐一a d v e r s a r y 缸p o s s i b l e 矿a n do n l y 矿p 爱艺ua i ia b e c a u s es e c u r i t yp r o o fo ft h ep r o t o c o li sn o tp r e s e n t e di nt h eo r i g i n a lp a p e r 卧 n o ww eg i v ei th e r e t h es e c u r i t yp r o o fo fm a u r e rv s sp r o t o c o l ：n o ww es h o wt h a tt h ep r o t o c o l d e s c r i b e di nf i g u r e1 , 2i ss e c u r ei np r e s e n c eo fa ( ，) - a d v e r s a r y , u n d e rt h ec o n d i t i o n ( 1 ) 。 f i r s tt h es c h e m ei st r i v i a l l ye - p r i v a t eb e c a u s ef o ra n ys e tt ，a tl e a s to n e s h a r e n a m e l yt h a tg i v e nt ot h ec o m p l e m e n to fam a x i m a ls e to f c o n t a i n i n gt ) i s m i s s i n g ，a n dh e n c et h es e tt h a sn oi n f o r m a t i o na b o u tt h es e c r e t r e c o n s t r u c t i o n b ya n yq u a l i f i e ds e ti nr = 2 p i sa l s ot r i v i a l ：a n ys e ts fc o n t a i n s ，f o re v e r y m a x i m a ls e t 霞，ap l a y e rn o ti n 互。t h i sp l a y e rk n o w ss i ，a n dh e n c et h ep l a y e r s i nsk n o wa l lt h es h a r e sa n dt h u sq u a l i f i e d s e c o n d ，f o re a c hs h a r e ，s a y8 i ，a l lp l a y e r sr e c e i v i n gt h a ts h a r e ( t h o s ei n 嚣) c h e c k p a i r w i s ew h e t h e rt h ev a l u er e c e i v e df r o mt h ed e a l e ri st h es a m e i fa n yi n c o n s i s - t e n c yi sd e t e c t e d ，t h ep l a y e r sd e t e c t i n gi tc o m p l a i nu s i n