# Non interactive threshold signature without bilinear pairing (is it possible)?

All threshold signature schemes that I have seen need bilinear pairings to avoid parameter exchange between parties. These are normally commitment schemes for a certain secret.

I believe a 2-round non-interactive scheme is possible, without using bilinear pairings, but I'm not entirely sure if it is secure.

Setup

Assume a set of parties with a pair of private/public keys $$s_{i} \times G \mapsto P_{i}$$, and a Shamir's secret shares $$y_{i}$$ of $$y$$ in a $$(t,n)$$-threshold where $$t+1$$ are required to recover the secret.

Assume there is a client interested in the signature result and that it can participate in the signature protocol. It can also try to break the protocol to get useful information (such as trying to get $$y$$), but gains nothing in receiving an invalid signature.

The Lagrange interpolation is defined as $$\mathcal{L}^{i}$$ such that $$\mathcal{L}^{i} y_{i} \mapsto y$$ and $$\mathcal{L}^{i} y_{i} \times G \mapsto Y$$. Also, $$y \times G \mapsto Y$$. I know this is already possible from this thread.

ThrGenSig(B) $$\mapsto$$ (c, p)

Produces a Schnorr signature for the $$B$$ data block from a 2-round multiparty computation.

Round 1) The client sends $$B$$ to more than $$t+1$$ parties. Each party computes an hash value $$H(s_{i}||B) \mapsto m_{i}$$ and replies with $$m_{i} \times G \mapsto M_{i}$$.

Round 2) The client selects the first $$t+1$$ to reply and computes $$\mathcal{L}^{i} M_{i} \mapsto M$$. The tuple $$(B, M)$$ is sent to the selected parties. Each party derives $$m_{i}$$ again and $$c = H(Y||M||B)$$, equal to all parties. Each party replies with $$(m_{i} - c \cdot y_{i}) = p_{i}$$. The signature result is computed in the client from $$\mathcal{L}^{i} p_{i} \mapsto p$$, and $$c$$ is already known.

VerSig(B, c, p) $$\mapsto$$ {0,1}

Verification is done as any Schnorr signature.

1. $$p \times G + c \times Y = M$$
2. Is c = H(Y||M||B)

Correctness: Note that, since the same $$t+1$$ parties are used to produce $$M$$ and $$p$$, the Lagrange interpolation works. The degree of the polynomial for $$m_{i}$$ is the same as for $$y_{i}$$, and we can sum shares of the same degree due to the homomorphic properties. The scheme only needs $$t+1$$ active parties during the 2-rounds.

Rushing adversary: A commitment scheme is not needed between parties since there is no interactivity. The client and a colluding party may try to perform $$M_{0}^{'} + \sum_{i=1}^{t} M_{i} = M^{'}$$ forcing the result where $$m^{'} \times G \mapsto M^{'}$$ is known. However, since $$m_{0}^{'}$$ cannot be known due to DLP, the party cannot participate to produce a valid signature for $$M^{'}$$. $$m_{i}$$ values are not exposed in any other way.

Distinct $$m$$ values: $$m$$ and $$m_{i}$$ values are the same for the same parties and $$B$$. No problem here. Even $$t$$ colluding parties cannot force the same $$m$$ for a different $$B$$. The $$m_{i}$$ share of the honest party will force a distinct $$m$$ with high probability. The adversary can try via the rushing adversary for a known $$M$$ via $$M_{0} + \sum_{i=1}^{t} M_{i}^{'} = M$$, but needs to derive a $$m^{'} \times G \mapsto \sum_{i=1}^{t} M_{i}^{'}$$ for the colluding parties. $$m^{'}$$ cannot be derived due to DLP.

Did I miss something. Is this safe?

• Might want to chat with the guys here: github.com/KZen-networks/multi-party-schnorr/issues/37 – Erik Aronesty Feb 8 at 21:14
• I have to say that this scheme is not entirely deterministic for the same message $B$. If you select a different set of t + 1 nodes, the nonce would be different. Nonetheless, it should be unique. – shumy Feb 10 at 11:28

The scheme as written is insecure if an attacker can get the same message signed twice.

The honest parties will compute their $$m_i$$ deterministically, but the attacker doesn't have to.

The attacker will get $$(m_i - c \cdot y_i) = p_i$$ and $$(m_i - c' \cdot y_i)= p_i'$$ for each participant.

These equations can be solved to get $$y_i = \frac{p_i - p_i'}{c' - c}$$. Since the attacker knows all the values on the right-hand side, the attacker can get $$t+1$$ shares and recover $$y$$.

One possible solution to avoid this is to ensure that the same message is never signed twice.

• Yes, thank you for pointing this out. Maybe a better solution would be to add a strictly increasing sequence to $H(s_i||seq||B) \mapsto m_i$. This makes the $m_i$ unique with high probability, but the signature is non-deterministic. – shumy Feb 13 at 10:23
• The sequence could be embedded in the message. Each party keeps track of the index of the latest message they signed and refuse to sign a message with a lower index. This would make the signature deterministic again. – Aman Grewal Feb 13 at 15:46
• The point is for the $seq$ to be controlled by each party, incremented for every request. What is in the message should not really matter. I don't see how a crafted $B$ could influence the determinism of $m$? – shumy Feb 13 at 16:00
• Maybe it's just semantics at this point. Let's say it's $H(s_i||seq||B) ↦ m_i$, where $seq$ is publicly known. Then the $m_i$ are deterministic w/r/t $(seq, B)$ – Aman Grewal Feb 13 at 16:16
• No, because the attackers can receive all the other $M_i$ before they send their own. If they control two nodes, then they can find two different $M_i$ that will interpolate to an M they have m for. This attack does not break DLP. The attackers will have to compute many $m_i, M_i$ pairs for this to work. See people.eecs.berkeley.edu/~daw/papers/genbday.html for information on the k-sums/generalized birthday problem, and see eprint.iacr.org/2018/417.pdf for some attacks on two-round signatures – Aman Grewal Feb 17 at 15:47

There's another weakness with this that isn't often discussed. Assuming that your M is 2, and assuming that you increment stuff for every request, then it should be OK... but it still isn't.

The problem is that the process of mapping a hash to a prime field can result in a bit of bias. In the case of schnorr signatures, even one bit of bias (say because you hashed and took a modulo, or hashed and threw away some bits), can result in a massive loss of security. For example: https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf

So even though your favorite hash "behaves" like a random oracle in that it is very good at being collision free and irreversable. Does it behave like a good prime number when reduced?

Schnorr sigs, in general seem scary to me the more I think about all the things that can go wrong.

Pairings solve this problem in a way that seems, to me, less prone to minor implementation bugs causing major issues.

• Maybe so, but this is a problem for all frameworks assuming the oracle model, not specific to my proposed scheme. It doesn't make it any weaker than other schemes at the same level. – shumy Mar 6 at 9:51
• it's not a problem for a paring signature because the hashing is only used for collision resistance in a few bits of loss in collision resistance doesn't result in some massive security leak. – Erik Aronesty Mar 7 at 12:55