“反向”Reed-Solomon 糾錯，給定輸入前綴
我有一個字元串 $ S $ 長度（比如說）34，我知道第一個（比如說）24個字節，但不知道最後一個10個。我也有10個字節的糾錯碼 $ RS_{44,34}(S) $ 在全。我有康復的希望嗎 $ S $ ?
的資訊量 $ S $ 我錯過的遠遠超出了 Reed-Solomon 的理論保證（我認為在這種情況下是 3 個字節），但同時， $ 2^{80} $ 未知部分的可能值 $ S $ ，並且 $ 2^{80} $ 糾錯的可能輸出。如果我們要遍歷未知部分的所有可能值 $ S $ ，我天真地期望其中大約 1 個與糾錯匹配。但 $ 2^{80} $ 太暴力了。
鑑於其 Reed-Solomon EC，是否有任何技術可以恢復（或至少減少其狀態空間）輸入？是否有任何理由認為 RS 在這種意義上是加密安全的？
作為背景，這裡的“現實世界”應用程序是我有一個 QR 碼（版本 2，L 級 EC），其中我沒有主要數據位，但我有 EC 位。我知道數據是特定域上的 URL，因此是前綴。
鑑於其 Reed-Solomon EC，是否有任何技術可以恢復（或至少減少其狀態空間）輸入？
你很幸運——Reed-Solomon 是線性碼，也就是說，糾錯部分是輸入的線性函式，實際上，通過固定輸入的 10 個字節以外的所有字節，它是雙射。
這意味著您可以有效地重建輸入中失去的 10 個字節；高斯消除將起作用，雖然可能有更有效的算法可用，但高斯消除大約需要 $ 10^3 $ 操作，這樣就足夠高效了。
並非所有程式碼都具有 RS 程式碼所具有的良好屬性，即每個 $ k $ 符號是可用於重構原始碼字的資訊集。
那裡有高效的擦除解碼器。擦除意味著某些符號是未知的，而不僅僅是錯誤的。
例如，最近的這篇論文提出了一種有效的 RS 碼在有限域上的解碼算法 $ q $ 元素， $ \mathbb{F}_q $ 和 $ q=2^m, $ 在 $ O(q \log_q q^2) $ 時間。它使用沃爾什變換進行拉格朗日插值。