课程名称︰後量子密码学 课程性质︰选修 课程教师︰杨柏因 开课学院：电资学院 开课系所︰电机所 考试日期（年月日）︰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/cn.aspx?n=bbs/NTU-Exam/M.1620192030.A.A75.html