并行安全多方计算协议应用研究 .pdfVIP

并行安全多方计算协议应用研究--第1页

并行安全多方计算协议应用研究

摘要：安全多方计算蕴含了对任何密码协议问题在原则上的实现方

案，它能在原则上告诉我们哪些问题是可以解决的，哪些问题是不可

能解决的。首先介绍了并行安全多方计算（SPMC）的相关工具和概

念知识；接着通过模拟改进后的密码学就餐问题显示SPMC的实际

应用，并在此基础上构建了SPMC的协议；最后通过“直和”方法

对其安全性进行了验证分析，提出了值得进一步探讨的SPMC问题

以及SPMC协议的改进研究。

关键词：并行；安全多方计算；线性密钥共享体制

0引言

随着网络技术的不断发展，网络安全中的多方计算变得越来越普

遍，极大地改变了计算的含义及计算的方式。计算可能发生于相互信

任的参与者之间，此时问题是很容易解决的；也有可能存在于部分信

任的合作者之间，甚至存在于竞争者之间，此时问题的计算也随之复

杂起来。这些参与者们特别担心的是在完成该计算的过程中，有可能

出现他们各自输入的信息被他人获悉或者被泄露的情况，也就是要确

保自己数据的安全性与秘密性。由此提出了安全多方计算（SMC，

securemultipartycomputation）协议的问题。

简单来说，SMC问题可以用数学的形式描述为：有n个参与者

P-1，P-2，„，P-n，通过一种安全的方式来共同计算一个函数，这

里的安全是指输入输出信息的必威体育官网网址性与输出结果的正确性。具体来

并行安全多方计算协议应用研究--第1页

并行安全多方计算协议应用研究--第2页

讲，每个参与者P-i，有一个自己的秘密输入信息x-i，n个参与者要

共同计算一个函数f（x-1，x-2，„，x-n）=（Y-1，Y-2，„，Y-n），

使得计算结束时每个参与者P-i只能得到Y-i，除此之外得不到其它地

方的任何信息。

对于并行安全多方计算（SPMC，secureparallelmultiparty

computation）的概念提出时间并不长，实际上，SPMC是作为SMC

的一个拓展的概念。一般情况下，SMC是针对一个特定的函数进行

计算的，而对于SPMC来说，是指同时安全多方计算了多个函数，

并且每个函数对应的攻击者结构是不同的。

1预备知识

SPMC协议的设计，需要一些基本的工具以及概念知识。

1.1密钥共享

为了描述一般密钥共享方式，引入存取结构的概念。

定义1：存取结构AS（accessstructure）。设P={P-1，„，P-n}

是n个参与者集合，用AS来命名P上的一个存取结构，也就是AS

是由P上的一些子集组成的一个非空子集合，即AS2+p，而且满足单

调性质：如果同时满足A∈AS和BP，而且AB，那么有B∈AS。

通常研究SPMC问题利用的是线性多密钥共享体制（LMSSS），

那么线性密钥共享体制是一个必需的理论知识。

定义2：线性密钥共享体制（LSSS，linearsecretsharingscheme）。

令P={P-1，„，P-n}为参与者集合，其AS是P上一个存取结构。令