Lattice-based Cryptography

RLWE (Ring 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

Lattice-Based Cryptography

公钥为 (a, t)

a*s + e = t

随机生成(r, e1)

r*a + e1 = u

r*t + e2 + m = v

明文为m, 密文为 (u, v)

解密

\[ \begin{align}\begin{aligned}v - u*s = r*t + e2 + m - (r*a + e1)*s\\ = r*(a*s + e) + e2 + m - (r*a + e1)*s\\ = m + r*e + e2 - e1*s\end{aligned}\end{align} \]

LWE signature

\[ \begin{align}\begin{aligned}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\end{aligned}\end{align} \]

BLISS (Bimodal Lattice Signature Scheme)

Lattice Signatures and Bimodal Gaussians

Post-quantum Signature Bliss

基础

私钥S, 公钥(T, A)

T = A*S mod q

message digest μ

c = H( A*y mod q, μ )

z = S*c + y

签名 (z, c)

校验 c = H( A*z − T*c mod q, μ) = H( A*S*c + A*y − T*c mod q, μ)

BLISS

A*S = q*I_n mod 2q

签名: y 为随机数 c = H( A*y mod 2q, μ ) b 为随机选取的0/1 z = y + (−1)^b*S*c

校验 c = H( A*z + q*c mod 2q, μ) = H( A*y + (-1)^b*A*S*c + q*c mod 2q, μ)

NTRU

ntru prime

Quantum technology and its impact on security in mobile networks

falcon

falcon

dilithium

dilithium