PQC: Lattice-based
参考
Practical Aspects of Modern Cryptography
A Decade of Lattice Cryptography
Summer School on real-world crypto and privacy
NIST Cryptographic Standards and Guidelines
ETSI Quantum Safe Cryptography and Security
ETSI Implementation Security of Quantum Cryptography
Lattice Based Cryptography for Beginners
2019 Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process
RLWE (Ring Learning With Errors) Problem
Introduction to post-quantum cryptographyand learning with errors
Equivalence of Search and Decisional (Ring-) LWE
Learning With Errors (LWE) and Ring LWE
Python and Crypto: Learning With Errors (LWE) and Ring LWE
The Learning with Errors Problem
在F_q有限域上的多项式 p(x) 环
b_i(x) = a_i(x) * s(x) + e_i(x)
search LWE problem: 已知(b_i(x), a_i(x))求解s(x)是困难的
Decision LWE problem: 已知(b_i(x), a_i(x))，检查是否可以求解s(x)，还是随机pair
RLWE-KEX
Ring Learning With Errors for Key Exchange (RLWE-KEX)
b_A(x) = A * s_A(x) + e_A(x)
b_B(x) = A * s_B(x) + e_B(x)
两边交换b_A(x), b_B(x)
share_A = s_A(x) * b_B(x) / p(x) = s_A(x) * (A * s_B(x) + e_B(x)) / p(x)
share_B = b_A(x) * s_B(x) / p(x) = s_B(x) * (A * s_A(x) + e_A(x)) / p(x)
LWE encryption
Directions in Practical Lattice Cryptography Vadim Lyubashevsky IBM Research – Zurich.
On Ideal Lattices andLearning With Errors Over Rings
公钥为 (a, t)
a*s + e = t
随机生成(r, e1)
r*a + e1 = u
r*t + e2 + m = v
明文为m, 密文为 (u, v)
解密
v - us = rt + e2 + m - (ra + e1)s
= r(as + e) + e2 + m - (ra + e1)s
= m + re + e2 - e1s
LWE signature
t = a*s + e
c = H( a*u + v, m )
z = s*c + u
a*z - t*c = a*(s*c + u) - (a*s + e)*c = a*u - e*c
BLISS (Bimodal Lattice Signature Scheme)
Lattice Signatures and Bimodal Gaussians
基础
私钥S, 公钥(T, A)
T = A*S mod q
message digest μ
c = H( A*y mod q, μ )
z = S*c + y
签名 (z, c)
校验 c = H( Az − Tc mod q, μ) = H( ASc + Ay − Tc mod q, μ)
BLISS
A*S = q*I_n mod 2q
签名 y 为随机数 c = H( Ay mod 2q, μ ) b 为随机选取的0/1 z = y + (−1)^bS*c
校验 c = H( Az + qc mod 2q, μ) = H( Ay + (-1)^bASc + q*c mod 2q, μ)
