A Brief Introduction to Techniques forSolving Lattice-based Quantum-Safe Schemes

Martin R. Albrecht
http://malb.io

Linear System Solving

m×n
Given (A, c) with c ∈ Zm
, s ∈ Znq isq , A ∈ Zq

           c =
  
  
  
  
  ( )or c ←$ U Zmq .

←n →A    × s 

Learning with Errors

m×n
Given (A, c) with c ∈ Zm, s ∈ Znq and small e ∈ Zm isq , A ∈ Zq



  
         c =          ( )or c ←$ U Zmq .

← nA→






      
× s + e 












Parameters• Parameters are:1

• dimension n,• modulus q (e.g. q ≈ n2 ),√• noise size α (e.g. αq ≈ n),• number of samples m.

≈ Pr(x)0.8
0.60.4• Elements of A, s, e, c are in Zq .

0.2

• e is sampled from χαq , adiscrete Gaussian with width

0−10−50x510αqσ=√ .
2πLattice Attacks

Solving?

c=A·s+e
Primal Attack solve Bounded Distance Decoding problem (BDD), i.e.
ﬁnd x s.t. ∥A · x − c∥ is minimised,• via uSVP embedding and lattice reduction or• via Babai’s nearest planes resp. enumeration.
Dual Attack solve Short Integer Solutions problem (SIS) in the left
kernel of A, i.e. ﬁnd a short w such that w · A = 0 andcheck if ⟨w, c⟩ = w · (A · s + e) = ⟨w, e⟩ is short.

Primal Attack (uSVP Version)
There is an unusually short vector in the q-ary lattice)(AT 0(n+1)×(m+1)∈ Zq
B=cT 1since (s | −1) · B = (e | −1) mod q. It will be found by lattice
reduction with block size β if1√
1/dβ · σ ≤ δ02β−d · det(B) .
1
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange A New Hope. In: 25th USENIX Security Symposium, USENIX Security 16. Ed. by Thorsten Holz andStefan Savage. USENIX Association, 2016, pp. 327–343. url: https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/alkim;
Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the
Expected Cost of Solving uSVP and Applications to LWE. Cryptology ePrint Archive, Report 2017/815.
http://eprint.iacr.org/2017/815. 2017.

Small Secrets

Attack doesn’t work when we only have m = n samples, but then theinstance has small secrets.
• Consider the latticeΛ = {v ∈ Zn+m+1 |(A|Im |c) · v ≡ 0 (mod q)}• It contains an unusually short vector (s|e| − 1) since(A|Im |c) · (s|e| − 1) ≡ A · s + e − c ≡ 0 (mod q)• Analysis proceeds as before with d = n + m + 1.

Dual Attack

1. Construct a basis for the (scaled) dual lattice from A, i.e.
{x | x · A ≡ 0 mod q}.
2. Run lattice reduction algorithm to obtain short vectors vi .
3. Check if ⟨vi , c⟩ are small.2

2Daniele Micciancio and Oded Regev. Lattice-based Cryptography. In: Post-QuantumCryptography. Ed. by Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen. Berlin,Heidelberg, New York: Springer, Heidelberg, 2009, pp. 147–191.

Dual Attack: Trade-off
Given an LWE instance characterised by n, α, q and a vector v oflength ∥v∥ such that v · A ≡ 0 (mod q), the advantage ε ofdistinguishing ⟨v, c⟩ from random is close to3 exp(−π(∥v∥ · α)2 ).

log2 (BKZ cost)

400
350
300
250
0102030405060iε = 1/2

3Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In:CT-RSA 2011. Ed. by Aggelos Kiayias. Vol. 6558. LNCS. Springer, Heidelberg, Feb. 2011, pp. 319–339.

Amplifying Advantage()log2 22 i · BKZ cost

To achieve constant advantage, repeat experiment ≈ 1/ε2 times formajority vote.4400

350

0102030405060i

ε = 1/24We can do better by amortising costs: Martin R. Albrecht. On Dual Lattice Attacks Against
Small-Secret LWE and Parameter Choices in HElib and SEAL. In: EUROCRYPT 2017, Part II. ed. byJean-Sébastien Coron and Jesper Buus Nielsen. Vol. 10211. LNCS. Springer, Heidelberg, May 2017,pp. 103–129

Small Secrets

If s is small,• we do not need to ﬁnd v · A ≡ 0 mod q, but any short v such thatv · A = w is short sufﬁces.
• Consider the normal form of the dual attack on LWE
Λ(A) = {(x, y) ∈ Zm × Zn : x · A ≡ y mod q}• Given a short vector (v, w) ∈ Λ(A) compute⟨v, c⟩ = v · (A · s + e) = ⟨w, s⟩ + ⟨v, e⟩Finsage: load("https://bitbucket.org/malb/lwe-estimator/raw/HEAD/estimator.py")
sage: n, alpha, q = 256, 0.000976562500000000, 65537
sage: _ = estimate_lwe(n, alpha, q)
usvp: rop: ≈2^170.4, m:488, red: ≈2^170.4, δ _0: 1.005147, β : 274,
dec: rop: ≈2^159.8, m:459, red: ≈2^159.8, δ _0: 1.005561, β : 243,
dual: rop: ≈2^171.2, m:751, red: ≈2^171.2, δ _0: 1.005048, β : 282,

http://ia.cr/2015/046

d:d:
d:745,715,751,…
…
…