Bits needed to send parameters of perfect hash functions
If I understand you correctly, the following is the case:

The server has $n$ files in some order $f_1, f_2, \dots, f_n$.
The user also has exactly one of those files, $f_u$, but does not know $u$.
The user and server agree on some protocol beforehand, which does not depend on any of the $f$.
The server gets to communicate some bits of information to the user once, and only in this direction.
From this information the user must be able to find integer $k$ such that $f_k = f_u$.


Based on the above I would choose some strong cryptographic hashing function $H$, and use it to hash all files on the server. Take the $k$-bit prefix of this hash such that all prefixes are unique. Send these in the correct order for $O(kn)$ total complexity.
How big does $k$ need to be in practice? The chance that the first hash is not a duplicate is $1$, the second $1- \frac{1}{2^k}$ chance, the third $1- \frac{2}{2^k}$, etc. We find that none are duplicates as $\prod_{i=0}^{n-1} (1 - i/2^k) \approx e^{-n^2/2^{k+1}}$ by the Birthday paradox. Let's say we're okay with constant chance of failure $\epsilon$, and thus we want $e^{-n^2/2^{k+1}} &gt; 1-\epsilon$, which gives $k \in O(\log(n))$.
Thus our solution uses $O(n \log n)$ bits. You can't beat this (asymptotically) either, because a full permutation worth of information needs to be transferred, which takes $O(\log n!) = O(n \log n)$ bits.