A function \(f\colon X\to Y\) is a map that associates an element \(y\in Y\) to each element \(x\in X\). We write \(f(x)=y\) and \(f(X)=\{f(x):x\in X\}\subseteq Y\) for the image of \(f\) in \(Y\). We say \(f\) is

  • injective when each \(x\in X\) maps to a distinct \(y\in Y\), i.e. \(f(x)=f(x')\iff x=x'\),

  • surjective when for each \(y\in Y\) there exists at least one \(x\in X\) that maps to \(y\), i.e. \(f(X)=Y\),

  • bijective when it is both injective and surjective.

(i) 判斷五個函數

For each function below determine whether it is injective, surjective, bijective or none.

  1. \(f\colon\{1,2\}\to\{1,2,3\}\), \(f(1)=1\), \(f(2)=3\).

  2. \(g\colon\{1,2\}\to\{1,2,3\}\), \(g(1)=1\), \(g(2)=1\).

  3. \(h\colon\{1,2,3\}\to\{1,2\}\), \(h(1)=1\), \(h(2)=2\), \(h(3)=1\).

  4. \(i\colon\{1,2,3\}\to\{1,2,3\}\), \(i(1)=1\), \(i(2)=3\), \(i(3)=2\).

  5. \(j\colon\{1,2,3\}\to\{1,2\}\), \(j(1)=1\), \(j(2)=1\), \(j(3)=1\).

(i) 的五個函數。單射：箭頭不合流；滿射：右側每點都被指到。

C0.8cmL2.3cmL2.3cmL2.0cmL5.4cm & 單射？ & 滿射？ & 結論 & 理由
a. \(f\) &  是 &  否 & 單射 & \(f(1)=1\ne3=f(2)\)；\(2\in Y\) 沒有原像，\(f(X)=\{1,3\}\ne Y\)
b. \(g\) &  否 &  否 & 都不是 & \(g(1)=g(2)=1\) 但 \(1\ne2\)；\(2,3\) 無原像
c. \(h\) &  否 &  是 & 滿射 & \(h(1)=h(3)=1\)；\(h(X)=\{1,2\}=Y\)
d. \(i\) &  是 &  是 & 雙射 & 三個輸出 \(1,3,2\) 互異且恰好用完 \(Y\)；\(i\) 是對調 \(2,3\) 的排列，\(i^{-1}=i\)
e. \(j\) &  否 &  否 & 都不是 & 常數函數：三個輸入撞在 \(1\)；\(2\) 無原像

觀察：a 與 b 的定義域比對應域小（\(2<3\)），所以不可能滿射；c 與 e 的定義域比對應域大（\(3>2\)），所以不可能單射；只有 d 的兩邊一樣大，才有機會雙射。這就是 (ii) 要證明的一般定理。

(ii) 單射、滿射與集合大小

Let \(X\) and \(Y\) be finite sets. Prove that if \(f\colon X\to Y\) is injective then \(\abs{Y}\ge\abs{X}\). Prove that if \(f\) is surjective then \(\abs{X}\ge\abs{Y}\). Prove that if \(f\) is bijective then \(\abs{X}=\abs{Y}\).

令 \(X=\{x_1,\dots,x_s\}\)（\(s\) 個互異元素）、\(\abs{Y}=t\)。

（1）單射 \(\Rightarrow\abs{Y}\ge\abs{X}\)。考慮 \(f(x_1),f(x_2),\dots,f(x_s)\in Y\)。因為 \(f\) 單射，\(x_a\ne x_b\Rightarrow f(x_a)\ne f(x_b)\)，所以這 \(s\) 個元素兩兩相異。\(Y\) 至少包含這 \(s\) 個相異元素，故 \(t=\abs{Y}\ge s=\abs{X}\)。 （等價說法：\(f\) 把 \(X\) 一一對應到它的像 \(f(X)\)，所以 \(\abs{f(X)}=\abs{X}\)；又 \(f(X)\subseteq Y\)，所以 \(\abs{X}=\abs{f(X)}\le\abs{Y}\)。）

（2）滿射 \(\Rightarrow\abs{X}\ge\abs{Y}\)。因為 \(f\) 滿射，每個 \(y\in Y\) 至少有一個原像；對每個 \(y\) 選定一個原像，記為 \(g(y)\in X\)，使 \(f(g(y))=y\)。這定義了函數 \(g\colon Y\to X\)。\(g\) 是單射：若 \(g(y)=g(y')\)，兩邊套 \(f\) 得 \(y=f(g(y))=f(g(y'))=y'\)。對 \(g\) 套用（1），得 \(\abs{X}\ge\abs{Y}\)。 （直接的鴿籠說法：\(Y\) 的 \(t\) 個元素各需要至少一個不同的「箭頭」，而每個 \(x\) 只射出一支箭，所以箭至少 \(t\) 支，即 \(s\ge t\)。）

（3）雙射 \(\Rightarrow\abs{X}=\abs{Y}\)。雙射同時單射與滿射，由（1）\(\abs{Y}\ge\abs{X}\)、由（2）\(\abs{X}\ge\abs{Y}\)，故相等。

  • 鴿籠原理（(1) 的逆否）：若 \(\abs{X}>\abs{Y}\)，任何 \(f\colon X\to Y\) 都不是單射——必有兩個輸入撞在一起。

  • 有限等大集合上三者等價：若 \(\abs{X}=\abs{Y}<\infty\)，則 \(f\) 單射 \(\iff\) 滿射 \(\iff\) 雙射。（單射時像有 \(\abs{X}=\abs{Y}\) 個元素，填滿 \(Y\)；滿射時若有兩輸入相撞，像至多 \(\abs{X}-1<\abs{Y}\) 個，矛盾。）這在 (iv) 很好用。注意對無限集合不成立：\(n\mapsto 2n\) 在 \(\N\) 上單射但不滿射。

題目背景：無歧義解密

Decryption is unambiguous when, given the secret key \(\sk\), it is possible to recover the encrypted message from the ciphertext. This is required for correctness. We consider necessary conditions on \(\Enc(\sk,\cdot)\) as a function. When decryption is not unambiguous we say it is ambiguous. Let \(\SKE=(\KGen,\Enc,\Dec)\) with message and ciphertext spaces \(\calM\), \(\calC\). For a fixed \(\sk\) let \(\Esk\colon\calM\to\calC\), \(\Esk(m)=\Enc(\sk,m)=c\).

把「無歧義」翻成數學：對每個合法密文 \(c\in\Esk(\calM)\)，恰有一個 \(m\) 使 \(\Esk(m)=c\)，於是「知道 \(\sk\) 就能還原 \(m\)」有意義；否則，即使知道 \(\sk\)，看到 \(c\) 也不知道是哪一個 \(m\)——\(\Dec\) 是確定性函數，只能輸出一個值，對另一個訊息正確性必然失敗。

(iii) 滿射但有歧義

Give an example of a message space \(\calM\), a ciphertext space \(\calC\) and a surjective \(\Esk\) for which decryption is ambiguous. (Hint: imagine a situation where, even knowing the secret key, it is impossible to know which message was encrypted.)

最小例子：\(\calM=\{0,1\}\)，\(\calC=\{0\}\)，\(\Esk(m)=0\)（對任何金鑰、任何訊息都輸出同一個密文）。

  • 滿射：\(\calC\) 唯一的元素 \(0\) 被打到，\(\Esk(\calM)=\{0\}=\calC\)。

  • 有歧義：收到 \(c=0\)，即使知道 \(\sk\)，訊息可能是 \(0\) 也可能是 \(1\)。確定性的 \(\Dec(\sk,0)\) 只能回其中一個，對另一個訊息 \(\Dec(\sk,\Esk(m))\ne m\)，正確性失敗。

稍微「像加密」的例子：\(\calM=\bits^2\)，\(\calC=\bits\)，\(\calK=\bits\)，\(\Esk(m_1m_2)=m_1\oplus\sk\)（把第二個位元丟掉）。滿射（\(\sk\oplus0\) 與 \(\sk\oplus1\) 給出 \(0,1\) 兩個密文），但 \(m_1 0\) 與 \(m_1 1\) 加密成同一個 \(c\)，第二個位元的資訊永遠消失。

有歧義的本質是不單射：兩個訊息撞到同一個密文。滿射與此無關——(iii) 與 (iv) 合起來說明「滿射」既不保證也不妨礙無歧義。

(iv) 滿射且無歧義

Give an example of a message space \(\calM\), a ciphertext space \(\calC\) and a surjective \(\Esk\) for which decryption is unambiguous.

例 1（單字母 Caesar）：\(\calM=\calC=\calK=\Z_{26}=\{0,\dots,25\}\)，\(\Esk(m)=m+\sk\bmod26\)。

  • 滿射：對任何 \(c\)，\(m=c-\sk\bmod26\) 滿足 \(\Esk(m)=c\)。

  • 無歧義：\(\Esk(m)=\Esk(m')\Rightarrow m+\sk\equiv m'+\sk\Rightarrow m\equiv m'\pmod{26}\)，單射。\(\Dec(\sk,c)=c-\sk\bmod26\) 對每個 \(c\) 恰好還原唯一的 \(m\)。

例 2（一次性密碼本）：\(\calM=\calC=\calK=\bits^n\)，\(\Esk(m)=m\oplus\sk\)。它是對合（\(\Esk\circ\Esk=\mathrm{id}\)），因此是雙射：滿射且單射。

兩個例子裡 \(\abs{\calM}=\abs{\calC}\) 有限，由 (ii) 的推論，滿射自動蘊含單射，所以無歧義。

(v) 無歧義 \(\Rightarrow\) 單射 \(\Rightarrow\abs{\calC}\ge\abs{\calM}\)

Prove that if decryption is unambiguous then \(\Esk\) is injective. What can you conclude about the sizes of \(\calM\) and \(\calC\) if they are both finite?

若 \(\SKE\) 對金鑰 \(\sk\) 的解密無歧義（等價地，正確性對 \(\sk\) 成立），則 \(\Esk\colon\calM\to\calC\) 是單射。因此若 \(\calM,\calC\) 有限，\(\abs{\calC}\ge\abs{\calM}\)。

Proof. 用反證法。假設 \(\Esk\) 不是單射：存在 \(m\ne m'\) 使 \(\Esk(m)=\Esk(m')=c\)。 解密無歧義（正確性）要求 \(\Dec(\sk,\Esk(m))=m\) 且 \(\Dec(\sk,\Esk(m'))=m'\)。但兩者的輸入都是 \((\sk,c)\)，而 \(\Dec\) 是確定性函數，對同一輸入只能有一個輸出，所以 \(m=\Dec(\sk,c)=m'\)，與 \(m\ne m'\) 矛盾。故 \(\Esk\) 單射。

若 \(\calM,\calC\) 有限，對單射 \(\Esk\colon\calM\to\calC\) 套用 (ii) 的（1），得 \(\abs{\calC}\ge\abs{\calM}\)：密文空間至少要和訊息空間一樣大。這就是講義 p. 10 註腳預告的 \(t\ge s\)。 ◻

  1. 隨機化加密膨脹得更多。若 \(\Enc(\sk,m;\rho)\) 隨機化，無歧義要求不同訊息的密文集合互不相交：\(\Esk(m,\calR)\cap\Esk(m',\calR)=\varnothing\)。於是 \(\abs{\calC}\ge\sum_m\abs{\Esk(m,\calR)}\)。若每個 \(\rho\) 給不同密文（例如密文包含 nonce），\(\abs{\calC}\ge\abs{\calM}\cdot\abs{\calR}\)——這是隨機化加密「密文比明文長」（ciphertext expansion）的根本原因，也是 IND-CPA 的代價。

  2. 單射是「每把金鑰各自」的要求。定理只說對固定 \(\sk\)，\(m\mapsto\Enc(\sk,m)\) 單射；它沒有說 \((\sk,m)\mapsto\Enc(\sk,m)\) 單射。事實上安全性需要跨金鑰的碰撞：一次性密碼本裡每個 \(c\) 都能由每個 \(m\)（配上某把金鑰）產生，正是這一點讓敵手無從分辨。

  3. 計數。由命題 [prop:counting]，合法的 \(\Esk\) 只能是 \(\binom{t}{s}s!\) 個單射之一，而非全部 \(t^s\) 個函數。

(vi) 單射、非滿射、無歧義：最小的必要假設

Give an example of a message space \(\calM\), a ciphertext space \(\calC\) and an injective \(\Esk\) that is not surjective for which decryption is unambiguous. Conclude with a minimal necessary assumption for unambiguous decryption.

例子：\(\calM=\bits\)，\(\calC=\bits^2\)，\(\calK=\bits\)， \[\Esk(m)=(m\oplus\sk)\concat 0 ,\qquad \Dec(\sk,\ c_1c_2)=\begin{cases} c_1\oplus\sk & \text{若 } c_2=0,\\ \bot & \text{若 } c_2=1.\end{cases}\]

  • 單射：\(\Esk(m)=\Esk(m')\Rightarrow m\oplus\sk=m'\oplus\sk\Rightarrow m=m'\)。

  • 非滿射：像 \(\Esk(\calM)=\{00,10\}\)；\(01\) 與 \(11\) 永遠不會被產生。

  • 無歧義：對合法密文 \(c=(m\oplus\sk)0\)，\(\Dec\) 回 \(c_1\oplus\sk=m\)，正確；對非法密文回 \(\bot\)——這正是定義裡 \(\bot\) 的用途。

結論（最小必要假設）：無歧義解密所需的全部條件是

它是必要的（定理 [thm:unambiguous-injective]），也是充分的：給定單射 \(\Esk\)，定義 \(\Dec(\sk,c)=\Esk^{-1}(c)\)（當 \(c\in\Esk(\calM)\)，原像唯一）、否則 \(\bot\)，即得正確的 \(\Dec\)。因此它是「最小」的：不能再弱（去掉就錯），也不需再強。不需要滿射、不需要 \(\abs{\calC}=\abs{\calM}\)、不需要跨金鑰的單射。

定理說單射保證 \(\Esk^{-1}\) 存在，但沒說它容易算。一個單射函數可能在知道 \(\sk\) 的情況下仍然難以反算——這聽起來奇怪，卻是 Problem 3 (ii) 的主題（碼書的右欄沒有排序，反查要線性搜尋），也是「單向函數」概念的雛形：正向容易、反向困難的單射。好的加密方案要求 \(\Dec\) 和 \(\Enc\) 一樣有效率，這是定義裡「演算法」一詞隱含的要求（PPT）。