# Keyed digest function with odds of collision below the birthday bound?

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:

1. $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;
2. 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);
3. 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$];
4. 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$.

• Question: can we choose how $R_S$ is derived in a way to help our $F$ function? (assuming, of course, that the adversary in (3) does not know it; if he does, iot looks infeasible) Commented Dec 3, 2013 at 17:47
• Really well written question. [answer removed due to missing (4)] Commented Dec 3, 2013 at 17:52
• minor thought: I would have preferred "Keyed digest function with beyond birthday bound collision resistance?" as a title - the current one confused me as I misunderstood 'under birthday bound' Commented Dec 3, 2013 at 18:13
• @figlesquidge: tried to address the issue with a change of title, making it clear we want low odds of collision
– fgrieu
Commented Dec 3, 2013 at 18:15
• Make $R_s$, $S$, $K$ 256-bits or larger; $F = Scrypt(ENC_K(S || R_s))$ ? Commented Dec 3, 2013 at 19:45

Quite a difficult question. What you seem to need is a one-way permutation $P$. Indeed, suppose you have it of width $d$, then consider the function $$F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S))),$$ where $E$ is any good 64-bit block cipher (say, Simon) and $K_1,K_2$ are derived from $K$. This function $F$ should fulfill (2) because of the encryptions of both sides and (4) because it is a permutation. To satisfy (1) and (3) the permutation $P$ must be moderately easy to compute and difficult to invert.

It is quite hard to construct such permutations on so small domains as 48-64 bits. There are so called trapdoor permutations, which are easily invertible given a secret $K'$. However, this secret can probably be found very quickly in this domain, whether we talk about RSA or HFE.

I would consider algebraic constructions. There are some interesting permutations that have a compact description but no trapdoors, hence usually overlooked by cryptographers. For instance, how about $$\left(X^{2^k}+X+a\right)^{s}+X$$ over $\mathbb{F}_{2^n}$ from a 2010 paper? Here $a$ is a field element, and $s,k$ are integers; restrictions on them are given in the paper. Even though I am not aware of any inversion algorithm, some generic methods like Groebner basis algorithms may find a preimage faster than $2^n$. In this case, if the permutation is fast enough, you may iterate it several times as long as you still conform to property (1).

• Are you aware of any attempt to invert such permutations faster than brute-force? First step would probably be to distinguish the polynomial system from random. Commented Dec 4, 2013 at 23:12
• If $\pi$ is a random permutation, then $\: \pi \circ P \:$ and $\: P\circ \pi \:$ will both be random permutations, $\:$ but $\: \pi \circ P \circ \pi \:$ would not (it has the same parity as P), and I don't see a reason why it would have to be pseudorandom. $\;\;\;$ A possible alternative for P is to implement swap-or-not with $F_i$ given by $\:F_i(\hat{X})$ = [s/b]crypt(salt,i||$\hat{X}$)$\:$, $\:$ although I don't how large of a work factor could be used while still satisfying (1). $\hspace{1.53 in}$
– user991
Commented Dec 4, 2013 at 23:37
• @RickyDemer: good catch, but easily fixed in the context, where we can use $F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S)))$, where $K_1$ and $K_2$ are different extracts of $K$.
– fgrieu
Commented Dec 5, 2013 at 8:29
• My first point was that we can just use $\:F(K,S,R_S) = P(E_k(S,R_S))\:$, $\:$ rather than two encryptions. $\;\;\;$ On the other hand, I now realize that my suggested alternative for P would fail completely, since I forgot about the fact that one could just run swap-or-not's decryption algorithm. $\;\;\;\;\;\;$
– user991
Commented Dec 5, 2013 at 8:36
• Is there any reason to think that the polynomial given here is hard to invert? It looks to me like that paper shows that these polynomials are easy to invert. In particular, it looks like the proofs of Propositions 1 and 2 give an explicit algorithm to find $x$ such that $p(x)=d$ (where $p$ is one of these permutation polynomials). For instance, equation (9) shows how to solve $(x^{2^k}+x+a)^{-l}+x=d$ for $x$, and the displayed equation at the end of Proposition 2 shows how to solve $(x^{2^k}+x+a)^s+x=d$ for $x$. (Cc:ing @fgrieu)
– D.W.
Commented Dec 6, 2013 at 23:50