（计算机软件与理论专业论文）常数轮的并发不经意传输.pdf

摘要 摘要 不经意传输( o b h v l o u st r a n s f e r ，简称o t ) 是密码学中一种重要的工具。 在1 9 9 2 年，b e a v e r 首次对单机的o t 协议的安全性做了形式化的定义【3 】，将现 实的o t 协议与理想的o t 系统进行比较，要求攻击者的视图是不可区分的。在 文献中的大多数o t 协议考虑的都只是在单次执行下的安全眭。而在协议并发 运行时，由于消息的传送是交错进行的，攻击者很可能会通过对消息进行某种 调度，对协议进行攻击。因此，g a r a y 和m a c k e n z m 3 8 t - 2 0 0 0 年提出了并发o t 协 议，并证明了具在并发运行的环境中的安全性；然而，他们的协议却不是常数轮 的。n a o r 等人于0 1 年提出的两轮m o t 协议【5 8 】虽然, - p a 同时执行多次，但其安全 性却并不完全是基于b e a v e r 的安全性定义。在他们所用的安全眭定义中，接收方 的安全性所针对的只是半诚实的发送方。因此，在本文中，我们对常数轮的、并 发安全的o t 协议进行了研究和探讨。在分析了o t 方面已有的工作之后，我们研 究了如何在随机o r a c l e 模型和公共引用串模型中构造常数轮的并发安全的o t 协 议。 首先，我们给出了一个随机o r a c l e 模型下的o t 协议。在证明了其安全性及具 存在的问题后，我们又在该模型下利用非交互式零知识的知识证明构造了两轮的 并发安全的( 二中取一的) o t ，并将其扩展到了中取k 的情况。接着，我们在公 共引用串模型下构造了一个三轮的并发o t ，并证明了其安全性。考虑到该o t 协 议的计算效率不高，我们又考虑了如何降低o t 的计算代价，利用【3 9 】中的q 协议 构造了高效的五轮的并发o t 协议。 关键词：不经意传输，多义提交，零知识，知识证明，随机o r a c l e 模型，公共引用 串模型 中图分类号：t p 3 0 97 a b s t r a c t a b s t r a c t o b h v l o u st r a n s f e r ( o t ，i ns h o r t ) i sa ni m p o r t a n tt o o li nc r y p t o g r a p h mp r o - t o c o sb e a v e rw a st h ef i r s tt of o r m a l l yd e f i n et h es e c u r i t yo fo t a ，c o m p a r i n g t h er e a lo tp r o t o c o lw i t ht h el d e a ls y s t e mf o ro ta n dr e q m n n gt h ev i e w so ft h e a d v e r s a r i e st ob em d l s t m g m s h a b l e m o s to ft h eo tp r o t o c o l si nt h eh t e r a t u r e c o n s i d e r e do n l yt h es t a n d - a l o n es e c n r l t y w h e r e a s ，w h e np r o t o c o l sr u nc o n c u r - r e n t l y ，t h em e s s a g e sa r em t e r l e a v e d t h ea d v e r s a r i e sm a ya t t a c kt h eo tp r o t o c o l b ys o m eh n d o fs c h e d u l eo fm e s s a g ed e h v e r m g h e n c e ，g a r a ya n dm a c k e n z m 【3 8 】 p r e s e n t e dac o n c u r r e n to ts c h e m ei n2 0 0 0 a n dp r o v e d1 t ss e c u r l t yi nt h ea s y n - e h r o n o u ss e t t i n g h o w e v e r ，t h e i rp r o t o c o l1 8n o tc o n s t a n t - r o u n d t h e2 - r o u n d o ts c h e m ep r o p o s e db yn a c re ta 1 i n2 0 0 1f 5 s c o u l dr u nm a n yt i m e ss l m u l - t a n e o u s l y , b u tl t 8s e c u r i t yi sn o tb a s e do nt h ed e f i m t l o no ft h a tb yb e a v e r i n t h e i rd e f i m t l o no fs e c u r eo t ，t h er e c e w e r 8s e c u r l t yi so n l yw i t hr e s p e c tt ot h e s e m i h o n e s ts e n d e r t h e r e f o r e ，i nt h i sp a p e r ，w em m n l ys t u d ya n di n v e s t i g a t et h e c o n s t a n t - r o u n dc o n c u r r e n t l y - s e c u r eo tp r o t o c 0 1 8a f t e rt h ea n a l y s i so fe x s l t e n t w o r ko no t ，w ef o c u so nh o wt oc o n s t r u c tc o n s t a n t - r o u n do ts c h e m e smt h e r a n d o mo r a c l em o d e la n dc o m m o nr e f e r e n c es t n n gm o d e l ，r e s p e c t i v e l y f i r s t ，w ep r e s e n tac o n s t a n t - r o u n do tp r o t o c o li nt h er a n d o ms t r i n g a f - t e rp r o v i n gi t ss e c u r i t ya n da n a l y z i n gi t sp r o b l e m s ，w eg i v ea n o t h e r2 - r o u n d c o n c u r r e n t l y s e c u r e ( o n e - o u t - o f - t w o ) o tn s m gn o n i n t e r a c t i v ez e r o - k n o w l e d g ep r o o f s o fk n o w l e d g e ，a n dt h e ne x t e n di tt ot h en o u t o f - kc a s e n e x t ，w ec o n s t r u c ta 3 - r o u n dc o n c u r r e n to ts c h e m ea n dp r o v ei t ss e c u r i t y b e c a u s eo ft t sb a dp e r f o r - m a n c eo ne f f i c i e n c y , w et r yt or e d u c ei t sc o m p u t a t i o nc o s t ，a n dp r e s e n ta n o t h e r h l 曲l ye f f i c m n t5 - r o u n dc o n c u r r e n to tb yu s m gt h es o - c a l l e d 啦p r o t o c o l si n1 3 9 k e yw o r d s ：o b h v m u st r a n s f e r ，e q u w o c a lc o m m i t m e n t ，z e r ok n o w l e d g e ，p r o o f o fk n o w l e d g e ，r a n d o mo r a c l em o d e l ，c o m m o nr e f e r e n c es t n n gm o d e l c a t e g o r y ：t p 3 0 97 图片列表 图片列表 3 1 1 3 e l l a r e - m m m l 的非交互式( ；) 一o t 3 2 g a r a y m a c k e n z i e 的并发的( ：) 一o t 3 3 n a o r - p m k a s 的基于随机o r a d e 的并行的( j ) 一o t 41 “单机”的常数轮的不经意传输 42 常数轮的并发不经意传输 3 1 6 1 7 1 8 2 0 2 4 5 1 随机o r a c l e 模型下安全的不经意传输协议r o o t 3 2 52 随机o r a c l e 模型下并发安全的不经意传输协议：r o c o t 。3 7 53 随机o r a d e 模型下常数轮的并发安全的( 墨) o t 协议( 譬) 一r o c o t 3 9 6 1c r s 模型下并发安全的不经意传输协议c r s o t 4 4 62 关于离散对数关系r d l = f l y ，9 ) ，z ) 口i 旷m o dp ) 的q 协议【3 9 】。 公共引用串为一个p a l l h e r 公钥和一个强r s a 模数及两个生成 元( ( ， ) ，( n ，h i ，屯) ) 。 4 8 6 3c r s c o t 2 协议5 0 第一章绪论 第一章绪论 1 1 背景介绍 不经意传输( o b h v i o m st r a n s f e r ，简称o t ) 是密码学中一种基本的原语。自 从r a b m 6 2 = j = 1 9 8 1 年把不经意传输引入了密码学之后，不经意传输已成为了 密码学中一种非常重要且破广泛应用的工具，例如：o t 可以被用来实现位提交 协议( b i tc o m m i t m e n t ) 、零知识证明( z e r ok n o w l e d g ep r o o f ) 1 0 ，2 7 、安全多方 计算( s e c u r em u l t i p a r t yc o m p u t a t i o n ) 4 6 ，4 5 ，5 2 ，6 7 1 以及秘密信息检索( p r i v a t e i n f o r m a t i o nr 砒n e v a l ) 1 1 9 ，4 1 ，5 4 ，1 5 等。 大致来讲，不经意传输是一种两方计算协议，其中一方是发送者f 我们称她 ：为a h c e ) ，她持有一个消息b ；另一方是接收者( 我们称他：为b o b ) ，他可以选择是 否接收消，6 5 。a h c e 和b o b 通过执行o t 协议来传输消息b 。b o b 或者接收了b ，或 者完全不知道b ( 除了随机猜测) ，并且这两个事件发生的概率都是；1 ；此外，对 于a h c e 来说，她除了随机猜测之外，不会清楚b o b 是否接收了这个消息。 在从r a b m 提出o t 到现在这二十五年时间的发展当中，出现了很多种o t 的变 体，例如：e v e n 等人提出的二中取- - i 拘o t ( 简称为( ；) 一o t ) 3 5 、c r 卸e a u 提出的可 验证的o t ( v j n f i a b l eo t ，或者称为c o m m i t e do t ) 2 3 ，4 0 1 、量子o t 5 ，2 0 】、n 中 a - s o t ( ( 9 一o t ) 【1 ，5 s 、以及中取的o t ( ( 2 ) 一o t ) 【2 4 】等。研究人员已经 对此做过广泛的研究【1 ，2 ，i 0 ，3 8 ，1 4 ，2 3 1 ，并将其大量应用到密码学协议中。 而所有这些变体都已经被证明是等价的。在所有这些o t 的变体中，我们最 关心、最感兴趣的一种变体是( ；) 一o t ，它是由e v e n 、g o l d r e m h 和l e m p e l 三人 于1 9 8 5 年提出的 3 5 】。1 9 8 7 年，c r 6 p e a u 证明了( ；) 一o t 和r a b l n 最初提出的o t 是 等价的f 2 2 】o 在( 2 ) o t 中，a h c e 的输入包含两个消息：m o 和m l ；b o b 的输入是 一个位盯 o ，1 。协议执行结束时，b o b 接收了消息，但是却不知道消 息m l 一，具体是什么；另一方面，a h c e 并不清楚b o b 到底选择接收了哪一条消息。 在1 9 8 9 年，b e l l a r e 和m m a h 1 0 】以离散对数问题难解性的假设为基础，给出了( ；) o t 协议的一个非常精巧的“非交互式”实现。之后许多文章中所提出的o t 协议 有很多就是以他们这个协议为基础而做的各种改进。 在不经意传输的安全性定义问题上，b e a v e r 3 是第一个对“单机”( s t a n d - a l o n e ) o t 的安全性做了形式化的定义( 从这以后我们称它为单机m o t ) 。 在b e a v e r 的定义中，他将现实中构造的o t 协议和o t 的一个理想系统关联起 来并做比较。在这个理想系统中除了a h c e 和b o b 之外，还存在一个可信第三 方t e d 。a h c e 和b o b 分别与t e d 进行秘密的通讯交流，完成o t 服务：并且在这个 第一章绪论2 系统中的所有到可信第三方以及所有从可信第三方来的通讯都是绝对安全的。 为了证明o t 协议的安全性，我们需要利用理想的0 t 来模拟现实的o t 协议。这 个思想的关键在于如果存在一个攻击者能够攻破现实的o t 协议，那么我们可以 利用它来构造一个攻击者用以攻击理想的o t 协议；然而，根据定义，这是不可能 的。因此我们就可以掘此推出，所构造的现实的o t 协议是安全的。 大多数的文献中给出的o t 协议所基于的安全性定义考虑的是半诚实的发送 方( a h c e 会遵照协议的规定去执行，但是企图从所收到的消息中获取更多的信 息) 和恶意的接收方( b o b 可能会背离协议的规定) 。对于b o b 的安全性来说，这个 半诚实的a h e e 不能从所收到的消息中区分出b o b 的选择是哪个，b o b 选择接收消 息m o 和选择接收m l 时a h c e 的视r e ( v i e w ，指的是协议参与方在协议执行过程中 所使用的随机带的内容及其收到的消息的集合1 是不可区分的；而对于a l , c e 的安 全性来说，这个恶意的攻击者b o b 所能做的事情，理想模型中相应的攻击者也能 做到。 为了证明o t 协议的安全性，一种比较好的方法是使用零知识证明：证明 方使用零知识协议来向另一方证明他知道某些知识。零知识证明这个概念 是i 由g o l d w a s s e r ，m i c a h 和r a c k o f f 于1 9 8 5 年提出来的【4 7 】。大概地说，零知识证 明足一种特殊的交互式证明系统，其中一方是证明者p ，而另一方是验证 者矿。p 和y 进行交互，p 向y 证明他知道某个语句的正确性。在协议执行到最 后，y 相信这个语句是正确的，但是除此之外，y 不会获得到更多的信息。要证明 一个协议是零知识的，我们要求存在一个概率( 期望) 多项式时间的模拟器s ，它 的输出和y 与p 真实地进行交互时的视图是不可区分的。s 在进行模拟时，通常是 以一种黑盒( b l a c k - b o x ) 4 3 1 的方式对y 进行访问，然后再给出它的输出值。简单 地说，对于任意的证明者矿( 可能是诚实的，也可能是恶意的) ，s 都能以一种统 一的方式工作，并给出与真实交互不可区分的消息副本输出。 1 2 相关工作 在为现实世界构造密码学协议时，尤其是当这些协议需要应用或者运行于 异步环境中时，例如因特网等，原来在单次执行时是安全的协议就不一定 仍然是安全的了。这方面的一个例子就是零知识证明系统的并发组合问 题。g o l d r e n c h 和k r a w c z k y 已经于1 9 9 6 年证明了零知识证明系统在并发执行时可 能会泄露信息而不再保持零知识的特性【4 3 】。因此，我们要就必须得考虑所构造 的协议在并发运行时的安全性。研究人员已经对并发环境中的安全认证和密钥 交换协议做了大量的研究工作【4 ，1 1 ，1 2 ，3 1 ，5 0 ，5 1 ，5 5 ，6 5 1 。 在最近几年的关于并发协议的工作中，其中有很大一部分是关于并发零 知识。1 9 9 8 年，d w o r k 、n a o r $ 1 1 s a h m 3 3 考虑了异步环境中并发零知识的一般 第一章绪论3 情况，并指出在时间模型( t i m i n gm o d e l ，对p 和y 的处理器的相对速度存在一 定限制) 中，我们可以为p 中的任何语言构造出四轮的并发零知识证明。后 来d w o r k 年f l s a h m 在 3 4 1 中指出，并发零知识证明所用的时间假设可以被简化成一 个预处理阶段。很快，在1 9 9 9 年，d 1c r e s c e n z o 和o s t r o v s k y 就消去了时间模型。他 们在f 3 0 1 中证明了在预处理模型中， 厂p 中的任何语言都存在并发零知识证明。接 着，d a m g a r d 又于2 0 0 0 年在公共引用串模型( c o m m o nr e f e r e n c es t n n gm o d e l ，所 有参与方都共享一个辅助串) 中给出了一个常数轮( 三轮) 的并发零知识协i 义 2 5 】。 同年，c a n e t t l 等人1 1 6 1 提出了公钥模型( p u b h ek e ym o d e l ) 下的常数轮的并发零 知识证明系统。 然而，如果不基于任何模型假设( 比如时间模型、预处理模型和公 共引用串模型等) ，是否存在常数轮的并发零知识呢? 这个问题首先 由k l h a n 、p e t r a a k 和r a c k o 盱1 9 9 8 年在 5 3 1 中做了部分解答。他们证明了一个 语言l 如果有四轮的、关于成员关系的并发零知识证明系统，并且是黑盒模拟的， 那么l b p p 。后来这个轮数的下界又被r o s e n 提高到了七轮【6 3 】，也就是说，如 果一个语言l 有七轮的、关于成员关系的黑盒模拟的并发零知识证明系统，那 么l b p 尸。2 0 0 1 年，c a n e t t l 、k a l l a n 、p e t r a n k 和r o s e n 对上述问题做了完全解 答。他们在f 18 1 中证明了黑盒模拟的并发零知识协议至少需要对数多项式轮。 在并发o t 协议方面，g a r a y 和m a c k e n z l e 3 8 = j = 2 0 0 0 年给出了一个并发安全 的o t 协议，并在标准模型( 不基于任何模型假设) 下证明了它的并发安全性。他 们这个协议是第一个并发o t 协议，并且没有借助于零知识证明就能证明其安 全性。但是，他们的协议最大的一个不足之处在于协议并不是常数轮，而是在 任意非常数轮内实现。2 0 0 4 年，g a r a y ，m a c k e n z i e 和y a n g 又提出了通用可组合 的提交的o t ( u m v e r s a l l y c o m p o s a b l ec o m m l t t e do t ) 4 0 。他们的这个常数轮 的0 t 协议是基于公共引用串模型。 1 _ 3 动机 我们对常数轮的并发o t 的研究有着很现实的考虑。o t 协议在密码学中有着很多 重要的并且很现实的应用，例如o t 可以应用于秘密信息检索【1 9 ，4 1 ，5 4 ，1 5 】、不 经意多项式演算【5 7 】以及不经意的关键字搜索【5 9 】等。而且，任何多方安全计算都 可以e h o t 来实现【6 7 ，4 5 ，5 2 】，因而o t 也就成了实现多方安全计算协议的一个基 础。另一方面，当o t 协议运行于异步环境中时，比如，客户端和数据库服务端通 过因特网执行多次秘密信息检索协议，同样也可能会存在和并发零知识类似的 问题。因此，如何去构造一个并发安全的o t 协议也就成了一个值得我们去考虑 的问题。 据我们所知，到目前为止，在并发安全的不经意传输 第一章绪论4 方面还只有g a r a y 和m a c k e n z m 于2 0 0 0 年提出的并发o t 协议【3 8 1 以 及g a r a y ，m a c k e n z m 和y a n g 提出的通用可组合的提交的o t 4 0 1 。f 3 8 1 中的 并发o t 协议并不是常数轮的；1 4 0 1 中的提交的o t 协议是在公共引用串模型下构 造的。在因特网这样的环境中，消息在网络中传输所花的时间与消息的计算时间 相比是比较大的，所以，我们在构造协议时都会考虑去构造一个常数轮的协议， 而且，在满足安全性的前提下，协议的轮数是越少越好。所以，在本文中，我们 对如何构造常数轮的并发安全的0 t 协议进行了探讨和研究。 14 我们的贡献 在对已有的一些o t 协议做了介绍并分析了其中的优缺点之后，我们给出了一个 常数轮的、单机安全的o t 协议，然后尝试着将其扩展到并发运行的环境中，并指 出了具中可能存在的问题。接着，我们又分别在随机o r a c l e 模型和公共引用串模 型下构造了常数轮的o t 协议，并证明了它们的并发安全性。这些协议的一个共 同点是在协议中使用了一种特殊的知识证明协议。知识抽取器在抽取知识时不 需要对相应的证明者进行重置即可抽取到所需的知识，这一点很好的避开了使 用一般的知识证明的o t 协议所碰到的问题。在随机o r a c l e 模型和公共引用串模 型下，这种知识证明协议是存在的【3 6 ，2 8 ，3 9 】。利用这种知识证明协议，我们可 以很容易地证明所构造的o t 协议的安全性。 首先，我们给出了一个随机o r a c l e 模型下的o t 协议。在证明了其安全性及其 存在的问题后，我们又在该模型下利用非交互式零知识的知识证明构造了两轮 的并发安全的( 二中取一的) o t ，并将其扩展到了中取k 的情况。接着，我们在 公共引用串模型下构造了一个三轮的并发o t ，并证明了其安全性。由于该o t 协 议的效率并不是很高，因此我们利用 3 9 中所给出的n 协议替换了原协议中所使 用的非交互式零知识的知识证明，得到了一个高效的、五轮的、并发安全的o t 协 议。 1 5 文章结构 在本文的第二章中我们介绍了在文章中将使用到的一些符号、约定，以及一些 相关的定义和可能使用到的一些假设。关于不经意传输的介绍、安全性定义及 其相关的安全模型，则在第三章中给出。在第四章中我们给出了我们的第一个 常数轮的、单机的不经意传输协议，并证明了它的安全性，以及分析了它的性 能。接着我们考虑了如何将它推广为并发安全的o t 协议，以及如何扩展到常规 的o t ( 中取k ) 。在第五章中我们在随机o r a c l e 模型下，提出了一个只需要两轮 消息传送的o t 协议r 0 c o t ，并证明了它的并发安全性。问样，该o t 协议也被 扩展。得剑了中取k 的并发o t 。第六章分别给出了公共引用串模型下的一个 第一章绪论5 三轮和一个五轮的并发安全的o t 协议：c r c o t 和c r & c o t 2 。第七章是对我 们在常数轮的、并发安全的o t 方面的工作的一个总结，在其中指出了还未解决、 有待进一步研究的问题。 第二章预备知识 第二章预备知识 6 在本章中，我们将对在本文中会使用到的符号、定义以及相关复杂性假设做 一些介绍。 2 1 符号和约定 在本文中我们使用标准的符号和约定来书写概率算法、实验、以及交互式协 议。如果a 是一个概率算法，那么a ( 。1 ，z 2 ，；r ) 表示的是输入为z l ，x 2 ，以 及随机串为r 时a 运行后的结果。我们用y a ( x l ，z 2 ，) 来表示y 是随机选 择r 后运行a ( 0 1 ，2 2 ，；r ) 的实验结果。如果s 是一个有限集，那么z s 表 示的是从s 中均匀地选出一个元素z 的操作，并且我们用i 剐来表示s 的大小。 如果n 既不是概率算法也不是集合，那么茁一q 表示一般的赋值语句。我们 用 r 1 ；口】表示随机变量u 的取值集合，它服从由随机过程r 1 - ；所 决定的分布。另外，我们用p r r 1 ；：e 】表示在随机过程r i ；风按照 顺序执行之后，事件e 发生的概率。 我们用( a ，口) 表示一个概率的交互式协议，并且用符号( 口1 ，抛) 一似( z 1 ) ， b ( x 2 ) ) ( z ) 代表运行交互式协议( a ，b ) 这样一个随机过程，公共输入为$ ，a 的 秘密输入为x l ，b 的秘密输入为x 2 ，a 的输出为玑，b 的输出为抛。不失一般 性，我们假设协议似，b ) 执行到最后时a 和b 的输出都包含他们在这次执行中 相互交换的通讯消息的副本。 2 2 相关定义 下面我们给出一些在本文中将会用到的一些定义。 定义1 ( 可忽略函数) 函数，( ) ，如果对于任何正多项式p ( ) ，以及所有足够大 的仃， 1 m ) 高 那么我们称函数，( ) 是关于n , - i 忽略的。 定义2 ( 计算不可区分性) x 答t ) h e n 和y 笪 k ) 。n 是两个分布 族( e n s e m b l e ) ，如果对每个概率多项式时间算法d ，每个正多项式p ( ) ，以及 所有足够大的礼， 1 i p r d ( 矗，1 ”) = 1 卜p r 【d ( k ，1 “) = 1 】i 圪( z ) ，那么，当输入为z 并且可以访 问o r a c l e 只时，机器k 在由下面的式子所限定的期望步数之内，输出 集合兄( 嚣) 中的一个元素： 然 v ( x ) 一k ( 茁) 我们把这个d m c f e 机器称为通用的知识抽取器，并把k 称为知识错误率函 上述定义的有效性条件中，我们所要求的是抽取器在由与p 的成功概率成反 比的某个式子限定的步数( 不一定是多项式步) 之内一定会输出与。所对应的那 个秘密。在1 9 】中作者另外还给出了一个等价的定义，在有效性条件中，我们要 求k 在期望多项式步之内以一定的概率抽取出”吼( 宝) 。( 关于具体的等价性定 义，参见【9 】) 另外，在本文后面所给出的协议中，我们会用到一种称为“多义提交”的协 议，在这里我们给出( 黑盒的) 多义( 串) 提交协议，至于完整的定义，请参见【3 0 l o 定义7 ( ( 黑盒) 多义提交协议( b 1 a 出b 似) e q u i v o c a lc o m n u t m e n ts c h e m e ) ( a ，b ) 是一个交互式协议。我们说似，b ) 是缳盒的，多义提交方案，如果它满足下面的 条件： 第二章预备知识 9 完全( 或者计算上) 隐藏：对所有足够大的n ，任意一个概率多项式时间的攻击 者b 。以及任何长度为kf i 塞里岛= k ( n ) ，七( ) 是某个多项式，的8 和s ，下 列两个概率分布是完全一样的r - 或者计算不可区分的j ： 【( n ，p ) 一似( s ) ，b ) ( 1 “，1 ) 明和【( 0 ，) 一( a ( s ，) 驴) ( 1 ”，1 ) 卢，】 计算绑定：对所有足够大的n 以及任意一个概率多项式时间的攻击者， 下面的概率是关于n 可忽略的：p r ( a ，p ) 一( a + ，b ) ( 1 “，1 ) ；( t ，( t ， ) ) 一 ( a + ( a ) ，b ( 卢) ) ( 1 ”，1 。) ；( t ， ，) ) + 一( j 4 ( 口) ，b ( p ) ) ( 1 ”，1 ) ：i i = l ”7 i = ka 口钉，1 也就是说，没有任何概率多项式时间的攻击者a 能够以不可忽略 的概率将同样的提交信息解提交为两个不同的值。 不可区分性和多义性：存在一个概率多项式时间的模拟器s ，s 的工作分为两 个阶段：提交阶段s 。和解提交阶段) 使得对任何一个概率多项式时间算 法口+ ，它满足： 1 不可区分性对任何串8 o ，1 ) ，分布t ( s ) 和t ( p ) 是计算不可区 分的，这里 t ( s ) = 【( o ，p ) 一蹈( 1 “，1 ) ； ( t ，( ，s ) ) 一罐。( 口) ( o ，s ，1 “) ( p ，( t ，s ) ) 】， t ( p ) = 【( q ，p ) 一似( s ) ，b + ) ( 1 ”，1 ) ； ( t ，0 ，s ) ) 一( ( 口，8 ) ，b ( p ) ) ( 1 ”，1 ) ：( p ，( t ，s ) ) 】 也就是说，对任何长度为k 的串8 ，s 输出一个模拟消息副本饱括提 交阶段和解提交阶段j ，这个副本和伊在与a 的真实交互中的视图是 不可区分的，其中a 在提交阶段提交了8 ，然后在解提交阶段解提交s ，而提交阶段的模拟_ s c 和串s 不相关，并且5 只在酽的模拟结束之后 才输入给。 2 多义性对任意常数c ，所有足够大的n ，任何长度为k 的串sr 这 里= ( n ) ，七( ) 是某个多项式j ，i p o p 1 i 竹一。成立，这里伽和p 1 分别是： p o = p r ( a ，口) 一蹈( 1 ”，1 ) ； ( t ，( t ，u ) ) 一铝( p ) ( 1 ”，1 ，o ，s ) ：口= s 】， p l = p r 【( q ，卢) 一( a ( s ) ，b + ) ( 1 “，1 ) ； ( t ，0 ，口) ) + 一( a ( n ，s ) ，b ( 卢) ) ( 1 “，1 ) ：口= s 】 第二章预备知识 1 0 也就是说，s 能够把提交阶段的模拟消息副本正确地解提交成任何r 长 度为j 的值。 定义8 ( 协议 2 1 1 ) 一个三轮的公开随机串协议( p y ) 如果满足下面的条件，则 我们称它为关于关系用拘协议： 完备性( c o m p l e t e n e s s ) ：如果p ，v 按照协议去做，那么验证者总会接受。 特殊的可靠性( s p e c i a ls o u n d n e s s ) ：从任何长度为佗的公共输入茁以及任何一 对输入为z 的可接受的会话( o ，z ，e ) 和( o ，e ，2 ，) ，其中e e ，我们能很快地 计算出w ，满足( z ，埘) r 。这里a ，e ，z 分别代表第一轮、第二轮和第三轮消 息，并r e 是一个从 o ，l p 中均匀地选择出来的长度为k 促关于n 的某个多 项式) 的串。 完美的特殊诚实验证者零知识( p e r f e c ts h v z k ) - 存在一个概率多项式时 间( p p 刁的模拟器s ，它的输入为z 倚在一个w 满足( z ，叫) 剧和一个随 机的质疑串，输出一个可接受的会话( a ，a ，2 ) 。这个会话的概率分布 和p ( w ) - 与v 之间在输入为z 时的真实会话( n ，e ，z ) 的概率分布是一样的。 协议的d l p 实现 6 4 】：下面这个协议是d 目s c h n o r r 6 4 给出的，用于证明关于 离散对数w 的知识，这个协议的公共输入是，q ，g ，危) ，满足h = 旷m o d p ，这 里竹是一个安全参数，p 是一个均匀选取的n 位素数，满足q = ( p 一1 ) 2 也是一个 素数，9 是阶为g 的群z 中的一个元素。实际上，这是文献中所给出的第一个有效 的协议。 p 从乙中随机选取r ，计算o = 矿m o dp ，并把口发送给y 。 y 从忍中随机选取一个质疑串e ，并把它发送给p 。这里是一个固定的数， 满足2 g 。 p 发送z = r + e 叫r o o dg 给v 。然后y 检查g 。= a h er o o dp 是否成立，p ，口是 否都为素数以及夕， 的阶是否都是g 。如果上面几项都成立，那么y 接受：否 则就拒绝。 另外，g u l l l o u 和q u i s q u a t e r 【4 9 】于1 9 8 8 年给出了协议的r s a 实现。尸向y 证明 他知道y 模n 的口次方根。具体实现请参考【4 9 】。 第二章预备知识 23 相关假设 离散对数问题和d i f f i e - h e l l m a n f n 题：令p 为一个大素数，g p 是一个阶为p 的 群，9 是它的一个生成元。我们可以这样来构造群g ；：令q = i p + l h 一个素 数，召是模q 的乘法群，g 是召中的一个阶为p 的生成元由9 所生成的子群就构成 了我们所需要的群g p 。 定义9 ( 计算d 1 m e - h e l l m a n 问题( c d h ) ) 对任意的概率多项式时间的算法4 ，给 定随机的元素旷，g p ，a 正确计算出g 的概率是可忽略的。这里的概率考虑 了群的选择，旷和矿的选择以及4 所使用的随机串。d e h 段设意味着求解离散对 数问题也是难的。 定义1 0 ( 判定d 1 m e - h e l l m a n 问题( d d h ) ) 对于任意的概率多项式时间的算法4 ， 对于随机选择的g ，y ，z ，4 能成功区分( 旷，矿，9 4 ) 和( 矿，矿，g z ) 的概率是1 2 加上一 个可忽略值。这里的概率考虑了群的选择，z ，y ，z 的选择以及4 所使用的随机串。 定义1 1f 选择目标计算d l f l l e - h e l l m a n 问题( c h o s e n t a r g e tc d h ，简称 j 自c t - c d h ) ) 令g 为一个阶为素数p 的群，9 是它的一个生成元( g e n e r a t o r ) 。 令z 为彩中的一个元素，并让y 一旷。死为目标o r a c l e ，它返回g 中随机的 点五。( p 为h e l p e ro r a c l e 。攻击者b 的输入是( p ，g ，口) ，并且b 可以访问目标o r a c l e 尼和h e l p e ro r a c l e ( ) 。我们用q t 和分别表示b 向目标o r a c l e ：乖【l h e l p e ro r a c l e f i j 问的次数。攻击者攻击选择目标c d h i ；- 题的优势阳咖d 佗t 凹a d 昭一矾( b ) 定 义为这样一个事件的概率：b 输出一组( ( t 1 ，1 1 ) ，( t 2 ，2 2 ) ，( t k ，) ) ，满足对所 有1 。都存在1sj ，g t ，使得t 。= z i ，并且所有的t ；都是不同的，以 及q h 0 ，所有足够大的7 , 和所有的z l r ， p r 【( 6 ，o 们) 一岛( 1 ”) ，7 r p ( 6 ，$ ) 第六章公共引用串模型中的并发o t 伽+ 一a ( j ，n “z ，z ，7 r ) ：( x ，加) r 】 p n ( 1 一礼1 ) 这里我们用m 。来表示概率 p r 5 - 一 o ，1 “，7 r - 一尸( 最$ ) ；v e r z f y ( 5 ，z ，7 r ) = 1 】， 其中的v m y ( ，) 是验证者的验证算法。 r e m a r k s - 在n i z k p o k 中，对于任何算法p ，有效性条件都要成立。也就是 说，即使p 是一个具有无限计算能力的恶意的证明者，抽取器e 都可以从它给出 的证明中抽取出口l r 的证据。因此，我们要求晶输出的串6 必须和公共引用串 具有相同的分布，或者统计上靠近。 6 2 并发安全的o t ：c r s o t a h c e 和b o b 的公共输入6 包含两部分：以和如。a l i c e 的秘密输入为一对消 息( 伽，m 1 ) ，而b o b 的秘密输入为一位消息口 o ，l 。 s t e p1 a h c e 随机地从 o ，1 ，p 一2 中选出一个数r ，计算r a = g - 。 然后再以以为公共引用串，计算一个非交互式的零知识证明7 r a = n i z k p o k a ( 以，r a ，r ) ，用于证明她知道r 的离散对数。 b o b 把r a 。7 r a 发送给a l i c e 。 s t e p2 在收n a l , c e 的消息之后，b o b 首先验证“的正确陛。如果不正确，那 j 、b o b 就中止协议执行；否则，b o b 随机地选择一个数z 0 ，1 ，p 一2 ) ， 计算= 矿和y 1 一，= r a 如。然后，b o b 以如为公共引用串，计算一个 非交互式的零知识证明和= n i z k p o k b ( 如，( y o ，y 1 ) ，z ) ，用于证明他