Cryptographically linkable random tokens 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:


The third party should be able to verify the tokens are valid.
Ideally, the third party should be unable to forge tokens.
Tokens must be unique to a single key.
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.