I wonder if it is possible to devise a function $F(K,S,R_S)\mapsto D$ where:
- $K$ is some key (I have freedom on $K$, it could even be generated by a trusted party);
- $S$ is in $\{0,1\}^s$, say $s=32$; $S$ is a serial number;
- $R_S$ is a random value associated to $S$, in $\{0,1\}^r$, say $16\le r\le48$; $R_S$ is produced from $S$ once for all by a random-like function unknown to adversaries;
- $D$ is a short digest in $\{0,1\}^d$, say $48\le d\le64$.
such that:
- $D=F(K,S,R_S)$ can be computed knowing $K$, $S$, $R_S$, say in at most $2^{28}$ instructions of a typical 32-bit CPU;
- an adversary not knowing $K$, knowing $S$, $R_S$, $S'\ne S$, $R_{S'}$, has no advantage in trying to tell whether some $D$ is $F(K,S,R_S)$ or $F(K,S',R_{S'})$; Update: or better, an adversary with black box access to $(S,R_S)\mapsto F(K,S,R_S)$ for some fixed unknown $K$ can not distinguish that from a random oracle with the property laid below in (4);
- an adversary knowing $K$, and given $D$ known to be $F(K,S,R_S)$ for $S$ chosen at random, with $S$ and the corresponding $R_S$ unknown, has no method much better than brute force to guess $S$ [where brute force enumerates possible ($S$, $R_S$) pairs, computes $F(K,S,R_S)$, and makes a decision based on matches of that with $D$];
- odds that there exists distinct $S$, $S'$ with $F(K,S,R_S)=F(K,S',R_{S'})$ should be as low as possible, and much lower than the birthday bound (about $0.39$ when $7\le d=2s$).
The application is transforming the serial number $S$, and some auxiliary data which limited entropy after hashing is modeled by $R_S$, into a digest that is meaningless to a party not knowing $K$ (property 2), does not directly leak the serial number $S$ to a party knowing $K$ (property 3), and can reliably be used to recognize an object for a given $K$ (property 4). The computation of $F$ will be made as slow as bearable, which will correspondingly increase the cost of brute force in (3).
Things I considered but do not fit:
If $F$ is $H(K||S||R_S)$ with $H$ a random function with $d$-bit output, (4) is not met.
If $F$ is $\operatorname{ENC}_K(S||H(K||R_S))$ with $\operatorname{ENC}_K$ a $d$-bit block cipher with key $K$, and $H$ a random function with $d-s$-bit output, (4) is met with zero odds of collision, but (3) is not met, for an adversary can invert the cipher and find $S$.
If $D$ was wide enough (say $d=2048$), then instead of $\operatorname{ENC}_K$ in the above we could use a deterministic RSA encryption with public keys $K$ generated by a trusted party, and meet both (3) and (4); but I'm considering much smaller $d$.