What cryptography primitives can help me (generate unforgeable tag)?

Question

I have a read-only public bulletin board that It contains a series of information to form: $$[(a_1,g^{a'_1 \cdot m}), (a_2,g^{a'_2 \cdot m}), \cdots ,(a_n,g^{a'_n \cdot m})] \ ,$$ where $a_i\in\{0,1\}^n$ and $a'_i, m \in \mathbb{F}^*_q$ ($a'_i$ is output a PRF on input $a_i$).

I want to produce tags that are not forgeable, and also are validated by their public information. For example, for pair $((a_i,a_j),t_1,t_2)$, first fetch $(a_i,g^{a'_i \cdot m})$ and $(a_j,g^{a'_j \cdot m})$, and then validate the tags as follows:

$$\big (g^{a'_i \cdot m} \big) ^ {t_1} \stackrel{?}{=} \big (g^{a'_j \cdot m} \big) ^ {t_2}$$

What cryptography primitives can help me?

Answer 1

Assuming that all the $m$ values are the same, then about the only thing to do with the precise verification procedure you specified is to set:

$$t_i = c \cdot {a'_i}^{-1}$$

for some secret constant $c$ (which needs to be the same for every tag).

This would appear to work (and any value of $c$ would work)... until some $a'_j$ value is leaked; then, the attacker could rederive $c$, and thus recover all the $a'_i$ values from the corresponding $t_i$ values.