關於規律度的問題

我一直在閱讀一些關於基於多元系統的密碼學的論文，我有一個問題。如何將計算多元系統的 Gröbner 基 (GB) 的難度與其規律性程度聯繫起來？

據我了解，對於很多密碼系統，都有獲得多項式方程系統的方法，並且此類系統的解決方案將為我們提供密鑰（讓我們假設這是唯一的）。一旦我們有了這樣的系統，我們就可以“線性化”並解決它們（就像在 Arora-Ge 中一樣），或者我們可以通過計算其 GB 並從那裡找到根來攻擊系統。

從 Bardet 的論文中，對於半正則係統，有一個量稱為正則度（也有一種計算方法），她還給出瞭如何使用這個量來估計 GB 計算的難度。

**我的問題是：**如果我們不知道我們的系統是否是半正規的怎麼辦？這種規律性程度似乎是 GB 中程度最高的術語。如果是這樣，我如何估計我手中的多項式系統的 GB 的最高次數項？

似乎有幾篇論文詳細介紹了這些主題，所以如果我也能找到一些論文來閱讀，我會很高興。

對於多元多項式方程的隨機系統，通常接受它是正則或半正則的假設。這裡的“隨機”意味著對每個係數進行均勻採樣。該領域的一個懸而未決的問題是確定隨機系統是正則或半正則的機率，作為變數、方程和度數的函式。這個假設意味著這個機率在密碼學上可以忽略不計，但在證明這一點之前，它在技術上是一個假設。

不幸的是，對於非隨機的多元多項式方程系統，我們甚至沒有這樣的假設，更不用說支持它的嚴格框架了。您可以做的最好的事情是為各種小參數實例化方程組，並觀察經驗規律的程度（如果有的話）與具有相同維度的隨機系統的偏差程度。

話雖如此，在這方面可能有幾個有趣的來源：

1. Faugère 和 Perret 研究了對 UOV 的直接代數攻擊的複雜性，並觀察到所得到的多項式方程組的規律性程度等於隨機方程組的規律性程度。此後，該結果已被用於證明以這種方式攻擊 UOV 與求解隨機方程組相同的更強假設的合理性，這使得複雜性估計和參數選擇成為可能。IACR 電子列印
2. 丁*等人。*研究 Square 系統的第一個下降度，它與規則度相似但略有不同，它們是 $ \mathbb{F}q $ -仿射等價於單項式 $ \mathcal{X}^2 \in \mathbb{F}{q^n}[\mathcal{X}] $ 對於一些奇怪的 $ q $ . 他們得出的結論是，這個學位正是 $ q $ . 這是令人驚訝的，因為通常我們觀察到規律性程度與定義方程的域無關。不幸的是，由於與 Gröbner 基地無關的結構性攻擊，Square 系統是不安全的。科學直接
3. Ding 和多位合著者在 HFE 的背景下研究同一個秋季學位 $ _v^- $ 系統。作為隱藏多項式的次數、添加的醋變數的數量和丟棄的多項式數量的函式，它們實現了第一個下降次數的上限（他們混淆地稱為規律性次數）。不幸的是，這個上限並不嚴格，因此不能用來證明類似 HFE 的系統可能是安全的。Springer Journal page 作者首頁

引用自：https://crypto.stackexchange.com/questions/66393