International Association
for Cryptologic Research

This paper introduces the notion of timed secret sharing (TSS), which establishes lower and upper time bounds for secret reconstruction in a threshold secret sharing scheme. Such time bounds are particularly useful in scenarios where an early or late reconstruction of a secret matters. We propose several new constructions that offer different security properties and show how they can be instantiated efficiently using novel techniques. We highlight how our ideas can be used to break the public goods game, which is an issue inherent to threshold secret sharing-based systems, without relying on incentive mechanism. We achieve this through an upper time bound that can be implemented either via short-lived proofs, or the gradual release of additional shares, establishing a trade-off between time and fault tolerance. The latter independently provides robustness in the event of dropout by some portion of shareholders.

We present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share f+1 secrets with a total communication complexity of O(λn^2) words, where λ is the security parameter and n is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses O(λn^3) expected words and constant expected time, which we in turn use to construct an adaptively secure high-threshold asynchronous distributed key generation (ADKG) protocol that uses O(λn^3) expected words and constant expected time. To the best of our knowledge, our ADKG is the first to allow for an adaptive adversary while matching the asymptotic complexity of the best known static ADKGs.

In this paper we introduce a distributed key generation (DKG) protocol with aggregatable and publicly verifiable transcripts. As compared with prior approaches, our DKG reduces the size of the final transcript and the time to verify it from O(n^2) to O(n), where n denotes the number of parties. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. Finally, we experimentally evaluate our DKG and show that the per-party overheads scale linearly and are practical: for 64 parties it takes 71ms to share and 359ms to verify the overall transcript, while these respective costs for 8192 parties are 8s and 42.2s.

The Sponge function is known to achieve $$2^{c/2}$$ 2 c / 2 security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a $$\min \{2^{c/2},2^\kappa \}$$ min { 2 c / 2 , 2 κ } security bound, with $$\kappa $$ κ the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical $$2^{c/2}$$ 2 c / 2 security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of $$\min \{2^{b/2},2^c,2^\kappa \}$$ min { 2 b / 2 , 2 c , 2 κ } , with $$b>c$$ b > c the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity $$2^{c/2}$$ 2 c / 2 , therewith demonstrating that the techniques cannot be applied to APE.