适用于任意接入结构的可验证多秘密分享方案.doc

2007 年 11 月Journal on CommunicationsNovember 2007 第 28 卷第 11 期通 信 学 报Vol 28 No 11 适用于任意接入结构的可验证多秘密分享方案 张福泰 1 王育民2 1 南京师范大学 数学与计算机科学学院 江苏 南京 210097 2 西安电子科技大学 ISN 国家重点实验室 陕西 西安 710071 摘 要 对一般接入结构上的可验证多秘密分享进行了研究 给出了可适用于任意接入结构的一类可验证多秘 密分享方案的构造方法 用这种方法构造的可验证多秘密分享方案具有以下性质 可在一组分享者中同时分享 多个秘密 分发者发送给每一分享者的秘密份额都是可公开验证的 关于每一秘密的公开信息也是可公开验证 的 恢复秘密时可防止分享者提供假的份额 分析表明 用此方法构造的可验证多秘密分享方案不仅是安全的 而且是高效的 关键词 秘密分享 接入结构 可验证秘密分享 多秘密分享 RSA 公钥体制 中图分类号 TN918 4 文献标识码 A 文章编号 1000 436X 2007 11 0059 06 Verifiable multi secret sharing schemes applicable to arbitrary access structures ZHANG Fu tai1 WANG Yu min2 1 College of Mathematics and Computer Science Nanjing Normal University Nanjing 210097 China 2 Key Lab of ISN Xidian University Xi an 710071 China Abstract Verifiable multi secret sharing on general access structures was studied A method of construct verifiable secret sharing schemes with arbitrary access structure was given The verifiable multi secret sharing schemes constructed by this method have the following properties multiple secrets can be shared at the same time in a group of shareholders The secret shares sent to shareholders are publicly verifiable The public information with respect to each shared secret is publicly verifiable And the supply of false shares in the process of secret recovery can be prevented Analysis shows that the verifiable multi secret sharing schemes constructed by our method are not only secure but also efficient Key words ecret sharing access structure verifiable secret sharing multi secret sharing RSA public key cryptosystem 1 引言 秘密分享是信息安全和数据保密中的重要手 段 它在重要信息和秘密数据的安全保存中起着 非常关键的作用 秘密分享的概念最早是由 Shamir 1 和 Blakley 2 于 1979 年提出的 它是指将 秘密 s 分割成若干个份额 share 或小块 piece 或 影子 shadow 在一组分享者 H H1 H2 Hn 收稿日期 2005 05 17 修回日期 2007 08 20 基金项目 国家自然科学基金资助项目 60673070 江苏省自然科学基金资助项目 BK2006217 西安电子科技大学教育 部计算机网络与信息安全重点实验室开放课题资助项目 20040105 Foundation Items The National Natural Science Foundation of China 60673070 The Natural Science Foundation of Jiangsu Province BK2006217 The Open Project of Key Lab on Computer Networks and Information Security of Ministry of Education of China Xidian University 20040105 60 通 信 学 报第 28 卷 中进行分配 使得每一个分享者都得到关于秘密 s 的一个秘密份额 而只有 H 的一些特定的子集 称 为合格子集 才能有效地恢复 s 而 H 的其他子集 不能有效地恢复秘密 s 甚至得不到关于秘密 s 的 任何有用信息 一个秘密分享系统涉及秘密分发者 dealer D 分享者 shareholders 或参与者 participants 的 集合 H 及 H 上的一个单调接入结构 monotone access structure 合格子集的集合 包括 2 个算 法 分配算法和恢复算法 分享者集合给出参与 秘密分享的人员 接入结构 指出哪些分享者可 一起恢复秘密 具有性质 若 A 且 A B 则 B 称接入结构 中的 H 的子集为 合格子集 按包含关系而言 中的极小元称为 最小合格子集 由它的极小元的集合 0惟一 确定 我们称 0为 的基 多秘密分享 3 4 是指在同一组分享者中同时分 享多个秘密信息 早期的多秘密分享方案存在着 效率低及不能抵抗分发者或分享者欺骗等弱点 为解决效率低的问题 Laith 等人于 1989 年提出 了动态秘密分享的概念 5 Sun H M 和 Shieh S P 6 Hwang S J Chang C C 和 Yang W P 7 分别提出了 一些能够提供计算安全性的动态门限秘密分享方 案 通常的秘密分享方案 包括动态秘密分享方 案在内 在安全性方面 都附加了秘密分发者和 分享者是诚实的假设 然而 这样的假设在现实 世界中往往是不切实际的 Chor 等人于 1985 年提 出了可验证秘密分享 VSS 的概念 8 用以解决秘密 分发者欺骗的问题 在已经提出的一些可验证秘 密分享方案中 也提供了防止分享者欺骗的功能 9 由于可防止分享者欺骗的可验证秘密分享方案有 良好的安全性质 它在诸如保密通信 多方安全 计算 10 及电子商务等方面有着广泛的应用 已经提出的可验证秘密分享方案大多为门限 方案 由于门限接入结构仅是单调接入结构中的 一种极为特殊的情况 它在无形中增加了各分享 者具有完全平等的地位 权利和可靠性的假设 但在现实世界中 这样的假设往往难以得到满足 因此 对具有更广泛的适用性的一般接入结构上 的秘密分享和可验证秘密分享的研究不仅具有重 要的理论意义 而且具有重要的现实意义 目前 对一般接入结构上的秘密分享 广义秘密分享 的研 究已经取得了丰富的成果 然而对一般接入结构 上的可验证秘密分享 广义 VSS 的研究却显得很薄 弱 在现有文献中仅有 9 11 涉及到了广义可验证秘 密分享 而对一般接入结构上的可验证多秘密分 享的研究在现有文献中还见不到 Gennaro 在文献 11 中首先指出了研究广义可验证秘密分享的重要 性 而后给出了 2 个交互式的广义 VSS 方案 这 2 个广义 VSS 方案虽然有较好的安全性 但由于 它们是交互式的 而且需要各分享者保存的秘密 信息的量非常大 同时还使用了效率极低的分割 选择技术 因而效率很低 实用性不强 Stadler 在文献 9 中给出了一个具有一般接入结构的可公 开验证的秘密分享方案 但在其方案中 属于多 个最小合格子集的分享者必须持有多个秘密份额 因而既不适用于大的接入结构 也不适用于同时 在一组分享者中分享多个秘密 Lin T Y 和 Wu T C 在文献 12 中给出了一个 t n 门限可验证多秘密 分享方案 但在其方案中 由于秘密的分发者没 有对要分享的秘密做出任何形式的承诺 任何人 包括分享者在内 都无法验证分发者所公布的相应 于各秘密的公开信息是否正确 这一缺陷将会给 不诚实的分发者带来可趁之机 使他有可能公布 假的公开信息以欺骗分享者 例如 当要分享的 某一秘密是分享者的集合解密被加密了的重要信 息的密钥时 分发者提供的假的公开信息将使任 何分享者都无法获得正确的解密密钥 这样的后 果是非常严重的 本文将对基于一般接入结构的可验证多秘密 分享进行研究 将给出一种构造可适用于任意接 入结构的可验证多秘密分享方案的方法 用此方 法构造的分享方案具有以下几方面的特点 能在 一组分享者中同时分享多个秘密 分发者发送给 每一分享者的秘密份额都是可公开验证的 关于 每一秘密的公开信息也是可公开验证的 恢复秘 密时可防止分享者提供假的份额 分析表明 用 此方法构造的可验证多秘密分享方案不仅是安全 的 而且是高效的 2 可适用于任意接入结构的可验证多秘密 分享体制 2 1 系统参数生成 分发者 D 先创建一个公开的广告栏 NB 用于 存放系统的公开参数及用于份额验证和恢复秘密 第 11 期张福泰等 适用于任意接入结构的可验证多秘密分享方案 61 所需的公开信息 系统中的任何分享者都可获取 NB 中的信息 但只有 D 才能修改和更新 NB 中的 内容 D 生成 2 个大的强素数 p q 二进制长度至少 512bit p 2p 1 q 2q 1 p q 亦是大素数 计算 RSA 公钥体制的参数 模 N pq 公钥 e 私 钥 d 计算 R p q 随机选取 ZN 中的 R 阶元素 g 之后 D 把 N g e 公布于 NB 中 把 d R 秘 密保存起来 2 2 秘密份额的生成 设 S s1 s2 sm 是要在分享者 H1 H2 Hn 中分享的秘密的集合 是 H H1 H2 Hn 上 的单调接入结构 0 A1 A2 At 是 的基 D 在 NB 中依次公布最小合格子集 A1 A2 At 并对每一分享者 Hj计算一个相 应的身份信息 IDj j 1 2 n 再计算一个 IDn 1 使得当 j k 1 2 n 1 且 j k 时 有 IDj IDk ZR 把这些 IDj也依次公布于 NB 中 D 随机生成 ZR上的一个 n 次多项式 f x a0 a1x anxn 其中每一 aj ZR j 1 2 n an 0 并计算 V v0 v1 vn 其中 vk mod N k 0 1 n 向量 V 决定了 f x 的 k a g 系数 从而惟一确定了 f x 但由于计算离散对数 问题的困难性 要从 V 计算出 f x 甚至 f x 的任何 一个系数 是不可行的 这样公开 V 就相当于把 f x 固 定下来了 但并不会泄露对 f x 的任何一个系数 我们把这样的向量 V 称为是对 f x 的系数的一个承 诺向量 D 把 V 公布于 NB 中 之后计算 pj xj f IDj pj 1 mod R jk HHH kj IDID yj mod N j x g 对每一个最小合格子集 Aj Hj1 Hj2 Hjk 由 IDj1 f IDj1 IDj2 f IDj2 IDjk f IDjk 及 0 a0 共 k 1 个点用拉格朗日插值公式确定出一 个 k 次多项式 fj x 并计算出 fj IDn 1 的值 再把 xj 秘密地发送给 Hj 并把 yj j 1 2 n 及 fj IDn 1 j 1 2 t 依次公布于 NB 中 在收到 xj 后 Hj可通过 yj mod N 检验 xj的有效性 j x g 而其他任何人可通过下式来检验 xj的有效性 mod N 1 j p j y k j ID n k k v 0 当 是 m n 门限接入结构时 f x 的次数可选 为 m 1 而使所有的 fi x f x 这时计算 fi x 及 fi IDn 1 的过程可省略掉 2 3 证书生成 相应于要分享的 m 个秘密 s1 s2 sm D 随 机选取 2 组互不相同的整数 r1 r2 rm ZR及 T1 T2 Tm ZN 然后对秘密 sj计算 mod N Cj sj mod N e jj st j dr g dr j j T Tjsj mod N hj mod 0 a jj hC 0 a jj uC e N 2 最后 D 把对 sj的证书 六元组 tj rj Tj Cj hj uj 公布于 NB j 1 2 m 任何人都可验证 D 公布的对每一秘密 sj的证 书的有效性 这只需检验下述的等式是否成立即 可 mod N 3 j r j e j gtC 1 j er j T mod N 4 e jjj Ttu 2 4 秘密的恢复 设 A 是 H 的一个合格子集 最小合格子集 Aj A A 中成员要合作恢复秘密 sl Aj中成员首先 从 NB 中得到关于 sl 的证书 tl rl Tl Cl hl ul 经 验证有效后 Aj中的每一 Hi计算 Ali mod N Bli mod N Qli tl mod N i x l T i x l C i x 并把 Ali Bli Qli 通过安全信道秘密地发给 A 中其他成员 称 Ali Bli Qli 为 Hi 关于秘密 sl 的 实际份额 A 中每一成员通过 Qli Ali mod N e li B lr i y 1 l er 检验 Hi关于秘密 sl的实际份额 Ali Bli Qli 的有效 性 当 Aj中所有成员关于秘密 sl 的实际份额都被 检验为有效时 即可通过下式来恢复出秘密 sl sl mod N 其中 l w AH li z ll hBCT i ji j 1 wi ijk HAH k ID k AHH i IDID ji zj fj IDn 1 1 1 k AH nk IDIDID jk 3 可行性及安全性分析 假定分发者 D 所采用的 RSA 公钥体制是安全 62 通 信 学 报第 28 卷 的 在 ZN 中计算以 g 为底的离散对数是困难的 对于用我们的方法构造的可验证多秘密分享方案 的可行性与安全性 分析结果如下 命题 1 在上述秘密分享方案中 任何人都可 验证分发者D 发送给每一分享者的秘密份额的正确 性 证明 对任意的分享者 Hj 如果 D 发送给他 的秘密份额 xj是正确的 则应有 xj f IDj pj 1 mod R 且 f IDj a0 a1 IDj a2 IDj 2 an IDj n mod R 于是 mod N k j k jjj ID n k a IDfxp ggg 0 由公开信息 yj mod N 及 vk mod N j x g k a g k 0 1 n 可知 mod N n k ID k p j k j j vy 0 即满足验证等式 1 因此任何人可通过式 1 检验 xj的有效性 命题 2 对要分享的任何秘密 sj 在选定 rj Tj 的情况下 分发者要伪造一个证书以图通过证书 验证是困难的 证明 对要分享的任何秘密 sj 分发者伪造 rj Tj是无意义的 由于 Cj必须满足式 3 Cj tj mod N e j r g 1 j er j T 于是必须有 Cj sjop mod N j dr g 因此分发者无法伪造 Cj 显然 在选定Tj的情况下 根据式 4 mod N 是无法伪造的 对于hj 由于它 e j e jj sTu 必须满足 2 式 uj hj mod N 因而只能有 0 a j C e hj ujd Tjsj mod N 0 a j C 0 a j C 从而分发者无法伪造 hj 综合以上分析 对要分享的任何秘密 sj 分发 者都无法伪造一个能通过验证的证书 命题 3 秘密 sj的证书不会泄露关于 sj的任何 有用信息 证明 由 Cj sj mod N 知 sj Cj j dr g dr j j T mod N 由于 d 是分发者的私钥 j dr g j rd j T 其他任何人都无法得知 因而 Cj不会泄露关于 sj 的任何有用信息 由 Tjsj mod N 可知 0 a jj hC sj mod N 但除了分发者 D 0 1 j a jj hCT 外 任何人都不知道 因此 hj也不会泄露有关 0 a sj的任何有用信息 既是把 Cj sj mod j dr g dr j j T N 和 hj Tjsj mod N 结合起来 由于不知 0 a j C 道 d 和 仍然不能得到关于 sj的任何有用信息 0 a 命题 4 在恢复秘密时 对任何分享者来说 要伪造能通过检验的假的实际份额是困难的 证明 在恢复秘密 sl时 对任何分享者 Hi来 说 他提供给其他合作者的实际份额 Ali Bli Qli 应 满足 Bli Qli Ali mod N e lr i y 1 l er 上式等价于 Bli Qli d Ali mod N 5 l dr i y drl 由于 Hi不知道 d 他要伪造出满足式 5 的 Ali Bli Qli 是困难的 命题 5 设含有最小合格子集 Aj的某合格子 集要合作恢复秘密 sl 若最小合格子集 Aj中所有 成员关于秘密 sl的实际份额都被检验为有效 则 sl mod N l w AH li z ll hBCT ij ji j 1 其中 wij ijk HAH k ID k AHH i IDID ji zj fj IDn 1 1 1 k AH nk IDIDID jk 证明 由 hl Tlsl mod N 知 sl 0 a l C mod N 由拉格朗日插值公 0 1 l a ll hCT 式知 0 a ji AH ij IDf 1 k HAH ik IDIDID ijk fj IDn 1 1 1 k AH nk IDIDID jk ji AH i IDf 1 ki ik HHH IDID zj k HAH i AHH k IDIDID ijkjk 第 11 期张福泰等 适用于任意接入结构的可验证多秘密分享方案 63 zj mod R ji AH ijiw x 于是 sl hl 1 l T l C iijj HA ij x wz hl 1 l T ij i ji j w x AH l z l CC hl mod N 1 l T ij ji j w AH li z l BC 命题 6 在得不到任何最小合格子集的全体成 员的秘密份额或实际份额的前提下 任何非合格 子集中的全体分享者合作都无法恢复出任何秘密 sl 证明 对非合格子集而言 恢复秘密 sl有 2 种可能的途径 一是设法得到后由 sl 0 a mod N 计算出 sl 二是设法得到 0 1 l a ll hCT 某一最小合格子集的全体成员的实际份额后 从 sl mod N 计算出 sl l w AH li z ll hBCT ij ii j 1 由于是多项式 f x 及 fj x 的常数项 而每一 0 a 分享者 Hj只知道关于 f x 及 fj x 的公开信息 承诺 向量 V 及 fj IDn 1 和自己的秘密份额 xj f IDj pj 1 mod R 他连 f IDj 都无法得知 由于不知道 R 无 法计算出 pj 1 mod R 因此任意一组分享者合作 也不能得到除了公开信息外关于 f x 及 fj x 的其他 有用信息 因此任何非合格子集除了能得到关于 的公开信息 v0 mod N 外 得不到关于 0 a 0 a g 的任何其他有用信息 从而不能由 sl 0 a mod N 计算出 sl 由第二种方法 0 1 l a ll hCT 恢复秘密 必须得到某一最小合格子集的全体成 员的实际份额 在我们的假设下 这一点是办不 到的 因此任何非合格子集都不能恢复秘密 由上述几个命题可知 以我们的方法构造的 可验证多秘密分享方案是可行的 并且可抵抗分 发者和分享者欺骗 有效地克服了文献 11 中的方 案在安全性方面的缺陷 4 效率分析 为清楚起见 把用我们的方法构造的 t n 门 限方案在效率方面的主要数据与文献 7 中方案的 同类数据进行比较 表 1 给出两个方案在效率方 面 对每个分享者而言平均分享每个秘密所需的 主要数据 表 12 个方案的效率比较 方案 秘密份额的 数量及所需 模指数运算 次数 所需的公开信 息数量及计算 它们的模指数 运算次数 验证公开 信息所需 模指数运 算次数 计算 验证实 际份额及恢复 秘密所需模指 数运算次数 文献 7 中的 方案 1 t 13 1 n t 1 1 n 03t 2 我们的方案1 m t 1 m m 为秘 密的总数 1 t mn 6 n 1 t n 5 n 1 t m 4 n 4t 对我们方案效率的主要数据说明如下 分发 者可选 f x fj x j 1 2 并且 f x 的次数为 t n C t 1 这时不需要 IDn 1 也不需计算 fj IDn 1 因 此对每个分享者而言平均分享每个秘密所需的秘 密份额的数量为 1 所需的公开信息的数量为 1 t m 6 n 其中每个分享者有一个相应于秘密份 额的公开值 这需要 1 次模指数运算 n 个分享者 分享 m 个秘密所需的对 f x 的系数的检验向量 共 t 个分量 需要 t 次模指数运算 每一个秘密的证 书需 6 个数值 有 5 次模指数运算 每个分享者 验证对应于自己的秘密份额的公开值需 1 次模指 数运算 验证检验向量的正确性需 t 次模指数运算 验证每个秘密的证书需 4 次模指数运算 每一分 享者计算对应于每一秘密的实际份额需 3 次模指 数运算 验证实际份额的有效性每个分享者需做 3 t 1 次模指数运算 恢复秘密时每个分享者需做 t 次模指数运算 另外 文献 7 中的方案对要分享 的每个秘密 分发者都必须选择一个随机的 t 1 次 多项式和 n 个互不相同的随机整数 而这 n 个互 不相同的随机整数并不在公开信息之中 而在用 我们的方法构造的 t n 门限方案中 对要分享的 m 个秘密 分发者只需选一个随机的 t 1 次多项式 和 2m 个互不相同的随机整数 这 2m 个互不相同 的随机整数都出现在公开信息之中 由此及上述 对比数据可以看出 在 m 和 n 都比较大的情况下 用我们的方法构造的门限方案的效率比文献 7 中 方案的效率要高出许多 对一般接入结构上的可 验证秘密分享方案来说 以我们的方法构造的方 案的效率明显地高出文献 9 中方案的效率的许多 倍 5 结束语 能防止分发者和分享者欺骗的可验证秘密分 64 通 信 学 报第 28 卷 享方案是较为合理和实用的秘密分享方案 它们 在重要信息的安全保存以及多方安全计算等多个 方面都有着广泛的应用 因此对安全高效的可验 证秘密分享方案的构造方法的研究具有重要意义 在现实中可能有许多场合需要具有一般接入结构 的可验证多秘密分享方案 如一个公司的董事会 需要把公司的一些商业秘密在董事会成员中进行 分享 而董事会中各成员并不拥有完全平等的地 位 权利及可靠性 因此使用门限多秘密分享方 案是不合适的 因而具有某种非门限接入结构的 可验证多秘密分享方案就成为必然的选择 由于 现有文献中对一般接入结构上的可验证多秘密分 享的研究还见不到 这使可验证秘密分享的应用 范围在一定程度上受到了限制 本文探索了能适 应于任意接入结构的可验证多秘密分享方案的构 造方法 我们给出了具有广泛的适应性的一种构 造方法 分析表明 用我们的方法构造的可验证 多秘密分享方案具有很好的安全性 具有防止秘 密的分发者和分享者欺骗的功能 与现有的一般 接入结构上的可验证秘密分享方案和一些多秘密 分享方案相比 效率更高 实用性更强 参考文献 1 SHAMIR A How to share a secret J Communications of the ACM 1979 22 11 612 613 2 BLAKELY G R Safeguarding cryptographic keys A Proceedings of the AFIPS 1979 National Computer Conference C New York USA 1979 313 317 3 JACKSON W A MARTIN K M O KEEFE M Multisecret threshold schemes A Advances in cryptology CRYPTO 93 C Santa Barbara California USA LNCS 773 Springer Verlag Berlin 1993 126 135 4 HE J DAWSON E Multisecret sharing scheme based on one way function J Electronics Letters 1995 31 2 93 95 5 LAIH C HARN L LEE J et al Dynamic threshold scheme based on the definition of cross productin an N dimensional linear space A Proceedings of Crypto 89 C Santa Barbara California USA LNCS 435 Springer Verlag Berlin 1990 20 24 6 SUN H M SHIEH S P Construction of dynamic threshold schemes J E