1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – poncho Jul 25 '18 at 19:16
  • $\begingroup$ 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. $\endgroup$ – rafael Jul 25 '18 at 20:04
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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."? $\endgroup$ – rafael Jul 25 '18 at 20:40
  • $\begingroup$ Perhaps if you make the 'tags' the signature of the published values, that would work... $\endgroup$ – poncho Jul 25 '18 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.