Distributed Random Oracle with Verifiable Shares

$$Setup$$:

1. Let's assume a quorum of $$n$$ nodes where each have a secret share $$y_i$$ from a know and safe leaderless DKG protocol.
2. Define $$\mathcal{L}^i(y_i) = y$$ as the lagrange interpolation for $$x=0$$, giving $$y$$ as the secret that can only be known from at least $$f + 1$$ shares.
3. Define $$y \times G = Y$$ as the public key (EC point) for the scalar $$y$$ and base point $$G$$. This can also be derived from $$\mathcal{L}^i(Y_i) = Y$$. Confirmed here.
4. Define $$H_c(r) = R$$ as the hash-to-curve function on $$r$$ that gives R. $$r$$ is a public deterministic value that is known by all nodes. For instance, the round number in a blockchain consensus protocol.

The goal is to find a random value $$V$$ for the round $$r$$ that cannot be known or predicted in advance. The oracle value for a round $$r$$ is given by $$y \times R = V$$. Such value cannot be derived in this way because $$(y, \alpha)$$ are not known. Where $$\alpha \times G = R$$, but $$R$$ is derived from $$H_c(r) = R$$.

$$Derive(V)$$:

1. Each node calculates $$y_i \times R = V_i$$ and broadcasts $$V_i$$.
2. The value can be derived from $$\mathcal{L}^i(V_i) = V$$

$$SignInterlaced(V_i)$$:

1. Each node can sign $$V_i$$ with a Schnorr's Signature (SS) (a double interlaced signature).
2. From SS definition we start by deriving a local random nonce $$m \in \mathcal{Z}_p$$.
3. Define $$m_i \times G = M_i$$ and $$m_i \times R = M_{r,i}$$
4. Define $$c_i = H(Y_i||V_i||M_i||M_{r,i}||r)$$
5. Sign with $$p_i = m_i - c_i * y_i$$ where $$\sigma_i = (p_i, c_i)$$
6. Broadcast $$\sigma_i$$ and $$V_i$$

$$CheckShare(V_i)$$

1. On each node we can verify that $$V_i$$ is derived from $$y_i \times R$$ if we:
2. Get $$p_i \times G + c_i \times Y_i = M_i$$
3. Get $$p_i \times R + c_i \times V_i = M_{r,i}$$
4. Check that $$c_i = H(Y_i||V_i||M_i||M_{r,i}||r)$$

Informal Validation

Note that, if we try to fake $$y^{'}_i \times R = V^{'}_i$$ it will fail because $$p_i$$ is always derived from the same $$y^{'}_i$$.

1. It will result in an incorrect $$M_i$$ if $$p_i$$ is derived from $$y^{'}_i$$ (on $$SignInterlaced$$) and then calculated with $$Y_i$$ (on $$CheckShare$$).
2. It will result in an incorrect $$M_{r,i}$$ if $$p_i$$ is derived from $$y_i$$ (on $$SignInterlaced$$) and then calculated with $$V^{'}_i$$ (on $$CheckShare$$).

We cannot detach both verifications because they use the same $$\sigma_i = (p_i, c_i)$$, and $$(G, R, Y_i)$$ are known and forced EC points. Incorrect $$(M_i, M_{r,i})$$ will fail due to Fiat–Shamir heuristics.

If this really works, then we are "checking" a second degree constraint without Pairing-Based Cryptography! In PBC, normally this would be checked via $$ê(V_i, G) = ê(y_i \times R, G) = ê(R, y_i \times G) = ê(R, Y_i)$$

However, this is a naive security proof. So I'm posting this here for better scrutiny, if you can help me?

Edit: I saw that this is much similar to what is done here. I think this kind of proves that it works.

From here I can use it for different use-cases:

1. Generate a pseudonym from a piece of public information.
2. Build a distributed key escrow.