是否存在順序不敏感的恆定空間 MAC 結構？
是否有經過充分研究的 MAC 或 PRF 結構可以通過以下方式驗證字元串序列：
- 對序列中每個字元串的計數敏感，但對它們的順序不敏感；
- 使用獨立於序列長度和字元串長度的常量空間；
- 使用與序列中字元串長度之和成比例的時間？
類似鍵控功能的東西 $ F_k(M) : {0,1}^n \times {0,1}^{**} \to {0,1}^t $ , 這樣如果 $ M $ 是任何排列 $ [m_1, …, m_n] $ ， 然後 $ F_k(M) = F_k([m_1, …, m_n]) $ .
我能想到的最幼稚的事情是對單個字元串的 PRF 的輸出進行異或，但這顯然行不通，因為 $ F_k([m]) = F_k([m, m, m]) $ 對於任何 $ m $ .
是的。 設 p 是一個大於 2 的大素數 $ ^{\text{output_length_(innerMAC)}}\hspace{-0.03 in} $ .
如果innerMAC“使用獨立於”消息長度的常量空間，那麼
outerMAC $ _p\hspace{-0.03 in}\big(\hspace{.16 in} $ ķ $ _{\hspace{.02 in}outer} $ || ķ $ _{\hspace{.02 in}inner}\hspace{.08 in} $ , $ \hspace{.09 in} $ 多集 $ \hspace{.15 in}\big) $
$ = $
聚丙烯-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) $
會給這樣一個保護隱私的MAC。
如果另外 PP-MAC 是 PRF，則外層 MAC $ _p $ 也將是 PRF。
自從
$$ having a composite affects neither order-independence nor space-usage $$和
$$ security is only computational anyway $$, 就足夠了 $ p $ 可能是素數。 而不是硬編碼，例如 $ p $ 可以使用密鑰的附加部分有效地生成，如果找到可能的素數需要太長時間，則可以使用任何足夠大的奇數。