（计算机应用技术专业论文）一些基于私有信息保护的计算几何问题研究.pdf

硕_ j 学伊论文 摘要 多方保密计算是近几年国际密码学界的一个研究热点。它的应用范围很广，比如数 据挖掘、科学计算、数据库利用等等，已成为密码学领域旱一个极端重要的工具，计算领 域里一个必不可少的组成部分。虽然一般的多方保密计算问题在理论上可解，但是理论 解决方案可能因为效率或计算量的问题而在实际上并不可行，具体问题需要研究具体的 解决方案。因此，研究各种各样的具有实际应用背景的多方保密计算问题以及他们的解 决方案成为人们热衷于研究的问题之一。 由于大量应用领域提供了特有的几何问题，对于这些问题必须建立有效的算法，它 们是计算几何的基础。这些问题包括欧几里得巡回售货员问题、最小生成树问题、线性 规划问题等等。基于凸包的问题已研究得很多，并且已经有很多成熟的解决方案，但是， 在保护私有信息前提下的一些凸包问题还在研究探索中。保密的计算几何问题是多方保 密计算中的一个新的研究领域，是一类特殊的安全多方计算问题，虽然目前该问题已经 有一些理论上的通用解决办法，但是在实际的计算效率上是不可行的，需要特殊的办法。 目前国际上对这类问题的研究尚在起步阶段，研究高效实用的安全多方计算协议成为人 们致力于研究的热门课题之一。 本文所讨论的问题是基于私有信息保护的计算几何基本问题，重点在于问题的发现 和解决方法，而不仅仅是解决了什么问题。将多方保密计算应用于计算几何中解决的两 个问题：一个是保护私有信息的凸多边形相似判定问题，这是一个特殊的安全多方计算 问题。秘密判定两组数据是否相等、是否对应成比例是安全多方计算的基本问题，通过 利用相应的比较相等协议和点积协议，以及两组数据对应成比例的判定协议，解决了在 保护私有信息的前提下如何判定两个凸多边形是否相似的问题。 另一个是在保护私有信息的前提下由两个保密点确定一条直线的问题。凸包算法是 计算几何中的基本算法，但两保密点集如何确定一个大的凸包是一个特殊的计算几何问 题，也是一个特殊的安全多方计算问题。通过利用秘密判定两线段相交协议、比较相等 协议以及d 贮茫然传送的思想，提出了一个基于私有信息保护的两保密点确定一条直线 的协议。基于该协议，提出了一个在保护私有信息的前提下寻求平面点集凸包的解决方 案。 最后，对本文的研究工作进行了总结，并指出了多方保密计算在计算几何领域进一 步还要研究的问题。 关键词：多方保密计算：计算几何；协议：凸包；加密 计算儿何中一些多方保密汁芹的市川研究 a b s t r a c t s e c u r em u i t i p a n yc o m p u t a t i o ni sah o tr e s e a r c hf b c u si ni n t e m a t i o n a lc r y p t o g r a p h i c c o m m u n i t yi n r e c e n t y e a r s i t s a p p l i c a “0 ni sv e qw i d e ， l i k ed a t am i n i n g ，s c i e n t i f i c c o m p u t i n g ，d a t a b a s eu s i n g 锄ds o 咖，卸di th a sb e c o m e 卸i m p o n 卸tt o o li nt h ef i e l d0 f c r y p t o 铲a p h ye x t r e m e l y 柚d 柚i n d i s p e n s a b i ec o m p o n e n ti nt h ef i e l do fc a l c u l a t i o n t h o u g l l t h 斟萨n 9 r a lp r o b l e m s o fs e c u r cm u l t i p a r t yc o m p u t a t i o na r cs o l v a b l e ，t h et h e o r ) rs o l u t i o n sm a y n o tb cf c 弱i b l eb e c a u s eo ft h ee f f i c i e n c yo rt h ec a l c u l a t i o n t 1 l es p e c i f i cp r o b l e mn e e d s s p e c i f i cs 0 l u t i o n s o ，t 0s t u d yv 撕o u sp r o b l e m s0 fs e c u r em u l t i - p a r t yc o m p u t a t i o n 锄d s o l u t i o n sw h i c eh a v ep r a c t i c a lb a c k g r o u n di s0 n eo ft h ep 耐b l e m sw h i c ha r ea t t e n d e db y p e o p l e f 研t h e r ca r cs p e c i f i cg e o m e t 巧p r o b l e m sp r 0 v i d e di na1 0 to f 印p l i c a t i o nf i e l d s ，i ti s n e c c s 阻f ) rt 0b u i l de d c c t i v ea 1 9 0 r i t h m s f o rt h e s ep r o b l e m s ，柚dt h e ya r ct h eb 筋e0 f c o m p u t a t i o n a lg e o m e t r y t h e s cp r o b l e m si n c l u d i n ge u c l i d t o u r s a l e s p e r s o n sp r o b l e m ， m i n i m u ms p 咖i n gt r e ep r o b l e m s ，u n e a rp r o 鲈a m m i n gp r o b l e m s 柚ds 0o n t i i l e r ea r ea1 0 t 0 f l v c dp f o b l e m sb a s e do nc o n v e xh u l l ，锄d1 0 t so fm a t u 圮s 0 l u t i o n s ，b u tt h ec o n v e xh u l l p r o b l e m sb a s e d0 np r o t e c t i o n0 fp r i v a c yi n f o 唧a t i o na r co nt h ew a yo fr e s e a r c h i n g ( = 0 n f i d c n t i a l c o m p u t a t i o n a jg e o m e t r ) rp r o b l e m i san e wf i e l d0 fs e c u r e m u l t j p a r t y c 0 忉p u t a t i 伽r e a r c h i n 岛 锄di so n el 【i n do f s p i e c i f i c c u r em u l t i - p a n yc o m p u t a t i o n a i t h o u g ht l l e 坨a r c m et h e 0 坨t i c a l l u t i o 瓞，t l l e ym a yn o tb ef e 弱i b l eb _ e c a u s eo ft h e e f f i c i e n c y 柚dn e e ds p e c i f i ca p p r o a c h a tp r e s e n t ，i n t e m a t i o n a lr e s e 甜c h i n go nt h e s ep r o b l e m s i si nt h e 砌t i a ls t 蜀l g c ，柚dt 0 麟e 砌e f f i c i e n t 如dp 删c l l r cm u l t i p a r t y m p u t 缸i o n p m t o c o li s 彻eo ft h ep r o b l e m sw h i c ha r ea l t e n d e db yp c o p i e i nt h i s p a p e r t h e p r o b l e m s t h a th a v cb e e ns o l v e da r et h eb a s i c p r o b l e m s0 f c o m p u t a t i o n a lg e o m e 仃yb a s e d 彻州v a c yp r o t e c t i n g 1 n h em o s ti m p o r t a n tt h i n 笋a r ch o wt o f i n dt h ep r o b l e m sa n dt h em e t h o d st 0s o l v et h e mb u tt l l ep r o b l e m st h e ya r e t h es e c u r c m u l t i - p a n yc o m p u t a t i o ni su s e di n0 0 m p u t a t i o n a lg e o m e t r yt os o l v et w op r o b l e m s o n ei s p r i v a c yp r o t e c t i n gs i m i l i t u d ed e t e 加j n a t i o nf o rt w oc o n v e xp o l y 9 0 n s i ti sas p e c i a ls e c l l r e m u l t i - p a r t yc o m p u t a t i o nq u e s t i o n p r i v a t ed e t e 册i n a t i o no fw h e t h e rt w os e t so fd a t a 甜ee q u a l o ra r ep r o p o n i o n a lc o r r e s p o n d i n 翻yi sab a s i cp r o b l e mo fs e c u r em u l t i - p a r t yc o m p u t a t i o n t 1 1 e p r o b l e mo f s i m i l i t u d ed e t e 砷i n a t i o nf o rt 、oc o n v e x p o l y g o n s i ss o l v e d b yu s i n g c o r r e s p o n d i n ge q u a i j t y - t e s t i n gp r o t o c o l a n dd o t - p 剃u dp r o t o c o l ， a n dt h e p r o t o c o l f b r d e t e 册i n i n gw h e t h e rt w 0s e t s0 fd a t aa r ep r o p o n i o n a lc o r r e s p o n d j n g ly t h e0 t h e ro n ei sac o n v e xh u l ja l g o r i t h mf o rp l a n a rp o i n ts e tb a s e do np r i v a c y p l d t e c t i n g n 硕+ j 学伊论文 c b n v e xh u l la 1 9 0 r i t h mi sb a s ei nc o m p u t a t i o n a lg e o m e t b u tt 0d e t e 加i n eab i gc 0 n v e xh u l l b yt w op r i v a t ep o i n ts e t si sas p e c i a lc o m p u t a t i o ng e o m e t r yp r o b l e m ，a n di sa l s oas p e c i a l s e c u r em u l t i p a n yc o m p u t a t j o np r o b l e m b yu s i n gt h es c h e m ef o rs o l v i n gi n t e r s e c t i o n p r o b l e mo ft w ol i n e s e g m e n t s ，a n de q u a l i t y t e s t i n gp r o t o c o l ，a n do b l i v i o u st r 蚰s f e rm i n d ，a p r o t o c o lt od e t e 硼i n eal i n eb yt 、o s e c r e tp o i n t si sp r 0 1 ) o s e d ，锄db yw h i c hac o n v e xh u l l a l g o r i t h mf o rp l a n a rp o i n ts e tb a s e do np r i v a c yp r o t e c t i n gi sp r o p o s e d i nt h ee n d ，t h ec o n c l u s i o ni s 舀v e na n dt h ef u r t h e rr e s e a r c hd i r e c t i o ni sp o i n t e do u t 1 【e yw o r d s ：s e c i l r em u l t i p a j t yc o m p u t a t i o n ；o ) m p u t a t i 伽a lg e o m e t r ) ，；p r o t o c o l ；c o n v e xh u l l ； c r y p t o 铲a p h i c l i l 计剪儿何巾一。些多方保密计算的戍川研究 插图索引 图3 1 点积协议示意图1 4 图5 1 两点确定一直线示意图2 5 图5 2 寻求平面点集凸包示意图2 8 i v 硕十学传论文 附表索引 表4 1 角对应比2 1 表4 2 边对应比2 2 v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：2咬 日期：习年月召日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 2 皎 扮五啐 1 日期：) 罗辛月罗日 ， 日期： 叩年厶月勺日 1 1 多方保密计算概述 第1 章绪论 多方保密计算是近几年国际密码学界的一个研究热点，应用范围很广。该问题由 y 幻【1j 提出，g o l d r e i c h ，m i c a l i 和w i g d e r s o n 【2 j 等人发展了多方保密计算理论。g o l d w a s s e r 曾预言【3j ：多方保密计算今天所处的地位正是公开密钥密码学1 0 年前所处的地位，成为 密码学领域里一个极端重要的工具；丰富的理论将使它成为计算领域一个必不可少的组 成部分；它在现实中的应用才刚刚开始。 多方保密计算又叫安全多方计算，是指在一个互不信任的多用户网络中，各用户能 够通过网络来协同完成可靠的计算任务，同时又能保持各自数据的安全性1 4 j 。实际上， 安全多方计算是一种分布式协议，在这个协议中，刀个成员n ，扔，p 。分别持有秘密的 输入，试图计算函数值( 一，y ：，以) = 厂( 葺，镌，h ) ，其中厂为给定的函数。 安全的含义是指既要保证函数值的正确性，又不暴露任何有关各自秘密输入的信息，即 使参与方有欺骗行为，并对协议的安全性给出证明。安全多方计算协议要解决的问题可 以描述如下【5 1 ：一组参与者希望共同计算某个约定的函数，每个参与者提供函数的一个 输入，出于安全考虑，要求参与者提供的输入对其他人保密。如果存在安全可信第三方 ( 我们称其为p p t ) ，则安全多方协议所要解决的问题可以轻易地得到解决：只需各参 与者将各自的输入交给p p t ，由p p t 计算出函数值，再将函数值公布给各参与者。但现 实中很难找到这样的p p t ，从而安全多方计算协议的研究应运而生。 直接将一般的安全多方计算协议的研究成果应用于特殊情形是不实际的，因为这会 影响特殊情形下的计算效率或安全性。因此研究特殊情形下的安全多方计算问题，给出 效率高、安全性强的特殊安全多方计算协议并从理论上给出协议安全性的证明是一项有 意义的工作，也是人们目前致力于研究的热门课题。概括起来，目前众多的研究者的研 究主要集中在以下一些方面【6 j ：( 1 ) 、一般化的安全多方计算协议：这类研究的目的是设 计一种高效的、安全的、能够计算任意函数的安全多方计算协议，希望能够通过这样一 种协议一劳永逸地解决所有的涉及到安全多方计算的问题。( 2 ) 、对一般化的安全多方 计算协议进行剪裁：这类研究注意到如果一个协议是广泛适用的，那么必然会牺牲一些 性能上的代价来满足其广泛使用性。( 3 ) 、安全多方计算的定义：安全多方计算的目的 和应该具备的性质都为在这一领域研究的学者熟知了，但是安全多方计算至今还缺乏一 个为大家所认同的、完备的定义。这主要是因为安全多方计算协议的构造形式可以有多 种，各个学者研究的安全模型也是不一样的。( 4 ) 、新的安全多方计算协议的构造方法： 目前大部分学者提出的安全多方计算协议都使用了飓s 子协议作为其构造基石，因而 计算几何中一些多方保密计算的应用研究 这类协议在大体结构上都是类似的。有没有其他的方法来构造安全多方计算协议? 这也 是一些学者的研究内容。( 5 ) 、安全多方计算协议生成器：许多安全多方计算协议的研 究在研究了如何安全的计算域上定义的基本运算就停止了，因为这时从理论上讲，任何 函数都可以被安全地计算了。但是这离实际应用还有一步需要跨越，多方计算协议生成 器的作用就是弥补这最后的一步。安全多方计算协议生成器的输入是任意函数和如何计 算域上定义的基本运算的子协议，输出是安全计算该函数的协议。 1 2 论文选题的背景和意义 随着科学技术的发展，人类研究开发太空的能力在不断增强，国际上不同的科研机 构之间都希望开展合作来加快自己的研究进程。然而由于涉及到国家的安全与利益，这 种合作是极其有限的，任何一个机构都不会轻易向其他合作方公开自己的技术。例如两 个不同的国家各自都研制出自己的太空碎片分布图，为了确保自己的飞行器在太空飞行 过程中不会与太空碎片发生碰撞，他们都希望能同时参考对方数据来提高飞行的可靠 性，然而为了各自国家的利益，两方都不会向对方泄露自己的数据信息。计算双方如何 在协作计算中不暴露自己的隐私数据是一个急需解决的问题。上述问题是一类特殊的安 全多方计算( s e c u r em u l t i p 哪c o m p m a t i o n ，s m c ) 【4 j 问题，虽然目前该问题已经有一些 理论上的通用解决方法【啦 3 7 8 j ，但是这些方法在实际的计算效率上是不可行的，对于一 些特殊问题需要用特殊方法才能达到高效性。因此研究高效实用的安全多方计算协议是 人们目前致力于研究的热门课题之一。基于前面提出的问题，在考虑安全两方计算环境 下，判定空间几何对象间的相对位置关系问题，这类问题我们也称其为保护私有信息的 计算几何( p r i v a c y p r e s e r v i n gc o m p 喇i o r 脚g e o m e 仃y ，p p c g ) 问题。目前，国际上对 p p c g 问题的研究尚在起步阶段，文献 9 首次介绍了安全多方的计算几何问题，在提 出点积协议的基础上，设计了基于隐私保护的点在多边形中的包含判定协议及保护私有 信息的多边形相交判定协议。判定两组数据是否对应成比例是一个基本的数学问题，在 空间几何对象的相对位置关系判定中起着关键作用。已有人提出了一个秘密判定两组数 据是否对应成比例问题并设计了相应的两方判定协议，基于该协议，在保护用户私有输 入信息的条件下，解决了点、直线、平面等空间几何对象之间的相对位置判定问题。 随着社会的发展，工作的竞争日益激烈，但是又希望能够互相合作来提高自己的工 作效率。由于涉及到自己的利益，这种合作也是极其有限的。例如某工厂需要生产加工 一批横切面是某凸多边形的零件，a l i c e 和b o b 是工厂的职工，他们分别画出自己认为 是符合要求的零件图，为了让老板c t o r 满意，他们很想参考对方的图作为参考数据来 提高自己图的精确度，如果双方的图相似甚至全等则说明精确度高，但是考虑到自己的 隐私，他们会想尽一切办法不让对方得到自己图的具体信息。那怎样才能让他们既要互 相协作又要不泄露自己的信息昵? 再比如，a l i c e 和b o b 是两个村子的村长，他们之间 2 硕十学伊论文 隔着一座大山，他们想在不告诉对方自己准确位置的前提下，协作完成一项大工程，就 是在山里挖个洞并且修条最短的路。那这两个保密的点怎么样确定一条直线呢? 由此引 发出来的另一个问题，比如a l i c e 和b o b 是两个邻村的村长，他们想合作完成另一项大 工程，就是在他们两个村子的最外层修一道围墙，在用材最少的前提下把两个村子的所 有建筑物都包含进来，并且都不想向对方泄露自己村子的建筑物分布图，各自修各自部 分的墙，那怎么样寻求平面上这样两个保密点集的凸包呢? 1 2 1 计算几何问题 欧几里得的几何构造满足算法的所有需求：无二义性、有穷性、确定性、能行性、 输入、输出、正确性等。在欧几里得的几何构造中，限定了可允许使用的工具( 直尺和 圆规) 及原始运算( 圆规的一个脚置于一个给定点或一条直线上；作一个圆；直尺的边 通过一个给定点；作一条直线) 。但欧几里得原始运算并不能胜任所有的几何计算( 比 如角的三等分) ，这一点直到1 9 世纪，阿贝尔、伽罗华等数学家才给出了证明。称为计 算几何的学科大致有下述几种：f o r r e s t 等人依据样条函数处理曲线和曲面( 接近于数值 分析) ；m i n s k v 和p 印e r t 写的一本名为感知机的书，陈述用简单回路构成的网络实 现模式识别的可能性( 属于人工神经网络) ；计算机图形学是研究用计算机进行图形信 息处理( 包括表示、输入、输出、存储、显示、检索与变换等) 和图形运算( 如图的并、 交运算) 的一门学科，而不是算法分析；几何定理的机器证明，主要研究定理证明的探 索方法及证明过程的推断，而不是几何体。s 计算几何与上述的学科研究的内容不同， 是属于s h 锄o s 的文章( 1 9 7 5 a ) 中命名的“计算几何”。s 计算几何中考虑的基本对象 是点。虽然可以把点作为笛卡尔坐标系中的一个向量，但是几何算法的运行时间较大程 度上不受坐标系选取的影响，而是依赖于维数。因此可以在执行几何算法之前，假设在 选取的笛卡尔坐标系中已给定点。 s 计算几何中的问题大致可分为三类【1o 】： ( 1 ) 提取子集。在一批给定的对象中提取满足某种性质的子集。这类问题的特征是 不会产生新的对象，它的解完全由输入元素中的某些元素组成。比如，求点集的凸壳顶 点的问题。 ( 2 ) 计算。计算给定集合的某个几何参数的值。比如，计算点与线之间的距离、点 对之间的距离等。 ( 3 ) 判定。在“提取子集”和“计算问题中都有判定问题。比如，在点集s 中询 问是否存在距离大于d 的点对，回答“是 或“否”，其中d 是已知常数。这是“计算 问题中的判定问题。另外，若提取子集问题尸需要满足某个性质q 的给定集合s 的子 集，关联的判定问题d ( 尸) 对于类型为“集合s 满足p ? 的问题，要作“是”或“否 的回答。 计算几何中一些多方保密计算的应用研究 1 2 2 影响保密计算可信性的主要因素 每一个计算系统在其运行期间都可能受到来自各方面的干扰和影响，以致降低或损 害了系统的可信性、安全性。其中，影响可信性最重要的有如下三个相关因素：故障、 错误、失效。事实上，这三个因素是造成系统可信性受损的直接原因，而且三者之间有 着密切的因果关系。 按照事物发展的一般规律，任何一个系统在运行期间都可能出现非正常现象。即， 系统在运行到一定的时间，或在一定的条件下偏离它预期设计的要求或规定的功能。这 种现象通常称为失效。换句话说，就一般情况而言，系统的失效是不可避免的，是绝对 的。而保持系统的正常运行则是局部的，相对的。产生这种失效现象的根本原因则可以 归纳为“故障”。事实上，故障可以认为是( 系统) 产生失效的必然条件和推理上的原 因。故障的出现并不意味着它的影响一定会在系统的( 外部) 功能上立即表现出来。相 反，一般情况下，一旦出现故障，在系统外部并不是立即暴露，因而也无法立即发现故 障的存在。这是因为在一段( 运行) 期间内，故障的出现可能并不立即影响或反映在系 统所提供的服务上。从出现故障到系统的失效( 即系统提供了非正常的服务) 之间存在 一段延迟时间，称为故障潜伏期。故障的后果必定先影响到它所在部分的功能或状态， 然后，逐步向外传递或扩张。我们将在系统内部的某一个部分( 模块) 由于故障而产生 了非正常( 即违背了设计要求和说明规格) 行为或状态的现象称为错误。显然，错误是 故障的产物和后果，而故障是错误的起因。换句话说，错误是系统内部出现故障而导致 非正常状态的表现和反映。然而，错误就像传染病一样具有传递性和扩散性，把原始故 障的影响传递到系统的输出端( 外部) 为止。最终，可能造成整个系统的失效。 1 3 研究现状 受g o l d w a u s s e r 的预言和g o l d r e i c h 的观点的激发，人们研究了各种各样的具有实际 应用背景的多方保密计算问题以及它们的解决方案。已经研究的问题包括比较两个数的 大小问题【l 】、保密的数据挖掘问题】、比较两条信息是否相同问题【1 2 】、保密的科学计算 问题【1 3 j 、保密的数据库利用问题【1 4 j 、保密拍卖、保密的统计分析问题m 3 等。文献【3 ，1 7 】 对于多方保密计算在电子世界的应用做了很好的总结。国外关于安全多方计算的研究已 有一些成果，并已经成为理论密码学的研究热点。安全多方计算有很强的应用背景，特 别是在电子信息的时代，如网上电子投标( 拍卖) ，网上商业谈判，电子选举计票，比较 薪水、年龄等趣味问题，很多情况下还可用来认证等等。李顺东、司天歌、戴一奇等人 在文献 1 8 中用m o m ec a r l o 方法与c a n t o r 编码方法l 憎j 研究计算几何的多方保密计算 问题，给出了任意几何图形的点包含问题与几何图形包含问题的多方保密计算方案提 出一种集合包含问题的多方保密计算方案，并给出了安全性证明；将m o n t ec a r l o 方法 4 硕十学伊论文 与c a l l t o r 编码引入计算几何研究，提出一种任意几何图形的点包含与图形包含问题的 近似解决方案；利用密码学的可交换加密方案，结合前两种问题的解决方案设计了一种 任意几何图形的点包含与图形包含问题的多方保密近似计算方案。现有的方案【2 0 】只能解 决凸多边形的相交与点包含的多方计算问题。 保密的计算几何问题是多方保密计算中一个新的研究领域，d u 等人在保密的计算 几何方面做了一些工作f 1 7 2 0 1 ，研究了保密的计算几何中点包含问题、两个几何图形的相 交问题、若干保密点的凸壳问题，给出了凸多边形的点包含问题、凸多边形相交问题的 解决方案。文献 8 研究了两点之间的距离以及点与圆形、椭圆形区域的关系问题。 1 4 本文的研究内容及结构安排 第一章介绍了多方保密计算问题、选题背景及研究现状。 第二章介绍了目前常用的四类安全多方计算协议：基于不经意传输协议、使用牌 子协议、基于同态加密、使用m i xm a t c h 。 第三章介绍了计算几何中一些多方保密计算的协议，在本文中用到了它们，有比较 相等协议，点积协议，对应成比例判定协议，两线段相交判定协议等，分别介绍了这些 协议问题的描述、判定等。 第四章中提到一个保护私有信息的凸多边形相似判定问题的解决方案，介绍了问题 的由来，以及用到的几个基本协议，通过利用原有基本协议，设计了解决判定多边形相 似问题的方案。 第五章介绍了一个新的协议，通过这个协议能够由两个保密的点确定一条直线，使 用该方法可以解决一些多方保密计算中的计算几何问题，本文中就利用该协议提出了一 个寻求平面点集凸包问题的解决方案。 最后，对本文的研究工作进行了总结和展望。 计算几何中一些多方保密计算的应用研究 第2 章常用安全多方计算协议 对于参与计算的双方或者多方，由于现实中很难找到安全可信的第三方，因此研究 安全多方计算协议很有必要。目前，安全多方计算已得到许多学者的研究，其在密码学 上的地位也日益重要，它是电子选举、电子拍卖等密码学协议的基础。文【5 】中介绍了常 用安全多方计算协议： 2 1 基于不经意传输协议的安全多方计算协议 不经意传输( o b l i v i o u st r a n s f e r ，d r ) 是设计其他密码协议的基础口1 2 2 1 。0 丁可以用 来构造更为复杂的协议，不经意电路计算( o b l i v i o u sc i f c 试t e v a l 删i o n ) 。同时，不须任 何假设，利用它可以为n p 构造一个零知识证明【2 l 】。 不经意传输协议最早是由r a b i n 于1 9 8 1 年提出的【2 3 】。在d 丁中，有2 个参与者，假 设其中一方为舢i c e ( 发送方) ，另一方为b o b ( 接收方) 。在该协议中，舢i c e 输入1 个 消息m o ，1 。，a l i c e 和b 0 b 通过一定的方式交互之后，b o b 只能以的概率接收到 m ( 对a l i c e 的隐私性) ，而且，a l i c e 无法知道b o b 是否得到了m ( 对b o b 的隐私性) 。 b o b 可以确信地知道他是否得到了消息m ( 正确性) 。 1 9 8 5 年，e v e n 等人提出了2 取1 不经意传输2 4 1 。在2 取1 不经意传输协议中，a l i c e 的输入为2 个消息眠、m l o ，1 ) 。，b o b 的输入为f o ，1 ，舢i c e 和b o b 通过一定的 方式交互之后，b o b 可以得到鸩( 正确性) ，a l i c e 无法知道b o b 的选择c ( 对b o b 的 隐私性) ，b o b 无法同时得到眠和m ( 对灿i c e 的隐私性) 。2 0 0 0 年，s t e f 锄w | o l f 发现 2 取1 串不经意传输可以由2 取1 不经意传输来构造2 5 1 。 比2 取1 不经意传输更一般的不经意传输协议是刀取1 不经意传输掬。在这个协议中， b o b 只能得到刀则消息中的1 个。在1 9 9 6 年，b r a s s 矾、c r e p e a u 和s 觚恤发现一种构造力取 1 不经意传输协议的方法【2 刀。1 9 9 7 年，y a e lg e n l l e r 和t a jm a 脑n 提出了一个刀取1 分布式 不经意传输协议。2 0 0 1 年，w e n g u e yt z e n g 提出一个基于d i 仃eh e l l m a l l 问题的难解性的 刀取1 不经意传输协议f 2 8 j 。 刀取所不经意传输( o 朋 ，z 的话，他们就可以再讨价还价；而如果 埘 2 并对所有的“验证： o z 。 歹。 ( 6 ) 灿i c e 把这个结论告诉b o b 。 这里假设的是比较两个范围在1 到1 0 0 之间的数，如果是两个较大的数，由于复杂 度太高，这个方案是不实用的。文献 3 7 】给出了百万富翁问题的两个高效解决方案。 方案一：两个较小的数的比较( 1 口，6 0 j = 1 ，2 ，10 0 如果f 一6 o 利用d 正k 不经意传输，i c e 能够选择她愿意得到的唯一的数艺= g ( 口，6 ) 。d 互k 不经意传输方案保证了舢i c e 可以决定要得到的唯一的数，而b o b 不知道砧i c e 究竟选 择了哪个数。如果艺 1 0 0 ，那么口= 6 ；如果1 0 0 艺 6 ，如果 2 0 0 一 浠 一 硕十宁：伊论文 保持隐私是未来数据挖掘领域的焦点问题之，如何在不共享精确数据的条件下， 获取准确的数据关系是保持隐私的数据挖掘的首要任务。文 4 3 介绍了分布式环境下保 持隐私的数据挖掘的基本问题和措施，研究了一种基于向量点积的关联规则挖掘算法， 给出了一种安全的向量点积协议。对于垂直划分的分布式数据库，该协议既可用于搜索 频繁项集，又能保持各方数据的隐私。文 4 4 】针对分布式数据共享及计算中的隐私保护 问题，提出了一种适用于大规模分布式环境的隐私保护计算模型( p p c m l s ) ，通过综合 运用同态加密、安全点积协议、数据随机扰乱算法等多种安全技术，在实现了多个节点 在一个互不信任的分布式环境下合作计算的同时，任何节点无法获取其他节点的隐私信 息及敏感中间计算结果。又给出了基于该模型的分布式隐私保护方差计算、分布式隐私 保护数据聚类算法。从而满足了大规模分布式环境所要求的高效性和良好的动态适应 性。 ( 2 ) 、统计分析中的应用 多元回归分析是一类重要的预测方法。随着计算机网络技术的快速发展，用于统计 分析的样本数据有时由网络中不同的用户提供。当用户不愿意公开自己的私有数据信息