Proving item association without revealing one of the associated items

Question

I'm a total noob when it comes to cryptography but I believe this falls under the "zero knowledge" category.

I have two associated pieces of information:

1. tag — known by both parties. Unique per scenario.
2. identity — known by only one party. Potentially associated to multiple tags. Comes from a pool known by both parties.

I need a way to prevent the party with the association from changing the value of the identity. There are around 100 concurrent associations per scenario. The pool of potential identities can be relatively small, even smaller than the number of tags, but can be larger too.

The most primitive option would be to hash the tag and identity together but with a possibly small pool of potential identities I fear it would be trivial to brute force the hash...

During the scenario more and more of these associations will become public. At least at that point I should be able to confirm that the other party did not modify the association. I don't really have to confirm this before then, because unrevealed associations are not relevant. I just need to prevent the knowing party from picking and choosing at the time of revealing. And I need to prevent the other party from deducing the identity before the reveal.

Is such a thing even possible? How could it be done? How difficult would it be to implement?

Answer 1

What it sounds like you are looking for is a Commitment Scheme; that is, a way for Alice to compute a 'Commitment' based on a 'value', and publish the 'Commitment' to Bob (or a group of Bobs). Just from the tag, Bob cannot deduce the value (even if he know it's one of a small set of values). However, Alice at some point can 'open' the commitment, revealing the value; Bob can then verify that the revealed value did, in fact, correspond to the value that Alice originally committed to.

If so, well, this is quite well studied territory. The simplest commitment method is based on a secure hash function (say, SHA-256). We have all parties agree on a secure hash function, and the length of large random values (say, 128 or 256 bits) that will be used. To commit to a value, Alice selects a random value for R, and then computes:

Commitment := SHA256( R | Identity )

(where | is string concatination). She then publishes the Commitment as her tag, and saves the value of R she used.

Bob is unable to deduce anything about the identity from the tag; the best thing he can try is to iterate through the possible values of R, and if Alice chose a large enough R, he can't do that.

When it becomes time for Alice to open the commitment (that is, reveal the identity), she publishes both the identity and the value R; Bob can then verify that those two do, in fact, hash to the published tag. He also knows that it is computationally infeasible to find two different values that hash to the same commitment (because that's a property of a cryptographically secure hash function), and so the value that Alice revealed must be the value she originally committed to.

One subtle point in this particular technique: the reason we had all parties agree on the length of R is to prevent Alice from changing her mind about it. If not, then Alice can try to cheat in this way: she might try (for example) to commit to the value 01 02, and use the R value 00 00 00 (note: this R value is too small to be secure, this is just a toy example); and so she would publish SHA256( 00 00 00 01 02 ). However, when it comes time to reveal, she might change her mind, and claim the Identity 00 01 02, and that she used the R value 00 00; this also gives SHA256( 00 00 00 01 02 ), which is the exact same identity. Preventing Alice from changing the length of R after the commitment stops this method of cheating.