Secret-Sharing
對 Shamir 的秘密共享 SSS 進行暴力攻擊的時間複雜度
我在學術論文中到處搜尋關於對 Shamir 的秘密共享密鑰進行暴力攻擊的時間複雜度。我很困惑是否是 $ O(p^k) $ 或者 $ O(p) $ , 這樣 $ p $ 是加密的模數和 $ k-1 $ 是加密多項式的次數。因為實際上，如果我們要重建加密的多項式，就相當於暴力破解所有 $ p $ 的可能值 $ k $ 係數，這導致 $ O(p^k) $ 算法。但是直接搜尋多項式的常數係數這個秘密，並且知道 $ S<p $ ，導致 $ O(p) $ 算法。誰能告訴我什麼是正確的，如果是 $ O(p^k) $ ，為什麼線性算法不起作用？
我在學術論文中到處搜尋關於對 Shamir 的秘密共享密鑰進行暴力攻擊的時間複雜度。
暴力攻擊是不可能的；即使您可以執行任意計算，使用 $ k-1 $ 共享，您仍然不會獲得有關秘密的任何資訊（假設隨機性用於生成共享；如果它們是通過確定性隨機數生成器生成的，則可以）。
因為實際上，如果我們要重建加密的多項式，就相當於暴力破解所有 $ p $ 的可能值 $ k $ 係數，這導致 $ O(p^k) $ 算法。
不，即使這樣也行不通，因為無法確定您是否找到了正確的多項式；對於秘密的任何可能值，都有相同數量的多項式與之一致。因此，您不會獲得有關該秘密的任何資訊（甚至是機率資訊）。