What in the Smurf is a silent-setup multiverse unpredictable function?

 

tl;dr: This blog post investigates whether threshold verifiable unpredictable functions (VUFs) can be efficiently instantiated in the silent setup setting, which avoids the need for an interactive, expensive and often complex distributed key generation (DKG) phase. We show that (1) silent setup threshold VUFs are possible from multilinear maps and (2) efficient constructions may be as hard to obtain as $n$-party non-interactive key exchange. In fact, we focus on a more general multiverse setting, which captures the threshold setting.

Why do we care about threshold verifiable unpredictable functions (VUFs)? Because the most efficient designs for distributed randomness beacons1 rely on them! Yet, all practical threshold VUFs require an expensive DKG phase between the beacon nodes (e.g., BLS2). This DKG must be run (1) when the beacon is first deployed and (2) when nodes enter or leave the distributed deployment (e.g., via a DKG-like secret resharing scheme).

Today, several beacon protocols based on threshold VUFs incur this expensive DKG phase (e.g., Aptos Roll3, drand4, Flow5, Sui6). This makes it intriguing (and potentially-useful) to consider the possibility of a silent setup threshold VUF: a scheme that avoids the need for a DKG!

In this blog post, we show such a scheme exists, if efficient multilinear maps exist! In fact, our proposed scheme is slightly stronger: it is a silent-setup multiverse VUF, or a SMURF, which works in a recently-proposed, more general multiverse setting7 that implicitly captures the threshold setting too.

Quick idea: BLS with multilinear maps

We modify the BLS2 multisignature scheme to be a threshold VUF as follows.

Each player $i$ has a secret key $\sk_i$ and a verification key $\vk_i = g^{\sk_i}$, generated locally, as usual. Player $i$ produces a signature share on message $m$ as $\sigma_i = H(m)^{\sk_i} \in \Gr$, as usual.

What is different then? To aggregate a $t$-out-of-$n$ threshold VUF, we will plug the $t$ signature shares as the first inputs to an $n$-multilinear map $e$ and the remaining $n-t$ public keys as the last inputs.

For example, a 2-out-of-3 threshold VUF $\sigma$ over a message $m$ would be aggregated from BLS signature shares $(\sigma_1,\sigma_2)$ as: \begin{align} \label{eq:example-agg} \sigma &= e_3(\sigma_1, \sigma_2, \pk_3)\\
&= e_3(H(m)^{\sk_1}, H(m)^{\sk_2}, g^{\sk_3})\\\ &= e_3(H(m), H(m), g)^{\sk_1 \cdot \sk_2 \cdot \sk_3} \end{align}

To verify such a threshold VUF, the proof would consist of the actual signature shares $H(m)^{\sk_1}$ and $H(m)^{\sk_2}$. Verification would involve two steps. First, validate each signature share using the multilinear map (or via a DLEQ $\Sigma$-protocol proof): \begin{align} \label{eq:example-ver} e_3(\sigma_i, g,g) \equals e_3(H(m), \pk_i, g),\forall i\in\{1,2\} \end{align} Second, re-aggregate the signature shares and check they yield the same signature $\sigma$ from Equation \ref{eq:example-agg}.

We fully describe this strawman scheme below and improve it with succinctness later via an argument of knowledge (AoK) of signature shares that satisfy Equation \ref{eq:example-ver} and, when aggregated via Equation \ref{eq:example-agg}, yield the threshold VUF.

Note: We assume symmetric multilinear maps. Generalizing this to asymmetric ones would be interesting. (Naively, porting the construction over does not work due to the apparent necessity of defining multiple hash functions $H_i$ into each one of the asymmetric groups $\Gr_i$, which would break the uniqueness of the scheme.)

Recently, there has been increased interest in silent-setup threshold signatures: i.e., threshold signatures that avoid DKGs8$^,$7$^,$9$^,$10. However, silent-setup unique threshold signatures, a.k.a. threshold VUFs, have not received much attention.

Part of the reason may be that a silent-setup threshold VUF is actually a strong primitive: it implies $n$-party non-interactive key exchange (NIKE). Specifically, a $1$-out-of-$n$ silent-setup threshold VUF $=$ an $n$-party NIKE11. Nonetheless, it may be that higher-threshold silent setup VUFs are still efficiently-instantiatable, since they should not imply $n$-party NIKE.

Note: While the strawman silent-setup threshold signature construction from [BGJ+23]7 (see a screenshot here) does satisfy uniqueness, it lacks silent setup: it still requires a DKG-like protocol for exposing evaluations on a degree-$(n-1)$ polynomial.

Preliminaries

Notation

When we write $(a_i)_{i\in T}$ as an input to an algorithm, it is shorthand for $\left(T, (i, a_i)_{i\in T}\right)$.

Verifiable unpredictable functions (VUFs)

A VUF12 is a unique signature scheme. Note that uniqueness is a stronger property than deterministic signing. It means that, an adversary cannot create two different signatures $\sigma_1 \ne \sigma_2$ such that they are both accepted as valid signatures on a message $m$ under some public key $\pk$. For example, BLS is a unique signature scheme but Ed25519 is not! While Ed25519 supports deterministic signing, it is not a unique scheme because a verifier will glady accept many different signatures for the same message $m$.

Multilinear maps

Important: As of 2024, practical multilinear map constructions do not exist13$^,$14. In other words, the schemes in this blog post are purely-theoretical and serve only to indicate the feasibility of a SMURF.

An $n$-multilinear map $e : \Gr^n \rightarrow \Gr_T$ has the following properties:

  1. $\Gr$ and $\Gr_T$ are both Abelian groups of prime order $p$
  2. $\forall (a_1, \ldots, a_n) \in \Z_p^n, (g_1,\ldots, g_n)\in \Gr^n$, we have $e_n(g_1^{a_1}, \ldots, g_n^{a_n}) = e_n(g_1, \ldots, g_n)^{a_1 \cdots a_n}$
  3. If $g$ is a generator of $\Gr$, then $e_n(g, \ldots, g)$ is a generator of $\Gr_T$.

Accumulators

An accumulator scheme is used to compute a short, collision-resistant digest of a set $S$.

$\mathsf{Acc.Commit}(S) \rightarrow d$. Computes the digest $d$ of the set $S$.

An accumulator scheme is collision-resistant if there is no polynomial time adversary that can output two different sets which have the same digest. As an example, simply sorting the set in a canonical order and hashing the result using a collision-resistant hash function yields an accumulator scheme.

Arguments of Knowledge (AoKs)

An AoK for a relation $\mathcal{R}$ consists of two algorithms:

$\mathsf{AoK.Prove}_\mathcal{R}(x; w) \rightarrow \pi$. Generates a proof $\pi$ that $R(x; w) = 1$, given a public statement $x$ and a witness $w$. The proof $\pi$ is succinct (i.e., much smaller than $w$), but might still leak information about $w$.

$\mathsf{AoK.Verify}_\mathcal{R}(x; \pi)\rightarrow \{0,1\}$. Verifies the proof $\pi$ that the prover knows a witness $w$ such that $R(x; w) = 1$.

Silent-setup Multiverse (Verifiable) UnpRedictable Functions (SMURFs)

To avoid mistakes, we formally define a SMURF as a tuple of algorithms (with correctness and security definitions in the appendix):

$\mathsf{SMURF.KeyGen}(1^\lambda) \rightarrow (\sk_i, \vk_i)$. Locally generates a player’s key pair: their secret key and corresponding verification key.

Ideally, $\vk_i$ should be succinct (i.e., its size should be independent of the maximum number of players $n$).

$\mathsf{SMURF.AggPubkey}(t, (\vk_j)_{j\in [n]}) \rightarrow (\pk, \ak)$. Takes the verification keys of $n$ players (generated locally via $\mathsf{SMURF.KeyGen}$) and a threshold $t$. Aggregates them into:

  • a $t$-out-of-$n$ public key $\pk$ which can be used to verify threshold signatures against
  • an aggregation key $\ak$ which can be used to aggregate threshold signatures via $\mathsf{SMURF.AggSig}$

The necessity of an aggregation key AK $\ak$ in the definition is artificial. An ideal definition would not require this. However, because our succinct SMURF construction requires the VKs of all players during aggregation, we rely on an AK to pass in this information.

$\mathsf{SMURF.ShareSign}(\sk_i, m) \rightarrow \sigma_i$. Computes a signature share $\sigma_i$ over $m$ under $\sk_i$.

$\mathsf{SMURF.ShareVer}(\vk_i, m, \sigma_i) \rightarrow \{0,1\}$. Verifies the signature share $\sigma_i$ on the message $m$ from the player with VK $\vk_i$.

$\mathsf{SMURF.AggSig}(\ak, m, (\sigma_i)_{i\in T}) \rightarrow \sigma$. Aggregates the signature shares $\sigma_i$ from a subset $T$ of players into a signature $\sigma$ that can be verified via $\mathsf{SMURF.Verify}$.

$\mathsf{SMURF.Verify}(\pk, m, \sigma) \rightarrow \{0,1\}$. Verifies that $\sigma$ is a valid signature on $m$ under $\pk$.

$\mathsf{SMURF.Derive}(\pk, m, \sigma) \rightarrow y$. Derives a unique output $y$ from the signature $\sigma$.

$\mathsf{SMURF.Eval}(t, (\vk_j)_{j\in[n]}, m) \rightarrow y$. Returns the unique output $y$ on message $m$ given a threshold $t$ and the VKs of the $n$ players.

Note: We intentionally defined $\mathsf{SMURF.Eval}$ to take the VKs rather than the SKs as input. This allows us to define unpredictability in the silent setup setting, where it will not be possible to extract the SKs under which the adversary’s prediction was made (unlike in the DKG setting), since VKs can be adversarial. Lastly, even though $\mathsf{SMURF.Eval}$ is not a polynomial-time algorithm, this is not a problem since it is only used for the security definition.

Non-succinct SMURF from multilinear maps

Here, we describe the scheme from above in more detail.

Let $g$ be the generator for $\Gr$, which admits an $n$-multilinear map15 $e$, as defined above. We construct a non-succinct SMURF as follows:

$\mathsf{SMURF_1.KeyGen}(1^\lambda) \rightarrow (\sk_i, \vk_i)$:

  • $\sk_i\randget\Zp$
  • $\vk_i \gets g^{\sk_i}$

$\mathsf{SMURF_1.AggPubkey}(t, (\vk_j)_{j\in [n]}) \rightarrow (\pk, \ak)$.

  • $\pk \gets \left(t, (\vk_j)_{j\in[n]}\right)$
  • $\ak \gets \pk$

$\mathsf{SMURF_1.ShareSign}(\sk_i, m) \rightarrow \sigma_i$:

  • $\sigma_i \gets H(m)^{\sk_i}$

$\mathsf{SMURF_1.ShareVer}(\vk_i, m, \sigma_i) \rightarrow \{0,1\}$:

  • Return $e_n(\sigma_i, g, \ldots, g) \equals e_n(H(m), \vk_i, g, \ldots, g)$

$\mathsf{SMURF_1.AggSig}(\ak, m, (\sigma_i)_{i\in T}) \rightarrow \sigma$:

  • $\pi \gets (\sigma_i)_{i\in T}$

Just a naive aggregation here. Will fix this in the succinct construction below.

$\mathsf{SMURF_1.Verify}(\pk, m, \sigma) \rightarrow \{0,1\}$:

  • Parse $(\sigma_i)_{i \in T} \gets \pi$
  • Parse $\left(t, (\vk_j)_{j\in[n]}\right) \gets \pk$
  • Assert $T$ is a size-$t$ subvector of $[n]$
  • $\forall i\in T$, assert $\mathsf{SMURF_1.ShareVer}(\vk_i, m, \sigma_i) \equals 1$

Also a naive verification here, which we fix in the succinct construction below.

$\mathsf{SMURF_1.Derive}(\pk, m, \sigma) \rightarrow y$.

  • Parse $(\sigma_i)_{i \in T} \gets \pi$
  • Parse $\left(t, (\vk_j)_{j\in[n]}\right) \gets \pk$
  • Parse $\{i_1, \ldots i_t\} \gets T$
  • Parse $\{j_1,\ldots,j_{n-t}\} \gets [n]\setminus T$
  • $y \gets e_n(\sigma_{i_1}, \ldots, \sigma_{i_t}, \vk_{j_1},\ldots,\vk_{j_{n-t}})$

$\mathsf{SMURF_1.Eval}(t, (\vk_j)_{j\in[n]}, m) \rightarrow y$.

  • For all $j\in[n]$, compute $\sk_j$ such that $\vk_j = g^{\sk_j}$
    • Note: This is not supposed to be efficient.
  • $y \gets e_n(H(m), \ldots, H(m), g, \ldots, g)^{\prod_{j\in[n]} \sk_j}$
    • Note: $H(m)$ appears $t$ times as an input to $e_n$.

Recall that a polynomial time $\mathsf{SMURF.Eval}$ is not necessary, since we only use this algorithm to define security.

Succinct construction from multilinear maps and AoKs

From a theoretical standpoint, the $\mathsf{SMURF_1}$ construction above is not succinct:

  1. The public key $\pk$ is $O(n)$-sized
  2. The aggregated $\sigma$ is $O(t)$-sized
  3. Verifying $\sigma$ takes $O(t)$ time
  4. Deriving the VUF output $y$ takes $O(n)$ time since it involves evaluating the multilinear map.

Fortunately, all of these can be addressed with a succinct argument of knowledge (AoK), often known as a SNARK. (Note that a zkSNARK is not necessary; we do not need zero-knowledge here.)

Specifically, instead of (1) doing all the signature share verification inside $\mathsf{SMURF_1.Verify}$ and (2) doing all the aggregation work inside $\mathsf{SMURF_1.Derive}$, we will give an AoK of having done this work when aggregating in $\mathsf{SMURF_2.AggSig}$.

We denote the resulting scheme as $\mathsf{SMURF_2}$. It has the same $\mathsf{KeyGen}$, $\mathsf{ShareSign}$, $\mathsf{ShareVer}$ and $\mathsf{Eval}$ algorithms as $\mathsf{SMURF_1}$, except for:

$\mathsf{SMURF_2.AggPubkey}(t, (\vk_j)_{j\in [n]}) \rightarrow (\pk, \ak)$.

  • $d \gets \mathsf{Acc.Commit}\left(\{\vk_j\ \vert\ j\in[n]\}\right)$
  • $\pk \gets \left(t, d\right)$
  • $\ak \gets (\pk, (\vk_j)_{j\in[n]})$

We make the PK succinct by converting it to an accumulator over the VKs. The aggregation key (AK) still needs to maintain all the individual VKs. It is an interesting open question whether the AK can be made succinct (and thus eliminated).

$\mathsf{SMURF_2.AggSig}(\ak, m, (\sigma_i)_{i\in T}) \rightarrow \sigma$:

  • Parse $\left((t, d), (\vk_j)_{j\in[n]}\right) \gets \ak$
  • Parse $\{i_1, \ldots i_t\} \gets T$
  • Parse $\{j_1,\ldots,j_{n-t}\} \gets [n]\setminus T$
  • $y \gets e_n(\sigma_{i_1}, \ldots, \sigma_{i_t}, \vk_{j_1},\ldots,\vk_{j_{n-t}})$
  • $\pi \gets \mathsf{AoK.Prove}_\mathcal{R}(d, m, t, y; T, (\sigma_i)_{i\in T}, (\vk_i)_{i\in [n]})$
  • $\sigma \gets (y, \pi)$

The new $\mathsf{AggSig}$ proves knowledge of $t$ valid signature shares, against the VKs accumulated in the PK, such that these shares aggregate into a unique output $y$. More formally, the proof argues knowledge of $\sigma_i$’s and $\vk_i$’s such that $\mathcal{R}(d, m, t, y; T, (\sigma_i)_{i\in T}, (\vk_i)_{i\in [n]}) = 1$. We describe the relation $\mathcal{R}$ in detail below.

$\mathsf{SMURF_2.Verify}(\pk, m, \sigma) \rightarrow \{0,1\}$:

  • Parse $\left(\cdot, d\right) \gets \pk$
  • Parse $(y, \pi) \gets \sigma$
  • Assert $\mathsf{AoK.Verify}_\mathcal{R}(d, m, t, y; \pi) \equals 1$

$\mathsf{SMURF_2.Derive}(\pk, m, \sigma) \rightarrow y$.

  • Parse $(y, \pi) \gets \sigma$
  • Return $y$

That’s it! This (theoretical) construction now achieves succinctness.

We assume the $\mathsf{AoK}$ scheme is succinct and lacks a trusted setup. However, this $\mathsf{SMURF_2}$ scheme should still be interesting even if the $\mathsf{AoK}$ scheme requires a trusted setup. After all, the trusted setup would only need to be redone to support a higher $n$ and would be reusable for any number of players $n_0 < n$.

The relation

$\mathcal{R}(d, m, t, y; T, (\sigma_i)_{i\in T}, (\vk_i)_{i\in [n]}) = 1$ iff.:

  1. $|T| \equals t$ and $T\stackrel{?}{\subseteq} [n]$
  2. $\mathsf{Commit}(\{\vk_i\ \vert\ i\in [n]\}) \equals d$
  3. $\forall i\in T, \mathsf{SMURF_1.ShareVer}(\vk_i, m, \sigma_i) \equals 1$.
  4. Let $\{i_1, \ldots i_t\} \gets T$
  5. Let $\{j_1,\ldots,j_{n-t}\} \gets [n]\setminus T$
  6. $e_n(\sigma_{i_1}, \ldots, \sigma_{i_t}, \vk_{j_1},\ldots,\vk_{j_{n-t}}) \equals y$

Conclusion & future work

If symmetric multilinear maps exist, then there exist SMURFs! Unfortunately, if efficient SMURFs exist (or even their weaker, threshold variant), then efficient $n$-party non-interactive key exchange (NIKE) exists11. (This explains why our two SMURF constructions are very similar to an $n$-party NIKE based on multilinear maps16.)

Future work:

  1. Proving our SMURF constructions secure.
  2. A SMURF with $O(1)$-sized aggregation keys.

Acknowledgements: Thanks to Valeria Nikolaenko, Joe Bonneau, Rex Fernando, Benny Pinkas, Dan Boneh and Trisha Datta for reading, providing feedback and brainstorming together!

Appendix: Formalizing SMURFs

Correctness definitions

Correctness: $\forall$ number of players $n$, $\forall$ thresholds $t\le n$, where $(\sk_j, \vk_j) \gets \mathsf{SMURF.KeyGen}(1^\lambda),\forall j\in[n]$ and $(\pk,\ak) \gets \mathsf{SMURF.AggPubkey}(t, (\vk_j)_{j\in[n]})$, for any subset $T\subset[n]$, where $|T| \ge t$, $\forall$ messages $m$, $\sigma_i \gets \mathsf{SMURF.ShareSign}(\sk_i, m),\forall i\in T$, $\sigma \gets \mathsf{SMURF.AggSig}(\ak, m, (\sigma_i)_{i\in T})$ we have: \begin{align*} \forall i\in T,\mathsf{SMURF.ShareVer}(\vk_i, m, \sigma_i) &= 1 \wedge {}\\
\mathsf{SMURF.Verify}(\pk, m, \sigma) &= 1 \wedge {}\\
\mathsf{SMURF.Derive}(\pk, m, \sigma) &= \mathsf{SMURF.Eval}(t, (\vk_j)_{j\in [n]}, m) \end{align*}

Note: This implies that, for a correctly-generated $t$-out-of-$n$ threshold PK from $n$ VKs, if a signature pases verification via $\mathsf{SMURF.Verify}$, then calling $\mathsf{SMURF.Derive}$ on it would yield the same result as calling $\mathsf{SMURF.Eval}$ on the same message, the same $n$ VKs and the same threshold $t$.

Uniqueness: For all polynomial time adversaries $\Adv$, for any number of players $n=\poly(\lambda)$, for any threshold $t\le n$, we have: \begin{align*} \Pr\begin{bmatrix} (\pk, m, (\sigma_i)_{i\in[2]} \gets \Adv(1^\lambda),\\
(y_i \gets \mathsf{SMURF.Derive}(\pk, m, \sigma_i))_{i\in[2]} :\\
y_1 \ne y_2 \wedge \forall i\in [2], \mathsf{SMURF.Verify}(\pk, m, \sigma_i) = 1 \end{bmatrix} = \negl(\lambda) \end{align*}

Uniqueness says that an adversary is not able to produce two signatures for the same message that both verify against a threshold PK yet derive different outputs. This particular definition is rather strong, since it allows the adversary to produce the PK adversarially.

Oracle

In order to define security of a SMURF, we will need to define an oracle that the adversary can query as he attempts to break the scheme. The oracle will allow the adversary to:

  1. Create new players
  2. Corrupt players
  3. Request signature shares from uncorrupted players

This helps formally model the power of the adversary in the multiverse setting in which the SMURF is supposed to remain secure.

How does the oracle work? First, the oracle $\mathcal{O}$ maintains some state:

  • the total number of players so far $N$, initially zero
  • the list $L$ of players and their key pairs, initially empty
  • the set $H$ of honest players, initially empty
  • the set $M$ of malicious players, initially empty
  • for any message $m$, the set $Q_m$ of players who have been queried for a signature share on $m$ by the adversary; initially, $Q_m = \varnothing,\forall m$

Then, the oracle handles the following requests from the adversary $\Adv$:

$\mathcal{O}.\mathsf{KeyGen}() \rightarrow (i, \pk)$:

  • $(\sk, \pk)\gets \mathsf{SMURF.KeyGen}(1^\lambda)$
  • $i \gets N$ and $N \gets N+1$
  • $L \gets L \cup \{(i, \sk, \pk)\}$
  • $H \gets H \cup \{i\}$
  • return $(i, \pk)$

This generates a new player numbered $i$, adds it to the list $L$ and marks it as honest in $H$.

$\mathcal{O}.\mathsf{CorruptPlayer}(i) \rightarrow \sk$:

  • if $\exists (i, \sk, \cdot) \in L$, then:
    • $H \gets H \setminus \{i\}$
    • $M \gets M \cup \{i\}$
    • return $\sk$
  • else:
    • return $\bot$

This checks if player $i$ actually exists and, if so, corrupts it by revealing their SK. The player is marked as malicious by adding it to $M$ and removing it from $H$.

$\mathcal{O}.\mathsf{ShareSign}(i, m) \rightarrow \sigma_i$:

  • if $\exists (i, \sk, \cdot) \in L$ and $i\in H$, then:
    • $Q_m \gets Q_m \cup \{i\}$
    • return $\mathsf{SMURF.ShareSign}(\sk, m)$
  • else:
    • return $\bot$

This returns a signature share $m$ from player $i$, assuming $i$ is honest. The oracle tracks the set of signature queries by adding $i$ to $Q_m$.

Security definitions

Now that we’ve defined the oracle, we can meaningfully define security as follows.

Unforgeability: For all polynomial time adversaries $\Adv$ with oracle access to $\mathcal{O}$:

\begin{align*} \Pr\begin{bmatrix} (t, (\vk_{i\in[n]}), m, \sigma) \gets \Adv^\mathcal{O}(1^\lambda),\\
(\pk,\cdot) \gets \mathsf{SMURF.AggPubkey}(t, (\vk_{i\in[n})) :\\
\mathsf{SMURF.Verify}(\pk, m, \sigma) = 1 \wedge |Q_m| < t \end{bmatrix} = \negl(\lambda) \end{align*}

Unpredictability: For all polynomial time adversaries $\Adv$ with oracle access to $\mathcal{O}$:

\begin{align*} \Pr\begin{bmatrix} (t, (\vk_{i\in[n]}), m, y) \gets \Adv^\mathcal{O}(1^\lambda),\\
(\pk,\cdot) \gets \mathsf{SMURF.AggPubkey}(t, (\vk_{i\in[n})) :\\
\mathsf{SMURF.Eval}(t, (\vk_i)_{i\in[n]}, m) = y \wedge |Q_m| < t \end{bmatrix} = \negl(\lambda) \end{align*}

Unpredictability must be defined to prevent trivial instantiations. Otherwise, for example, the signature $\sigma$ could be any non-unique multiverse signature (e.g., BLS multisignatures with proofs-of-possession) while $\mathsf{SMURF.Derive}$ could always uniquely set the VUF output to $y=\bot$. Such a trivial scheme is excluded by our unpredictability definition.


  1. Although verifiable delay functions (VDFs) also give rise to efficent distributed randomness beacons, we do not of VDF-based beacons that are responsive: i.e., they produce beacon values as fast as the network speed. 

  2. Short Signatures from the Weil Pairing, by Boneh, Dan and Lynn, Ben and Shacham, Hovav, in Advances in Cryptology — ASIACRYPT 2001, 2001  2

  3. Roll with Move: Secure, instant randomness on Aptos, by Alin Tomescu and Zhuolun Xiang, 2024, URL 

  4. https://drand.love/ 

  5. Flow’s DKG 

  6. Sui DKG 

  7. Threshold Signatures in the Multiverse, by L. Baird and S. Garg and A. Jain and P. Mukherjee and R. Sinha and M. Wang and Y. Zhang, in 2023 IEEE Symposium on Security and Privacy (SP), 2023, [URL]  2 3

  8. Threshold Signatures from Inner Product Argument: Succinct, Weighted, and Multi-threshold, by Sourav Das and Philippe Camacho and Zhuolun Xiang and Javier Nieto and Benedikt Bunz and Ling Ren, in Cryptology ePrint Archive, Paper 2023/598, 2023, [URL] 

  9. hinTS: Threshold Signatures with Silent Setup, by Sanjam Garg and Abhishek Jain and Pratyay Mukherjee and Rohit Sinha and Mingyuan Wang and Yinuo Zhang, in Cryptology ePrint Archive, Paper 2023/567, 2023, [URL] 

  10. Decentralized Threshold Signatures for Blockchains with Non-Interactive and Transparent Setup, by Kwangsu Lee, in Cryptology ePrint Archive, Paper 2023/1206, 2023, [URL] 

  11. Big thanks to Guru Vamsi Policharla for this observation during the 3rand workshop 2

  12. Verifiable random functions, by S. Micali and M. Rabin and S. Vadhan, in 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), 1999 

  13. Indistinguishability Obfuscation from Well-Founded Assumptions, by Aayush Jain and Huijia Lin and Amit Sahai, in Cryptology ePrint Archive, Paper 2020/1003, 2020, [URL] 

  14. Multilinear Maps from Obfuscation, by Martin R. Albrecht and Pooya Farshim and Shuai Han and Dennis Hofheinz and Enrique Larraia and Kenneth G. Paterson, in Cryptology ePrint Archive, Paper 2015/780, 2015, [URL] 

  15. A multilinear map of size $n’ > n$ inputs would also work by forcing the last $n’ - n$ inputs to be some predetermined values from a common-reference string. 

  16. Applications of Multilinear Forms to Cryptography, by Dan Boneh and Alice Silverberg, in Cryptology ePrint Archive, Paper 2002/080, 2002, [URL]