Lattice-Based Cryptography: Theory and Encryption Schemes

Lattice-Based Cryptography: From Practice to Theory to Practice Vadim Lyubashevsky INRIA / CNRS / ENS Paris (September 12, 2011)

La Cryptographie Reposant sur les Rseaux: de la Pratique la Th orie la Pratique Vadim Lyubashevsky INRIA / CNRS / ENS Paris (Septembre 12, 2011)

Lattice-Based Encryption Schemes 1. NTRU [Hoffstein, Pipher, Silverman 98] 2. LWE-Based [Regev 05] 3. Ring-LWE Based [L, Peikert, Regev 10] 4. NTRU-like with a proof of security [Stehle, Steinfeld 11]

Cryptosystmes Reposant sur les R seaux 1. NTRU [Hoffstein, Pipher, Silverman 98] 2. Reposant sur LWE [Regev 05] 3. Reposant sur Anneau-LWE [L, Peikert, Regev 10] 4. NTRU avec une preuve de la s curit [Stehle, Steinfeld 11]

Subset Sum Problem Subset-Sum Based [L, Palacio, Segev 10] LWE-Based [Regev 05] Ring-LWE Based [L, Peikert, Regev 10] NTRU-like with a proof of security [Stehle, Steinfeld 11] NTRU [Hoffstein, Pipher, Silverman 98]

Part 0. The Subset Sum Problem

Subset Sum Problem ai ,T in ZM ai are chosen randomly T is a sum of a random subset of the ai a1 a2 a3 an T Find a subset of ai's that sums to T (mod M)

Subset Sum Problem ai ,T in Z49 ai are chosen randomly T is a sum of a random subset of the ai 15 31 24 3 14 11 15 + 31 + 14 = 11 (mod 49)

How Hard is Subset Sum? ai ,T in ZM a1 a2 a3 an T Find a subset of ai's that sums to T (mod M) Hardness Depends on: Size of n and M Relationship between n and M

Complexity of Solving Subset Sum M 2log (n) 2n 2n log(n) 2n poly(n) 2 (n) poly(n) run-time generalized birthday attacks [FlaPrz05,Lyu06,Sha08] lattice reduction attacks [LagOdl85,Fri86]

Subset Sum Crypto Why? Simple operations Exponential hardness Seems very different from number theoretic assumptions Seems to resist quantum attacks

Subset Sum is Pseudorandom [Impagliazzo-Naor 1989]: For random a1,...,an in ZM and random x1,...,xn in {0,1} distinguishing the distribution (a1,...,an, a1x1+...+anxn mod M) from the uniform distribution U(ZM finding x1,...,xn n+1) is as hard as

Part 1. Cryptosystem Based on Subset Sum [L, Palacio, Segev 2010]

Public Key Encryption Allows for secure communication between parties who have previously never met

Public Key Encryption public key: p secret key: s Encrypt, Decrypt Decrypt(s,Encrypt(p,M))=M c=Encrypt(p,M) M=Decrypt(s,c)

Public Key Encryption What does secure mean? Intuitive answer: The adversary should not be able to read the message. c=Encrypt(p,M)

Public Key Encryption What does secure mean? Intuitive answer: The adversary should not be able to read the message. But what about other information about the message? c=Encrypt(p,M), c=Encrypt(p,M) E.g. If adversary can figure out that the same message was sent twice, is the scheme secure ?

Public Key Encryption What does secure mean? Semantic Security: For every 2 messages M, M', it's impossible to distinguish Encrypt(p,M) from Encrypt(p,M') in polynomial time The Encrypt algorithm must be randomized!

Subset Sum Cryptosystem Semantically secure based on Subset Sum for M nn Main tools Subset sum is pseudo-random Addition in (Zq)n where M=qn is kind of like addition in ZM The proof is very simple

Facts About Addition Want to add 4679+3907+8465+1343 mod 104 2 1 2 4 6 7 9 3 9 0 7 8 4 6 5 1 3 4 3 3 8 4 6 7 9 3 9 0 7 8 4 6 5 1 3 4 3 2 6 7 4 9 4 Adding n numbers (written in base q) modulo qm carries < n If q>>n, then Adding with carries Adding without carries (i.e. in ZM) (i.e. in (Zq)n )

So... 4 6 7 9 3 9 0 7 8 4 6 5 1 6 4 3 1 1 0 1 4 6 7 9 3 9 0 7 8 4 6 5 1 6 4 3 1 1 0 1 + 2 1 1 0 0 2 2 9 = 8 1 1 9 = NOT Pseudorandom! Pseudorandom based on Subset Sum!

Column Subset Sum Addition Is Also Pseudorandom 4 6 7 9 3 9 0 7 8 4 6 5 1 6 4 3 1 1 0 1 1 1 1 0 0 9 8 0 + =

Hybrid Subset Sum Addition Is Also Pseudorandom 4 6 7 9 0 3 9 0 7 9 8 4 6 5 8 1 6 4 3 0 1 1 1 0 0 6 3 2 2 0 1 0 0 1 pseudorandom + =

Encryption Scheme (for 1 bit) r A A s t t + = {0,1}n + Zq n x n {0,1}n = u v Public Key

Encryption Scheme r A A s t t + = + = u v Is pseudo-random based on the hardness of the subset sum problem

Encryption Scheme r A A s t t + = + = u v v r r = + s + s A A r + = s s A A

Encryption Scheme r A A s t t + = + = u v r u + = A s s v r + = s A

Encryption Scheme r A A s t t + = + = u v Encryption of 0 u v - = s

Encryption Scheme r A A s t t + = + = u v + Encryption of 1 0 q/2 = u v - + = q/2 v u s

Part 2. Cryptosystem Based on Learning With Errors and Worst-Case Lattice Problems [Regev 2005]

Encryption Scheme (what we needed) r A A s t t + = + = u v small Pseudorandom

Picking the Carries In Subset Sum: carries were deterministic What if we pick the carries at random from some distribution?

So... 4 6 7 9 3 9 0 7 8 4 6 5 1 6 4 3 1 1 0 1 4 6 7 9 3 9 0 7 8 4 6 5 1 6 4 3 2 3 0 1 + 2 1 1 0 0 2 2 9 = + 1 3 2 1 7 2 0 3 = Pseudorandom based on Subset Sum! Pseudorandom based on LWE and worst-case lattice problems [Reg 05] (with a lemma from [ACPS 09])

Learning With Errors (LWE) Problem a1 a2 s e b + = . . . am Given ai and <ai,s>+ ei find s. (ei and s are small ) (Once there are enough ai , the s is uniquely determined) Theorem [Regev '05] : There is a polynomial-time quantum reduction from solving certain lattice problems in the worst-case to solving LWE.

Decision LWE Problem World 1 World 2 a1 a1 a2 a2 s b + e =b . . . . . . am am uniformly random in Zp m Lemma[Reg 05]: Search-LWE < Decision-LWE

LWE vs. Subset Sum The Subset Sum assumption has deterministic noise The LWE assumption is more versatile LWE Problem Subset Sum Problem a1 a2 s s a1 a2 an + e =b =b . . . n2 n2 + am n n

LWE / Subset Sum Encryption r A A s t t + = + = u v n-bit Encryption Public Key Size Secret Key Size Ciphertext Expansion (n) / (1) Encryption Time Decryption Time Have (n) / (n2) (n) / (n2) Want O(n) O(n) O(1) O(n) O(n) (n3) / (n2) (n2)

Part 3. Cryptosystem Based on Learning With Errors over Rings and Worst-Case Ideal Lattice Problems [L, Peikert, Regev 2010]

Source of Inefficiency of LWE Getting just one extra random-looking number requires n random numbers and a small error element. 2 8 7 3 1 0 2 1 2 1 + = * Wishful thinking: get n random numbers and produce n pseudo-random numbers in one shot 2 8 1 0 2 1 + = * 7 3

Use Polynomials f(x) is a polynomial xn + an-1xn-1+ + a1x + a0 R = Zp[x]/(f(x)) is a polynomial ring with Addition mod p Polynomial multiplication mod p and f(x) Each element of R consists of n elements in Zp In R: small+small = small small*small = small (depending on f(x) )

Polynomial Interpretation of the LWE-based cryptosystem a s + = t r a r t + + = = u v Public Key v - u s = r t + - r a + s + - r a s + r a + s + r - s =

Security a s + = t r a r t + + = = u v Pseudorandom??

Learning With Errors over Rings s a1 a2 a3 e1 e2 e3 b1 b2 b3 + = am em bm Theorem [LPR 10]: Finding s is as hard as solving lattice problems in all ideals of the ring Z[x]/(f(x))

Decision Learning With Errors over Rings World 1 World 2 s a1 a2 a3 a1 a2 a3 b1 b2 b3 b1 b2 b3 + = am am bm bm Theorem [LPR 10]: In cyclotomic rings, Search-RLWE < Decision-RLWE

Use Polynomials in Zp[x]/(f(x)) a s + = t r a r t + + = = u v n-bit Encryption Public Key Size Secret Key Size Ciphertext Expansion (n) / (1) Encryption Time Decryption Time From LWE / SS (n) / (n2) (n) / (n2) From Ring-LWE (n) (n) (1) (n) (n) (n3) / (n2) (n2)

Part 4. 1-Element Cryptosystem Based on Learning With Errors over Rings and Worst-Case Ideal Lattice Problems [Stehle, Steinfeld 2011]

Number of Ring Elements a s + = t r a r t + + = = u v p 2 Encryption of m: u v + m , Can you have a ciphertext with just 1 ring element?

Stehle, Steinfeld Cryptosystem small coefficients f g a u a r + + m mod p = = 2 mod p Uniformly random Pseudorandom based on Ring-LWE u g 2 f r + g + g m = u g mod 2 = g m u g mod 2 g m =

Part 5. NTRU Cryptosystem [Hoffstein, Pipher, Silverman 1998]

NTRU Cryptosystem f g - Very small f g a u a r + + m mod p = = 2 mod p looks random If a is random, then pseudorandom based on Ring-LWE u g 2 f r + g + g m = Since f, g are smaller, p can be smaller as well