# 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:

1. Is sensitive to the count of each string in the sequence but not their order;
2. Uses constant space independent of sequence length and string length;
3. 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$.

• How about instead of XOR'ing the PRF outputs of the individual strings, you add them in a large prime finite field (e.g. modulo $2^{127}-1$), and then send that sum through a finalization PRF? You need to make some additional assumptions on your PRF, but it sounds workable... – poncho Nov 19 '16 at 2:02

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.

• Wow. Except for the formula hurting my eyes (which is probably due to the formula rather than the formatting) this is an amazingly informative answer. – Maarten Bodewes Nov 19 '16 at 14:30
• The formula mostly matches with what poncho's comment described, although this answer is mostly-independent of that comment. ​ (Rereading his comment let me notice that overall outputs can be greater than p.) ​ ​ ​ ​ – user991 Nov 19 '16 at 15:15
• Maybe it's better to write this down as separate steps or pseudo code than one big formula. There's little wrong with the answer or the formula itself, but combined with the limited MathML support for $\TeX$ it gets a bit messy. – Maarten Bodewes Nov 19 '16 at 15:40