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

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?

• Might I enquire what security problem you are trying to solve? Why wouldn't, say, $a_i, \text{Sign}_{pk}(a_i)$ (or something similar) solve whatever problem you're trying to solve (where Sign is a signature generated with private key $pk$, verifiable by a globally accessible public key? – poncho Jul 25 '18 at 19:16
• I have some information that has already been made available to the general public, and I want to provide tags that are validated on public information and unforgeable. Using digital signature and message on a public board allows us to validate a message without generating a tag that ignores our main purpose that produces a trusted token. – rafael Jul 25 '18 at 20:04

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.
• Thanks. I think your method does not need to leak $a'_j$, and with the two valid tags you can generate the third valid tag. What do you think I have to study for the issue "I have some information that has already been made available to the general public, and I want to provide tags that are validated on public information and unforgeable."? – rafael Jul 25 '18 at 20:40