我怎樣才能使 MAC 兩次安全？
讓我們假設 MAC 計算為 $ t = a m + b $ 和 $ a,b,m \in \mathbb{Z}_p $ , $ p $ 主要。 $ a $ 和 $ b $ 表示私有生成密鑰， $ m $ 指消息。
然後，此 MAC 是一次安全的，但不是兩次安全的。一次安全意味著知道一個消息-mac 對的攻擊者只有很小的機會找到具有有效 mac 的單獨消息。兩次不安全意味著當他學習兩對時，他就可以很容易地求解得到的線性方程組的秘密 $ a $ 和 $ b $ .
如何更改 MAC 生成方案以使其具有兩次安全性？
據我了解 $ am $ 和 $ b $ 組件獨立且均勻分佈在 $ [0..p-1] $ ， 作為 $ p $ 是素數。鑑於此，我想我可以添加第三個組件，源自新添加的部分 $ c $ 私鑰，它又是獨立且均勻分佈的。但我不知道怎麼做。
首先，顯然，只需使用類似的東西 $ t = a m + b + c $ 或者 $ t = a m + b + c m $ 不起作用，因為新組件可以與 $ a $ 或者 $ b $ ，因此沒有提供任何有效的好處。
就像是 $ t = a m + b + c m^2 $ 似乎不起作用，因為 $ m^2 $ 沒有均勻分佈在 $ \mathbb{Z}_p $ . （我錯過了什麼嗎？）
另一個想法可能是在生成中添加一個計數器： $ t = a m + b + c i $ 在哪裡 $ i $ 是一個消息計數器。這似乎是兩次安全的 $ p > 2 $ ，但前提是攻擊者不能簡單地使用 $ p $ -分開的消息，顯然共享相同的消息 $ c i $ 零件。這個要求對我來說似乎太高了，所以我不喜歡這個想法。
就像是 $ t = a m + b + c m^2 $ 似乎不起作用，因為 $ m^2 $ 沒有均勻分佈在 $ \mathbb{Z}_p $ . （我錯過了什麼嗎？）
你錯過了一些東西。給出兩種解決方案 $ (m_0, t_0), (m_1, t_1) $ 到方程 $ t = cm^2 + am + b $ （對於未知 $ a, b, c $ )，任何第三種解決方案 $ (m_2, t_2) $ 將有機率保持 $ 1/p $ （假設 $ m_2 \ne m_0, m_1 $ ); 如果 $ p $ 很大，這完全滿足您正在尋找的標準。你可以通過修復看到 $ m_2 $ 並考慮可能 $ t_2 $ 之間的值 $ 0 $ 和 $ p-1 $ ; 對於每一個這樣的 $ t_2 $ 值，有一組獨特的 $ a, b, c $ 使所有三個方程都起作用的值，並且作為 $ a, b, c $ 是隨機生成的（因此任何集合的機率都高於其他集合），這意味著所有可能的 $ t_2 $ 值是等機率的。
這正是使 Shamir Secret Sharing 發揮作用的洞察力。
沒關係 $ m^2 $ 分佈不均。如果它真的困擾您，您可以執行以下操作 $ GF(2^n) $ 而不是 $ GF(p) $ . 在 $ GF(2^n) $ , $ m^2 $ 是均勻分佈的（但是，如上所述，這實際上不是問題）。