我們能解決隱藏數字問題嗎高飛_(2n)GF(2n)GF(2^n)?
是否可以解決擴展欄位中的隱藏數字問題？特別是在 $ GF(2^n) $ ?
假設攻擊者知道一些最低/最高有效位 $ r_i = a_i \times k $ 在給定的領域 $ GF(2^n) $ ，對於許多均勻分佈且已知的 $ a_i $ 和一個固定的和未知的 $ k $ . 是否有可能恢復 $ k $ ?
據我所知，這是最初由 Boneh 和 Venkatesan 引入的隱藏數字問題的一個實例，主要用於破壞數字簽名方案，提供了幾個簽名和各自隨機數的部分知識。
據我所知，HNP一直應用於 $ GF(p) $ ，此外，用於解決它的技術，通過格子和最近向量問題，恕我直言，不容易適應 $ GF(2^n) $ .
問題背後的理由（不需要回答）：
我在一個特定的、純粹假設的場景中比較了 GCM 和 Poly1305 的身份驗證，其中攻擊者在最終添加加密的 nonce 之前獲得了一些關於身份驗證函式結果的資訊。
假設我們有單個塊消息。
Poly1305 身份驗證（不添加加密隨機數）只是： $ (c\times r)\mod {2^{130}-5} $ 在哪裡 $ c $ 是消息塊和 $ r $ 是身份驗證密鑰。我可以看到如何應用 HNP 來解決 $ r $ 在這種情況下。
但是 GCM 執行（我假設使用硬體加速器，以便我可以在提供帶有 aad 和有效負載大小的最終消息時作弊）： $ (c\times h) \mod {x^{128}+x^7+x^2+x+1} $ 在哪裡 $ h $ 是 GHASH 密鑰。我不知道如何解決 $ h $ , 有幾個不同的和已知的結果的部分資訊 $ c $ .
是的，它似乎可以在實際時間內解決 $ GF(2^n) $ ，如果攻擊者得到 $ n+\epsilon $ 隨機的 $ a_i $ 值，即使他得到了一點 $ a_i \times k $ 價值觀。
主要的觀察是映射從 $ a_i $ 咬 $ j $ 的 $ a_i \times k $ （我將其稱為 $ bit_j(a_i \times k) $ ) 是按位線性的（對於常數 $ j $ , $ k $ ).
所以，假設我們有 $ a_i $ 和相應的 $ bit_m(a_i \times k) $ 值（對於一些已知的 $ m $ )，我們的第一步是找到 $ n $ 線性無關 $ a_i $ 值（其中，給定 $ n+\epsilon $ 隨機的 $ a_i $ 值，我們很有可能擁有）；我們將其視為一組 $ n $ 線性方程組，並求解它們 $ O(n^3) $ 時間，給我們任何值之間的映射 $ a $ 和 $ bit_m(a \times k) $
現在，對於多項式表示 $ GF(2^n) $ , 對於每個 $ i, j $ 對，有一個常數 $ c_{i,j} $ 在哪裡 $ bit_i(a) = bit_j(a \times c_{i,j}) $ 對所有人 $ a $ .
這個觀察使我們能夠找到線性映射 $ bit_n(a \times k) $ 對於任何 $ n $ ， 作為 $ bit_n(a \times k) = bit_m(a \times k \times c_{n,m}) = bit_m( (a \times c_{n,m} ) \times k ) $ ; 換句話說，為了執行這個映射，我們將向量乘以常數 $ c_{n,m} $ ，然後應用我們已經知道的映射（兩者都是線性運算）。
結果是 $ n $ 線性地圖給了我們所有人 $ n $ 產品的一部分。然後，我們可以解決這些 $ n $ 輸入的線性映射，為 lsbit 映射提供 1 位，其餘為 0；解決方案是 $ k^{-1} $ ，這立即給了我們價值 $ k $ .
我懷疑有明顯更有效的方法來解決這個問題；但是這個算法應該足以回答這個問題。