DSKE: Digital Signatures with Key Extraction

The problem

Signatures that are valid forever are a liability

A digital signature stays valid until the scheme breaks or the key leaks. That is exactly what you want for a contract. For email it is harmful. Under DKIM, the mail server signs every outgoing message with one domain key. Anyone who later obtains a leaked mailbox can prove who sent each message, which invites extortion and retaliation.

The paper asks whether recipients can verify a signature while the sender still gains plausible deniability, "without requiring the constant release of old key materials or relying on any additional components". That sounds like it contradicts non-repudiation. DSKE's answer is an extractable set: $\mathsf{Extract}(\{(m_i,\sigma_i)\}_{i\in[k]}, pk)$ returns $sk$ with probability $\delta$ (Definition 7).

Interactive 1 · hash-based DSKE (§4.1)

Every Lamport signature gives away half of the key

A Lamport key is $2\lambda$ random strings $sk_i[b]$, and the public key is their hashes. To sign, you hash the message and reveal $sk_i[d_i]$ for every digest bit $d_i$. One signature is safe. But each new message reveals a fresh random half, and once every column $i$ has shown both $sk_i[0]$ and $sk_i[1]$, the union of signatures is the private key (Figure 1). This demo runs real SHA-256 with $\lambda=256$ in your browser.

Failure branch
Switch to malicious signer. The signer grinds each message (appending a nonce) until the first digest bit is $0$. This is the attack in §4, limitation (3): $sk_1[1]$ is never revealed, so extraction never succeeds. Theorem 3 only covers trusted generation, and $\mathsf{DSKE}_{\mathsf{hash}}$ has no extractability under untrusted generation. The polynomial construction below fixes this.

Interactive 2 · polynomial-commitment DSKE (§5) → rate-limiting nullifier (§6.2)

$d$ points hide the key; $d+1$ points reveal it

In $\mathsf{DSKE}_{\mathsf{poly}}$ the private key is a degree-$d$ polynomial $f(X)$ and the public key is its KZG commitment $C_f$. A signature on $m$ is an opening of $f$ at $x=H(m)$, so each signature is one point $(x, f(x))$ plus a proof. Any $d+1$ such points interpolate to $f$. Here a user registers with an RLN server and posts messages. The server counts them, and on message $d+1$ it runs $\mathsf{Extract}$, publishes $sk_{\mathcal U}$ and expels the user.

This is a toy for intuition. It works over the rationals, with $x = H(m)$ taken as a SHA-256-derived value in $[-1,1]$ and small integer coefficients, and it computes no KZG commitment or proof. The real scheme works in $\mathbb{Z}_p$ over BLS12-377. There, below the threshold the key stays hidden by computational hiding (Definition 3) rather than by a picture, and interpolation binding (Definition 6) is what makes extraction work against a malicious signer (Theorem 6).

Source disagreement
The generic $\mathsf{Extract}$ in §5 says to return $\bot$ "if the number of distinct $m_i$ is less than $d$", yet it interpolates over $\{x_i,y_i\}_{i\in[d+1]}$, and Theorems 5 and 6 both require $k \ge d+1$. This demo follows the theorems ($d+1$), as does the RLN slashing rule ($\mathsf{MsgNum} > d$).

Interactive 3 · GroupForge, deniable email (§6.1)

One public key, many time chunks, no key publishing

GroupForge generates $2^{h_T}$ DSKE key pairs, one per time chunk of length $\Delta$, and publishes only the Merkle root $R$. An email sent during chunk $i$ is signed with $sk_i$ and carries $pk_i$ with its Merkle path. Once $k$ signatures exist in chunk $i$, anyone can run $\mathsf{Expire}$ to extract $sk_i$ and then $\mathsf{Forge}$ emails in that chunk. At that point a leaked email proves nothing. This is the $h_T=2$ tree of Figure 2. Advance the clock, send emails, and try the failure paths.

$k$ here is illustrative. Figure 2 uses groups of two, and the measured $\mathsf{GroupForge}_{\mathsf{kzg}}$ in Table 2 uses $k=32$. An email counts as valid if $\mathsf{Ver}$ accepted it on arrival. Read literally, $\mathsf{Expire}$ re-runs $\mathsf{Ver}$, whose clock check ($i = i'$) would reject signatures from a chunk that has already ended. The demo assumes the intended reading, that validity is judged at delivery.

Interactive 4 · measured performance (§7)

What extraction costs

Every value here is copied from Tables 1 and 2 (Rust prototypes on an Apple M1, 8 GB RAM, SHA-256 and BLS12-377 from arkworks). The controls only snap to the measured group sizes and tree heights. Both scales are logarithmic, because the values span microseconds to minutes.

Source disagreement
In Table 2, $\mathsf{GroupForge}_{\mathsf{kzg}}$ signing takes 1.554–1.722 ms. That is less than the 2.523 ms Table 1 reports for plain $\mathsf{DSKE}_{\mathsf{kzg}}$ signing at the same $k=32$, even though GroupForge's $\mathsf{Sign}$ calls the DSKE $\mathsf{Sign}$ and then adds a Merkle path. The hash variant behaves as expected (21.791 µs vs 17.625 µs). Both tables are reproduced as printed.

Observation
Table 2's key-generation times double exactly with each extra level of the tree (7.407 → 14.815 → 29.631 → 59.262 s, and 46.294 → 92.588 → 185.175 → 370.350 s), and they match $2^{h_T}$ × the Table 1 per-key cost (e.g. $2^{14} \times 2.825$ ms ≈ 46.29 s). They may have been computed from single-key measurements rather than timed end to end. The paper does not say which.

Guarantees

What each construction guarantees

Deniable signatures compared (Table 3)

✓ means the scheme does not require the item in the column header. Table 3 in the paper.

Measured results

Tables 1 and 2, as printed

Testbed: macOS Monterey, Apple M1 (8-core, 3.2 GHz), 8 GB RAM. Prototypes in Rust. KZG from arkworks poly-commit on BLS12-377, and Merkle trees from arkworks crypto-primitives with SHA-256.

Table 1 · Performance of $\mathsf{DSKE}_{\mathsf{lamp}}$ and $\mathsf{DSKE}_{\mathsf{kzg}}$

"The probability of extracting the key in $\mathsf{DSKE}_{\mathsf{lamp}}$ is overwhelming in $k$, so the actual size of the extractable group can be smaller than $k=64$."

Table 2 · Performance of GroupForge constructions with $\Delta=0.5$ hour

Tree heights 14–17 correspond to 0.93, 1.87, 3.74 and 7.48 years of time chunks. Key generation dominates because $2^{h_T}$ key pairs are generated.

Where the paper disagrees with itself

1. Extraction threshold. §5's $\mathsf{Extract}$ returns $\bot$ if there are fewer than $d$ distinct messages, but interpolates $d+1$ points. Theorems 5 and 6 state $k \ge d+1$. This page uses $d+1$.
2. Private-key size. §8 says $f(X)$ "contains $d$ elements of $\mathbb{F}$, i.e., the coefficients $f_0,\ldots,f_{d-1}$". A polynomial in $\mathbb{F}^{\le d}(X)$ has $d+1$ coefficients $f_0,\ldots,f_d$.
3. GroupForge signing vs DSKE signing. Table 2 reports $\mathsf{GroupForge}_{\mathsf{kzg}}$ signing (1.554–1.722 ms) faster than Table 1's $\mathsf{DSKE}_{\mathsf{kzg}}$ signing at $k=32$ (2.523 ms), even though the former includes the latter.
4. Naming. Tables 1 and 2 label the polynomial construction $\mathsf{DSKE}_{\mathsf{kzg}}$ / $\mathsf{GroupForge}_{\mathsf{kzg}}$, while the text and Table 3 call it $\mathsf{DSKE}_{\mathsf{poly}}$ / $\mathsf{GroupForge}_{\mathsf{poly}}$. The charts use the table labels.

Cite

BibTeX

@inproceedings{wang2025dske,
  title     = {{DSKE}: Digital Signatures with Key Extraction},
  author    = {Wang, Zhipeng and Alpos, Orestis and Kavousi, Alireza and
               Wong, Harry W. H. and Chau, Sze Yiu and Le, Duc V. and
               Cachin, Christian},
  booktitle = {CT-RSA 2025},
  year      = {2025}
}

@misc{cryptoeprint:2022/1753,
      author = {Zhipeng Wang and Orestis Alpos and Alireza Kavousi and Harry W. H. Wong and Sze Yiu Chau and Duc V. Le and Christian Cachin},
      title = {{DSKE}: Digital Signatures with Key Extraction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1753},
      year = {2022},
      note={Available at:  \url{https://eprint.iacr.org/2022/1753}}
}

Code availability

The paper does not link a code release. It describes Rust prototypes of $\mathsf{DSKE}_{\mathsf{lamp}}$, $\mathsf{DSKE}_{\mathsf{kzg}}$ and both GroupForge variants, built on the arkworks poly-commit and crypto-primitives libraries (§7). The full version, which includes the Winternitz-based construction and all proofs, is on ePrint.