課程名稱︰後量子密碼學 課程性質︰選修 課程教師︰楊柏因 開課學院：電資學院 開課系所︰電機所 考試日期（年月日）︰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分鐘。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.103.99 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1620192030.A.A75.html