门限秘密共享及其典型应用

任方1，2，王倩1

（1.西安邮电大学通信与信息工程学院，陕西西安710121；

2.无线网络安全技术国家工程实验室，陕西西安710121）

摘要：秘密共享技术是密码学的重要分支，目前已经有了大量的理论与应用研究成果。（k，n）门限秘密共享方案将秘密信息分成n 份无意义的子秘密，只有拥有至少k 份子秘密才能恢复秘密信息，可以有效提升其安全性。在介绍了基本的门限秘密共享方案的基础上，对其在密码学几个重要分支如数字签名、基于身份加密、基于属性加密以及图像加密中的典型应用进行了全面的归纳与总结，分析了当前存在的问题，并对未来的研究趋势进行展望。

教育期刊网 http://www.jyqkw.com
关键词 ：秘密共享方案；数字签名；身份密码学；属性加密；图像加密；视觉密码学

中图分类号：TN918.4?34 文献标识码：A 文章编号：1004?373X（2015）13?0071?05

收稿日期：2015?01?03

基金项目：国家自然科学基金项目（61272037，61472472）；西安邮电大学青年基金项目（ZL2013?06）

0 引言

随着计算机与网络技术的迅速发展，信息安全已经成为日益严峻的问题。密码技术可以用来实现安全的数据通信与存储，是信息安全技术的基础。由于所有密码体制的安全性都依赖于密钥的保密性，因此如何实现安全的密钥管理成为信息安全领域头等重要的大事。

秘密共享技术将一个秘密值分成若干份，由不同的实体进行分散保存以提高安全性，可以用来实现安全的密钥管理。1979 年，Shamir 和Blakley 分别用代数学和几何学的方法给出了最早的门限秘密共享算法[1?2]。其基本实现思想如下：给定正整数k 和n，其中k≤n，一个（k，n）门限秘密共享方案指的是将秘密信息D分成n 份子秘密，其中的任意k 份或更多的子秘密可以重构秘密信息D，而任意k-1份或更少的子秘密则无法得到D的任何信息，称k 为门限值。

利用门限秘密共享方案可以实现密钥的分布式管理，即将密钥SK分成n 个不同的子密钥，将其分发给不同的用户，任意k 个用户将其所持有的k 份子密钥进行共享即可以恢复出密钥SK。门限秘密共享实现密钥管理的优势在于：

（1）有利于限制合法用户的权利，即少于k 个合法用户无法得到SK；

（2）有利于提高系统安全性，攻击者即使得到了k-1份子秘密，仍然不能得到有关SK的任何信息；

（3）有利于提高系统健壮性，攻击者即使破坏了n-k 份子秘密，余下的k 份子秘密仍然能够恢复出SK。

门限秘密共享自提出以来吸引了众多的研究者，产生了大量的研究成果[3?4]，在密码学的很多分支都有着广泛的应用。本文在回顾基本门限秘密共享方案的基础上，对其当前最主要的应用进行归纳和总结，并进一步展望其未来的发展方向。

1 门限秘密共享方案

1.1 Shamir的门限秘密共享方案

Shamir使用多项式插值实现了基本的（k，n）门限秘密共享方案，该方案具体由以下三个阶段构成：

显然对于任意的xij，j=1，2，…，k，上式右端计算的结果恰好等于sij，由多项式理论可知，若两个k-1 次多项式在变量的k 个不同取值处得到的函数值相等，则这两个多项式必定相等，于是上式成立。由此可以计算出s = a0 = g(0) 。

1.2 Blakley的门限秘密共享方案

Blakley使用几何学的方法给出了另一个（k，n）门限秘密共享的方案。其基本思想是将秘密值看成一个k 维空间中的点，分发给不同参与者的子秘密是不同的k-1维子空间，当k 个参与者将其子秘密进行共享时，可以得到这些子空间的惟一交点，从而得到秘密值。具体描述如下：

选择有限域Fq，其中q ? n。设参与者集合为P={P1，P2，…，Pn}，k 为门限值，秘密信息s ∈ F kq 。选择Fq上的k 元线性方程组为：

则方程组可写成AX = B。选择矩阵A 时需要满足两个条件：

（1） A 的任意k 行线性无关；

（2）秘密值s 是以上线性方程组的解。

每一个方程可以看作一个k-1维的子空间，为每一个参与者分发这样的一个方程，当其中k 个参与者共享其方程时可以得到一个满秩的k 元线性方程组，可以解出惟一的值，即秘密值s。而任意k-1 个方程联立则无法得到惟一解。

2 门限秘密共享在数字签名中的应用

数字签名用来实现消息的完整性保护和签名者的不可否认服务，是信息安全重要的组成部分。当需要对消息m 进行签名时，签名者用自己的私钥SK 对消息的Hash 值进行签名运算，验证者验证签名时需要用签名者的公钥PK 进行。一个（k，n）门限数字签名算法指的是利用门限秘密共享的方法实现签名运算。即将签名私钥SK作为秘密值分成n 个子密钥交由n 个用户保管，只有至少k 个用户的子密钥共享后才可以进行签名运算。门限数字签名的算法框架如图1所示。

门限数字签名的重要应用场合是在公钥基础设施[5]（Public Key Infrastructure，PKI）中实现分布式的证书中心（Certificate Authority，CA）。PKI 是以用户公钥数字证书为中心的一整套公钥管理机制，可信的CA是其核心组件，主要实现对用户公钥数字证书的管理。公钥数字证书将用户的身份与其公钥进行捆绑，由CA的私钥进行签名以保证其有效性。由于CA的独特地位，往往成为PKI系统的安全瓶颈与性能瓶颈。因此利用门限秘密共享技术保护CA私钥的分布式CA有着重要的理论与实际意义。

在分布式CA模型中，由n 个指定的用户（称为服务者）秘密保存CA 私钥，将CA 的私钥看作秘密值分成n个子密钥分别由这n 个服务者保管。当某用户需要证书服务时，服务者中的任意k( ? n) 个相互合作即可以完成一份合法的证书签名，而k-1或者更少的服务者即使相互共享了子密钥也无法完成合法签名。分布式CA如图2所示。

一般来讲直接采用门限秘密共享实现分布式CA是不安全的，因为k 个服务者进行一次证书签名就会计算CA的私钥，他们以后就可以独自进行证书签名。为了弥补这一缺陷，分布式CA往往采用更实用的技术，即k 个服务者进行证书签署时不恢复CA私钥，而是分别独立用各自的子密钥对证书进行部分签名运算，用户利用部分签名值计算完整的证书签名。这样可以有效保护CA私钥与服务者子密钥不泄露，提高分布式CA 的安全性。目前该领域主要的研究内容包括如何降低服务者节点的通信负担，提高整个分布式CA系统的实现效率。

3 门限秘密共享在IBC 中的应用

为了降低PKI 体系中公钥证书管理的巨大开销，Shamir 提出了基于身份的公钥密码体制[6]（IdentityBased Cryptography，IBC）。在IBC 体制中，用户的公钥PK是根据其公开身份信息如姓名、地址、邮箱等进行计算得到的，而用户的私钥SK 则由可信的私钥生成中心（Private Key Generator，PKG）根据系统的主密钥以及用户公钥PK计算得出。要获得一个用户的公钥，只需要知道其身份以及系统公开参数而无需验证公钥证书，从而避免了证书管理的开销，大大减轻了密钥管理的沉重负担。美国国家标准技术研究所（National Institute ofStandards and Technology，NIST）密钥管理工作组在密钥管理总结报告中明确指出了IBC 在密钥管理中的地位与优势[7]。

尽管IBC 体制有着明显的优势，但其仍存在缺陷，即用户必须无条件相信PKG，这就导致PKG 成为系统的安全瓶颈，也往往成为攻击者首选的攻击目标。一旦PKG被攻击者攻陷，整个IBC体制就没有安全性可言，因此PKG的私钥安全是整个IBC体制中的核心。将秘密共享技术用于IBC 可以实现分布式的PKG（DistributedPKG，DPKG），能够有效提升系统安全。

DPKG 的基本实现思想如下：将PKG 的私钥SK 作为秘密值利用（k，n）门限秘密共享技术分给n 个可靠的服务者，只有k 个服务者合作才能行使PKG 功能，利用用户的身份公钥信息为用户生成合法的私钥。任意少于k 个的服务者无法恢复PKG私钥，也无法计算出用户私钥，从而有效避免了传统PKG的缺陷。

采用DPKG的IBC体制如图3所示。

DPKG自从提出以来就得到了广泛的研究，主要成果有：Zhang 和Fang 等人将IBC 用于Ad Hoc 网络[8 ? 9]。

Ren提出的方案[10]通过DPKG在公开信道对用户进行认证来消除对秘密信道的依赖，缺点是导致存储与通信负担过重。Chan基于可验证秘密共享技术提出的DPKG方案[11]摒弃了单一实体，增强了PKG本身以及IBC系统的安全性。Da Silva等人提出了用于Ad Hoc网络的完全自组织IBC密钥管理方案[12]，解除了对PKG的依赖。

目前该领域的主要研究内容包括：

（1）如何降低服务者节点的通信负担，特别在AdHoc网络中，节点通信与计算能力均较弱，这一问题尤为突出；

（2）用户的身份公钥撤销问题。IBC系统中的身份公钥撤销往往较难实现，在采用DPKG的IBC中更是如此。如何在不增加DPKG 系统复杂性的前提下实现安全高效的身份公钥撤销是目前的研究热点[13]。

4 门限秘密共享在ABE 中的应用

基于属性的加密方案（Attribute Based Encryption，ABE）可以看作基于身份加密方案的推广，其中用户的惟一身份被多个属性所替代，用户拥有与其属性相对应的属性私钥集，其解密能力完全由用户所拥有的属性值而非其身份所确定。

最早的ABE 是Sahai 与Waters 于2005 年提出的门限式ABE[14]，在该方案中，用户能够解密密文当且仅当他所持有的属性私钥数达到预设的门限值。此后陆续出现的密钥策略的ABE[15]（KP?ABE）和密文策略的ABE[16]（CP?ABE）是将门限秘密共享推广到一般访问结构的秘密共享而得到的ABE，具有更细致的访问控制能力，应用场合也更广。

典型的（k，n）门限式ABE的算法构成如下：

（1）Setup，初始化算法，由属性中心（Attributes Au?thority，AA）生成系统的各项参数。包括全属性集合At = {1，2，…，n}，系统的主私钥集合MK，公开参数集合PK等。

（2）Key Generation，私钥生成算法，由AA 为一个属性子集ω ? At 生成私钥集合。这个属性子集对应于一个合法用户U 所拥有的所有属性，U 提交私钥申请和自己的ID 号、属性集合，该算法将生成的私钥集合{D | i i ∈ ω} 分发给用户U。

（3）Encryption，加密算法，由加密方运行，用户V 使用一个属性集合ω′? At 对明文消息m 进行加密，得到密文c。

（4）Decryption，解密算法，由解密方运行，用户U 能够解密密文c，当且仅当他所拥有的属性集合ω与加密属性集合ω′的交集包含至少k个属性，即| ω ? ω′| ? k。

算法流程如图4所示。

目前ABE 的主要研究内容与发展趋势包括：使用更一般的秘密共享技术将门限式ABE推广至一般访问结构的ABE；可变门限式ABE技术，即用户的解密属性门限可以在每次加密时动态指定；用户的属性撤销问题，与IBC类似，这也是一个研究热点。

5 门限秘密共享在图像加密中的应用

随着多媒体处理技术的发展，数字图像的地位日益重要。数字图像蕴含的大量信息使其安全性成为当前信息安全研究中重点关注的对象。典型的数字图像加密技术包括基于矩阵变换的图像加密与基于混沌映射的图像加密[17]，前者的缺陷是密钥空间太小，难以抵抗穷举攻击；后者的缺陷是算法安全性依赖混沌映射的数学特征，难以实现完善保密性。将秘密共享技术引入图像加密领域可以得到一大类安全性更高的算法，目前已经有了大量的研究成果。

5.1 基本的图像秘密分存加密算法

基于秘密分存的图像加密算法根据门限秘密共享的理论而设计，其基本实现思想为：将待加密图像按照某种规则分成n 幅杂乱无章的子图像，将它们分发给n 个用户保管；每幅子图像本身不表示任何信息，其中任意k 幅或更多子图像可重构原始图像，但少于k 幅则得不到原始图像的任何信息，从而达到保护图像的目的。

下面给出一个典型的灰度图（4，4）秘密分存加密算法。设待加密灰度图像为M，将其灰度值排列成一个二进制串，长度为（l M），则加解密的过程如下：

（1）随机选择3个二进制串R，S，T，要求（l R）=（l S）=（l T）=（l M）；

（2） 将这4 个二进制串进行逐比特异或，得到U = M⊕R⊕S⊕T；

（3）将R，S，T，U 作为4 个子图像分别发给不同的4个用户；

（4）4个用户将其所持有的子图像共享，可以重构出秘密图像M=R⊕S⊕T⊕U，而任意3个用户的子图像无法得到秘密图像的任何信息。

实验结果如图5，图6所示。

5.2 视觉密码学

视觉密码学（Visual Cryptography Scheme，VCS）是1994年Naor和Shamir在欧密会上提出的一种新的图像加密技术[18]，它基于秘密共享的思想，将需要保护的秘密图像分解成若干幅无意义的分享图像（shares）。解密时无需算法支持，只需找到若干幅满足条件的分享图像，直接利用人的视觉进行合成解密就可以得到原始的秘密图像。视觉密码学可以实现完善保密性，近年来发展十分迅速[19?21]。

二值图的（2，2）VCS方案的加密过程是将秘密二值图像分成两个随机的二值分享图像，每一个像素进行4倍的像素扩张，并以随机的形式选择扩张结果；解密过程是直接将两个分享图像进行叠加，若同为白色像素则叠加结果是白色，若至少有一个是黑色像素则叠加结果是黑色。单个像素的加解密规则如表1所示。

该领域的研究内容与发展趋势有：基于门限结构的灰度图像VCS与彩色图像VCS；基于一般访问结构秘密共享的VCS；可进行多幅秘密图像分享的VCS；分享的子图像为有意义图像的VCS。

6 结语

门限秘密共享技术是密码学的重要分支之一，经过30 多年的发展，目前已经在多个领域有了广泛的应用。本文在回顾了Shamir和Blakley基本门限秘密共享方案的基础上，介绍了目前门限秘密共享方案最主要的几个典型应用，包括门限签名与分布式CA、分布式PKG、门限式ABE、图像秘密分存与视觉密码学等重要的密码学前沿领域。对于每一种应用，给出了基本的实现思想与算法概述，并对该领域的研究现状与未来发展趋势进行了介绍。研究表明，门限秘密共享作为重要的秘密分享技术，其理论与应用在密码学中占据重要的地位。

教育期刊网 http://www.jyqkw.com
参考文献

[1] SHAMIR A. How to share a secret [J]. Communications of theACM，1979，22（11）：612?613.

[2] BLAKLEY G R. Safeguarding cryptographic keys [C]// Pro?ceedings of 1979 AFIPS National Computer Conference. [S.l.]：AFIPS，1979：313?317.

[3] FARRAS O， PADRO C. Ideal hierarchical secret sharingschemes [J]. IEEE Transactions on Information Theory，2012，58（5）：3273?3286.

[4] TIAN Youliang，MA Jianfeng，PENG Changgen，et al. Fair（t，n）threshold secret sharing scheme [J]. IET Information Security，2013，7（2）：106?112.

[5] MAO Wenbo. Modern cryptography：theory and practice [M].Upper Saddle River，USA：Prentice Hall，2004.

[6] SHAMIR A. Identity ? based cryptosystems and signatureschemes [C]// Proceedings of 1984 CRYPTO on Advances inCryptology. Berlin：CRYPTO，1984：47?53.

[7] ELAINE B，DENNIS B，SANTOSH C，et al. Cryptographickey management workshop summary [R]. USA：NIST，2009.

[8] ZHANG Y，LIU W，LOU W，et al. Securing mobile ad hocnetworks with certificateless public keys [J]. IEEE Transactionson Dependable and Secure Computing，2006，3（4）：386?399.

[9] FANG Y，ZHU X，ZHANG Y. Securing resource?constrainedwireless ad hoc networks [J]. IEEE Wireless Communications，2009，16（2）：24?30.

[10] REN Y，WANG J，ZHANG Y，et al. Identity?based key issuingprotocol for ad hoc networks [C]// 2007 IEEE InternationalConference on Computational Intelligence and Security. Har?bin：IEEE，2007：917?921.

[11] CHAN A. Distributed private key generation for identity basedcryptosystems in Ad Hoc networks [J]. IEEE Wireless Commu?nication Letters，2012，1（1）：46?48.

[12] DA S E，ALBINI L C P. Towards a fully self?organized identi?ty ? based key management system for MANETs [C]// 2013IEEE the 9th International Conference on Wireless and Mo?bile Computing， Networking and Communications. [S.l.]：IEEE，2013：717?723.

[13] LIU S，LONG Y，CHEN K. Key updating technique in identity?based encryption [J]. Information sciences，2011，181（11）：2436?2440.

[14] SAHAI A， WATERS B. Fuzzy identity based encryption[C]// Proceedings of 2005 CRYPTO on Advances in Cryptolo?gy. Berlin：CRYPTO，2005：457?473.

[15] GOYAL V，PANDEY O，SAHAI A，et al. Attribute?based en?cryption for fine?grained access control of encrypted data [C]//Proceedings of 2006 ACM Conference on Computer and Com?munications Security. [S.l.]：ACM，2006：89?98.

[16] WATERS B. Ciphertext?policy attribute?based encryption：anexpressive， efficient， and provably secure realization [C]//Proceedings of 2011 International Conference on Practice andTheory in Public Key Cryptography. Taomina：PKC，2011：53?70.

[17] PATEL K D，BELANI S. Image encryption using differenttechniques a review [J]. International Journal of EmergingTechnology and Advanced Engineering，2011，1（1）：30?34.

[18] NAOR M，SHAMIR A. Visual cryptography [C]// Proceedingsof 1994 Workshop on the Theory and Application of Crypto?graphic Techniques. Perugia：EUROCRYPT，1995：1?12.

[19] YU B，XU X，FANG L. Multi?secret sharing threshold visualcryptography scheme [C]// 2007 IEEE International Conferenceon Computational Intelligence and Security Workshops. Har?bin：IEEE，2007：815?818.

[20] YANG C N，WANG D S. Property analysis of XOR?based vi?sual cryptography [J]. IEEE Transactions on Circuits and Sys?tems for Video Technology，2014，24（2）：189?197.

[21] HOU Y C，WEI S C，LIN C Y. Random?grid?based visualcryptography schemes [J]. IEEE Transactions on Circuits andSystems for Video Technology，2014，24（5）：733?744.

作者简介：任方（1981—），男，陕西西安人，讲师，博士。主要研究方向为密码学与信息安全。

王倩（1990—），女，新疆伊犁人，硕士研究生。主要研究方向为密码学与信息安全。