（计算机软件与理论专业论文）广义公钥模型下并发及可重置的零知识证明系统.pdf

摘要 零知识证明系统在当代密码学中处于中心的位置并且是定义和证明各种各样密码任务的广 为接受的方法。伴随着i n t e r n e t 以及i n t e r n e t 上基于智能卡的电子商务的广泛普及和大规模 应用，零知识证明系统在并发及可重置环境中运行时所遇到的安全问题最近得到了高度重 视和深入的研究。 大量和深入的最新研究已经证明对于非平凡的语言常数轮r o u n d ) 的并发及可重置的零 知识系统在没有s e t u p 假设的朴素( p l a i n ) 模型下是不存在的。为了得到常数轮的并发及可 重置的零知识系统一些著名的计算模型已经提出来，其中最弱同时最令人关注的是秃公钥 ( b a r ep u b l i c - k e y ) 模型。( 在本学位论文中我们将统称秃公钥模型及其变体为广义公钥 模型) 不幸的是，至今我们不知道如何对非平凡的语言在秃公钥模型下构造具有并发验证 者安全( 即：并发可靠性及并发证据可提取性) 的并发及可重置的零知识系统也即是说， 所有以前在秃公钥模型下的并发及可重置的零知识系统仅仅能保证并发证明者安全f 即：并 发及可重置的零知识) 却不能保证并发验证者安全( 即：并发可靠性及并发证据可提取性) 。 但是，在大多数基于i n t e r n e t 和基于智能卡的现实应用中f 比如i n t e r n e t 上基于智能卡的安 全电子商务) ，同时保证并发证明者安全和并发验证者安全的零知识系统是系统安全所必需 的。 在本学位论文中，我们研究和显示如何在广义公钥模型下构造实用的及一般的同 时具有并发证明者安全和并发验证者安从而可以在并发及可重置环境中安全运行的零 知识系统。因为零知识证明系统在当代密码学中处于中心的位置，并且由于i n t e r n e t 以 及i n t e r n e t 上基于智能卡的电子商务的广泛普及和大规模应用，我们的工作具有极其重要 的理论和实际意义。 对于并发零知识，在秃公钥模型下对于常数轮且具有并发验证者安全( 即：并发可靠性 及并发证据可提取性) 的黑盒子( b l a c k - b o x ) 并发零知识知识辩论( a r g u m e n to fk n o w l e d g e ) 系 统我们给出了两个构造：一个是在离散对数假设下对于所有具有b 协议的语言运行6 轮 但勿需经一般的p 归约的实用构造；另一个是在单向函数假设下对于所有- p 一语言运 行4 轮f 这是最优的) 但需经一般的 厂p 归约的一般性构造。我们强调，无论是我们实用的 构造还是一般性的构造都代表了当代密码学在并发零知识领域的最高成就。 对于可重置零知识，我们引入了一个新的注册公钥模型：弱公钥( w e a kp u b l i o k e y w p k ) 模型。弱公钥模型是恰好处于 括c a n e t t i ，c o l d r e i e h ，o o l d w a s s e r 和m i c a l i 在s t o c 0 0 中 引入的秃公钥模型及由m i c a l i 和r e y z i n 在c r y p t o 0 1 中引入的上界公钥( u p p e r b o u n d e d p u b l i c ，k e yu p k ) 模型之间的一种注册公钥模型。弱公钥模型的合理性和优越性在运行丁分 布式c l i e n t s e r v e r 环境中的基于智能卡的安全电子商务中得到了充分的验证。接下来，我 们显示如何在弱公钥模型下对所有p _ 语言实现最少轮f 3 一r o u n d ) 同时具有并发可靠性的 可重置零知识辩论系统。我们在w p k 模型下关于具有并发可靠性的可重置零知识方面的 工作是对m i e a l i 和r e y z i n 在u p k 模型下并发可靠的可重置零知识工作( e u r o c r y p t 0 1 ) 的 一个极其重要的改进和扩充。更为重要的是，由于对所有 厂p - 语言常数轮且并发可靠的可 重置零知识系统是否在秃公钥模型中存在是一个著名的公开问题，我们此方面的工作对于 解决此一重要公开问题亦迈出了重要一步。 关键词：基于智能卡和基于互联网的安全电子商务，并发零知识，可重置零知识，并发验 证者安全，注册公钥模型 v a b s t r a c t z e r o - k n o w l e d g ep l a y sac e n t r a lr o l ei nt h e 矗e l do fc r y p t o g r a p h ya n di st h ea c c e p t e dm e t h o d o l o g yt od e f i n ea n dp r o v es e c u r i t yo fv a r i o u sc r y p t o g r a p h i ct a s k s w i t ht h ef a ra n dw i d e s w e e p i n gp o p u l a r i t yo ft h ei n t e r n e ta n ds m a r t c a r db a s e de - c o m m e r c eo v e ri n t e r n e t ，m u c h r e c e n tr e s e a r c ha t t e n t i o nh a sb e e np a i do nt h es e c u r i t yt h r e a t so fz e r o - k n o w l e d g ep r o t o c o l w h e nt h e ya r ee x e c u t i n gi nc o n c u r r e n ta n dr e s e t t a b l es e t t i n g s e x t e n s i v er e c e n tr e s e a r c he f f o r t sh a v ee s t a b l i s h e dt h a tc o n s t a n t r o u n d c o n c u r r e n t r e s e t t a b l e z e r o - k n o w l e d g ef o rn o n t r i v i a ll a n g u a g e sc a n n o tb e a c h i e v e di nt h ep l a i nm o d e lw i t h o u ts e t u p a s s u m p t i o n s t oa c h i e v ec o n s t a n t r o u n dc o n c u r r e n t r e s e t t a b l ez e r o - k n o w l e d g e ，s e v e r a lf a - m o u sc o m p u t a t i o n a lm o d e l sh a v eb e e ni n t r o d u c e d ，a m o n gw h i c ht h eb a r ep u b l i c k e y ( b p k ) m o d e i i st h ew e a k e s ta n da l s ot h em o s t a p p e a l i n g o n e f i nt h i st h e s i s w ew i l lr e f e rt ot h eb p k m o d e la n di t sv a r i a n t sa sg e n e r a lp u b l i c k e ym o d e i s 1 u n f o r t u n a t e l y , u pt on o ww ed on o t k n o wh o wt oc o n s t r u c tc o n c u r r e n t r e s e t t a b l ez e r o - k n o w l e d g ew i t hc o n c u r r e n tv e r i f i e rs e c u r i t y i e c o n c u r r e n ts o u n d n e s sa n dc o n c u r r e n tw i t n e s se x t r a c t i o n lf o rn o n - t r i v i a ll a n g u a g e s t h a ti s a l lp r e v i o u sc o n e u r r e n t r e s e t t a b l ez e r o - k n o w l e d g es y s t e m si nt h eb p km o d e lo n l y g u a r a n t e ec o n c u r r e n ta n dr e s e t t a b l ez e r o - k n o w l e d g ef o rc o n c u r r e n tp r o v e rs e c u r i t yb u td o n o tg u a r a n t e ec o n c u r r e n ts o u n d n e s sa n dc o n c u r r e n tw i t n e s se x t r a c t i o nf o rc o n c u r r e n tv e r i f i e r s e c u r i t y h o w e v e r z e r o - k n o w l e d g ep r o t o c o lt h a tg u a r a n t e eb o t hc o n c u r r e n tp r o v e rs e c u r i t y a n dc o n c u r r e n tv e r i f i e rs e c u r i t ya r er e a l l yd e s i r a b l ei nm o s ti n t e r n e tb a s e da n ds m a r t c a r d b a s e da p p l i c a t i o n s ( e g s e c u r es m a r t - c a r db a s e de - c o m m e r c eo v e ri n t e r n e t ) i nt h i st h e s i s w ei n v e s t i g a t ea n ds h o wh o wt oa c h i e v eb o t hp r a c t i c a la n dg e n e r a lz e r o - k n o w l e d g es y s t e m st h a tc a nb es e c u r e l yr u ni nc o n c u r r e n ta n dr e s e t t a b l es e t t i n g sw i t hb o t h c o n c u r r e n tp r o v e rs e c u r i t ya n dc o n c u r r e n tv e r i f i e r s e c u r i t yi ng e n e r a lp u b l i c k e y m o d e l s s i n c ez e r o - k n o w l e d g ep l a y sac e n t r a lr o l ei nt h em o d e r nc r y p t o g r a p h y , a n da l s os i n c et h e f a ra n dw i d es w e e p i n gp o p u l a r i t yo ft h ei n t e r n e ta n ds m a r t c a r db a s e de - c o m m e r c eo v e r i n t e r n e t ，o u rw o r k sa r eo fb o t hp r a c t i c a la n dt h e o r e t i c a ls i g n i f i c a n tc o n s e q u e n c e s f o rc o n c u r r e n t z e r o - k n o w l e d g e ，w ep r e s e n tt w oi m p l e m e n t a t i o n s f o rc o n s t a n t r o u n db l a c k b o xc o n c u r r e n tz e r o - k n o w l e d g ea r g u m e n to fk n o w l e d g et h a te n j o y sc o n c u r r e n tv e r i f i e rs e e n - r i t yf c o n c u r r e n ts o u n d n e s s a n dc o n c u r r e n tw i t n e s se x t r a c t i o n ) i nt h eb p km o d e l ：a p r a c t i c a l c o n s t r u c t i o nt h a ti su n d e rt h ed l pa s s u m p t i o na n dr u n si n6 一r o u n dw i t h o u tg o i n gt h r o u g h g e n e r a la l p - r e d u c t i o n sf o ra n yl a n g u a g et h a ta d m i t s 一p r o t o c o l ；a n dag e n e r a lc o n s t r u e - t i o nt h a tr u n si n4 。r o u n d ( t h a tl s o p t i m a l ) f o ra n yl a n g u a g ei n 厂_ pu n d e ro n l yo n e w a y f u n c t i o n s t oo u rk n o w l e d g e ，b o t ht h e p r a c t i c a lp r o t o c o la n dt h eg e n e r a lp r o t o c o ls t a n df o r t h ec u r r e n ts t a t e - o f - t h e - a r tc o n c u r r e n tz e r o - k n o w l e d g ew i t hs e t u pa s s u m p t i o n s f o rr e s e t t a b l ez e r o - k n o w l e d g e w ei n t r o d u c e dan e w r e g i s t e r e dp u b l i c k e ym o d e l ：t h ew e a k p u b l i c - k e y ( w p k ) m o d e l t h ew p km o d e l ；u s tl i e sb e t w e e nt h eb p km o d e l i n t r o d u c e d l l b yc a n e t t i ，g o l d r e i c h ，g o l d w a s s e ra n dm i c a l i ( s t o c 0 0 ) a n d t h eu p p e r - b o u n d e d p u b l i c k e y ( u p k ) m o d e li n t r o d u c e db ym i c m ia n dr e y z i n ( c r y p t 0 0 1 ) a n d i sw e u - m o t i v a t e di nt h e s m a r t c a r db a s e de - c o m m e r c eo v e rd i s t r i b u t e dc l i e n t s e r v e rs e t t i n g s ，w et h e ns h o wh o wt o a c h i e v em i n - r o u n df 3 - r o u n d ) r e s e t t a b l ez e r o - k n o w l e d g ea r g u m e n t sf o r pw i t hc o n c u r r e n t s o u n d n e e si nt h ew p km o d e l o u rt h i sw o r kf o nr c 8 e t t a b l ez e r o - k n o w l e d g ew i t hc o n c u r r e n ts o u n d n e s si nt h ew p km o d e l li sas i g n i f i c a n ti m p r o v e m e n ta n de x t e n s i o no ft h ew o r k o fm i c a l ia n dr e y z i no nr e s e t t a b l ez e r o - k n o w l e d g ei nt h eu p km o d e l ( e u r o c r y p t 0 1 ) f u r t h e r m o r e s i n c ei ti saw e l l - k n o w no p e np r o b l e mw h e t h e rc o n s t a n t - r o u n dr e s e t t a b l ez e r o - k n o w l e d g es y s t e m sw i t hc o n c u r r e n ts o u n d n e s sf o r pe x i s ti nt h eg e n e r o u sb p k m o d e lo r n o t ，o u rt h i sw o r km a k e sas i g n i f i c a n ts t e pf o rf i n a l l ys o l v i n gt h i si m p o r t a n to p e np r o b l e m k e y w o r d s ： s m a r t c a r d b a s e da n di n t e r n e t b a s e ds e c u r ee - c o m m e r c e ，c o n c u r r e n t z e r o - k n o w l e d g e ，r e s e t t a b l ez e r o - k n o w l e d g e ，c o n c u r r e n t v e r i f i e rs e c u r i t y ，r e g i s t e r e dp u b l i c k e y m o d e l 1 u 提示 本学位论文同时提供英文版和中文版，是首先由英文写成然后再翻译成中文的。本学位论 文涉及当代密码学在零知识领域的国际最新研究课题和进展。虽然零知识在当代密码学中 处于中心的位置并具有极其重要的理论和应用价值，但零知识亦是公认的当代密码学中最 难的领域之一。由于国内尚没有系统论述零知识的专著，零知识领域中的许多重要的术语 和论述并没有广为接受的中文对译，因此本学位论文虽然同时提供英文版和中文版，但英 文版中很多重要的术语和细节看起来难以在中文版中给出令人满意及广为接受的精确中文 表达。鉴于上述原因。作者强烈推荐审阅专家利用本学位论文的英文版进行审阅以节省您 宝贵的时间和减少不必要的误解。 致谢 首先，我要深深致谢我的导师朱洪教授我要深深感谢朱老师多年来严格及高标准的指导和 要求同时又慈父般的热情关怀和支持是朱老师鼓励和引导我进入密码学和计算复杂性的 科学殿堂，并使我深深痴迷于此一研究领域并将其作为自己终身不渝的事业 我最初认识朱老师是我大学本科三年级的时候，在当时的算法课上我对串匹配算法有一 些自己的创新和改进，因为当时我们的算法课用的是朱老师的书作教材我就和朱老师联系 并讲述了自己的结果，此结果后来发表在“计算机研究和发展”上从那时起我和朱老师之 间开始了频繁的书信往来朱老师在书信中不断地给我一些算法和复杂性方面的国际上的 最新进展和文献，并热切地鼓励和引导我继续从事算法和复杂性领域的研究正是在朱老师 的指引和鼓励下，我潜心钻研了算法和计算复杂性方面的几乎所有的经典著作，为我以后进 入复旦从事密码学的研究打下了坚实的基础 在本科大四的暑假期间，朱老师给了我一个数论的问题进行研究此问题即是著名 的“乘3 加1 问题”其实该问题是数论中一个世界著名的公开问题，但我当时却不知道我花 了3 个月不眠不休的研究和思考此问题为此我翻阅和钻研了大量数论领域的经典著作f 包 括华罗庚先生的名著”数论导引”) ，并写信给数论领域的一些院士请教，直到又一天四川大 学的一位院士回信告诉我此问题乃世界著名公开问题并建议我放弃对此问题的进一步的研 究虽然我最终放弃对此问题的研究，但此研究过程为我吕后进行密码学的研究打下了坚实 的数论的基础我想这也正是朱老师苦心所在 及至我进入复旦成为朱老师的一个正式弟子，朱老师让我们用了一年的时间系统学 习o d e dc o l d r e i c h 的计算复杂性导引一书，对我算法和复杂性方面的底子亲自进行了系统 化的调理和整固，使我的基础进一步稳固和扎实在有了足够的基础之后，朱老师才逐渐 地引导我进入零知识证明和当代密码学的殿堂零知识证明在当代密码学中处于中心的位 置，具有极其重要的理论和应用价值，但同时又是密码学和计算复杂性科学最难的领域之 一现在回想起来，我更一步体会到朱老师当初调理和整固我的基础的良苦用心可以毫不 夸张地说，没有朱老师严格而又良苦的栽培，就没有今日的我，尽管我还没有取得令朱老师 欣慰的大的成就。虽然我不是“千里马”，但朱老师绝对是我人生中的伯乐和恩师对朱老师 的深深感谢将永铭吾心，伴吾终身 我要感谢臧斌宇，赵一鸣，毛文博，沙朝锋，阐海斌，万惠玲老师对我的指导，关心和支 持同时我亦要感谢研究生院培养办老师的关心和支持 我要感谢香港城市大学的邓小铁，c h l e e 和f r a n c e sy a o 教授在我访问城市大学期间 支持和帮助。他们的指导，支持和帮助对于我的成长亦是至关重要的我要感谢图灵奖得 主m b l u m 和a n d r e wy a o 在他们访问城市大学期间对我的研究工作的指导和讨论，特别地， 我从a n d r e wy a o 教授所主持的算法和复杂性的讨论班中获益良多 我要感谢国际密码学的大师：b a r a k ，b e l l a r e ，c r a m e r ，d a m g a r d ，d w o r k ，d ic r e s c e n z o ， o d e dg o l d r e i c h ，l i n d e l l ，p e r s i a n o ，r e y z i n ，y u n g ，他们友好而又耐心的指导，建议，及业务 上的讨论在我的研究中起了极其重要的作用，使我能时刻掌握国际密码学的最新课题和进 v l 展 我要感谢我的同事多年来的帮助和支持他们是( 按拼音序) ：陈宁，陈志德，s h i r l e y c h e u n g ，邓冬华，邓红素，李弋，鲁鸣鸣，孟杰，彭政，彭超，曲惠琴，宋建涛，吴华怡，左益 强 最后也是最重要的，我要深深感谢我的家人感谢父母几十年来始终如一的对我这样一 个痴迷于科学研究，脑子里充满零知识的儿子的理解，期望，和无论世道艰难而始终不渝的 最大的支持和宽容父母的爱和支持是我漫漫学涯中最难以释怀和无以报答的恩情。 我要感谢姐姐和弟弟多年来的深厚和真挚手足之情他们总是对我充满希望，以我为他 们的骄傲，在我最困难的时候给我最宝贵和最温暖的亲情的支持和鼓舞 我要感谢我的妻子多年来对我生活上的支持和春蚕般默默无闻的奉献她开朗的性格 是我孤独的学涯中的一股清泉，是我沮丧挫折时的一丝扑面春风，使我总以乐观开朗的心态 去面对挫折和挑战，从而保持最佳的研究状态 最后，我要感谢我2 岁大的儿子两年来带给我的所有欢乐。他使我总保持着孩子般的对 一切事物好奇的童心，这对我的研究亦是非常重要的。 p a r ti 学位论文英文版 c h a p t e r 1 i n t r o d u c t i o n w jb e g i nt h i st h e s i sw i t ht h ef a m o u si n v i t e dt a l kf 3 8 1 g i y e nb yg o i d w a s s e ra tf o c s 9 7 w i t ht h et i t l e ：“n e wd i r e c t i o n si nc r y p t o g r a p h y ：t w e n t ys o m ey e a r sl a t e rf o rc r y p t o g r a p h y a n dc o m p l e x i t yt h e o r y ：am a t c hm a d ei nh e a v e n ) ”i nt h a tt a l k g o l d w a s s e rc l a i m e dt h a t t h em o s ts i g n i f i c a n tp r o g r e s so fm o d e r nc r y p t o g r a p h yi nt h el a s tt w od e c a d e si st ob a s e c r y p t o g r a p h yo n t oc o m p u t a t i o n a lc o r n p l e x i t yt h e o r y , a n di t i s c o m p u t a t i o n a lc o m p l e x i t y t h e o r yt h a tb r i n g sc r y p t o g r a p h yf r o m a na r ti n t oa r i g o r o u ss c i e n c e g o l d w a s s e rp o i n t e do u t t h a tt h es u c c e s s f u li n t e r p l a yb e t w e e n c o m p l e x i t yt h e o r ya n de r y p t o g r a p h yi sw i t n e s s e dm o s t v i v i d l yb yt h ed e v e l o p m e n t so fz e r o - k n o w l e d g e t h en o t i o no fz e r o - k n o w l e d g e ( z k ) w a 8i n t r o d u c e di nt h es e m i n a lp a p e ro fg o l d w a s s e r ， m i c a l ia n dr a & o f f 4 0 1t oi l l u s t r a t es i t u a t i o n sw h e r eap r o v e rr e v e a l sn o t h i n go t h e rt h a n t h ev e r i t yo fag i y e ns t a t e m e n tt oa ne v e nm a l i c i o u sv e r i f i e r s i n c et h e i ri n t r o d u c t i o n ，z e r o - k n o w l e d g ep r o o f sh a v ep r o v e nt ob ev e r yu s e f u la sab u i l d i n gb l o c ki nt h ec o n s t r u c t i o no f c r y p t o g r a p h i cp r o t o c o l ，e s p e c i a l l ya f t e rg o l d r e i c h ，m i c a l ia n dw i 酿e r s o ni a t h a v es h o w n t h a ta l ll a n g u a g e si n pa d m i tz e r o - k n o w l e d g ep r o o 自b yn o w ，z e r o - k n o w l e d g eh a sp l w e d ac e n t r a lr o l ei nt h ef i e l do fm o d e r nc r y p t o g r a p h ya n di st h ea c c e p t e dm e t h o d o l o 盱t od 萌n e a n dp r o v es e c u r i t yo fv a r i o u sc r y p t o g r a p h i ct a s k s w i t ht h ee m e r g e n c ea n df a ra n dw i d es w e e p i n gp o p u l a r i t yo ft h ei n t e r n e t ，m u c hr e c e n t r e s e a r c ha t t e n t i o n ，i n i t i a t e db yd w o r k ，n n o ra n ds a h a i 【2 s ，h a sb e e np a i do nt h es e c u r i t y t h r e a t so fz e r o - k n o w l e d g ep r o t o c o l sw h e nt h e ya r ee x e c u t i n gc o n c u r r e n t l yi na na s y n c h r o n o u s n e t w o r ks e t t i n gl i k et h ei n t e r n e t i nt h i ss c e n a r i o ，m a n yc o n c u r r e n te x e c u t i o n so ft h es a n 2 e p r o t o c o lt a k ep l a c e i na n a s y n c h r o n o u s n e t w o r k s e t t i n g h o n e s tp l a y e r s a r ea s s u m e do b l i v i o u s o fe a c ho t h e r se x i s t e n c e ，n o rd ot h e yg e n e r a l l yk n o wt h et o p o l o g yo ft h en e t w o r k ，a n d t h u sc a n n o tc o o r d i n a t et h e i re x e c u t i o n s h o w e v e r am a l i c i o u sa d v e r s a r yc o n t r o l l i n ga l lt h e v e r i f i e r sc a nc o n c u r r e n t l ys c h e d u l ea l lt h ee x e c u t i o n sa ti t sw i s h m o t i v a t e db ys m a r t - c a r db a s e de - c o m m e r c eo v e ri n t e r n e t ，r e s e t t a b l ez e r o - k n o w l e d g e f r z k ) t h a ti st h es t r o n g e s tn o t i o no fz e r o k n o w l e d g et od a t e ，w o sr e c e n t l yp u tf o r w a r db y c a n e t t i ，g o l d r e i c h ，g o l d w a s s e ra n dm i c a l i 【1 5 r o u g h l ys p e a k i n g ，a nr z kp r o t o c o li s a n i n t e r a c t i v es y s t e mi nw h i c hav e r i f i e rl e a r n 8n o t h i n g ( e x c e p tf o rt h ev e r i t yo fag i v e ns t a t e m e n t ) e v e ni fh e c a r li n t e r a c tw i t ht h ep r o v e rp o l y n o m i a lm a n yt i m e s ，e a c ht i m er e s t a r t i n ga n i n t e r a c t i o nw i t ht h ep r o v e ru s i n gt h es a m ec o n f i g u r a t i o na n dr a n d o mt a p e r z ke n l a r g e st h e n u m b e ro fp h ) r s i e a lw a y st oi m p l e m e n tz e r o - k n o w l e d g ep r o t o c o lw h i l eg u a r a n t e e i n gs e c u r i t y i sp r e s e r v e d f o re x a m p l e r z km a k e si tp o s s i b l et oi m p l e m e n tt h ep r o v e ro fz e r o - k n o w l e d g e 2 p r o t o c o lb yu s i n gt h o s ed e v i c e st h a tm a b ep o s s i b l yf m a l i c i o u s l y ) r e s e t t e dt oi t si n i t i a l c o n d i t i o no rc a nn o ta f f o r dt og e n e r a t ef r e s hr a n d o m n e s sf o re a c hn e wi n v o c a t i o na ne x - a m p l eo ft h o s ed e v i c e si st h eo r d i n a r ys m a r tc a r d r z kp r o t o c o l sa r ea l s og u a r a n t e e dt o p r e s e r v et h ep r o v e r ss e c u r i t yw h e ne x e c u t e dc o n c u r r e n t l yi na na s y n c h r o n o u sn e t w o r kl i k e t h ei n t e n m t a c t u a u y , r z ki sa g e n e r 址i z a t i o na n ds t r e n g t h e n i n go f t h en o t i o no fc o n c u r r e n t z e r o - k n o w l e d g ei n t r o d u c e db yd w o r k ，n a o ra n ds a h a i 2 8 1 。1ah i s t o r i c a lv i e wo fr e l a t e dw o r k s t h es t u d yo fs e c u r i t yu n d e rc o n c u r r e n tc o m p o s i t i o ni si n i t i a t e db yd w o r k ，n a o ra n ds a h a ii n t h ec o n t e x to fc o n c u r r e n tz e r o - k n o w l e d g ef 2 8 i a l t h o u g hn o n c o n s t a n t - r o u n db l a c k - b o xc o i l c u r r e n tz e r o - k n o w l e d g e p r o o f sf o rn 9 e x i s ti nt h ep l a i nm o d e lu n d e rs t a n d a r di n t r a c t a b i l i t y a s s u m p t i o n s 5 2 ，4 2 ，4 3 ，5 1 ，4 6 l ，b u tt h e yc a n n o tb ec o n s t a n t - r o u n di nt h eb l a c k - b o xs e n s e 1 6 ，1 7 1 c o n s t a n t r o u n dn o n - b l a c k - b o xb o u n d e dc o n c u r r e n tz e r o k n o w l e d g ea r g u m e n t s a n d a r g u m e n t so fk n o w l e d g ef o r a r ea c h i e v e di nf 1 ，5 1 t oa c h i e v ec o n s t a n t r o u n db l a c k - b o x c o n c u r r e n tz e r o - k n o w l e d g e s e v e r a lc o m p u t a t i o n a lm o d e l sa r ei n t r o d u c e d ：t h et i m i n gm o d e l 2 8 ，3 5 l ，t h ep r e p r o c e s s i n gm o d e l1 2 4 1 ，t h ec o m m o n r e f e r e n c es t r i n gm o d e l 2 1 ，a n dt h eb a r e p u b l i c k e ym o d e l1 1 5 】 t h eb a r ep u b l i c - k e y ( b p k ) m o d e li sf i r s ti n t r e d u c e db yc a n e t t i ，g o l d r e i c h ，g o l d w a s s e r a n dm i c a l i 1 5 1t oa c h i e v er o u n d - e f l i c i e n tr e s e t t a b l ez e r o - k n o w l e d g e ( r z k ) t h a ti sag e n e r a l i z a t i o na n ds t r e n g t h e n i n go ft h en o t i o no fc o n c u r r e n tz e r o - k n o w l e d g e a sp o i n t e do u tb y m i c a ua n dr e y z i n 4 7 1 ，a l t h o u g hi n t r o d u c e dw i t has p e c i f i ca p p l i c a t i o ni nm i n d ，t h eb p k m e d e la p p l i e st oi n t e r a c t i v es y s t e m si ng e n e r a l ，r e g a r d l e s so ft h e i rk n o w l e d g ee o m p l e x i t 弘a p r o t o c o li nb p k r o o d e ls i m p l ya s s u m e st h a ta 1 1v e r i f i e r sh a v ed e p o s