Traceable Secret Sharing: Strong Security and Efficient Constructions

. Suppose Alice uses a t -out-of- n secret sharing to store her secret key on n servers. Her secret key is protected as long as t of them do not collude. However, what if a less-than-t subset of the servers decides to offer the shares they have for sale? In this case, Alice should be able to hold them accountable, or else nothing prevents them from selling her shares. With this motivation in mind, Goyal, Song, and Srinivasan (CRYPTO 21) introduced the concept of traceable secret sharing . In such schemes, it is possible to provably trace the leaked secret shares back to the servers who leaked them. Goyal et al. presented the first construction of a traceable secret sharing scheme. However, secret shares in their construction are quadratic in the secret size, and their tracing algorithm is quite involved as it relies on Goldreich-Levin decoding. In this work, we put forth new definitions and practical constructions for traceable secret sharing. In our model, some f < t servers output a reconstruction box R that may arbitrarily depend on their shares. Given additional t − f shares, R reconstructs and outputs the secret. The task is to trace R back to the corrupted servers given black-box access to R . Unlike Goyal et al., we do not assume that the tracing algorithm has any information on how the corrupted servers constructed R from the shares in their possession. We then present two very efficient constructions of traceable secret sharing based on two classic secret sharing schemes. In both of our schemes, shares are only twice as large as the secret, improving over the quadratic overhead of Goyal et al. Our first scheme is obtained by presenting a new practical tracing algorithm for the widely-used Shamir secret sharing scheme. Our second construction is based on an extension of Blakley’s secret sharing scheme. Tracing in this scheme is optimally efficient, and requires just one successful query to R . We believe that our constructions are an important step towards bringing traceable secret-sharing schemes to practice. This work also raises several interesting open problems that we describe in the paper.

假设爱丽丝使用一个(n,t)门限秘密共享方案将她的密钥存储在n个服务器上。只要其中t个服务器不勾结，她的密钥就是受保护的。然而，如果少于t个服务器的子集决定出售它们所拥有的份额会怎样呢？在这种情况下，爱丽丝应该能够追究它们的责任，否则就没有什么能阻止它们出售她的份额。基于这种动机，戈亚尔、宋和斯里尼瓦桑（密码学2021）引入了可追踪秘密共享的概念。在这样的方案中，可以有根据地将泄露的秘密份额追溯到泄露它们的服务器。戈亚尔等人提出了可追踪秘密共享方案的第一个构造。然而，他们构造中的秘密份额在秘密大小上是二次的，并且他们的追踪算法相当复杂，因为它依赖于戈德里奇 - 莱文解码。在这项工作中，我们提出了可追踪秘密共享的新定义和实用构造。在我们的模型中，一些f < t的服务器输出一个重构盒R，它可能任意地依赖于它们的份额。给定另外的t - f个份额，R重构并输出秘密。任务是在对R进行黑盒访问的情况下将R追溯到被破坏的服务器。与戈亚尔等人不同，我们不假设追踪算法拥有关于被破坏的服务器如何从它们所拥有的份额构造R的任何信息。然后我们基于两个经典的秘密共享方案提出了两个非常高效的可追踪秘密共享构造。在我们的两个方案中，份额仅为秘密的两倍大，相比戈亚尔等人的二次开销有所改进。我们的第一个方案是通过为广泛使用的沙米尔秘密共享方案提出一种新的实用追踪算法而得到的。我们的第二个构造基于布莱克利秘密共享方案的一个扩展。这个方案中的追踪是最优高效的，只需要对R进行一次成功查询。我们相信我们的构造是将可追踪秘密共享方案付诸实践的重要一步。这项工作还提出了几个我们在论文中描述的有趣的开放问题。