Eurocrypt 2024: Twinkle (A Fully Adaptive Threshold Signature from DDH)
Published:
This blog post is a mirror of this blogpost.
TL;DR: Twinkle [BLT+24] is a three-round threshold signature that supports adaptive corruption and has been proved under standard assumptions (DDH) without the need for rewinding. This construction builds on Sparkle from Crypto’23 [CKM23], which is adaptively unforgeable under the One-More Discrete Logarithm (OMDL) assumption, known as a strong and interactive assumption. However there are some recent adaptive threshold signatures over bilinear groups that are under standard assumptions [DR23, MMS+24], Twinkle operates over pairing-free curves. Instead of using a proof of knowledge of the secret key in its signature, like Sparkle, Twinkle uses a proof of well-formedness to avoid rewinding. By doing this, Twinkle achieves full adaptivity, allowing the adversary to corrupt up to \(t\) parties. This improves Sparkle, where this number is limited to \(t/2\). Twinkle also addresses a gap in the security of the Sparkle. Finally, to prove security under the DDH assumption, the authors extend the technique introduced by Tessaro and Zhu [TZ23], to turn the interactive one-more CDH assumption into the non-interactive DDH assumption.
We often sign documents for various reasons, such as agreeing to job contract conditions or confirming the delivery of a package. Similar to handwritten signatures, digital signatures, a well-known cryptographic technique, can associate a message with its author. The security of these systems ensures that only the party possessing the secret key can generate a valid signature. If the secret key is leaked, anyone can forge signatures and impersonate the victim.
Threshold signatures by sharing the secret key among multiple parties, i.e. signers, tolerate some fraction of corrupt signers. To sign a message, the cooperation of at least \(t+1\) parties is necessary. However, any number of partial signatures less than this threshold will fail to meet the verification conditions.
As a simple example, consider a student who has completed their academic program and is eligible to receive a university certificate. The university could form a threshold signing group including multiple authorized administrators or officials, such as the administration office, the dean, the head of the ICT division and so on. To issue a certificate, this group can collectively generate a threshold signature (TS) on the certificate. This signature is only considered valid if an quorum of administrators agree to sign.
A Threshold Signature (TS) is said to be interactive if the group of signers needs to interact during the signing phase. In contrast, a non-interactive TS doesn't require any interaction or pre-processing phase. Although the non-interactive TS appears more appropriate for practical applications, Twinkle operates over pairing-free curves and requires three rounds of communication.
A threshold signature is said secure, i.e. unforgeable, if nobody can produce a valid signature, even if t of the signers act maliciously. This concept was studied in depth by Bellare et al. [BCK+22]. They focused on multiple security notions for threshold signatures, specifically non-interactive ones. They introduced two key security notions for these signatures, labeled TS-UF-0 and TS-UF-1. The TS-UF-0 notion restricts the adversary from observing any partial signatures for the challenge message it is trying to forge. In contrast, the TS-UF-1 notion, which provides stronger security, allows the adversary to make partial signing queries up to (\(t −\) |# corrupted signers|) times on the challenge message. In Twinkle, the authors use (an interactive version) of the T-UF-0 notion, more precisely the adversary cannot see any partial signature on the challenge message.
Wrapping up our discussion on the security aspects of threshold signatures, lets briefly explain the difference between static and adaptive corruptions. A threshold signature is considered secure against static adversaries when the corrupted parties are declared at the start of the security game, before their verification keys are seen. However, in real-world scenarios, corruption often happens gradually, requiring protection against stronger adversaries — those capable of adaptive corruption. Here, adversaries can choose which signers to corrupt as the security game unfolds. This choice can be influenced by information gathered from observing public parameters and access to the partial signing oracle.
In Sparkle, the adversary can corrupt up to \(t/2\) and also it is proved under interactive assumption of OMDL. Twinkle has two main goals. The first is to allow the adversary to corrupt up to \(t\) parties. The second is to prove its security under standard and non-interactive assumptions, namely the DDH assumption. Let's briefly see how these two objectives are achieved.
In an (n, t)-Shamir Secret Sharing Scheme, a secret \(s \in \mathbb{Z}_p \) is shared among \(n\) parties. The dealer forms a random polynomial, \(f(x)\in \mathbb{Z}_p[X]\), of degree \(t\) where \(f(0)=s\). The dealer then evaluates \(f(x)\) on each shareholder's index and securely gives each shareholder \(s_i=f(i)\), where \(i \in [1,n]\). To reconstruct the secret, one can compute the Lagrange coefficients \(\lambda_i:=\Lambda_i(0)=\sum_{j \in S, j \neq i}{\dfrac{j}{j-1}}\), for a subset \(S \subseteq [1,n]\) and then combine them with the shares, i.e., \(s=f(0)=\sum_{i \in S}{s_i \lambda_i}\). A minimum of \(t+1\) polynomial evaluations are required due to the degree of the polynomial, and fewer than this threshold does not reveal any information about \(s\).
In below, we assume a key generation phase has been run and all parties have access to their shares, in other words, their secret keys. These keys can either be obtained by assuming a trusted dealer or they can be achieved via a Distributed Key Generation (DKG) protocol. For simplicity, like the authors, we assume a trusted dealer. However, this trust assumption can be relaxed by running a DKG protocol instead.
The signature in Sparkle is basically a proof of knowledge of the secret key. This proof is obtained after multiple rounds of communication among a quorum of signers.
In the security game, the challenger defines each party's public key using the OMDL experiments. To respond to the corruption oracle, the challenger uses the OMDL oracle to obtain the corrupted party's secret key.
If there is an adversary who can generate a valid forgery on a fresh, i.e., not queried before, the T-UF-0 challenger can potentially break the OMDL assumption, that is, having a high chance of returning \(f(0)\). To achieve this, the challenger needs to rewind the adversary, as the signature in Sparkle is proof of knowledge on the secret key.
To prevent rewinding, the authors of Twinkle use a different technique. They introduce an additional, message-dependent term, (pk’=H(m)^{sk}), where (H(.)) is a collision-resistant hash-to-curve function to the list of public keys. With this extra parameter, signers in Twinkle can prove the well-formedness of the following statement, instead of proving the knowledge of (sk).</p>
This new relation in the signature doesn't necessitate any rewinding. If the verification conditions for a frogary hold, the challenger can directly use it to break the CDH assumption. Conversely, because this is a sound proof, the adversary cannot pass the verification conditions if \(pk'\neq H(m^*)^{sk}\) for any challenge message \(m^*\).
We have discussed how the authors have managed to avoid rewinding and establish the security of their scheme under the CDH assumption, a standard non-interactive assumption. However, they have yet to cover the adaptive corruption of parties by an adversary and also grant the access to the singing oracle. Similar to the OMDL assumption, by adding the DLog oracle to the CDH assumption, the challenger can now respond to corruption queries adaptively for up to t parties. This modified assumption is referred to as the One-More CDH assumption, or OMCDH for short. While providing the signing oracle, the authors also fix a gap in Sparkle proof.</p>
So far, we've discussed how Twinkle can modify the proof of knowledge statement in the Sparkle scheme by adding an extra parameter, which then reduces its unforgeability to the CDH assumption without rewinding. We have also briefly touched on how adaptive corruption can be obtained under the OMCDH assumption. Despite OMCDH is still an interactive assumption, the authors discuss a method to instantiate Twinkle based on the DDH assumption.
In general, the authors extend the technique proposed by Tessaro and Zhu in [TZ23] to replace an interactive assumption with a non-interactive one. To keep this blog post short, we didn't discuss an important building block introduced in this paper, known as Tagged Linear Function Families. We recommend interested readers to refer to section 3 of the paper for more information about this building block and to section 4.2 to see how this function families can be instantiated based on the DDH assumption. Additionally, the authors in this paper identify and fix a security gap in Sparkle and we refer the readers to section 1.2 of the paper.
Some cool open questions:
- As mentioned, Twinkle is proved under an interactive version of T-UF-0 notion which we know this is weaker than T-UF-1. Is it possible to prove Twinkle under T-UF-1? Hint: After asking this question, Benedikt said they know how to simulate signing oracle under challenge message till second round while this is non-trivial how to to for the last round.
- Twinkle-style signature with two round of communcation?
- As said before, Twinkle adds /(pk')/, can we acheive all these features w/o this extra parameter? Note that Sparkle signature can be verified by the Schnorr verification algorithm while this is not the case for the Twinkle.
Acknowledgement: Thanks to Benedikt Wagner for his comments. Source of the images: https://iacr.org/submit/files/slides/2024/eurocrypt/eurocrypt2024/19/slides.pdf.
References:
[BLT+24] Renas Bacho, Julian Loss, Stefano Tessaro, Benedikt Wagner, and Chenzhi Zhu. Twinkle: Threshold signatures from DDH with full adaptive security. EUROCRYPT 2024.
[CKM23] Elizabeth C. Crites, Chelsea Komlo, and Mary Maller. Fully adaptive schnorr threshold signatures. CRYPTO 2023.
[DR23] Sourav Das, and Ling Ren. Adaptively secure bls threshold signatures from DDH and CO-CDH. Cryptology ePrint Archive (2023).
[MMS+24] Aikaterini Mitrokotsa, Sayantan Mukherjee, Mahdi Sedaghat, Daniel Slamanig, and Jenit Tomy. Threshold Structure-Preserving Signatures: Strong and Adaptive Security Under Standard Assumptions. PKC 2024.
[TZ23] Stefano Tessaro and Chenzhi Zhu. Threshold and multi-signature schemes from linear hash functions. EUROCRYPT 2023.
[BCK+22] Mihir Bellare, Elizabeth C. Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro, and Chenzhi Zhu. Better than advertised security for non-interactive threshold signatures. CRYPTO 2022.