Are there order-insensitive, constant-space MAC constructions? Are there well-studied MAC or PRF constructions that can authenticate a sequence of strings in a way that:


Is sensitive to the count of each string in the sequence but not their order;
Uses constant space independent of sequence length and string length;
Uses time proportional to the sum of the lengths of the strings in the sequences?


Something like a keyed function $F_k(M) : \{0,1\}^n \times \{0,1\}^{**} \to \{0,1\}^t$, such that if $M$ is any permutation of $[m_1, ..., m_n]$, then $F_k(M) = F_k([m_1, ..., m_n])$.

The most naïve thing I can think of is to XOR of the outputs of a PRF over the individual strings, but that clearly won't do because $F_k([m]) = F_k([m, m, m])$ for any $m$.
Yes. ​ Let p be a large prime that's also bigger than 2$^{\text{output_length_(innerMAC)}}\hspace{-0.03 in}$.

If innerMAC "Uses constant space independent of" message length, then

outerMAC$_p\hspace{-0.03 in}\big(\hspace{.16 in}$k$_{\hspace{.02 in}outer}$ || k$_{\hspace{.02 in}inner}\hspace{.08 in}$,$\hspace{.09 in}$multiset$\hspace{.15 in}\big)$
$=$
PP-MAC$\left(\hspace{-0.07 in}k_{\hspace{.02 in}outer},\left(\hspace{-0.08 in}\left(\displaystyle\sum_{\operatorname{string} \in \operatorname{multiset}} \operatorname{int}\hspace{.02 in}\hspace{-0.04 in}\left(\operatorname{innerMAC}\left(k_{\hspace{.02 in}inner},\hspace{-0.03 in}\operatorname{string}\right)\right)\hspace{-0.08 in}\right) \operatorname{mod} p\hspace{-0.08 in}\right)\right)$

will give such a privacy-preserving MAC.

If additionally PP-MAC is a PRF, then outerMAC$_p$ will also be a PRF.



Since [having a composite affects neither order-independence nor space-usage] and

[security is only computational anyway], it's enough for $p$ to be probably prime. ​ Rather than being hard-coded, such $p$ can be efficiently generated using an additional part of the key, falling back on any large-enough odd number if finding a probable prime takes too long.