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.


$p \times G + c \times Y = M$
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?
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.