（计算机软件与理论专业论文）不经意传输协议.pdf

摘要 密码学在当今的政治、经济、军事和日常生活中起着越来越重要的作 用。不经意传输协议是设计一些重要密码协议的基础。例如，不经意传输 协议可以用来设计位承诺协议和零知识证明协议。本文主要包括以下几部 分内容： 在第一章中，首先介绍了些与本文相关的背景知识和预备知识；其 次，对不经意传输的研究状况( 包括经典的和量子的) 进行了分析，探讨 了可以进一步研究的方向。 在第二章中，首先给出了各种不经意传输的定义。如( 统计安 全) 2 取1 位( 串) 不经意传输，( 统计安全) n 取1 位( 串) 不经意传 输，( 统计安全) n 取m 位( 串) 不经意传输协议，并分析了各种不经意传 输协议的关系，得到了如下几个主要结果： 2 取1 位不经意传输可以用来构造2 取1 串不经意传输，反之也成立； 2 取1 不经意传输可以用来构造n 取1 不经意传输，反之也成立； n 取1 不经意传输可以用来构造n 取m 不经意传输，反之也成立。 在第三章，提出一个基于公钥密码系统直接构造n 取m 不经意传输协 议，该协议具有更好的通信复杂性。 量子密码学是密码学里一个新的研究分支，量子密钥分配 协议在实践上被证明是可行的，同时，在理论上被证明是安全 的。1 9 9 4 年，c r 4 p e a u 提出了一个基于量子位承诺协议的量r 不经意传 输协议。但在1 9 9 6 年，l o 和c h a u ，然后是m a y e r s 分别证明了量子位承诺 v 中文摘要 v i 协议是不安全的。从而，基于量子位承诺的量子不经意传输协议也是不安 全的。 在第四章，在量子力学基本理论的基础上( 不基于任何子协议) ， 构造了一个量子2 取1 弱不经意传输协议。该协议满足正确性，相对较弱的 对a l i c e 隐私性和对b o b 隐私性。 2 0 0 0 年，a h a r o n o v 等人提出了一个量子弱位承诺协议。在第五章旱， 在这个协议的基础上，推广了c r 6 p e a u 的工作，构造了一个量子n 取m 不 经意传输协议。该协议满足如下3 个条件：正确性、对a l i c e 的隐私性和 对b o b 的隐私性。 在前几章工作的基础上，第六章提出了量子随机 串不经意传输协议( q r s o t ) ，在q r s o t 协议中，a l i c e 有n 个 位6 l ，b 2 ，b 。，a l i c e ：f g b o b 通过定的方式交互之后，b o b 从这n 个位叶| 得到大约p 儿个位f o p 1 ) ，a l i c e 无法知道b o b 得到的是哪几个位。这 个协议是不经意传输协议的推广。q r s o t 和量子2 取1 不经意传输的不同 之处是，在q r s o t 协议中，b o b 无法确定地选择某个位，他只能被动地 得到某个位。并且，b o b 只以很小的偏差得到大约p n 个位，即他得到超 过+ 6 ) n 个位或者少于( p 一6 ) n 个位( 6 ( 0 ，1 ) ) 的概率小于忆( 岛 1 ) 。 最后，第七章对本文的工作做个总结，并对未来的研究方向做了展 望。 关键词：不经意传输，公钥密码系统，安全，协议，量子，随机性 中图分类号：t p 3 0 9 a b s t r a c t c r y p t o g r a p h yp l a y sa ni m p o r t a n tr o l ei nm o d e r nl i f ei np o l i t i c s e c o n o m y ，m i l i t a r ya n dd a i l yl i f e o b l i v i o u st r a n s f e r ( o t ) i su s e da sak e yc o i n p o n e n ti nm a n ya p p l i c a t i o n so fc r y p t o g r a p h y i nc h a p t e r1 ，w ef i r s tp r o v i d es o m ep r e l i m i n a r yo fc r y p t o g r a p h ya n d q u a n t u mm e c h a n i c s s e c o n d l y ，w ea n a l y s i st h er e s e a r c h e so no b l i v i o u st r a n s f e r ，d i s c u s st h ep o s s i b i l i t yf o rf u r t h e rr e s e a r c h i nc h a p t e r2 ，w ef i r s tp r e s e n tt h ed e f i n i t i o n so fv a r i o u so b l i v i o u st r a n s f e r ， i n c l u d i n g ( s t a t i s t i c a ls e c u r e ) i - o u t o f - 2b i t ( s t r i n g ) o b l i v i o u st r a n s f e r ，( s t a t i s t i e a ls e c u r e ) 1 - o u t o f - nb i t ( s t r i n g ) o b l i v i o u st r a n s f e r ，( s t a t i s t i c a ls e c u r e ) m o u t o f - nb i t ( s t r i n g ) o b l i v i o u st r a n s f e r ，a n a l y s i st h er e l a t i o n sa m o n gt h e 0 t sa n dh a v et h ef o l l o w i n gm a i nr e s u l t s ： 1 - o u t 、o f - 2b i to b l i v i o t i st r a n s f e rc a nb eu s e dt oc o n s t r u c t1 - o u t o f - 2 s t r i n go b l i v i o u st r a n s f e r ，a n dv i c ev e r s a ； 1 - o u t o f - 2b i to b l i v i o u st r a n s f e rc a nb eu s e dt oc o n s t r u c ti - o u t o f - nb i t o b l i v i o u st r a n s f e r ，a n dv i c ev e r s a ； i - o u t o f - 2b i to b l i v i o u st r a n s f e rc a nb eu s e dt oc o n s t r u c tm o u t o f - nb i t o b l i v i o u st r a n s f e r ，a n dv i c ev e r s a i nc h a p t e r3 ，w ec o n s t r u c tam o u t o f - no b l i v i o u st r a n s f e rd i r e c t l yb a s e d o np u b l i ck e ys y s t e mw i t hb e t t e re f f i c i e n c y v i i 英文摘要 q u a n t u mc r y p t o g r a p h yi so n eo ft h en e wr e s e a r c hd i r e c t i o n s o fc r y p t o g r a p h yq u a n t u mk e yd i s t r i b u t i o ni sp r o v e dt ob ef e a s i b l eb o t hi nt h e o r y a n di na p p l i c a t i o n i n1 9 9 4 ，c r b p e a up r e s e n t e daq u a n t m no b l i v i o u st r a n s f e r s e h e m eb a s e do nt h es e c u r i t yo fq u a n t u mb i tc o m m i t m e n t h o w e v e r ，q u a n r u mb i tc o m m i t m e n tw a sp r o v e dt ob ei m p o s s i b l eb yl oa n da l s ob ym a y e r s s o ，t h eq u a n t u mo b l i v i o u st r a n s f e rb a s e do nq u a n t u mb i tc o m m i t m e n ti s u n _ s e c u r e i nc h a p t e r4 ，w ec o n s t r u c taq u a n t u m1 - o u t o t - 2w e a ko b l i v i o u st r a n s f e r o n l yb a s e do nq u a n t u mm e c h a n i c s t h es c h e m es a t i s f i e dt h e c o r r e c t n e s s w e a kp r i v a c yf o ra l i c ea n dw e a kp r i v a c yf o rb o b i n2 0 0 0 ，a h a r o n o v ，e t cp r e s e n t e daq u a n t u mw e a kb i tc o m m i t m e n t i n c h a p t e r5 ，w ee x t e n dt h ew o r ko fc r e a u ，c o n s t r u c t saq u a n t u mm o u t o f - no b l i v i o u st r a n s f e rs c h e m e t h ep r o t o c o ls a t i s f i e st h ef o l l o w i n g3c o n d i t i o n s ： c o r r e c t n e s s ，p r i v a c yf o ra l i c ea n dp r i v a c yf o rb o b i nc h a p t e r6 ，w es h o wan e ws c h e m e ，q u a n t u mr a n d o ms t r i n go b l i v i o u st r a n s f e r ( q r s o t ) i nq r s o t ，a l i c eh a snb i t sb l ，b 2 ，一，b n ，a f t e rt h e i n t e r a c t i o nw i t hb o b ，b o bk n o w st h a th eg e t sa r o u n dp nb i t s ( p ( 0 ，1 ) ) f r o mt h enb i t s ，a l i c ec a n n o tk n o ww h i c hp a r t i c u l a rb i t sb o bg e t s t h i s s c h e m ei sag e n e r a l i z a t i o no fo b l i v i o u st r a n s f e r t h ed i f f e r e n c eb e t w e e nq r s o ta n d1 - o u t o f - 2o b l i v i o u st r a n s f e ri st h a t ，i nq r s o t ，b o bc a n n o tc h o o s e ap a r t i c u l a rb i td e t e r m i n a t e l y ，h ec a no n l yk n o wt h a th eg e tap a r t i c u l a rb i t n e g a t i v e l y f u r t h e r m o r e ，b o bc a ng e ta r o u n dp nb i t sw i t hal i t t l eb i a s t h e p r o b a b i l i t y t h a th eg e t s m o r e t h a n ( p + 6 ) - 礼b i t so r l e s s t h a n ( p 5 ) nb i t s ( 5 ( 0 ，1 ) ) i sl e s st h a n 矿( 印 1 ) f i n a l l y ，i nc h a p t e r7 ，w eh a v eac o n c l u s i o na n dp r o v i d es o m ew o r k sf o r f u r t h e rr e s e a r c h k e yw o r d s ：o b l i v i o u st r a n s f e r ，s e c u r i t y ，p r o t o c o l ，q u a n t u m ，p u b l i ck e y s y s t e m ，r a n d o m 第一章 己i 言 l 口 随着计算机的普及和互联网技术的应用，密码学在当代政治、经济、 军事和日常生活中扮演着越来越重要的角色，有时甚至是决定性的。如_ 战中，图灵破译了德国的密码，加速了德军失败的进程。电子商务的日益 普及，安全性是几个最突出的问题之一，要求密码学提供更安全更有效的 底层支持。密码学在这些需求的推动下，得到了更进一步的发展，并从 直以军用为主转变为军民共用。从事密码学的研究人员也越来越多，不管 是国内还是国外，官方还是民间，对信息安全的重视程度也不断加大了。 但是，随着技术的进一步发展，有些一直被认为是安全的密码算法或 者协议被破解了。在一些商业网站中，对安全性的认识程度还不够高，比 如说，国内大部分提供电子邮件服务的网站没有提供对用户密码提供足够 的安全保护，而密码被窃取的危害则显而易见。 密码分析学是专门分析各种密码算法、协议的安全性的学科，有密码 学研究就必然伴随着密码分析学的研究。密码学和密码分析学犹如矛和 盾，因此，在矛和盾的较量的过程中，从事矛和盾的研究永远不会停止。 这就是密码学研究的魅力之所在。 随着量子密钥分配协议在理论和实践上的成功f 6 ，4 1 ，量子密码学成为 密码学又。个新的热门研究方向。在本章，我们按经典密码学和量子密码 学这种分类方式，逐个展开讨论，介绍一些与本文相关的预备知识以及不 经意传输协议的研究状况。 1 1 1 经典密码学2 1 1 经典密码学 经典密码学包括对称密码算法、非对称密码算法、安全协议等等。相 关知识可以参考 2 9 ，1 4 ，2 8 ，7 3 ，7 5 ，8 9 ，1 0 4 ，1 0 5 ，1 1 ) 6 ，1 1 3 ，1 1 5 ，1 2 6 ，下面 我们分别展开讨论。 1 1 1 对称密码算法 基于密钥的加密解密算法通常可以分为两类：对称密码算法和非对称 密码算法 1 2 1 ，9 5 ，7 4 ，2 6 ，7 7 ，1 1 8 ，4 7 ，8 5 ，8 8 ，2 7 ，1 2 5 ，1 1 1 ，1 1 2 ，4 4 1 。对称 密码算法有时又叫传统密码算法，就是加密密钥能够从解密密钥中推算出 来，反过来也成立【2 9 】a 在大多数对称算法中，加解密密钥是相同的。这 些算法也叫秘密密钥算法或单密钥算法，要求发送者和接收者在安全通信 之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着 任何人都能对消息进行2 , 解密。只要通信需要保密，密钥就必须保密。对 称算法的加密和解密表示为： e k ( m ) = c d k ( c ) = m 常见的对称密码算法有美国数据加密标准d e s 、a e s ( 高级加密标 准) 和欧洲数据加密标准i d e a 等， ，密 崭们 解南 密镪 瞅密密艾壹 图i i ：对称密码算法 豫0 二 i 制之 1 1 经典密码学 3 1 1 2 非对称密码算法 非对称算法( 也叫公开密钥算法) 1 1 5 ，1 5 ，4 2 ，6 3 ，8 1 ，1 1 5 ，1 5 ，4 2 ，6 3 ， s 1 是i t 样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钏 不能根据加密密钥计算出来( 至少在合理假定的长时间内) 。之所以叫做 公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信 息，但只有用相应的解密密钥才能解密信息。在这些系统中，加密密钥叫 做公开密钥( 简称公钥) ，解密密钥叫做私人密钥( 简称私钥) 。私人密 钥有时也叫秘密密钥。为了避免与对称算法混淆，此处不用秘密密钥这个 名字。 明史密瞅毒 图1 2 ：非对称密码算法 用公开密钥k ，加密表示为 e ( k p ，m ) = c 虽然公开密钥和私人密钥聪是不同的，但用相应的私人密钥解密町表 示为： d ( 蜘，c ) = m 常见的非对称密码算法有r s a 、d s a i d i f f i eh e l l m a n 等。 1 1 3 密钥分配协议 所谓协议，就是两个或者两个以上的参与者为完成某项特定的任务而 采取的一系列步骤 1 1 7 ，1 2 0 ，1 0 ，l ，2 ，1 7 ，1 8 ，1 9 ，2 5 ，3 9 ，6 9 ，9 0 ，9 1 ，8 6 ，1 0 8 ， 1 0 9 ，1 1 0 ，1 2 2 ，4 8 。参与者常以a l i c e 、b o b i l e v e 等命名。 1 1 经典密码学 4 密钥交换协议是指在参与协议的两个或者多个实体之间建立共享的秘 密，通常用于建立在一次通信中所使用的会话密钥。协议可以采用对称密 码体制，也可以采用非对称密码体制，例如d i f f i e h e l l m a n 密钥交换协议。 1 1 4 位承诺协议 位承诺协议( 比特承诺协议，b i tc o m m i t m e n t ) 是一个两方协议f 7 l ， 3 3 ，8 ，4 5 ，4 6 ，6 4 ，5 3 ，4 1 ，4 5 ，6 4 1 。两个参与者分别是a l i c e 和b o b 。a l i c e 有 一个输入位b ( 0 或1 ) 。位承诺协议包括2 个子协议，一个是承诺踟议， 另一个是揭露协议。在承诺协议中，a l i c e 通过一定的方式向b o b 承诺她拥 有一个位b 。在揭露协议中，a l i c e 告诉b 给b o b ，b o b 检查这个位的l 是龠 与a l i c e 承诺的值是一致的。位承诺协议应该满足2 个条件： 保密性：在揭露协议执行之前，b o b 无法知道a l i c e 所承诺的那个位： 不可更改性： 在执行承诺叻、议之后，a l i c e 无法更改她所承诺的那个位的 内容。 位承诺协议可以用下面的类比来理解。在承诺协议中，a l i c e 将一 封信放在一个盒子里，并将这个盒子锁上，将钥匙留在自己手中，将 盒子给b o b 。在揭露协议中，a l i c e 说出这封信的内容并将盒子的钥匙 给b o b 。b o b 用这个钥匙打开这个盒子，并将信的内容5 f l l a l i c e 告诉的内容 进行对比，如果一致，说明a l i c e 是诚实的，如果不一致，说明a l i c e 在承诺 中采取了欺骗的策略。 位承诺协议是设计其他密码协议的一个基本模块，例如，在设计掷 币、多方计算和零知识证明等等协议中，都有用到位承诺协议。 1 1 5零知识证明协议 零知识证明协议( z e r o - k n o w l e d g ep r o o f ) 在密码学巾占据着中心的 位置【6 0 1 。零知识证明协议是一个两方协议【1 2 9 ，9 7 ，5 9 ，9 8 ，3 4 ，6 2 ，4 3 ，1 1 5 5 ，9 5 ，2 1 ，5 ，1 6 ，7 6 ，9 2 ，1 1 9 ，6 1 ，5 4 ，7 2 】， 一力- j q a l i c e ( 证明者) ，另力 1 2 经典不经意传输协议 5 为b o b ( 验证者) 。形象地说，零知识证明能够i ：b o b 相信a l i c e 有证明某 个问题的能力，例如，她知道验证两个图是同构的的证据。反之，如果 她不知道如何证明这两个图是同构的，她就无法欺骗b o b 。也就是说，如 果a l i c e 不知道如何证明两个图是同构的，在向b o b 证明的过程中，她被识 破的可能性很大。同时，在这证明之后，b o b 确信和接受a l i c e 懂得证明这 两个图是同构的论证是正确的，但在零知识汪明的过程中，他无法知道这 两个图同构的直接证据，即图同构的对应关系。 1 2 经典不经意传输协议 图1 3 ：不经意传输结构图 不经意传输( o b l i v i o u st r a n s f e r ，o t ) 是设计其他密码协议的基础 7 0 ，1 0 0 。o t 可以用来构造更为复杂的协议，不经意电路计算( o b l i v i o u s c i r c u i te v a l u a t i o n ) ，同时，不基于任何假设，利用它可以为n p 构造一个 零知识证明【7 0 。 1 2 经典不经意传输协议 6 1 。2 1不经意传输协议 不经意传输协议最早是由r a b i n 于1 9 8 1 年提出的f 1 0 7 1 。在o t 中， 有2 个参与者，假设其中一方为a l i c e ( 发送方) ，另一方为b o b ( 接收 方) 。在该协议中，a l i c e 输入1 个位b o ，1 ) ，a l i c e 和b o b 通过一定的 方式交互之后，b o b 只能以= 1 的概率接收n b ( 对a l i c e 的隐私性) ，而 且，a l i c e 无法知道b o b 是否得到了b ( 对b o b 的隐私性) 。b o b 可以确信地 知道他是否得到了位b ( 正确性) 。 1 2 22 取1 不经意传输协议 1 9 8 5 年，e v e n 等人提出了2 取1 不经意传输4 9 1 。在2 取1 不绎意传输协 议中，a l i c e 的输入为2 个位6 0 ，b 1 o ，1 ) ，b o b 的输入为位c o ，1 ) ，a l i c e h b o b 通过一定的方式交互之后，b o b 可以得n b 。( 正确性) ，a l i c e 无法 知道b o b 的选择c ( 对b o b 的隐私性) ，b o b 无法同时得到6 0 和6 】( 对a l i c e 的 隐私性) 。2 0 0 0 年，s t e f a nw o l 跋现2 取1 串不经意传输可以由2 取1 位不经 意传输来构造1 2 8 1 。 1 2 3n 取1 不经意传输协议 比2 取1 不经意传输更一般的不经意传输胁、议足n 取l 不经意传输 9 9 1 。在这个协议中，b o b 只能得n n 个消息( 位或串) 中的1 个。 在1 9 9 6 年，b r a s s a r d 、c r e p e a u 和s a n t h a 发现一种构造n 取1 位不经意传 输协议的方法5 6 。1 9 9 7 年，y a e lg e r t n e r * l l t a lm a l k i n 提出了一个n 取1 分 布式不经意传输协议。2 0 0 1 年，w e n g u e yt z e n g 提出个基于d i f f e - h e l l m a n 问题的难解性的n 取1 不经意传输防议f 1 2 3 1 。 1 2 4n 取i n 不经意传输协议 n 取1 t i 不经意传输( o m n ) 是所有的不经意传输协议中最般 的，尉 a l i c e 有n 个输入，b o b 只能得到其中的i n 个。在2 0 0 2 年，m u 、z h a n g t l v a r a d h a r a j a n 提出了个基于离散对数的n 取m 不经意传输协议【94 。 1 2 经典不经意传输协议 7 至今为止，尚未有人构造出基于一般公钥密码系统的n 取m 不经意传输协 议。2 0 0 4 ：f = 1 i ，c h e n g - k a n gc h u ； u w e n g u e yt z e n g 提出了一个两轮n 取m 不 经意传输协议，这个协议式基于d 衙e h e l l m a n 问题不可解来设计的 1 2 4 1 。 1 2 5 其他不经意传输协议 不经意传输协议还有其他相关的协议，这方面的相关背景，可参考下 面的相关文献。 分布式不经意传输协议【1 0 0 ，1 0 3 ，2 0 自适应查询不经意传输协议1 9 9 】： 可验证同构不经意传输协议【8 4 1 。 1 2 6 不经意传输协议的相近协议 保密信息检索( p r i v a t ei n f o r m a t i o nr e t r i e v a l ，p i r ) 是指用户从重复 分布于k 个数据库的n 位串数据中查询第i 位，保密性意味着服务器无法知 道t 的值，也就是说，服务器无法知道用户的选择 9 3 ，3 5 ，3 6 ，3 7 ，7 8 ，5 7 ，6 8 1 2 ，5 7 ，5 8 ，7 9 ，1 3 ，3 2 】。 1 2 7 不经意传输协议的应用 2 0 0 1 年，a i e l l o 等人提出了不经意传输协议的一些应用，在他们的文章 里列举了如何利用不经意传输协议，保护顾客在购买数字商品时的隐私。 在顾客购买商品的时候，供货商无法知道顾客买的是什么商品，再进步 扩展到什么时候买以及如何买f 3 1 。2 0 0 3 年，曲甄东等人还提出了个基丁 不经意传输协议的合同签订协议f 1 3 2 1 。 1 3 ，量子密码学 8 1 3 量子密码学 在上世纪7 0 年代初w i e s n e r 从数学的角度提出了”共轭编码”这 一概念f 1 2 7 。很遗憾的是，这个思想在十多年以后才被人们所重 视。1 9 8 4 年，c h a r l e shb e n n e t t 和g i l l e sb r a s s a r d 在这个思想的基础卜， 提出了可以实现这一概念的技术原型6 1 。量子密码利用了h e i s e n b e r g 不 确定性原理，窃听会导致通信信道的扰动，从而被合法的通信者所 发现。各种量子密钥分配协议最早的量子密钥分配协议使用了量子 的4 种状态f 6 1 ，此后，其他人提出了各种不同的实现方法，女 i e k e r t 采片j t e i n s t e i n p o d o l s k y - r o s e n 量子纠缠位f 5 0 1 ，b e n n e t t 只使用2 个非正交的罩 子状态【4 】，还有其他各种不同的实现方式 5 1 ，2 3 ，2 4 ，6 7 1 3 1 预备知识 在这一部分，我们介绍在本文中可能用到的量子方面的基础知移 ，更 详细完整的知识可以参考文献 1 0 2 】。 1 3 i i 量子力学计算模型 量子力学的计算模型可以用以下4 个假设来刻画： 假设1 ：状态空间任一孤立物理系统都有一个称为系统状态牢间的复内积 向量空间( b 1 h i l b e r t 空间) 与之联系，系统完全由状态向量所描述， 这个向量是系统状态空间的一个单位向量。 最简单非平凡的h i l b e r t 空间是一个2 维，状态向量成为一个量f 比特 ( 量子位，q u b i t ，q u a n t u mb i t ) 。假设1 0 ) 和1 1 ) 是这个状态空间的 个正交基，那么这个状态空间的任何状态向量可以表示如卜： j 妒) = a l o ) + 6 1 1 ) 这边a 和b 都是复数，满足如下条件： l a l 2 + 1 6 1 2 = l 1 3 量子密码学 9 假设2 ：演化一个封闭量子系统的演化可以由一个酉变换( 幺正变换) 来 刻画。即系统在时刻t 1 的状态f 妒) 和系统在时刻t 2 的状态f 妒，) ，可以通 过一个仅依赖于时间t 1 和t 2 的酉算子u 相联系： 量子系统里的酉操作必须是可逆的。下面是常见的几个酉变换 p a u l i s 门偿聿子jj x = ( ：。1 ) h a d a m a r d 门 y =( z = ( 。11 。) h = ( 激二) c o n t r o l l e d n o tf c n o t l1 7 ：一个双量子位门 、 0 0 1 0 0 0 o l o l 0 o 1 o o 0 ，。一 1 3 量子密码学 1 0 假设3 ：量子测量量子测量由一组测量算子尬。描述，这些算子作用在被 测系统状态空间上，指标m 表示试验中可能的测量结果。若在测量 前，量子系统的最新状态是l 妒) ，则结果m 发生的可能性由 p ( m ) = ( 妒i m 未尬。l 妒) 给出，且测量后系统的状态为 l 妒) ( 妒l m 袁尬。 妒) 测量算子满足完备性方程， 坞= 假设4 ：复合系统复合物理系统的状态空间是分物理系统状态空间的张量 积，若将分系统编号为1 到n ，系统i 的状态被置为l 吡) ，则整个系统的 总状态为i 妒1 ) p i ) 。 1 3 1 2 量子纠缠( q u a n t u me n t a n g l e m e n t ) 考虑如下包含2 个子系统的量子系统h a j i h b ；设h ) ( i = 1 2 ) 表 示h a 的正交基，l i b ) ( i = l 2 ) 为h b 的正交基。量子力学将这两个子系 统连接成h i l b e r t 空间h aoh b ，也就是说h i l b e r t 空间由状态i i a ) o1 2 b ) 生 成。有时，张量积的符号。可以省掉，i t a ) o i 咕) 就可以写成1 i a ) h b ) 。 任何基向量h ) i i b ) 的线性组合都是这个系统的一个向量，这个系统的 任何状态i 妒) b 都可以写成 j ；f ，) a 日= 气i l i a l i b ) c i ，是复系数，并满足。l c i , j 1 2 = 1 与经典的信息处理方式相比，纠缠赋予量子信息处理一螋很奇特的能 力。如，量子纠缠态被用来作为量子远程通信( q u a n t u mt e l e p o r t a t i o n ) 7 ， 超密集编码( s u p e r d e n s ec o d i n g ) 3 0 】和基于b e l l 定理的量子密码 5 0 。 1 4 量子不经意传输协议 1 3 2 量子密钥分配协议 1 9 8 4 年b e n n e t t 和b r a s s a r d 矛l j 用量子力学原理设计了一个在通信的双方 之问创建一个共享密钥，也就是b b 8 4 协议。这是最早的也是最有名的量子 密钥分配协议。 在量子密钥分配协议模型中，a l i c e 发送一些非正交的量了状态 给b o b ，b o b 通过_ 、一定的方式测量这些量子态。然后利用电话( 不安全 的方式) ，他们确定对于e v e 是否对这些量子态有所改动。如果没有，他 们共同拥有具有安全保证的共享密钥。必须注意的是，a l i c e s f l l b o b 事先 必须共享一些认证的信息，否则，b o b 就无法确认在通话中的对象是小 是a l i c e ，还是一个模仿者。这个密钥可以作为加密和认证。 1 _ 3 3量子位承诺协议 1 9 9 3 年，g i l l sb r a s s a r d 等人提出了一个量子位承诺协议，并声称该协 议对f - 2 个参与者来说都是证明安全的【9 。然而，1 9 9 6 年，：舣：l o s h c h a u 8 2 ，然后是m a 睥r s 【8 7 ，分别证明了无条件安全的量子位承诺协议被证明 是不可能的。2 0 0 0 年，a h a r o n o v 等人提出了一个量子弱位承诺协议 4 0 o 1 4 量子不经意传输协议 在量子的情形下，c l a u d ec r 6 p e a u 提出了一个量子2 取1 小经意传输协 议，该协议的安全性是基于量子位承诺的安全性。由于量子位承诺协议被 证明是不可能的【8 2 ，8 7 。所以，基于量子位承诺的量子不经意传输也是不 安全的( 3 1 。1 9 9 7 年，l o 证明无条件安全的量子2 取l 不经意传输协议也是 不安全的。 1 5 本文的工作 本文后面的工作主要包括以下几部分内容 l ，5 本文的工作 1 2 在第二章中，首先给出了各种不经意传输的定义。如( 统计安 全) 2 取1 位( 串) 不经意传输，( 统计安全) n g x l 位( 串) 不经意传 输，( 统计安全) n 取i n 位( 串) 不经意传输协议，并分析了各种不经意传 输协议的关系，得到了如下几个主要结果： 2 取1 位不经意传输可以用来构造2 取1 串不经意传输，反之也成立 2 取1 不经意传输可以用来构造n 取1 不经意传输，反之也成立 1 2 取1 不经意传输可以用来构造n 取m 不经意传输，反之也成立。 在第三章，提出一个基于公钥密码系统直接构造1 1 取m ) v 经意传输协 议，该协议具有更好的通信复杂性。 量子密码学是密码学里一个新的研究分支，量子密钥分配 协议在实践上被证明是可行的，同时，在理论上被证明是安全 的。1 9 9 4 年，c r 6 p e a u 提出了一个基于量子位承诺协议的量子不经意传 输协议。但在1 9 9 6 年，l o 干g c h a u ，然后是m a y e r s 分别证明了量子位承诺 协议是不安全的。从而，基于量子位承诺的量子不经意传输协议也是不安 全的。 在第四章，在量子力学基本理论的基础上( 不基于任何子协议) ， 构造了一个量子2 取1 弱不经意传输协议。该协议满足正确性，相对较弱的 对a l i c e 隐私性和对b o b 隐私性。 2 0 0 0 年，a h a r o n o v 等人提出了一个量子弱位承诺协议。在第五章里， 在这个协议的基础上，推广了c p e a u 的工作，构造了一个量子n 取m 不 经意传输协议。该协议满足如下3 个条件：正确性、对a l i c e 的隐私性和 对b o b 的隐私性。 在前几章工作的基础卜，第六章提出了量子随机 串不经意传输协议( q r s o t ) ，在q r s o t 协议中，a l i c e 有n 个 位b 1 ，b 2 ，k ，a l i c e $ 口b o b 通过一定的方式交互之后，b o b 从这n 个位中 得到大约p n 个位( o p 1 ) ，a l i c e 无法知道b o b 得到的是哪几个位。这 个协议是不经意传输协议的推广。q r s o t 和量子2 取l 不经意传输的不同 之处是，在q r s o t 协议中，b o b 无法确定地选择某个位，他只能被动地 15 本文的工作1 3 得到某个位。并且，b o b 只以很小的偏差得到大约p - n 个位，即他得到超 过( p + 6 ) n 个位或者少于( p 一6 ) n 个位 e ( 0 ，1 ) ) 的概率小于p ( e 5 1 ) 。 最后，第七章对本文的工作做个总结，并对未来的研究方向做了展 望。 第二章 各种不经意传输协议之间的关系 2 1引言 r a b i n 于1 9 8 1 年首次提出了不经意传输协议的概念【1 0 7 】。1 9 8 5 年，e v e a 等 人推广了这个概念，提出了一个基于公钥密码体制的2 取l 不经意传输咖议 f 4 9 1 。在1 9 9 6 年，b r a s s a r d 、c r e p a u 和s a n t h a 发现一种构造n 取1 位不经意传输协 议的方法5 6 1 。2 0 0 2 年，m u 、z h a n g ； n v a r a d h a r a j a n 提出了一个基于离散划数 的1 2 取m 不经意传输协议【9 4 1 。 到目前为止，尚未有人对各种不同的不经意传输协议之问的关系进行进步 深入的研究。在本章，我们首先给出了各种不经意传输协议的定义。然后，存这 些定义的基础上，探讨各种不经意传输协议的之间的关系。从而得到结论，这些 协议之间可以相互构造，即由其中的一个町以构造出另外一个。 本章按如f 方式展开， 1 在第2 部分，我们给出了各种不经意传输协议的形式化定义 2 在第3 部分，我们探讨了位不经意传输和串不经意传输的关系 3 在第4 部分，我们探讨了2 取1 不经意传输和n 取m 不经意传输之间的关系 4 在第5 部分，我们给出了本章的小结。 1 4 2 2 定义 1 5 2 2定义 图2 1 ：不经意传输构造关系图 在分析各种不经意传输协议之间的关系之前，我们首先给m 完美2 取1 位不纷 意传输协议和完美1 1 取m 位不经意传输协议的定义： 定义2 1 完美2 取j 位不经意传输( b i t p o 码) 在一个两方协议中，a l i c e 的输入为2 个位6 0 ，6 1 o ，1 ) ，b o b 的输入为c o ，1 ) ， 如果一个协议为完美2 取位不经意传输协议，必须满足如下3 个条件： 正确性：，归0 6 得到b 。fb o b 是诚实的j j a l i c e 是诚实的= ； 对b o b 的隐私性：户弘z i c 8 得到cb d 6 是诚实的，= ； 对a l i c e 的隐私性：尸归0 6 得到蛞1a “c e 是诚实的，= 在定义2 1 中，我们说某一方是诚实的，即这一方按照l 办议的规定来执行， 没有偏离协议的规定。正确性说明了在a l i c e 和b o b 都是诚实的，即双方都遵守协 议的前提下，b o b 总是可以得到k ，或者说得到6 c 的概率是1 ；对b o b 的隐私性说 明，a l i c e 得到c 的概率是 ，也就是说，和a l i c e 随机地猜测到c 的概率是一样的。 2 2 定义 1 6 即，如果她通过偏离协议的方法想得到c 的概率不会比她遵守协议得到c 的概率 大；x , j a l i c e 的隐私性说明，b o b 可以通过猜来得到b ( - = 1 一c ) 的概率是 ，如果 他通过偏离协议的方法想得到6 i 的概率不会比他遵守协议得到蛞的概率大。 对应地，我们可以得到完美n 取i n 不经意传输的定义： 定义2 2 完美诹m 位不经意传输( b i t p d z 孑) 存一个两方协议中，a l i c e 的输入为n 个位b 1 ，6 礼 o ，1 ) ，b o b 的输入为m 个小 同的选择c 1 ，c m l ，n ) ，如果一个协议为完美椭i m 位不经意传输协议， 必须满足如下价条件： 正确性：p b o b 得到6 ib o b 是诚实的且a “c e 是诚实的，= j ，i c l ，c m ) ； 对b o b 的隐私性：p a l i c e 衔l j jb o b 是诚实的，= 署，j e l ， ，c m ) ； 对a l i c e 的隐私性：尸f 田d 6 ! 导到ba 是诚实的，= ， j 1 ，一，n ) 一 c l ，) 。 在定义2 2 中，正确性说明了在a l i c e 和b o b 都是诚实的，即双方都遵守协议 的前提下，b o b 总是可以得到“，i c 1 ，c m ) ：对b o b 的隐私性说明，a l i c eu j 以通过猜来得到。，的概率是等，如果她通过偏离协议的方法想得到c ，( ， c l ，一，c 。) ) 的概率不会比她遵守协议得到c j 的概率大；对a l i c e 的隐私性说 明，b o b - 以通过猜来得至l j b j ( j 1 ，n ) 一 c 1 ，) ) 的概率是 ，如果 他通过偏离协议的方法想得到6 ；的概率不会比他遵守阱 义得至1 b j 的概率大。 我们无法构造得到完美不经意传输，但是，我们可以放松对a l i c e 隐私性的限 制，得到统计意义安全的不经意传输。 定义2 3 统计安全锨j 位不经意传输( b i t s o 码) 在一个两方协议中，a l i c e 的输入为b o ：和b 1 ，b o b f i q 输入为c o ，1 ) ，如果一个防 议为统计安全鲰j 位不经意传输协议，必须满足如f 3 个条件： 正确性：-