鼓励合作秘密分享方案的概念与构建_程小刚.pdf

第 卷第期华 侨 大 学 学 报（自 然 科 学 版）年月 （）：鼓励合作秘密分享方案的概念与构建程小刚，郭韧，卢正添，周长利，陈永红，（华侨大学 计算机科学与技术学院，福建 厦门 ；华侨大学 厦门市数据安全与区块链技术重点实验室，福建 厦门 ；华侨大学 工商管理学院，福建 泉州 ）摘要：提出一种新的鼓励合作秘密分享方案的概念，即参与秘密重建的成员越多，则重建过程越简单、计算量越小；若有少数成员缺席重建秘密过程，则秘密重建仍然是可能的，只是计算量有所增加，即重建计算工作量随缺席成员的个数指数级增加，而成功概率指数级降低基于区块链中的工作量证明（）和哈希函数碰撞方法，构建一个具体可行的方案 通过随机预言模型（）证明了所提方案的安全性关键词：秘密分享；哈希函数；区块链；比特币；计算复杂度中图分类号：文献标志码：文章编号：（），（，；，；，）：，（），（）：；秘密分享是指秘密分发者（）可以把一个秘密值分成多份，分别传输给不同的参与方，全部或部分满足预先设定好条件的参与方集合（访问结构）就能恢复秘密，而不满足条件的参与方集合则不能恢复秘密 如果不能恢复，甚至不能获得任何关于秘密的信息，则称为完美秘密分享方案常用的（，）秘密分享是指个参与方中如有方以上参与秘密重建，则可以重建秘密；若参与重建秘密的人数不足个，则不能获得关于秘密的任何信息 基于多项式的拉格朗日差值公式，收稿日期：通信作者：程小刚（），男，讲师，博士，主要从事信息安全、应用密码学的研究 ：基金项目：福建省社会科学基金资助项目（，）：构建了第一个且最重要的（，）完美秘密分享方案其他的实现方式还有基于几何的秘密分享方案、基于中国剩余定理的（，）秘密分享方案等 秘密分享方案有很多变种，如支持不同的访问结构、可验证秘密分享（）、对量子比特进行分享的量子秘密分享（）方案、支持越多人参与可减少通讯复杂度的 方案、混合式秘密分享、阈值可调秘密分享方案、理性秘密分享（）、量子理性秘密分享 、主动安全秘密分享（）等在区块链技术 中，多参与方以分布式方式共同维护一个记录账本，在没有一个中心可信任方的情况下，确保记录的唯一性，其典型应用是为比特币（）维护一个交易账本，用计算难度大的数学难题的解决，证明某个交易的合法性 常用的数学难题就是哈希（）函数的碰撞 近年来，区块链技术在隐私保护、智能家居、共识协议、智能合约等方面都有广泛的研究和应用 的秘密分享方案特性是只要参与重建秘密的人数大于阈值即可，更多的人参与不能带来任何益处，甚至可能使重建工作量更大，因为重建次多项式只要个点即可 基于此，本文提出一种新的鼓励合作秘密分享方案初步知识定义鼓励合作多方秘密分享方案如下秘密分发者 可将秘密分成份，分别分给个参与方：若有方都参与秘密重建过程，则可高效恢复秘密并验证秘密的正确性；若有方缺席秘密重建过程，如果想重建秘密，则要花费较多的计算量且成功概率稍低；一般地，如果有方缺席重建过程，若要重建秘密，花费的计算工作量随指数级增长或成功概率随指数级降低区块链中，共识机制是在分布式环境下多方能达成一致意见的机制，在 的应用中是让各方都同意和维护一个唯一的交易账本，从而防止货币的重复使用问题基于工作量证明（）的共识机制是通过计算能力来保证达成共识，即只要网络中诚实的参与者（矿工）计算力大于攻击者，就可以保证交易账本的唯一性，保证 的正常运行计算力主要是通过 函数（如 ）的碰撞实现，如要求找到一个随机数，使得交易数据与此随机数的哈希结果前面若干位必须为在基于区块链的加密货币 中，挖矿的目的就是找到 值符合一定条件（如前若干位为）的原像作为工作量证明，奖励系统分配给发现 碰撞的矿工若干比特币进行激励，从而保证系统的正常运行借鉴 ，把符合条件的 函数值作为秘密，参与人的秘密为原像，全部都参与，则有原像，可简单构建出作为秘密的 值，而缺方或多方的话，则原像不完整，必须对缺少的部分原像进行猜测，才能构建秘密显然，缺少的秘密越多，则要随机猜测的比特数越多，工作量也就越大鼓励合作秘密分享方案的构建 初始构建秘密分享的步骤如下）若有方参与秘密分享，那么，就要为每一方生成比特的随机信息，即，每个的长度都为比特）对这些数据进行 运算，（，）.那么，得到的 值的指定部分比特（如后 比特）就是要共享的秘密，而其他部分（如前 比特）是作为验证的比特，即可验证重构出来的秘密是否正确；此时，共享的秘密显然是随机值，若希望共享一预先给定的值，则可以将此随机值作为对称加密方案（如 ）的秘钥来加密给定值，重建秘密时只需重建出共享的随机值（即秘钥），再进行解密即可）把，分别传送给参与秘密分享的方作为他们的秘密值，同时传送作为验证的那部分（如前 比特）值比特重建秘密的步骤如下）如果参与秘密分享的方都参与重建，那么，重构过程非常简单，只要计算 值，即第期程小刚，等：鼓励合作秘密分享方案的概念与构建 ：（，）.）验证 把 中的指定部分（如前 比特）同公开的验证比特进行比较，如果相同，那么剩下的部分就是重建出来的秘密；如果不同，就说明成员中有一部分是恶意的，即没有贡献出真正的秘密，或者不是参与方之一）缺方 如果缺方，不失一般性地，假设缺席的是第个参与方（即），则前个参与方也可尝试重构秘密，即对每个可能的值计算 值，如果某个 值的指定部分同公开验证比特相同，那么，高概率剩下的部分就是秘密，计算代价为（），其中，为个参与方从 处获得的分享（）的比特长度）缺方、多方如果缺席是方，那么，计算代价为（）；一般地，若缺席方，那么，计算代价为（），计算代价随着缺席的人数指数级上升；若（即缺失的比特数大于 函数的输出长度），那么，会有原像冲突，即个 值可能对应多个原像，则平均每个 值有个原像，猜测成功的概率为（）上述分析其实不够精确，由于敌手可以直接盲目猜测作为秘密的那部分 比特，那么，计算代价就是固定的（），成功的概率为秘密长度 因此，可以通过加长秘密的长度来增强安全性 提高安全性的构建为避免上述的安全性问题，可考虑进行多次 ，把多个 函数输出值作为秘密，即在一次（，）的基础上，延长秘密包含（，），（，），（，），即加长了秘密的长度，可把（，）的部分或全部比特作为验证比特，后面的 值作为秘密值.此时，可根据需要设定的值，值越大，秘密越长.由于秘密的长度较大，直接盲目猜测的成功概率就大大降低，甚至可忽略不计.一个简单的示例选取一个简单的 函数（实际应用中，应该选取更安全的 函数，如 ）如下（，）上式中：为一素数；系数（，），为随机数.以方为例，令 ，（，）（，），则 函数为（，），则容易得到（，），（，）.基于此 函数可设计秘密分享方案如下随机选择，计算 值为（，）（）可设置要分享的秘密为后四位 ，而前四位 作为验证比特显然，当方都参与秘密重建时，只需方各自提供自己的部分，进行一次 运算即可，并可用得到的 值前四位同 比较，若相同，则剩下四位即为重建的秘密 ；若不同，则重建失败，说明有用户提供了假的秘密部分若只用方参与秘密重建，设参与方为，此方也可尝试重建秘密，即对，的每个值尝试计算 值，前四位为 的 值区间为 值满足前四位条件的原像与秘密值，如表所示由表可知：个 值都可能是秘密，因为其值的前四位都是 ，假如任选其中之一作为秘密，显然成功的概率为 符合条件的原像个数与成功概率，如表所示 类似地，假设只有方 想重建秘密，那么，可对，的每个可能值进行 运算，可知符合前四位条件的 值有 ，与理论估计值 非常接近，任选其中一组，重建成功概率为 ；若假设一个参与方都没有，成功的概率为 ，华 侨 大 学 学 报（自 然 科 学 版）年 ：与理论估计值 也非常接近，说明此 函数的输出随机性较好，即实现了计算量和成功概率随缺失方数指数级增加和降低表 值满足前四位条件的原像与秘密值 值二进制展开秘密（后四位）值二进制展开秘密（后四位）表符合条件的原像个数与成功概率 缺失方数计算量符合条件的原像个数理论估计值实际个数成功概率不缺 缺方 缺方 缺方 但上述的分析有问题，即如果敌手直接忽略各方的 ，直接瞎猜后四位，成功的概率也是，即此时多参与方并不能真正带来重建工作量的减少或成功概率的提高需要进行安全性的加强，即延长秘密的长度，降低盲目猜测的概率，促使敌手进行大量计算此时，秘密不只是上述 值的后四位，还包括（，），需要可继续加长秘密，包含（，），（，）等）.是另一个 函数，定义为（，）显然，（，）跟上述的 函数是一样的.同上，取，计算 值为（，），（，）.用（，）即 的前 比特 作为验证比特，而后四位和（，）作为秘密，此时秘密长度为 位；若敌手忽略，直接盲目猜测，那么，成功概率为，此时，敌手的理性选择是利用，对所有可能的进行 运算尝试，运算量为，成功概率是.二次 延长秘密长度，如表所示表中任何一行都是可能的秘密表二次 延长秘密长度 （，）二进制展开秘密（后四位）秘密（，）（，）二进制展开秘密（后四位）秘密（，）由表可知：（，）与（，）有简单的线性关系，即敌手可在盲目猜测（，）后加上 得到后八位，成功概率不变；然而，此处用的 函数很简单（线性运算），实际中第期程小刚，等：鼓励合作秘密分享方案的概念与构建 ：的 函数（如 ）采用的是比较复杂的非线性运算，即敌手盲目猜测（，）后，不会得到关于（，）的任何信息，只能先猜测原像，的值，再计算（，）和（，），直接猜测 值的成功率较低假设缺方，直接盲目猜测的成功概率为，此时秘密的长度为 位，对缺的方所有值进行 计算工作量为，可得到符合条件的 值约为（假设每个 值都是随机），即成功概率为，同盲目猜测概率相当；采取类似方法继续扩展秘密长度，把（，）也作为秘密，秘密长度为 ，盲目猜测的概率为，此时，敌手的理性选择为对所缺的方所有可能值进行尝试.在实际应用中，可根据具体情况调整秘密的长度，以确保重建的工作量满足设计要求，利用包含（，）技术增加秘密长度.安全性与参数分析上述方案的安全性主要是基于 函数的安全性，同 中的工作量证明 类似，持有原像，则可直接通过 运算得到 值，否则，只能随机尝试只要 函数是安全的，文中方案就是安全的，下面基于随机预言模型（）证明文中方案的安全性定理基于随机预言模型，鼓励合作秘密分享方案满足安全性性质，即计算量和成功概率随缺失方数分别指数级增长或指数级下降证明：设参与秘密重建的人数少人，即缺失的 原像位数为，对缺失的位的每一种可能进行尝试，计算量为，目标是找到 函数值的前 位（假设用于验证的比特位数为 位）满足给定值的缺失的位原像注意 下 有个性质性质在 中，获得 值的唯一方法是查询预言器 ，查询次就获得个对应的 值，内部如何运作是黑箱，不能被了解性质每次查询，返回的 值都是独立和随机的（要满足对同一个原像的查询返回的 值一致的条件）在这个性质下，不能快速求逆，因为其黑箱运作不能逆向工程破解，要找到符合条件的原像只能做随机尝试，即）当缺失的原像位数 时，重建的成功概率较高，而计算量随指数级增加，即；）当缺失的原像位数 时，重建成功的概率随指数级降低，约为 ，因为缺失的原像位数为（）时，对每个可能的原像（有个）求 值，会得到个 函数值（每个长度为 ），而所有可能的 函数值只有 个，在 函数是随机的假设下，每个 值对应的原像数量平均为 个，其中，只有个是真正的秘密，所以，成功的概率为 设每个人的秘密 为位、个参与人，函数的输入消息为位，若采用 哈希函数，则一个 输出为 位，平均每个输出对应的原像个数为 .假设把（，）的前 比特即 位作为验证比特，则后 比特为秘密比特，如果秘密长度不足，还可扩展秘密包括（，），（，），（，），此时，秘密长度为 比特.）当每方的分享长度 时，则缺方时需要尝试的次数为，计算量较大，假设每个 值都是随机的，那么，个随机 位 值有原像的概率为 ，即只要尝试缺失那方的每一个值，成功重建秘密的概率很高；失败只可能是符合 位验证比特的 值有多个，产生了冲突，即重建出的秘密有多个，不能分辨哪一个是正确的，只能随机选择此时，总共 个 值，每个 值符合条件（即前 位符合给定的验证比特）的概率为 ，则可能产生冲突（重建失败）