开放科学(资源服务)标志码(OSID)：

0 概述

秘密共享体制可将一份秘密安全地交给多方保管，其在商业秘密保管、银行网络管理等注重信息安全的领域发挥重要作用。秘密共享又称(k，n)门限秘密共享。将一份秘密信息S在n个参与方中进行分配，每个参与方所保管的部分称为S的一个影子秘密。若掌握其中任意k个影子秘密，即可计算还原出S，但若只是掌握任意不足k个影子秘密，则无法获取S的任何内容，k为恢复S所需影子的最小秘密个数。现有的秘密共享方案大部分基于SHAMIR算法发展而来，这类方法均涉及复杂多项式计算，在实际应用中处理信息非常耗时。针对该问题，本文基于异或运算构建秘密共享算法，以期提高数据处理速度。

1 相关工作

1979年，SHAMIR^[1]提出了秘密共享的概念，其方案基于多项式插值进行，涉及大量多项式计算，方案较为复杂且计算量较大，速度较慢。此后多种基于异或运算的秘密共享算法被相继提出^[2-4]，与SHAMIR算法相比显著提高了计算效率。

传统秘密共享面临的问题主要有分发者欺骗和恶意参与者攻击两类。分发者欺骗是指分发者在下发影子秘密时可能会给参与者无效的影子秘密，恶意参与者攻击是指授权子集外的人伪装成授权子集的成员去骗取他们的影子秘密^[5]。为了解决这些问题，研究者相继提出可验证秘密共享以及可更新的秘密共享方案。何晓婷等^[6]基于SHAMIR算法提出一种集中式的认证方案，快速辨认出了非法参与者；刘鹏等^[7]提出基于异或运算的份额可更新(2，n)门限秘密共享算法，但该方案只能进行(2，n)门限秘密共享，不能实现任意份额的(k，n)秘密共享；谷婷等^[8]提出无可信中心可验证可更新的向量空间秘密共享。份额更新的基本思想是：在每一个阶段，对现存的秘密份额进行更新，每次更新后的影子秘密不与之前阶段的影子秘密有任何联系。这种做法可以有效解决多次部分秘密泄露导致原密码的泄露的问题。王彩芬等^[9]提出一种可验证的口令授权的多秘密分享方案，在秘密共享过程中可防止分发者欺骗和恶意参与者攻击。张艳硕等^[10]提出基于特征值的可验证特殊门限秘密共享方案，利用n阶矩阵的特征方程具有重根的特点，密钥分发者给每一个参与者分发2种不同的子密钥，这2种子密钥满足线性无关和对应的特征值相等。

近年来，抗泄漏秘密共享^[11-12]成为一个热门的研究方向。随着侧信道攻击技术^[13-14]不断发展，传统秘密共享方案的安全性受到严重威胁，特别对于需长期维护的秘密，敌手可利用侧信道攻击技术获取一定数量的秘密、秘密份额或者方案相关信息^[15]。对此，AGGARWAL等^[16]提出一种强抗泄露的秘密共享方案，提出一种基于一般访问模型将非抗泄露的秘密共享方法转化为抗泄露的方法。

身份认证协议^[17-18]的目标是确认用户当前声称自己的身份信息是准确无误的。作为抵御攻击的第一道屏障，身份认证可以有效防止离线字典攻击和身份伪造攻击^[19-20]。生活中常见的输入密码登录网站、指纹验证解锁手机等场景均是身份认证协议的应用。

作为一种基础的加密协议，秘密共享协议可以应用于身份认证。一种较直接的思路是，对某个密钥S进行(k，n)秘密共享分散，用户持有其中m(m < k)个影子秘密。服务器持有剩余(k-m)个影子秘密和密钥S。当用户发送验证请求后，服务器先尝试使用用户发送的影子秘密和自身存储的影子秘密对S进行还原。若能成功还原S，则验证成功，否则验证失败。

2 本文算法 2.1 异或运算的性质

异或(XOR)运算是一种二进制运算。假设对于一个二进制序列L₁，将其与另一个等长的二进制序列L₂进行异或运算，记运算结果为L₃，L₁ XOR L₂ = L₃。根据异或运算的可逆性，有L₃ XOR L₂ = L₁。将L₁视作待加密信息，将L₂视作加密键，序列L₃为加密后的密文。在缺失L₂的情况下，解密者只掌握L₃的信息，无法根据L₃推测出秘密L₁。只有获取L₂和L₃后，解密者才可通过L₃ XOR L₂ = L₁来还原秘密L₁。

以(3，4)门限秘密共享为例介绍本文算法原理和具体过程。

2.2 (3，4)秘密共享算法

(3，4)秘密共享算法整体包含以下2个步骤：

1) 将秘密S转化为6个二进制序列，S能且只能由全部6个二进制序列一起通过计算还原，其中每个二进制序列称为秘密S的1条线索。

2) 对这6条线索，按照一定规则进行分组存储，每组二进制序列形成S的1个影子秘密。只有掌握足够数量的影子秘密，使这些影子秘密包含着全部6条线索，原秘密S才能被还原。

在(3，4)秘密共享的情况下，将秘密S转化为线索的过程描述如下：

1) 对于秘密S，将其转化为对应的二进制序列G。

2) 对于G，随机生成1个等长的二进制序列，记为K₁。

3) 对G和K₁进行异或运算，记运算结果为G₁，G XOR K₁=G₁。

4) 随机生成1个与G₁等长的二进制序列K₂，G₁ XOR K₂=G₂。

5) 随机生成1个与G₂等长的二进制序列K₃，G₂ XOR K₃=G₃。

6) 随机生成1个与G₃等长的二进制序列K₄，G₃ XOR K₄= G₄。

7) 随机生成1个与G₄等长的二进制序列K₅，G₄ XOR K₅=G₅。

8) 保留K₁、K₂、K₃、K₄、K₅、G₅这6个二进制序列为算法所需的全部线索，删除过程中所有其他二进制序列。线索获取完毕。

9) 线索获取完毕后，按照一定规则将6个线索分为4组，分配结果将使得每组线索的集合成为原秘密S的一个影子秘密。记这4个影子秘密分别为A、B、C、D。在分组时，需遵循以下2条规则：

(1) 对于S的任意一个线索，都要至少存储在2个不同的组中各1次。

(2) 对于A、B、C、D，任取其中2组，都至少有1个线索是只存在于这2组中各1次的。

根据数学排列组合的知识，S至少要有6条线索才能满足分组规则。分配结果并不具有唯一性。一种可行的分配结果如表 1所示。分配完成后，当A、B、C、D，中只缺失任意某1组时，剩余3组已携带全部6个线索，S可被还原。若4组中缺失任意2组，必有1个线索缺失，S无法还原，目标达到(3，4)秘密共享算法。

假设掌握了A、B、C的信息，从A、B、C的影子秘密恢复出S的步骤如图 1所示。

假设待加密信息S转化为二进制序列后为11010010，算法分散过程如图 2所示。按照从上往下的顺序，随机二进制生成器生成一个与G等长的二进制K₁，并与G进行异或运算，将运算结果记为G₁。在此基础上，G₁再与随机生成的二进制序列K₂进行异或运算。依次异或，直至异或运算进行5次为止。

在全部异或运算完成后，只保存K₁、K₂、K₃、K₄、K₅、G₅这6条线索，其余信息均不保存。对于线索的分组，根据前述规则，某一个线索只能存入某2组中各1次，且每次影子秘密的组合不与之前任意1次组合重复。记4组线索集合为A、B、C、D。具体分组过程描述为：1)对于K₁，分别存入A、B组；2)对于K₂，分别存入A、C组；3)对于K₃，分别存入A、D组；4)对于K₄，分别存入B、C组；5)对于K₅，分别存入B、D组；6)对于G₅，分别存入C、D组。

假设已完全掌握了A、B、C的全部信息，还原S的步骤如图 3所示。首先从C中取出G₅，从B中取出K₅，两者异或生成G₄。在此基础上，依次从A、B、C中取出线索K₄、K₃、K₂、K_1，并依次与上一次异或运算的结果进行异或运算。当全部异或运算完成时，秘密信息S即被成功还原。

2.3 (k，n)秘密共享算法

基于2.2节的举例说明，本节提出一种基于异或运算的(k，n)秘密共享算法。记算法生成的影子秘密分别为A₁，A₂，$ \cdots $，A_n ，全体影子秘密的集合为U。算法步骤描述如下：

算法1   (k，n)门限秘密共享算法

输入    $ (s, k, n, U) $

输出   $ ({A}_{1}, {A}_{2}, \cdots , {A}_{n}) $

1.Convert S to binary sequence G₁

2. $ \mathrm{J}={\mathrm{C}}_{\mathrm{n}}^{\mathrm{n}-\mathrm{k}+1} $/*J为算法所需的线索个数*/

3.For i ← 1 to J do

4.Generate a new random sequence k_i

5.G_i+1 ← G_i XOR k_i

6.End

7.k_J ← G_J

8. Co ← GetAllCombinations(n-k+1，U) /*GetAllCombination方法用于获得从全部影子秘密中挑出n-k+1个影子秘密的全部结果的集合，返回值Co为影子秘密的组合的List*/

9. For i ← 1 to J do

10. For q ← 1 to Co.Count do

11. Co[q].add(k_i)

12.End

13.End

将S转化为线索的方法并不唯一，本文采用图 4所示方法进行分散。将S转换为二进制序列G，随机生成一个等长的二进制序列K₁、G和K₁进行异或运算，将结果记为G₂。重复此步骤，每次生成的K与之前一次异或运算的结果进行异或运算。重复异或m－1次，保留最后一次异或的结果G_m-1和全部的K。S能且只能由这m条线索还原，缺少任意一条线索都会导致S无法还原。

恢复S的过程是分散S的逆过程。在获取到任意k个影子秘密全部信息的前提下，按照分散的逆序，依次异或运算还原G：G_m-1 XOR k_m-1 XOR k_m-2 XOR…XOR k₁ = G。当获取的影子秘密个数不及k时，至少一个线索缺失，S无法还原。

3 安全性证明

对本文算法进行安全建模，如图 5所示，安全目标如下：

1) 被攻破的服务器数量少于k时，原秘密信息仍维持保密。攻击者必须攻破至少k台服务器才能获取到原秘密信息。

2) 原秘密信息可被长期安全存储。一定时间后已经泄露的少量信息将失去价值。

以(2，3)秘密共享为例，假设攻击者试图获取秘密信息S，必须渗透2台存储影子秘密服务器，设法获取到每台服务器上的全部影子秘密的信息，理论上S才有泄露的可能性。由于单个影子秘密和原秘密信息S没有任何逻辑上的联系，即使1台服务器中的影子秘密的信息全部被窃取，理论上原秘密S仍然维持保密状态，攻击者无法根据现有信息推测出任何原机密信息S的内容。

算法的安全性依赖于可信第三方以及安全的信道。可信第三方可定期重新运行算法对现存影子秘密进行更新，由于算法基于随机二进制的生成而构建，每次更新后影子秘密与更新前影子秘密不存在联系，因此加大了攻击者获取S的难度，解决了多次部分影子秘密信息的泄露导致S泄露的问题，从而使秘密信息长时间存储的安全性得到保证。

4 实验与结果分析

Crypto++是基于C++语言实现的加密算法库，库中实现了SHAMIR秘密共享算法^[1]。由于Crypto++加密库和SHAMIR的秘密共享算法均被广泛使用，因此将本文算法与Crypto++所实现的SHAMIR算法进行对比，完成速度方面的性能评估。

在相同的实验环境下，通过对一个大小为10 MB的文件进行(3，4)秘密共享算法的处理，分别记录2种方法加密和还原过程的耗时。多次实验后，取平均耗时进行对比。实验环境设定为：操作系统为Windows 10 Professional Edition，处理器为Intel I7-4700HQ 2.40 GHz。本文算法和SHAMIR算法的处理耗时和还原耗时数据如表 2所示。实验数据表明，无论加密或者恢复，本文算法处理效率都明显优于SHAMIR秘密共享算法。相较于SHAMIR算法最后生成的影子秘密体积10 MB，本文算法所储存的影子秘密体积更大，为30 MB，因此，本文算法对于运行内存和存储内存的要求较SHAMIR算法更高。

通过以下3个方面对算法进行评估：1)是否能实现任意份额的(k，n)秘密共享；2)高效性；3)算法实现的难易程度。如果一个算法能够实现任意份额的(k，n)秘密共享，则称该算法是通用的；如果一个算法的实现原理易于理解，生产中易于实现和维护，则认为该算法是易于实现的。

将本文算法与SHAMIR算法和MATSUO算法^[4]进行对比，如表 3所示。由于都实现了任意份额的秘密共享，因此这3种算法都是通用的。由于SHAMIR算法涉及大量多项式计算，因此整体较为复杂，处理速度较慢，且难以实现。MATSUO算法亦是基于异或运算构建，数据处理速度较快，但是当k和n的值改变时，其算法的实现原理也有较大改变，因此，MATSUO算法整体上是难以实现的，并且该算法在部分影子秘密的信息泄露时，虽然不会导致原秘密信息整体泄露，但可能会导致部分秘密信息泄露。而本文算法不存在此类安全隐患，其不仅可实现任意(k，n)秘密共享算法，而是更易于实现和高效的。

5 结束语

本文提出一种基于异或运算的秘密共享算法。通过连续的异或运算生成算法所需的所有线索，并通过排列组合将这些线索进行合理分组。该算法不仅能够实现任意份额的秘密共享，而且还具有极快的运算速度。与SHAMIR算法相比，其对同一秘密信息分别多次加密解密的平均耗时大幅减少。但本文算法存在影子秘密体积过大的问题，单个影子秘密与原秘密的体积比值大于1。而在实际应用中，对运行算法的机器运行内存和对存储影子秘密的机器的存储空间要求较高。下一步将寻找更理想的将秘密分散为线索的方法，通过减小每个线索体积的方式缩小影子秘密的体积。