单调张成方案的一些性质

论文摘要

安全多方计算问题的研究对于密码学有着重要的指导意义。线性密钥共享方案是实现安全多方计算协议的主要工具之一，而实现线性密钥共享方案的其中两个主要的工具是线性码和单调张成方案，而线性码与单调张成方案之间存在一一对应的关系，从而单调张成方案就成为实现安全多方计算协议的关键。一方面，单调张成方案的行规模决定了线性密钥共享方案的有效性，而列规模则反映了密钥重构的计算量，因此寻找单调张成方案的行规模和列规模的最小值是一个很有意义的课题；另一方面，在利用线性密钥共享方案实现安全多方计算协议的时候，需要用到乘性的单调张成方案，因而构造乘性单调张成方案是实现安全多方计算的核心。针对这两个问题，本文得到了如下结果：1.对于给定的存取结构Γ，实现它的线性码C与单调张成方案(Fq,M, φ,ε)存在一一对应的关系。2. infRsize(M)=minG,H{number(Gc)1|GH=0}，其中Rsize(M)表示矩阵M的行数，infRsize(M)是Rsize(M)的下确界，number(Gc)表示G的列数。3. infCsize(M)=minG,H{Rrank(G)|GH=0}≤|R(G)|，其中Csize (M)表示矩阵M的列数，infCsize(M)是Csize(M)的下确界，|R(G)|表示极大攻击者结构中元素的个数，Rrank(G)表示G的行秩。4.给出了算法来生成行规模和列规模都达到下确界的单调张成方案。5.给出了乘性单调张成方案的一种新的构造算法，该算法较Cramer等人的构造方法的优点在于：在不改变列规模的前提下，可以得到行规模小于原来的2倍的乘性单调张成方案。6.得到一个定理：当攻击者结构不满足Q2条件时，上述算法得到的单调张成方案中一定存在两列，使得这两列做“”运算的结果为零向量。7.最后指出了最优乘性单调张成方案在理论上是可以找到的，从而理论上可以用它来实现最优的安全多方计算协议。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 安全多方计算协议的研究背景
• 1.2 安全多方计算的实现方法
• 1.3 安全多方计算的已知研究结果
• 1.4 本文的主要工作与组织
• 第2章 基础知识介绍
• 2.1 密钥共享方案
• 2.1.1 Shamir门限密钥共享方案
• 2.1.2 存取结构与一般的密钥共享方案
• 2.1.3 单调张成方案与线性密钥共享方案
• 2.1.4 线性码与线性密钥共享方案
• 2.2 安全多方计算
• 2.2.1 安全多方计算的定义
• 2.2.2 线性密钥共享方案与安全多方计算协议
• 2.3 乘性单调张成方案
• 2.4 本章小结
• 第3章 单调张成方案的下确界
• 3.1 单调张成方案与线性码
• 3.2 实现任意存取结构的最优线性码
• 3.3 单调张成方案的下确界
• 3.3.1 单调张成方案的下确界
• 3.3.2 生成最优单调张成方案的算法
• 3.4 本章小结
• 第4章 乘性单调张成方案的构造
• 4.1 Cramer的构造
• 4.2 一个新的构造
• 4.2.1 构造算法
• 4.2.2 例子
• 4.2.3 两个构造的比较
• 4.3 最优乘性单调张成方案的讨论
• 4.4 本章小结
• 第5章 结论
• 5.1 总结
• 5.2 未来工作展望
• 参考文献
• 攻读硕士学位期间所发表的论文
• 致谢