Cryptographically linkable random tokens

Question

Are there any algorithms/protocols that let you produce a specific length of random tokens/bits in such a way that you can cryptographically determine which 2 or more tokens/bitstrings where produced using the same seed/key. Is it possible at all?

For example, if I produce these random bits: 12432, 15693, with key A and 57322, 57483 with key B. I want a third party who gets 12432 and 15693 to be able to determine they were both produced under the same key.

I thought of digital signatures as the obvious solution. However digital signatures will be to long for my requirement. I would like the token to be between 10-20 bits long, any pointers will be greatly appreciated.

Requirements:

1. The third party should be able to verify the tokens are valid.
2. Ideally, the third party should be unable to forge tokens.
3. Tokens must be unique to a single key.

Answer 1

A full solution is impossible. If the third party is able to verify the validity of tokens, they can brute force through the 10-20 bit token space and generate all valid tokens. So the third party cannot both be able to validate and not be able to forge. The below solution achieves one of the two.

Tie each secret key $k_i$ to an identifier $i$. Generate tokens of the form $i||H(k_i, x)$ where $x$ is a small value. $H$ could be e.g. HMAC-SHA256 truncated to ~16 bits. For uniqueness, the generator should discard any value that collides with one before it ($x < x'$). This is still very fast due to the small domain.

Anyone who does not know the key cannot verify if the token is valid, but can look at the first bits to see whose it is if valid. Someone who has the key can iterate values of $x$ until they find one that matches or they quit (at some defined upper bound like $2^{8}$). The upper bound and the token length determine the probability that a forgery can be generated by using a random bitstring – with 8 and 16 bits the probability is about $2^{-8}$.

If the third party is trusted and the tokens generated under different keys are allowed to collide, the identifier $i$ can be omitted. Then you cannot uniquely determine who generated a particular value, however.

---

With a small block cipher the collisions above could be avoided. However, implementing such a block cipher securely would in my opinion be more complex than just checking for collisions. With a larger number of tokens it might not be the case.

Answer 2

I see 2 options that fit the requirement (small, verifiable within some limit).

Because the sizes are small, the probability of the collision of a random value showing linked is high, larger values will obviously help.

Option 1 is to have a random value, and encrypt or hash it, then truncate the result and concatenate to the original value. The size of the value limits the pool of available tokens, and the size of the truncated output limits the probability of a collision. For example:

$A$ is a random or sequential 14-bit value, $B = HMAC_k(A)$ truncated to 16-bits.
$A || B$ is a 30-bit (5 character base64 encoded) token that can be easily verified as being linked to $k$, with a pool of 16384 maximum tokens linkable to $k$

Option 2 is to encrypt the entire value using a block cipher, and limit the inputs to a small subset of the available plaintext space. Upon decryption, only values that fall into that space will be considered valid. The cipher must have a small enough block size for your application, which limits available choices to those designed for low resource systems, like SPECK with a 32-bit block size.