證明密文集的基數大於或等於對稱密碼系統的明文集的基數
我一直在解決這個問題，希望能得到一些幫助
考慮具有非空有限集的對稱密碼系統 $ P, C, K $ 明文、密文和密鑰，分別具有加密功能 $ e_k : P \rightarrow C $ 和解密函式 $ d_k : C \rightarrow P $ 鍵索引 $ k \in K $ .
顯示 $ |C| \geqq |P| $
這是我的嘗試：
自從 $ d_k $ 是的左逆 $ e_k $ 根據密碼的定義
認為 $ e_k(x) = e_k(y) $ 然後 $ x = d_k(e_k(x)) = d_k(e_k(y)) = y $ 為了 $ x \in P $ 和 $ y \in C $
意義 $ e_k $ 是內射的 $ \forall k \in K $
還， $ e_k(p) = c \in C, \forall p \in P $
假設，對於有限集 $ P $ 和 $ C $ , $ |P| \gt |C| $
而且，由於兩者 $ P $ 和 $ C $ 是非空的，那麼 $ |C| $ 至少為 1 並且 $ |P| $ 至少為 2。
然後 $ \exists a,b \in P $ 英石 $ a \neq b $ 和 $ e_k(x) = e_k(y) $ 這引起了矛盾（因為這意味著 $ e_k $ 不是內射的）
因此， $ P \not\gt C $ IE $ |P| \leqq |C| $ 或者 $ |C| \geqq |P| $
證明開始，結束 $ e_k $ 對所有人都是內射的 $ k $ ，沒問題。只有超級挑剔的人會補充說 $ d_k $ 是的左逆 $ e_k $ 根據密碼的定義，並且該部分的其餘部分認為 $ x $ 和 $ y $ 要點 $ P $ .
根據我的口味，其餘使用反證法的方法過於復雜和循環，而且不夠嚴謹：“那麼 $ \exists a,b \in P $ 英石 $ a \neq b $ 和 $ e_k(x) = e_k(y) $ " 不是很清楚（至少它不是從既定的定義或定理中得出的）。
我會將整個第二部分更改為：根據 cardinality 的定義，注入的目標集的基數至少是其源集的基數。
或者，如果在學術環境中還沒有正式定義基數*：注入的目標集的大小至少是它的源集的大小，通過一個計數參數。*計數參數的概念經常在加密、雜湊衝突或存在證明的上下文中呼叫。
如果我們確實想通過矛盾來證明，可以呼叫鴿子原則，這在加密貨幣中也很常見，其調子如下： $ \lvert C\rvert<\lvert P\rvert $ 和 $ e_k $ 單射將與鴿籠原則相矛盾。