课程名称︰后量子密码学
课程性质︰选修
课程教师︰杨柏因
开课学院：电资学院
开课系所︰电机所
考试日期（年月日）︰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分钟。