Signature schemes you've never heard about

An exploration of some interesting signature schemes!

August 27, 2025

Most of you have heard about ECDSA and Schnorr signatures. A bunch of you have seen BLS. A few brave ones have also seen BBS. But we're not going to talk about these today...

I've stumbled upon a couple of very interesting signature schemes through some topic I'm looking into with Guillermo. Both of them are a bit unusual in the sense that they're useful in niche areas, but when you need them - they're extremely useful.

Let's look at them.

Locally verifiable signatures

First, let's recap aggregate signature schemes, through the lens of BLS signatures. Aggregate signature schemes allow you to compress signatures on distinct messages into a short signature. BLS signatures look roughly as follows:

σ = sk \cdot H (m) pk = sk \cdot G

where G is a group generator, sk is the private key, pk is the public key and H is hash to group, so H(m) is a group element. Using the properties of the group, you can create an aggregate BLS signature by adding the messages together:

σ = σ_{1} + \dots + σ_{n} = sk \cdot (H (m_{1}) + \dots H (m_{n}))

Nice and easy. When the verifier encounters this aggregate signature, they would hash all the messages themselves and do the following check:

e (σ, G) = e (H (m_{1}) + \dots + H (m_{n}), pk)

so the pairing essentially checks that sk is consistent between the signature and the public key combined with the set of messages.

The key thing to see here is that the verifier needs to hash all the messages, as there's no way to run the pairing equation without that.

What if we only want to verify only one message and only possess the aggregate signature?

That's where locally verifiable signatures come in. First introduced in the paper by Goyal and Vaikuntanathan, locally verifiable signatures allow you to simultaneously achieve:

Aggregate short signature on multiple messages, especially when the signatures have been generated separately of each other
Verifying the signature for a single message is efficient

The authors present two constructions - one based on RSA and one based on pairings.

RSA-based locally verifiable signatures

In the RSA case, a signature looks like:

σ = g^{\frac{1}{H ( m )}}

where g is the RSA group generator and H is a specific hash function defined in the paper. Note that only the person that knows the RSA primes used to generate the group can compute the signature, since performing an inversion on H(m) requires knowing order of the group. The primes serve as the secret key. An aggregate signature is:

e_{m_{i}} : = H (m_{i}) σ = \prod σ_{i} = \prod g^{\frac{1}{e _{m_{i}}}}

It's not immediately obvious why this is locally verifiable. To see that, note that an actor called a hint generator can generate the following hints to help with local verification:

e_{m \ m_{i}} = j \neq = i \prod e_{m_{j}} f_{i} = j \neq = i \sum k \in / {i, j} \prod e_{m_{k}}

These, in turn, can be used to compute:

g^{\frac{1}{e _{m_{i}}}}

This seems a bit weird, since it's basically just the original signature! This works due to a cool observation the authors made, where given the aggregate signature and the hints above, the hint generator can extract the original signature without knowing the secret key.

Pairing-based locally verifiable signature

The construction is similar in spirit. A signature looks like:

\frac{1}{α + m} G

where ⍺ is the secret key. In this case, we know the order of the group, but we rely on the BDHI assumption, which roughly says that given:

g, α G, \dots, α^{n} G

it's hard to compute the inverse of ⍺ in the exponent, even in the target group of the pairing:

\frac{1}{α} e (G, G)

During the setup, the public key includes powers of ⍺ in the exponent, up until the maximum amount of messages in an aggregate signature. Aggregating signatures is done by computing:

σ = \frac{1}{\prod _{i} α + m _{i}} G

It's shown in the paper how to do this without knowing ⍺, using some Lagrange coefficient and partial fraction decomposition tricks.

In order to help the verifier, the following hints can be generated by the hint generator:

aux_{1} = i \sum β_{i} (α^{i} G) aux_{2} = i \sum β_{i} (α^{i + 1} G)

where the β coefficients are such that:

j, j \neq = i \prod (y + m_{j}) = j \sum β_{j} y^{j}

The local verification equation is:

e (σ, m_{i} aux_{1} + aux_{2}) = e (G, G) e (α G, aux_{1}) = e (G, aux_{2})

The first equation essentially checks that the signature contains the inverse of the product without the relevant expression of the message you want to locally verify. It looks like this:

m_{i} aux_{1} + aux_{2} = m_{i} (i \sum β_{i} (α^{i} G)) + i \sum β_{i} (α^{i + 1} G) = ((α + m_{i}) j \sum β_{j} α^{j}) G = (α + m_{i}) j, j \neq = i \prod (α + m_{j}) G = j \prod (α + m_{j}) G = σ

Relation to accumulators

Accumulators are a different primitive that allows you to efficiently get a compact representation of a set of elements and efficient membership proofs of individual elements in the set. Sometimes you can dynamically add, remove and even get non-membership proofs. That does feel similar, doesn't it?

Some readers may notice that the pairing-based construction is almost identical in mechanics to the pairing-based accumulator by Nguyen. The main difference is that in the accumulator ⍺ is secret to everyone, and everyone can add elements into the accumulator, while in the pairing-based signature ⍺ is known to the signer.

In the single-signer cases we've reviewed above, you can also create locally verifiable signatures by:

Accumulating messages into the accumulator
Signing the accumulator
Verifying membership proofs and the signature on the accumulator

The main difference is that you don't necessarily get aggregate signatures that you can aggregate non-interactively, so the set of messages has to be known ahead of time.

This is also true for concepts like vector commitments.

Signatures on linear subspaces

Another interesting signature scheme is the one by Boneh, Freeman, Katz and Waters, which allows you to sign a linear subspace. This means that given a set of basis vectors that are signed using this scheme, the signature would verify on any linear combination of them. This is wonderful, since this allows you to verify signatures on linear combinations you are sometimes required to do, without control of the coefficients of the vectors. But it comes at a cost. Let's see.

Signatures on individual vectors v look like:

σ = α (i \sum v_{i} H (id, i))

where id is some unique identifier and ⍺ is the secret key. You may notice this looks familiar. This is because it's an aggregate BLS signature, with the messages being (id, i) and aggregation coefficients being the elements of v, where previously we just used 1s. As such, verification of signatures on individual vectors looks like aggregate BLS verification.

You can guess where this is going - given multiple vectors for the same id, the messages on the matching positions would be the same and provide the separation between the elements of the vector, and so you can run the linear combinations in the exponent.

The really nice property about it is that given the signature on the subspace, you, or someone providing you with a hint, can run the linear combination on the signatures and get a short signature on the vector.

One other result they present in the paper is that there's a minimum signature size on the subspace, proportional to the dimension of the subspace. Note that this is the subspace signature, not the final vector, which can be short. The intuition is that if the signature is any less, you would have too many subspaces with the same signatures, and as a consequence the signature would eventually cover the entire space and be trivial.

Open questions

These left me with some other desired properties that I'd like to see:

Signing linear subspaces but different signers for each vector spanning the subspace
Aggregating existing aggregate locally verifiable signatures from different signers
Accumulators of accumulators - short witnesses to show multiple accumulators have been merged together
Efficient verification for aggregate signatures that are both multi signer and multi message

Get updates from Kobi's blog!