Secret-Sharing
打破資訊理論安全的計算複雜性
例如，維基百科提到沙米爾的秘密共享（SSS）具有資訊論安全性。雖然我理解對手沒有足夠的資訊來破壞安全性的概念，但它也必須對應於一些計算複雜性類，不是嗎？假設我是一個對手，我看到了一個 SSS 實例。我有無限的計算能力。我會發現它至少和停止問題一樣難嗎？比那更容易嗎？可以分配哪個類別來破壞這些資訊理論上安全的協議？
這是關於可計算性理論而不是複雜性理論。
停機問題是 CS 中的一個決策問題。來自維基百科的介紹；
在可計算性理論中，停機問題是根據對任意電腦程序的描述和輸入來確定程序是完成執行還是永遠繼續執行的問題。Alan Turing 在 1936 年證明，不可能存在解決所有可能的程序輸入對的停止問題的通用算法。
問題在於，給定程序和程序的輸入，確定程序在使用該輸入執行時是否最終會停止。在這個抽象框架中，程序執行所需的記憶體量或時間沒有資源限制；在停止之前，它可能會花費任意時間並使用任意數量的儲存空間。問題只是給定程序是否會在特定輸入時停止。
這並不意味著問題的所有實例都不可判定$$ * $$. 只是沒有適用於所有可能算法和算法所有可能輸入的通用算法。
在資訊論安全中，SSS 或 OTP 是可計算的，但沒有明確定義的正確答案。是的，無限的能力（或給通用圖靈機足夠的時間）可以計算 SSS 或 OTP 的所有可能解決方案，但如果沒有額外的資訊，就無法從字面上決定解決方案。所以; 沒有資訊沒有解決方案。
有一個重要的區別，Halting 的一些實例是可以判定的$$ * $$但沒有任何 SSS 或 OTP 實例可以有明確的答案（假設設置正確！）。
$$ * $$對於線性有界自動機 (LBA) 或具有有限記憶體的確定性機器，停止問題在理論上是可判定的。