為什麼要求公鑰和私鑰的長度至少為安全參數？
在 Jonathan Katz 和 Yehuda Lindell 的現代密碼學導論（第 3版）中，例如簽名的密鑰生成器有
密鑰生成算法 $ \mathsf{Gen} $ 將安全參數作為輸入 $ 1^n $ 並輸出一對密鑰 $ (\mathrm{pk},\mathrm{sk}) $ . 這些分別稱為公鑰和私鑰。**我們假設 $ \mathrm{pk} $ 和 $ \mathrm{sk} $ 每個至少有長度 $ n $ ,**那 $ n $ 可以從 $ \mathrm{pk} $ 或者 $ \mathrm{sk} $ .
我明白為什麼最小尺寸 $ \mathrm{pk} $ 和 $ \mathrm{sk} $ 必須與 $ n $ （有一些最低費率）以滿足任何合理的安全定義，但不是為什麼要這樣做。
您可能熟悉提供輸入的約定 $ 1^n $ 以一種算法來表示“該算法允許在多項式時間內執行 $ n $ .” 假設您正在撰寫有關加密方案的文章，並且希望對此非常精確。您會寫：
- $ \textsf{KeyGen}(1^n) \to (sk,pk) $
- $ \textsf{Enc}(1^n, pk, m) \to c $
- $ \textsf{Dec}(1^n, sk, c) \to m $
現在假設你知道（或堅持） $ |pk| \ge n $ 和 $ |sk| \ge n $ ， 然後 $ n $ 可以通過查看有效地計算 $ pk $ , $ sk $ . 然後 $ 1^n $ 可以省略作為輸入 $ \textsf{Enc} $ 和 $ \textsf{Dec} $ 不失一般性：這些算法有足夠的資訊和執行時間預算來有效地重構字元串 $ 1^n $ 如果需要的話。簡而言之，這個要求在不犧牲任何嚴謹性的情況下簡化了符號。
它也可以堅持 $ |sk|, |pk| $ 是 $ \Omega(n^c) $ , 所以任何多項式函式 $ |sk| $ 也是一個多項式函式 $ n $ . 基本上， $ |sk|, |pk| $ 不能指數級地小於 $ n $ . （事實是 $ \textsf{KeyGen} $ 是多項式時間算法已經意味著 $ |sk|,|pk| $ 不能以指數方式大於 $ n $ .)