Is this distributed random oracle scheme safe?
Attackers can choose their $M_0, m_0$ pair without solving DLP.

In particular, they generate multiple lists of $M, m$ pairs and try to solve for $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot M_n = M_0$.

In order to solve this, they no longer have $m_i$ for some $i$. The k-sums algorithm is effectively solving $l_1 \cdot M_1 + l_2 \cdot M_2 + ... + l_n \cdot (M_n - M_0) = 0$.

In this way, they can choose the final value ($M_0$), but are unable to recover anyone else's private values (an $m_i$ that the attacker doesn't own).

This shouldn't an issue for signatures (when computing the nonce) because the signature can never be computed without all the $m_i$. But it won't be secure for other applications.

However, there's another attack, presented in section 4 of https://eprint.iacr.org/2018/417.pdf. This attack relies on multiple parallel signature operations. Note that this attack still works with different messages even though it is only presented with the same message.

Suppose that $i$ indexes the participants and $j$ indexes the messages so that $M_j$ refers to the nonce of the jth message and $M_{ji}$ refers to ith participant's public value used to interpolate for $M_j$. In this attack, the attacker is searching for $M_{ji}$ and $a$ such that $a \cdot \Sigma H(Y||M_j||B) = H(Y||M||B^*)$, where $B^*$ is the message they want to sign.

The generalized birthday attack provides a somewhat efficient way to solve for these $j+1$ unknowns. For example, with a 256-bit hash and 127 parallel signatures, the equation can be solved in $O(2^{47})$, which is significantly less than the complexity of breaking the hash or solving the discrete log.