（概率论与数理统计专业论文）安全多方计算以及一个新的可公开验证秘密分离方案.pdf

摘要 安全多方计算( c i i m u l t i p 8 r t y 啪p u t a t i o n ) 是目前国际密码学界的一个研究热点如果可 以安全的计算计算任何函数，就掌握了一个强大的工具，实际上任何一个密码协议都可以归结 为一个特殊的安全多方计算协议特殊的安全多方计算协议的涉及与分析又是当前人们致力研 究的课题秘密分享是一种分发、保存和恢复秘密信息的方法，是信息安全和数据保密的重要 手段之一它在门限密码学、安全多方计算，电子商务、电子选举、密钥托管等诸多方面有着 广泛的应用。可验证秘密分享是解决多方安全计算的一个基本手段，可验证秘密分享方案是对 秘密分亭安全性的加强，可以验证秘密份额的合法性，可公开验证的秘密分享方案也是一个具 有很多实际应用的协议， 本文主要工作如下： 首先，对多方安全计算进行了简单的介绍和描述，总结了常用的安全多方计算协议；其 次，对秘密分享方案和应用进行了描述和研究，为后面给出一个新的方案做了背景描述，对可 验证秘密分享进行了研究，并且提出了一个基于双线性映射的可公开验证的秘密分享方案；最 后对给出的可公开验证的方案的效率和安全性做了分析。 关键词多方安全计算，秘密分享，可验证秘密分享，可公开验证的秘密分享，双线性映射 a b s t r a l c t s e c u r em 1 1 l t i - p a r 睁c 0 瑚p u t a t i j 8af g c u sj nt o d a 旷s 口y p t o 笋a p h yr 髑e 篮c k w ec 啦船c 】r e l y c o m p u t ea n yf i ：m c t i ，i tm 咖t h a t 耽h o i d8p 们陀r f l l l 伽l ，j nf h c t ，a 玛7c r y p t 0 乒印b yp 】删 咖b er e d l l o e d as p _ e c i a l c u r en n n t i - p a r t yp l 吲 o c 0 1 t h ed 鼯i 昏1a n d 撒l a i y 豳o fs p e c i a l 鼬删m 1 1 l t i - p 咖锄p u t a 舡o np t o c o l8 r e 蝴t h e rs i 鲥此蛐tt 叩i 翻f 撕m a n y 瑚e a r c b e 鹅 s o 口酏b h a 曲瞎8 c h 锄舱i sa m e t h o d t od i 8 打i b u t e ，s 撕缸dr e c o n s t m c ta $ e c 蹴i t i 8o o f t h e m o s ti m p o r t a n tt e c h n i q 啷o fi n 如衄a t i o ns e c l i t ya dd a t am l c r y p t i o n i ti 8w i d e l yu 鼬di n t h r 鹤h o l dc r y p t 蛔，e l e c t 瑚i cc o 姗e r o e ，e l e c t r o n i ce l e c t i ，k e ye 吕吼o w ，e t c ap u b h c l y w r m a b l e c r 武s h 8 r i n g ( p v s s ) $ d l e m ei saw r i 丘a b l e8 e c r e ts 出蛐ew i t ht h ep r o p 呻t h 8 tt h e v 鼍i l i d i t y0 ft h e 破l 删d i s t r i b u t e d 姆t h ed e 妇c a nb ew ! r i 丑e db ，r 柚yp a r t y ；h e n c ew 缸丘c a t i o ni s n o tu m i t e dt ot h e 唧e c t l v ep a r t i c 岫觚t sr e c e i 、，i n gt h e 曲l 硼w e 西、吧an e wc o n s t r u c t i o nf o r p v s s 文五e m eb a 8 e d 彻b i l i n e 村m a p b w h i c 妇r 锄b ee m d 曲t l yc 0 恤栅r t e d me i 】i p t 衍c 1 l | 惴 8 n d8 i c h i e 嘲g o o dp 娟咖a n o eb o t hi ne 伍c i e n c y 鼬di n 峙t y p eo fi n t r a c t 8 b i l i t y 嘲脚p t i o n k e yw o r d 8 船c t l r em u m 岬哪啪p 喊m ，钾c r e t 妇i n g ，v 盱m a b l e 卵口e t 曲埘n g p u b h c l y v 盱i 丑b b k8 e 皤e t8 h a r i n g 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：缴 加啤( 月1 曰 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： ：内部5 年c 最长5 年，可少于5 年) ! 秘密1 0 年( 最妖l o 年，可少于1 0 年) ；机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： b 。6 年g 月1 日 第一章引言 网络技术的飞速发展，使人们进入信息时代，网络已经是人们生活中不可缺少的交流媒 介人们通过网络收发电子邮件，进行电子商务以及获取及时信息。在给人们生活和工作带来 便利和变化的同时，也带来了相应的信息安全隐患利用网络犯罪，恶意传播计算机病毒以及 宣传不良文化，也给人们正常的信息生活带来了很多的威胁。信息( 数据) 同时作为一种重要 的资源和财富，越来越受到人们的重视，对有价值的和敏感的信息( 数据) 的保护也是刻不容 缓的现实。在社会生活中，大量的敏感信息如病例、法庭记录，资金转移、私人财产等常常通 过公共通信设施或计算机网络进行交换，需要保证这些信息的保密性和真实性；国家安全中， 大量的机密信息( 数据) 因为安全需要得到保护简而言之，信息安全是直接关系国家安全、经 济稳定的严重问题，日益受到各方面的关切。而现代密码学可以用于解决信息的保密性、完整 性，可用性、可控性和不可抵赖性，为信息安全提供关键理论和技术。是保护信息安全非常有 效的手段近年来，密码学得到长足的发展，其应用已经渗透了社会生活的各个方面，比如数 据加密，信息认证，网络安全，电子选举、电子现金等。 1 1 安全多方计算的基本概念 安全多方计算( 8 mm i l l t j - p a r t y 唧u t a t i o n ) 被定义为有n 个参与方希望正确地 计算一个由每个参与者的局部输入的共同的函数，并且尽量保持局部输入的安全性。 具体说，由f 1 个参与方p = p l ，p 2 ，p 。) ，每一方有局部输入z 1 z 。，函数，计 算，( 。l ，) = l ，。) ，使得每一方p l ，只是知道相应的输出轨。 1 2 秘密分享的基本概念 秘密分享( 8 e c r e t8 h ”m g ，也称为密钥分享或密钥共享) 是一种分发、保存和恢复秘密信 息的方法，其概念最早由s h m i r i l 】和b k i l d e y 囟分别提出，许多学者都对秘密分享方案进行 了研究，其中最常见的是门限体制( 即接入结构为门限接入结构) ，比较有代表性案有s h a m i r 的l a f a n g e 插值多项式体制【1 】，b l a i d e y 的矢量体制翻、a t h 等人的基于中国剩余定理 1 的同余类体制1 4 】等它是指将秘密信息8 分割成若干份额( 8 h a r e ，也称为碎片p i e 。或影 子8 h a d o w ) 在一组参与者p = t p l ，p 2 ，p 。) 中进行分配，使得每一个参与者都得到关于 该秘密的一个份额，并只有p 的一些特定子集能有效的恢复s ，而p 的其他子集不能有效的恢 复8 ，甚至不能得到关于$ 的任何有用信息。 通常，一个秘密分享方案由一个秘密分发者( d l 口) d 、参与者( p a r t i c i p a n t s ) 集 合p 、接入结构( 8 0 0 e 咖u c t u r e ) r 、秘密空间s 、份额空间t 分配算法、恢复算法等几个 方面构成。其中参与者集合是参与秘密分享的成员集合；接入结构r 指出哪些参与者集合可恢 复秘密信息，即r 是合格子集的集合。 秘密空间指秘密信息的取值范围；份额空间指秘密份额的取值范围；分配算法是一个以秘 密信息为输入，多个秘密份额为输出的多项式时间算法；恢复算法是一个以多个秘密份额为输 入，秘密信息为输出的多项式时间算法。构造一个秘密分享方案就是在一定的接入结构基础 上，设计相应的份额分配算法和秘密恢复算法，使得接入结构中的所有合法子集都能利用秘密 恢复算法获得秘密信息，而所有非合法子集均得不到被分享秘密的任何信息。如果在一个秘密 分享方案中，所有非合法子集都得不到关于被分享的秘密的任何信息，则称该方案是完备的 ( p e 正! c t ) 一个秘密分享方案的信息率( i n 】f o r m a t i o nr a t e ) 定义为p = 1 0 9 l t l 1 0 9 p i 如果 一个秘密分享方案的信息率为1 ，则称其为理想的( i d e a l ) 1 3 可验证秘密分享的基本概念 在秘密分享方案中，分发者、参与方可能有欺骗行为。所以需要验证秘密份额的合法性， 如果密码份额不单各个参与方可以验证自己份额的合法性，而且相互之间可以验证彼此的合法 性，那么就是一个可公开验证的秘密分享方案( p u b u c l yv 枷a b l e8 e c r e ts h 8 血g8 c h ) 可验证秘密分享( 曲a b l e8 e c r e t8 h a r i d g ，简记为v s s ) 是解决多方多方安全计算的一 个有用的工具。s h m j r q 和b l a 王d 呵圆最早独立地提出了秘密分享的方案，许多学者都对秘 密分享方案进行了研究，在对秘密分享体制研究深化过程中一个比较重要的概念是可验证 秘密分享( 衄a b l eb e c r e t8 h a r i n g ) 它是由c h o r 等人于1 9 8 5 年在文献闭中提出，主要 目的是为了解决分发者的欺骗问题。v s s 是在秘密分享的基础上增加了一个验证算法而形成 的。v s s 概念一经提出，许多安全、高效的v s s 方案相继出现。以文献【1 0 】和【1 1 1 中方案 为代表的v s s 方案具有较好的安全性和较高的效率。另一个重要的概念是可公开验证秘密分 享( p u b h c i yv 目进a b l es e a 喊s h a r i n g ，简记为p v s s ) ，它用来解决分发者和分享者相互欺骗 2 的问题。1 9 9 6 年，s t 8 d l 于文献【嘲中在v s s 基础上进一步提出p v s s 的概念，使得不仅验 证者( 不必是分享者) 可以验证秘密分发过程的正确性，分享者也可以验证自己所持有的份额 的正确性。f 、抽a l c i 和o k a m o t o 于1 9 9 8 年在文献l l 习中提出了一个效率相对较高的p v s s 方 案。后来，s 出o e n m a l 在文献f l4 j 中对s t a d l e r 和e i 8 a 垴等人的p v s s 模型做了简单的改 进。在这些方案中，验证算法依赖于公钥加密、零知识证明等工具，结构一般比较复杂，效率 也不是很好。 1 4 本文的主要内容 本文研究的主要问题是：安全多方计算的概念简单介绍，可验证秘密分享作为具体实现安 全多方计算的一个重要工具的研究，以及可公开秘密分享的研究；给出了一个新的基于双线性 映射的可公开秘密分享方案 本文各章内容安排如下：第二章简单介绍了多方安全计算的概念和一些基本的结果。对多 方安全计算的一些特性和概念做了具体的描述和定义，给出了一些具体的结论。并且对常用安 全多方计算协议进行了总结和介绍 第三章总结了秘密分享以及可验证秘密分享研究状况和结果。非正式的描述了秘密分享和 可验证秘密分享的模型，并做了简单的比较和分析。 第四章给出了一个新的基于双线性映射的可验证秘密分享方案。本章先介绍了9 8 p 伊o u p 的概念和性质，简单引入了必要的关于双线性映射的概念和关键性质，并利用这些性质构造了 一个新的简单的可( 公开) 验证的秘密分享方案，给出了简单的性能和安全性的分析。这也是 本文的主要成果 3 第二章安全多方计算简介 2 1 安全多方计算的概念和性质 安全多方计算协议( 8 e c l l r e m i - p t y p u t a t i o n ) 要解决的问题可以描述如下：一组 参与者希望共同计算某个约定的函数，每个参与者提供函数的一个输入，出于安全考虑，要求 参与者提供的输入对其他人保密因此安全多方计算有两个最基本的要求： 1 隐私性( p r i v a 呵) ：每个参与方除了需要知道的输入以外任何其它信息都不会得到； 2 正确性( c o e c t n e ) ：每一个参与方都可以得到正确的输出结果。 如果存在安全可信第三方( 我们称其为d e a b ) ，则安全多方协议所要解决的问题可以 轻易地得到解决：只需各参与者将各自的输入交给d e a l 日，由d e a l e r 计算出函数值，再将函 数值公布给各参与者但现实中很难找到这样的d e a l 口，从而安全多方计算协议的研究应运而 生，目前安全多方计算已得到许多学者的研究。a cy a o 于1 9 8 2 年最早提出了两方安全计 算协议1 2 鞠之后，o g 0 1 d r e i c h ，s ，m i c 8 l i 及a w i g d 口s o n 提出了可以计算任意函数的基于密 码学安全模型的安全多方计算协议【l 川，证明了存在被动攻击者时n 一c e 的协议是存在 的；存在主动攻击时m 一1 ) 一b e c e 的协议是存在的；d c h a m ，c c r e p 和i d m g a r d 中对信息论安全模型下的安全多方计算进行了研究，证明了在被动攻击下m 一1 ) 一8 e c e 的协议是存在的在主动攻击下( 【n 2 一1 ) 一c l r e 的协议是存在的1 5 1 此后，许多学者 在如何提高安全多方计算协议的效率，如何对安全多方计算进行形式化的定义如何对通 用的安全多方计算协议进行剪裁使之能更有效地适用于不同的应用环境，新的安全多方计 算协议的构造方法安全多方计算攻击者结构定义等方面进行了大量的研究。s g o i d w a 8 8 日 和l k m n 对于计算模型下，大部分协议参与者( 超过半数1 都被买通情况下的安全多方计算 协议1 3 田。o g o l d r e i c h ，s g 0 l d 口和n l i n i a l 对于不安全的通讯信道拥有无限计算能 力的攻击者模型下的安全多方计算协议进行了研究【2 9 】。r q 船o v s 蛔和m y l l n g 在安全信道 模型下对移动攻击者( m 0 b n ea d v e r 8 a r i ) 进行了研究f 3 0 】。s m i c a j i ，p m 替w a y1 3 1 】和【3 2 】 对安全信道模型下的安全多方计算给出了形式化的定义。 4 多方计算的环境可以包括小到简单的c o i n t 0 i n g 和b r o a d c a s t ，复杂到电子选举，电子 拍卖和p n 恤i n f o m m t i o nm t r i e v a ls c h e 。然由于安全多方计算的综合性，它可以建立模 型解决几乎所有的密码学问题( 包括经典的加密和认证) ，因此关于安全多方计算的可行性 ( 6 b i b i h 锣) 和不可行性( i n f e a 8 i b i l i 睁) 是密码学理论和实践研究的一个基础方面。 假设参与方是p = p l ，p 2 ， ，我们考虑如下模型：一个a d a r i a le n t 姆控制 了参与方的一个子集，并且打算攻击协议执行。我们称被a d v e m a r i a le n t i 钾控制的参与方 为c o m l p t e d 。显然安全协议应该可以承受任何敌对攻击。显然我们无法给出一个清晰确定的关 于s e 咖n 虬l l t i - p a r t yc 伽1 p u t g b o n 的安全( c i l r i t y ) 的定义。但是，我们可以认为如下是 安全的中心性质： ( 1 ) p r i v a c y ：没有任何一个参与方可以知道预先输出以外的信息； ( 2 ) c ( n e c t n e 每一个参与方可以得到保证接受到的输出是正确地； ( 3 ) i n d e p d e n c e0 fi n p u t s 就是说c o m l p t e dp 枷的输入和h o n e 8 tp a r t i 鹤的输入是相互 独立的； ( 4 ) g u 目8 n t e e do u 七p u 七d e h w 即协议的执行不因为敌对的攻击就中止； ( 5 ) f a j r e ：c o r m p t e dp a r t i 接受到输出当且仅当h o n tp a r t i 接受到输出。 一般的标准的安全定义模型是这样的：考虑一个理想模型( 耐e a lw o r l d ) ，在这个理想模 型中参与方可以简单的按照协议的规范进行计算，得到输出结果。h o n e s tp a r t i 只要把自己的 输入传到信任方( i n c o m l p t i b l e ) ，然后接受计算结果显然这个模型满足以上的安全性质 考虑现实模型( r e a lw o r l d ) ，在这个模型中没有可以信任的外部信任方，参与方只能在没有 任何帮助情况下参与协议执行。尽管如此，一个现实模型应该模仿( e u l a t e ) 理想模型，也 就是说，一个协议被认为是安全的( 8 e c l l r e ) ，如果没有敌对方可以在现实模型里作出的危害多 于在理想模型里的危害。也就是说，任何对手在现实模型里成功的攻击也相应的在理想模型中 存在一个对手可以成功的执行相同的攻击；更形式化的说，一个协议的安全是建立在比较现实 模型执行的输出和理想模式的输出。也就是说，任何敌对方攻击现实模型中的协议执行，相应 的存在一个理想模型的敌对手的攻击，而且现实模型和理想模型中的对手和参与方的输入、 输出具有相同的分步。这也就是一个现实协议模仿( e m u l a t 8 ) 理想模型。这个安全程式被称 为：i d e a l r e a ls i l m l 址i o np a r a d i g m 5 以上是一个过分理想的模型，当多数参与方是姗p t e d ，则显然不可能得到一个保证输 出和公平的通用协议用于安全多方计算。所以在放松定义的情况下允许对手允许放弃( 8 b o r t ) 参与协议执行( 这个破坏了g l l t e e do u t p u td e l i _ v e r y ) ；同样如果对手在先于诚实方得到输 出后放弃协议也就破坏了f a i m 。 2 2 对手模型以及能力 对手模型以及能力( 血l w r s 8 r i a l r ) l 、c 0 r m p t i o n8 七r a t e 科：考虑参与方什么时间和如何被颠覆的 ( a ) s t 8 t | c 咖p t i m o d e l ；在这个模型中，假设对手拥有固定的控制参与方，在协议执行 过程中保持不变； ( b ) a d 印t i v e p t i m o d d ：也就是说对手可以在协议执行的时候选择颠覆参与方。 2 、可允许得对手行为( 灿l 刚a d v 口i a ib e h a v i o r ) ( a ) s 豇h e s ta d v h s a r 妇：指所有参与方忠实的执行协议，但是对手可以获得所有被颠覆 方的内部状态，而且可以利用它们活得隐秘信息； ( b ) m a 肛c i o ma d w a r 油：指颠覆方可以任意的不按照协议执行，而按照对手的指令 3 、c o m p j e 菇奶我们也会考虑对手的计算复杂性，一般有两个尺度 ( a ) p o l ”i o m i “t i m e ：指的是对手可以在多项式时间参与协议运行，一般对应于c o m p u t t i o n a lm o d d ； ， ( b ) c p u t a t i a l l ym i b o m l d e d ：指的是对手具有无限的计算能力，对应于i n 】f o r ma _ t ：| 蚀 t h e o r e t i cm o d e l 。 2 3 一些简单结果 一些关于安全多方计算得简单结果，假设n 代表参与方的数日，t 代表可能被颠覆的参与 者的上界，则有： ( 1 ) t n 3 ，则在p 而m 协p o i n t 网络中安全是可以保证的。在锄p l l t a t j 加越m o d e i 和h 1 - f 0 哪a t i o nt h e o r e t i cm o d e l 中也是安全的。 6 ( 2 ) 竹2 ，则在b r o a d c a 8 tc h 姐n e l 情况下也是安全的在p l l t a t i 伽_ a lm o d d 和i d 蠡m m 8 t i o nt h r e t i cm o d e l 中也是安全的。 ( 3 ) t n 2 ，安全多方协议可以在b r o a d c a s t 出a n n e l 并且存在t r 日l p d 0 0 rp 面t a t i o n 8 情况 下是安全的而且只能在p u t a t i o 玎_ a lm o d e l 在i n f o | m a t i o nt h e o r e t i cm o d e i 不存在 类似结果。 2 4 常用安全多方计算协议 下面简要介绍一下目前常用的四类安全多方计算协议。 2 4 1基于o t 的安全多方计算协议 这种安全多方计算协议的基础是o t 子协议：发送者s 有个输入d l d 2 ，丸 o ，1 ，接收者r 有输入z 1 ，2 ，田，协议执行后，r 得到由而不知道除面外的s 的其 他输入，s 不知道r 的选择f 为表述方便，我们将o t 子协议记为d 叫( d l ，d 2 ，如) ，f ，只用 o t 子协议有许多构造方法，利用任何公钥密码系统都可以构造o t 子协议。 下面介绍如何利用0 t 子协议进行安全多方计算。此类安全多方计算可以计算任意的比特 运算函数，我们知道所有的比特运算都可以分解成二元a n d ，x o r 运算及一元n o t 运算的 组合，因此只要利用o t 子协议可以安全地计算二元a n d ，x o r 运算及一元n o t 运算，则 可以安全地计算所有比特运算函数为了表述方便，我们将x o r 运算记为o ，将a n d 运算 记成，将n o t 运算记成1 其计算过程可以大致的分为三个步骤： 输入阶段：n 个参与者p 1 ，r 拥有各自的函数输入自变量甄0 = l ，2 ，n ) o ，1 ，只将其自变量z 。随机分解成，l ，。，2 ，茹。，。使得= 茹t ，1 0 z 。，2 0 o z 。一- 并将z 。j 秘密发送给只。 计算阶段： ( 1 ) = 元x o r 运算一一设运算逻辑上的输入分别为8 b ( a ，b 可以是初始输入，也可以是计 算过程的中间结果) ，且a ，b 已经分别被表示成口= o l 0 0 2 0 o 口。，6 = 6 1 0 6 2 毋6 。， 其中只只知道，b 则经过x o r 运算后，各只将其x o r 运算输出设置为o 。o6 。 运算的正确性可由下式保证： 0 6 = ( 口1 0 屹o o d 。) o ( 6 1 0 b o o k ) = 1 0 6 1 ) o 扣2 0 b 2 ) o o ( 口。o k ) 7 ( 2 ) 一元n o t 运算一一设运算逻辑上的输入为a ( 8 可以是初始输入，也可以是计算过程 的中间结果) 且a 已经被表示成口= 8 1on 2 0 o 口。，其中只只知道啦则经 过n o t 运算后，只将其n o t 运算输出设置为可。其他参与者n o t 运算输出设置 成口。g = 2 ，3 ，n ) 运算的正确性可由下式保证： 在= 苟百面面瓦= 石。口2 0 o 口。 ( 3 ) 二元a n d 运算一一设运算逻辑上的输入分别为a ，b ( a ，b 可以是初始输入。也可以是计算 过程的中间结果) ，且a ，b 已经分别被表示成口= 4 l o 眈o o 口。，6 = 6 1 0 b o k ， 其中只只知道啦，b 我们的目标是得到c 1 ，c 2 ，c ，i ，保证只只知道c i ，并满足下 式： c l oc 2 0 oc ，l = b b = ( o l o 眈0 o ) p 1 0 6 2 0 o k ) 、 先看n = 2 的特殊情况，这时候我们的目标是得到。1 ，c 2 ，保证p 1 只知道。l ，p 2 只 知道勿，使得c l o 吃= ( 口l + 口2 ) ( 6 l o b ) 可以利用d r 睁l 如，如，也) ，z ，最r 1 达到 我们的目标：p l 充当s 的角色，岛充当r 的角色，p l 随机的选择。l f 0 ，1 l ，并设 置各参数如下d l = c 1o 以l 6 1 ) ，d 2 = c lop l ( 6 1 毋1 ) 】d 3 = c 1o 【扣1o1 ) 6 l 】 ，d 4 = c l o i 以1 0 1 ) ( b 1 0 1 ) l 作为o t 的输入，马设置l ；1 + 缸2 + k l ，2 ，3 ，4 1 作为o t 的输入，执行d t 【( d l ，d 2 ，如，d 4 ) ，z ，p 1 ，p 2 】协议，由o t 的性质，p 2 只能得 到d l = d l + 2 盱而p 1 不知道z = l + 凯2 + 6 2 。尸2 设置c 2 = 西= d 1 + 2 口2 + k ，很容易验 证c l o c 2 = 1 + ) ( 6 1 0 6 2 ) ，且p 1 只知道c l 岛只知道q 。为了方便描述，我们 记d ( 只固= c 1 ，d 乃z ( s r ) = c 2 。 对于一般情况由于 nn ( o 毗) ( 0 6 ，) = o ( 口。6 。) oo b ) 毋“。) 】 f 1# 1i = l 1 s l 白“ n = ( n 一2 ) 【b ( n ；6 i ) 】oo 【扣i o ) ( k o6 j ) l ，= l l s t ( j s “ 不难看到，只可以单独计算一2 ) p t k ) = 薹( k ) ，任意 只，弓) ( 1 i j n ) 可以通过执行d t 【( d l ，如，如，d 4 ) ，z ，只，弓】协议，使得只得到d 砟 ( 只，巴) 8 、弓得到d t b ( 只，b ) 满足 。乃1 ( 只，弓) o d 耳j ( 只，弓) = ( d l o 勺) ( 6 。o b ) 只设置q ：苜h 6 | ) 。签d 强( 弓，只) 。蚤d 强( 只，己) ，则由上面的推导有 ，= j，= ij = i 十1 c l oc 2 毋o 岛= ( 口l 0 0 2 0 o 口。) ( 6 1 母6 2 0 o h ) = o 6 ，且只只知道c 而对q0 i ) 没有任何信息 输出阶段：对于需要安全计算的函数，设经过最后一步运算( 二元a n d ，x o r 运算或 一元n o t 运算) 后，只得到珧，很容易看出函数的输出结果为f = f l o 耽o o 只 将乳公布，则所有只正确得到了y 上面介绍的基于o t 的安全多方计算协议要求所有的协议参与者正确地执行涉及的每步运 算要处理某些参与者在参与过程中有恶意行为的情况，则在协议中还需用到比特承诺、投币 协议，零知识证明等子协议，具体参见i 鳓和【3 9 】。 2 4 2 使用v s s 子协议的安全多方计算协议 这种类型的安全多方计算协议使用了秘密分享协议，由于要求保证被分享的秘密的可验证 性，需要使用可验证的秘密分享协议( v s s ) 目前这类安全多方计算协议很多，如、【3 7 】 等，下面介绍一下【3 _ 7 】中提到的安全多方计算协议。与基于o t 的安全多方计算协议类似，这 类安全多方计算协议分为输入阶段、计算阶段、输出阶段。进行安全多方计算的函数的自变量 及函数值的取值域为g c 力，其中p 为一素数，由于域上的所有函数都可以分解成为域上加法 及乘法运算的组合，因此只要能够安全计算域上加法及乘法运算，则可以安全计算域上所有函 数： 输入阶段：n 个参与者p 1 ，r 拥有各自的输入自变量8 。a = 1 ，2 ，1 ) g p ) ，只 采用随机t 次多项式 和) = o 。一+ + 8 2 ，。$ 2 + 0 1 。+ 8 。将8 。分享，并将，i ( j ) 秘密发送 给弓 计算阶段： l 域上加法运算一一设运算逻辑上的输入分别为口，6 口。，) ( a ，b 可以是初始输入，也 可以是计算过程的中间结果) ，且a ，b 分别被分享在g p ) 上t 次随机多项式厶p ) 及 ( 功中，即厶( o ) = ， ( o ) = 6 其中只只知道，d ( f ) ，6 ( f ) 。则经过加法运算 9 后，各只将其加法运算输出设置为厶( i ) + ，b ( i ) ，也就是说n + 6 被分享在g p ) 上t 次随机多项式 ( z ) = 厶扣) + p ) 中，其中d + 6 = 厶( o ) + ( o ) = ( o ) ，只只知 道 0 ) = 厶( i ) + 0 ) 加法运算的正确性是显然的 2 域上的乘法运算一一设运算逻辑上的输入分别为口，6 g 加) ( a b 可以是初始输入，也可 以是计算过程的中间结果) ，且a ，b 分别被分享在g 白) 上t 次随机多项式厶 ) 及 如) 中，即厶( o ) = 口， ( o ) = 6 ，其中最只知道厶( ) ， ( i ) 则域上的乘法运算的结果要 求：找到g p ) 上t 次一随机多项式 p ) 分享n 6 ( 即 ( 0 ) = 曲) ，使得只只知道子 秘密 ( t ) 而不知道其他子秘密。记，曲扣) = 厶( p ) = 0 2 萨2 + + 口2 护+ 0 1 z + 曲 ( 注意，曲( z ) 是2 t 次多项式，且，厶( o ) = 厶( o ) ( 0 ) = 曲) ，则 a x = ll l2 1搿+ 1 l 2 搿 ( 盘+ 1 ) a 为范德蒙矩阵，可逆，设其逆矩阵a 一1 为： a l = 曲 o l ， 嗡 1 1 入2 + l 则d 6 = a 1 允( 1 ) + a 2 件1 ，矗协+ 1 ) ，注意 l ，a l ， 1 对所有人都是已知 的，允( i ) 只对只已知从而只要只0 = l ，2 ，嚣+ 1 ) 用g p ) 上t 次随机多项 式旭p ) 分享a 。，矗( 1 ) ( 即 ，( o ) = a ，曲a ) ) ，并将0 ) 秘密发送给己，令 p ) = 1 p ) + 2 扣) + + 如蚪1 ( z ) ，则 ( o ) = 。屯( 0 ) = 。a ，厶6 ( 。) = 曲只知 i = lt = l m + 1 1 道、e ( i ) = m i ) 而对 p ) 的其他函数值一无所知。从而完成了域上的乘法运算。 i ：l 似纵 j ： 舻 f k 输出阶段：对于需要安全计算的函数，设经过最后一步运算( g 函) 域上加法或乘法 运算) 后，只得到肌= o ) ，则由s h l i f 秘密共享方案的性质，任意t + l 可以共同 恢复f ( 0 ) ，容易知道( 0 ) 是函数的输出值。 上面介绍的安全多方计算协议要求所有的协议参与者正确地执行涉及的每步运算。要处 理某些参与者在参与过程中有恶意行为的情况，则在协议中还需用到同态承诺、检测v s s 的v s p s ( 可验证的多项式秘密分享) 性质、零知识证明等子协议。 2 4 3 基于同态加密的安全多方计算协议 此类安全多方计算协议需使用同态加密技术，同态加密技术是满足如下性质的公钥加密技 术：设a 表示明文a 的加密密文， ( 1 ) ，加法加密同态：如果已知d ，5 ，任何人都能得到8 + b 的密文石两( 记孑郅 为a 0 5 ) ； ( 2 ) 、常数乘法同态：如果已知d 及一常数d ，任何人都能轻易得到的密文百万； ( 3 ) 、已知明文证明：若某人知道n ，他可以利用零知识证明d 是d 的密文； ( 4 ) 、常数乘法正确性证明：若某人已知n 及a ，他可以使用瓦d ，蕊r 作为输入，零知识 证明丽确实是a 口的密文； ( 5 ) 、门限解密：用于加密的公钥p k 公开，用于解密的私钥被分享在参与者中。解密a 时，各参与者使用其子私钥作为输入( 每次解密不需要公开子私钥) ，可以共同解密出a 这 类安全多方计算协议同样包括输入阶段、计算阶段、输入阶段： 输入阶段：n 个参与者p 1 ，r 拥有各自的输入自变量q ，只使用p k 将z 。加密，将 密文磊发送给每个协议的参与者，并零知识证明他知道瓤 计算阶段： ( 1 ) 加法运算一一每个协议的参与者都知道加法运算的输入a b 对应的密文d ，5 ，由加法 加密同态性质，每个人都能得到d 0 5 = 五干百 ( 2 ) ，乘法运算一一每个协议的参与者都知道乘法运算的输入a ，b 对应的密文d ，5 ，目标 是每个参与者能够得到面：只随机选择血并使用p k 将其加密，将也广播并证明他知道d l ；由加法加密同态性质，每个参与者都知道石。瓦o o 瓦o d = 五了刁f f 干瓦瞄， 所有协议参与者共同解密得到d l + d 2 + + d ，l + 口( 注意，对每个参与者而言，这只是一个 随机数) ，由于或，n + 呜对只而言是已知的，p 1 设置n 1 = ( 口+ 妻d 1 ) 一d 1 ，其他只 1 1 设置= 一也“= 2 ，3 ，n ) ，显然吼= 4l 由常数乘法同态性质，只可以计算五万，只 公布硒并使用常数乘法正确性证明其运算是真实的；由加法加密同态性质，每个只知 道币u = l ，2 ，竹) ，从而知道币。币o o 丽= 币瓢两羽= 丽 输出阶段：对于需要安全计算的函数，设经过最后一步运算( 加法或乘法运算) 后得到得 密文为y ，所有参与者共同解密出y 就是整个函数的输出 上面的描述没有介绍在已知明文证明或常数乘法证明验证出错，门限解密时有参与者恶意 破坏时协议如何处理，这种情况的处理详见闻 2 4 4 使用m 奴m a t c h 的安全多方计算协议 这是一种使用盲表进行安全多方计算的协议，适用于逻辑运算和比特运算，可以在电子拍 卖等协议中使用与前面介绍的三种安全多方计算协议不同，它使用m i 】【m a t 血提供协议所需 的保密性和正确性。这种安全多方计算使用了e i g a m a l 加密方案的同态性质及门限解密性质。 首先简要介绍一下e 1 9 a l 加密方案：p 是大素数，g 是g ( p ) 的生成元，私钥g 加) 对应 的公钥为”；矿，使用y 对m g p ) 加密的密文为 ，卢) = ( m r ，矿) ，其中r g p ) 为随机 数，解密过程为m = 最e i g a m a l 加密方案的同态性质：对于相同的系统参数g ，p 及公私钥 对k ，y ，设( 蜘，岛) 是o 的密文 1 ，n ) 是m l 的密文，则( a o a l ，风卢1 ) 是( m o m 1 ) 的密 文；进一步，设n ，q ) 是l 的密文，则( 咖岛q ) 是”o 的另一个密文e l g a m | 卫加密方案的门 限解密性质：设私钥k 使用t 1 次多项式，p ) = o “一1 1 z o 一1 ) + + 0 2 2 2 + 口1 z + 女在参与者中 分享，只得到缸= ，( i ) 要解密( a ，卢) ，只计算并公布展= 芦托。选择t 个风，以。，氏 ，则m = 彘，其中a a 衄- ，k 满足七= a 。以。+ 衄+ a 。尻，+ + a d i 几这 些9 种类型的安全多方计算可以分为四个阶段：系统建立阶段、输入阶段、计算阶段、输出阶段。 系统建立阶段： ( 1 ) 、e l g 锄a i 系统分布式建立：所有协议参与者约定一个大素数p 及g p ) 的生成元g ，每 个只选择一个随机数r l 并使用一随机一1 次多项式，| ( ) = 吼j 一1 9 。一1 + + d 。妒2 + 口。1 $ + ，公布矾= 9 n ，将 0 ) 秘密发送给弓；当只收到所有其他参与者发送的a ) 后，计 算f = n 的t = ( 1 ) ，容易验证系统分布式建立了私钥= 登r ，并将私钥以t 一1 次 f 1 9 k f 1 随机多项式，0 ) = 厶( z ) 分享在所有参与者中，只得到峨= ，( i ) k 对应的公钥为y ( 2 ) 、混合网络( m k n e t r k ) 建立：所有协议参与者的一部分只，j k 组成建立 混合网络的服务器。将计算中可能涉及的所有门电路( 注意是比特运算) 的真值表进行混合运 算：设门电路的真值表共有t 行h 列，表示成 t = t 1 1 t 1 2 t 2 1t 2 2 如，1如，2 t 1 t 2 t 1 ，其中t 。d 一l ，1 ) ( o o = 一1 表示逻辑上的o ) ， 足，使用公钥y 将表t 中的所有元素进行随机加密，然后将t 的各行进行随机置换( 注 意只是行置换，没有列置换) 。得到表噩；吃使用公钥y 将丑的所有元素进行再次加密 ( 利用加密系统的同态性质，将t 。f 的密文与1 的随机加密结果组合成。，的另一个密文) ， 并将乃的各行进行随机置换得到死；类似的，圪+ l 使用公钥y 将卫的所有元素进行再次加 密、对各行进行随机置抉得到t i + 1 ；最后输出的，k 为门电路真值表t 的随机密文表( 各行 元素已被随机加密，各行的顺序已随机打乱) 输入阶段：n 个参与者，每个参与者只拥有计算函数的某个输入戤( 若乱= 0 则以一1 代替) ，使用公钥y 将毛随机加密，将加密结果巧公布。 计算阶段：所有参与者共同执行p e t ( 明文相等测试) 子协议进行查表运算：当遇到要 计算的门电路时，将门电路输入值的密文( 初始输入或中间结果) 与该门电路真值表随机密文表 的每一行( 最后一个元素除外】进行对照，检测是否都表示相同明文的密文，如果查到与某行 一致，则将该行最后一个元素( 表示该门电路对应于输入的函数值的密文) 作为查表结果，即 该门电路运算的结果。其中检测两密文是否表示相同明文要使用p e t 子协议：设( 口o ，风) ， ( a 1 ，芦1 ) 分别表示m o ，m 1 的密文，如果m o = m l ，则( 仉叩) = ( 鲁，舞) 表示1 的密文， 则n 。，矿) ( z 为某随机数) 仍是1 的密文，否则n 。，矿) 表示( 署r 为一随机数( 因为2 为随机 数) ；各只随机选择气计算并公布“，仇) = n 4 ，铲) ，令彳= n 气，自= nq 。，所有参与 者共同参与解密( 彳 日) ，如果解密结果为l 则表示( o o ，岛) 1 ，卢1 ) 表示相同明文对应的密文 否则表示不是。 输出阶段：执行函数的最后一个门电路后。设输出的密文为( n ，们，所有参与者共参与解 密( a ，卢) ，得到的结果即为函数的运算结果与前面介绍的几种类型的安全多方计算一样，上 面介绍的安全多方计算没有考虑参与者恶意破坏的情况，这种情况的处理详见1 3 8 】。 第三章秘密分享以及可验证秘密分享 3 1 可验证秘密分享 可验证秘密分享( v 础a b l e8 e c r e t 蛐g ，简记为v s s ) 是解决多方多方安全计算的一个 有用的工具。s h a m i r l q 和b l a h e y