Public-Key
比較強假設和弱假設
如果我不得不爭論假設 A 比 B 強，我應該這樣爭論：-
攻擊者破壞 A 的安全性並不能轉化為破壞 B 的安全性。但是，如果攻擊者破壞了 B 的安全性，它也可以破壞 A。
正確的？或者，還有其他方法可以比較強假設與弱假設。
是的你是對的。基本上當我們說 $ A $ 是一個比 $ B $ , 我們的意思是那個假設 $ A $ 暗示假設 $ B $ . $ A $ 暗示 $ B $ 告訴我們：
- 如果 $ A $ 是真的，那麼 $ B $ 一定是真的。
$ A $ 暗示 $ B $ 也相當於 $ \neg B $ 暗示 $ \neg A $ ， 因此
- 如果 $ B $ 是假的，那麼 $ A $ 一定是假的。
在密碼學中，假設通常與某些問題的難度有關。在這種情況下，更強的假設是“更容易”的問題，可以簡化為更弱的假設，即“更難”的問題（解決更難的問題意味著更容易的問題也可以解決）。例如，假設我們有以下兩個假設：
- $ A $ : 分解一個整數 $ n $ 很難；
- $ B $ : 分解一個整數 $ n $ 只有大的素因數是困難的。
顯然，如果 $ A $ 是真的，那麼 $ B $ 是真的; 如果 $ B $ 是假的， $ A $ 是假的。如果我們能解決 $ B $ 那麼我們可以使用求解的算法 $ B $ 解決 $ A $ .