保护私有信息的统计计算问题研究

论文摘要

网络技术的飞速发展,开启了信息处理的新时代。随着大量共享数据资源日益充盈,信息安全问题逐步引起了人们的重视。一方面,企业、团体在自身发展中不断积累着各种有价值的数据,它们做为财富的一种特殊形式被严密地保护起来;另一方面,合作利益又不断地驱使各行各业进行协同计算以实现信息价值的最大化。在这种情形下,既能够保护私有信息又能够实现合作计算的信息安全技术逐渐发展壮大,并为社会各界所认同和推广。安全多方计算正是在这样的实际需求下应运而生的技术。1982年姚期智首次提出了这一概念,并以百万富翁协议诠释了安全多方计算的含义,后经OdedGoldreich等人的理论完善,现已逐步进入了“为特殊问题设计特殊求解”的时代。时至今日,这项技术已经在数据挖掘、电子交易、科学计算、信息检索、计算几何等越来越多领域显示出了巨大的应用潜力,并做为信息安全学科中一个不可或缺的研究项目吸引着越来越多的学者和研究团体投入其中。保护私有信息的统计计算是安全多方计算技术的一个重要分支,其主要功能在于帮助互不信任的两个或多个用户实现不泄露各自隐私数据前提下的协同统计分析。自2001年杜文亮将之列举为安全多方计算的一大应用领域以来,平均值、方差分析、线性回归等基本问题都已逐渐得到了解决。然而在军事、政治、金融、医疗等多个领域中,统计计算形式多样而又无处不在,这就使得保护私有信息的统计计算在广泛的应用前景之下成为了亟待研究的课题。本文从统计计算所涉及的矩阵操作入手,在解决统计分析基本问题的成果之上考察实际问题中的应用,并关注于各种协议的复杂度和安全性分析。其主要的研究成果包括:1.灵活地运用安全多方计算技术改进了数据对应成比例协议,使之在统计性能上更加卓越。并且在保证不泄露参与者私有信息的情况下解决了分享矩阵的求秩问题。成功地将问题的解决方法转化成协议的形式,并借用迭代的思想通过模拟器的构造证明了安全性。2.构造了保护私有信息地求解矩阵特征值的安全协议。综合运用代数学知识和安全多方计算技巧,为不同类型的实际情况设计完成了分享矩阵环境下的一种可快速返回局部解的协议算法和一种可返回全部解的协议算法。它们既可用于快速求解从而判定属性,又可用来全面地求解问题。并在此结果的基础之上继续求解了特征值对应的特征向量,同时针对一类具有特殊性质的矩阵提出了快速求幂运算的协议。3.系统地研究了保护私有信息的各类统计度量值运算,包括调和平均值、加权平均值、几何平均值、众数、均方根等。深入剖析了各度量值的计算特点,比较异同并总结归纳为三类,分别采用最直接有效的的安全多方计算原理和技术设计了求解相应问题的安全协议,同时对每类协议的模块进行了严密的安全性证明。4.细致地分析了两方安全模型下多元线性回归问题的求解,在完成极大似然估计的基础之上,对回归关系的残差平方和与总平方和进行了推断计算。通过总结分享矩阵与向量的特定组合下的连乘操作的规律,发现了可使计算大幅得到简化的关键,从而降低了计算代价,并获得了良好的性能。同时将这一成果与现有技术相结合在两方合作无法泄露数据之和的前提下实现了多元分析。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景与现状
• 1.3 选题意义及主要贡献
• 1.4 内容安排
• 1.5 本章小结
• 第二章 基本理论概述
• 2.1 安全多方计算理论
• 2.2 协议设计基础
• 2.2.1 计算模型
• 2.2.2 安全定义及分析方法
• 2.2.3 数据分享模型
• 2.2.4 计算复杂性理论及一些约定
• 2.3 基本原理与协议
• 2.3.1 数据扰乱原理
• 2.3.2 同态加密与可交换加密系统
• 2.3.3 茫然传送协议
• 2.3.4 安全求和
• 2.3.5 向量点积
• 2.3.6 集合求交
• 2.3.7 秘密比较
• 2.3.8 矩阵乘积
• 2.4 本章小结
• 第三章 保护私有信息的矩阵求秩
• 3.1 矩阵秩的概念与代数学求解算法
• 3.2 数据划分模型
• 3.3 数据对应成比例协议
• 3.3.1 正确性说明
• 3.3.2 安全性证明
• 3.3.3 性能分析
• 3.4 矩阵求秩协议
• 3.4.1 安全矩阵求秩协议的正确性
• 3.4.2 安全矩阵求秩协议的安全性
• 3.4.3 安全矩阵求秩协议的复杂度
• 3.5 协议的应用
• 3.6 本章小结与展望
• 第四章 求解矩阵特征值的保护私有信息协议
• 4.1 基础知识简介
• 4.1.1 求解特征值和特征向量的代数算法
• 4.1.2 矩阵求幂的的代数知识
• 4.2 第一类协议—快速返回局部解
• 4.2.1 快速返回局部解的安全求解矩阵特征值协议
• 4.2.2 Protocol 4.1的正确性分析
• 4.2.3 Protocol 4.1的安全性证明
• 4.3 第二类协议—返回全部解
• 4.3.1 可返回全部解的安全求解矩阵特征值协议
• 4.3.2 Protocol 4.2的正确性分析
• 4.3.3 Protocol 4.2的安全性证明
• 4.4 协议设计方案的比较
• 4.5 求解特征向量的安全协议
• 4.5.1 安全地求解矩阵的特征向量
• 4.5.2 Protocol 4.3的协议分析
• 4.6 联合矩阵求幂的安全协议
• 4.7 本章小结与展望
• 第五章 统计度量值问题的安全解决方案
• 5.1 背景知识简介
• 5.1.1 统计度量值的概念
• 5.1.1.1 平均值
• 5.1.1.2 众数
• 5.1.1.3 中位数
• 5.1.1.4 集中趋势度量值之间的关系
• 5.1.1.5 离散型度量值
• 5.1.2 研究现状分析
• 5.1.3 保护私有信息的统计度量值问题描述
• 5.2 安全求和协议解决度量值问题
• 5.2.1 调和平均值的安全求解协议
• 5.2.2 加权平均值的安全求解协议
• 5.2.3 均方根及一些离散度量值的安全求解协议
• 5.2.4 协议模块说明
• 5.2.5 协议模块的安全性证明
• 5.3 数据扰乱原理可解决的度量值问题
• 5.3.1 几何平均值的安全求解协议
• 5.3.2 协议模块分析
• 5.3.3 协议模块的安全性证明
• 5.4 可交换加密解决的度量值求解问题
• 5.4.1 众数的安全求解协议
• 5.4.2 中位数的经验求解
• 5.4.3 模块功能说明
• 5.4.4 协议模块的安全性证明
• 5.5 本章小结与展望
• 第六章 回归关系的统计推断
• 6.1 背景知识介绍
• 6.1.1 回归关系的统计推断问题
• 6.1.2 研究现状分析
• 6.2 矩阵连乘模块的设计
• 6.2.1 符号说明
• 6.2.2 矩阵连乘协议
• 6.2.3 协议的分析
• 6.3 极大似然估计
• 6.4 残差平方和
• 6.5 总平方和
• 6.6 协议的应用分析
• 6.7 本章小结
• 第七章 总结与展望
• 7.1 研究工作总结
• 7.2 未来研究展望
• 参考文献
• 致谢
• 攻读学位期间完成的学术论文
• 参加的科研项目与获奖情况