匿名用户Shamir提出的基于Reed–Solomon编码的秘密共享方案，能够抵御排列、插入和删除等攻击

《IEEE Transactions on Information Theory》：Anonymous Shamir’s Secret-Sharing via Reed–Solomon Codes Against Permutations, Insertions, and Deletions

研究Reed-Solomon码对抗置换后插删攻击的性能，构建首个同时满足匿名性及完美重建的间隙阈值秘密共享方案。摘要：

　　

摘要：

在这项研究中，我们探讨了Reed-Solomon码在面对以下对手时的性能：该对手首先对码字符号进行排列，然后进行插入和删除操作。这种对抗模型的提出是基于最近对完全匿名秘密共享方案的兴趣。一个完全匿名的秘密共享方案具有两个关键特性：首先，在秘密被重构之前，参与者的身份不会被暴露；其次，任何未经授权的参与者组合所获得的份额都是均匀且独立的。具体来说，任何未经授权的子集所获得的份额都不会透露持有这些份额的参与者的身份。我们首先观察到，当Reed-Solomon码能够抵抗对手对码字进行排列并随后删除符号的攻击时，可以用来构建完全匿名的间隙阈值秘密共享方案。接着我们证明了，存在[n,k]种Reed-Solomon码（在足够大的域上），它们能够抵抗对手对排列后的码字进行n?2k+1次插入和删除操作。这意味着存在一个(k?1,2k?1,n)间隙阈值秘密共享方案，它是完全匿名的。也就是说，任何k?1个份额都不会透露秘密的任何信息，也不会暴露参与者的身份。相反，任何2k?1个份额就足以重构秘密，而不会暴露参与者的身份。我们还基于之前关于能够纠正插入和删除操作的Reed-Solomon码的研究，提供了这类方案的明确构造方法。这里提出的构造方法是首批同时实现最强匿名性和完美重构能力的间隙阈值秘密共享方案。

引言

Reed-Solomon（RS）码是一类重要的纠错码，在确保各种通信和存储系统中的数据完整性方面发挥着重要作用。这些码开发于20世纪60年代[3]，在纠正多个符号错误方面特别有效，因此非常适合数据传输和存储。具体应用包括分布式存储系统、二维码以及通过噪声信道的数据传输。这些码的普及归功于它们优美的代数结构，这种结构使我们能够在存在替换和擦除的情况下高效地进行编码和解码。