課程名稱︰後量子密碼學
課程性質︰選修
課程教師︰楊柏因
開課學院：電資學院
開課系所︰電機所
考試日期（年月日）︰2021/04/30
考試時限（分鐘）：158
試題 :
PQC 期中考, 本卷作答時間 2h 總分為 200 最高可得分上限為 150。
1. 想要求 X^-1 mod B^n 時經常使用 Hensel lifting (共 40 分)
a. 解釋何為 Hensel Lifting, 並說明它和 Newton's Method 的關係 (10分)
b. 試求 4591^-1 mod 10000 (5分)
c. 試求 4591^-1 mod 65536, 其中 65536 = 2^16 (10分)
d. 有環 R = Z_256[x]/(x^5-1), 即 Z[x] mod 256 mod (x^5-1),
試在 R 中求 (x^3+x^2+1)^-1 (15分)
e. 承上, 為什麼這題不是求 (x^2+1)^-1 或 (x^3+2x+1)^-1 ? (10分)
2. 試說明基本操作 (生成 Keys, 加密, 解密), 共 20 分
a. NTRU (共10 分)
b. Ring-LWE Ctyptosystem (10 分)
3. (共60分)今欲計算環 R = Z_4591[x]/(x^761-x-1) 中的乘法, 試說明
a. 何為 Karatsuba 乘法, 如果遞迴的進行, 其計算複雜度為何？ (10分)
b. 何為 Toom-3 乘法, 如果遞迴的進行, 其計算複雜度為何？ (10分)
c. 關於 NTT 的多項式乘法 (此子題共 40 分)
i. 要用 (complete) NTT計算 Z_q[X]/(X^(2^k)-1) 的乘法, 則 q 有什麼限制?
過程如何? 為何用到 Cooley-Tukey 和 Gentleman-Sande Butterfly? (10分)
ii. 以 R => Z_4591[x] => Z_4591[x]/(x^n-1) 再用 NTT 計算R的乘法,
則 n 有什麼限制? 現在 n 應取多少? (10分)
iii.以 Z_8192[x]/(x^256+1) => Z[x]/(x^256+1)=>Z_q[x]/(x^256+1)
再用 NTT 計算 Z_8192[x]/(x^256+1) 的乘法, 則 q 有什麼限制? (5分)
iv. 簡述何為 Good's Trick (5分) incomplete NTT trick (5分) Twisting (5分)
4. Barrett Reduction (共30 分)
a. 說明何為 (signed 和 unsigned) Barrett reduction (10分)
b. 假設你的微處理機結構提供 32x32+64 bit 的乘帶加法,
那麼 mod 4591 的 Barrett 乘數應取多少?
123456 對 4591 的 Barrett reduction 為多少? (10分)
c. 為何 Barrett reduction 答案不見得正確?
要多大的 n, 用 Barrett reduction 才會得到錯誤的答案 (10分)
5. Montgomery Reduction (共 50 分)
a. 簡述何為 (signed 和 unsigned) Montgomery Reduction (10 分)
b. 請說明你剛剛說的那個 MR 其結果(在怎樣條件下)落在哪個區間 (10 分)
c. 實用上, 假設我要用 R=2^2048 來對 mod 一個 2048 bit 的奇數 N=pq 做
Montgomery式的計算, 那麼我一定需要算出一個 2048 bit 的乘數嗎?
如果不是, 為何? (5 分)
d. 承上, 要計算 (135 x 246 / 1000) mod 997
(10 分, 但用 c. 方法計算可得 15 分)
e. 計算 12345678 對 4591 的 Montgomery reduction, R=2^16 (10 分)
6. Bonus Questions
a. (5分) 說明量子密碼學與後量子密碼學之不同
b. (5分) 今有向量 (3,4,12) 和 (5,8,25), 試求出其 Lattice 的最短向量
◎ 可帶一頁雙面手寫A4筆記和計算機，考試時間延長38分鐘。