Introduction to Lattice-Based Cryptography and Linear Equations Solving
Explore the fundamentals of lattice-based cryptography and the significance of solving linear equations in cryptography. Learn about the exponential hardness and quantum resistance of lattice-based crypto, as well as the challenges and techniques involved in solving linear equations with various strategies. Discover the connection between Gaussian elimination, error introduction, and modular arithmetic in cryptographic applications.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
MIT 6.875 Foundations of Cryptography Lecture 18
TODAY (and next few lectures): Lattice-based Cryptography
Why Lattice-based Crypto? Exponentially Hard (so far) Quantum-Resistant (so far)
Why Lattice-based Crypto? Exponentially Hard (so far) Quantum-Resistant (so far) Worst-case hardness (unique feature of lattice-based crypto) Simple and Efficient Enabler of Surprising Capabilities (Fully Homomorphic Encryption)
Solving Linear Equations 5?1+ 11?2= 2 2?1+ ?2= 6 7?1+ ?2= 26 where all equations are over , the integers
Solving Linear Equations s and A Given: A GOAL: Find s. More generally, ? variables and ? ? equations.
Solving Linear Equations s and A Given: A GOAL: Find s. EASY! For example, by Gaussian Elimination
Solving Linear Equations s and A Given: A GOAL: Find s. Chop the head? How to make it hard: That is, work modulo some ?. (1121 ??? 100 = 21) Still EASY! Gaussian Elimination mod ?
Solving Linear Equations s and e A Given: A + GOAL: Find s. How to make it hard: Chop the tail? Add a small error to each equation. Still EASY! Linear regression.
Solving Linear Equations s and e A Given: A + GOAL: Find s. How to make it hard: Chop the head and the tail? Add a small error to each equation and work mod ?. Turns out to be very HARD!
Solving Noisy Modular Linear Equations Learning with Errors (LWE) s and e A Given: A + GOAL: Find s. Parameters: dimensions ? and ?, modulus ?, error distribution ? = uniform in some interval [ ?, ,?]. ? ?, s from ? ? A is chosen at random from ? and e from ??.
Learning with Errors (LWE) Decoding Random Linear Codes (over Fq with L1 errors) Learning Noisy Linear Functions Worst-case hardLattice Problems [Regev 05, Peikert 09]
Attack 1: Linearization Given?,?? + ?, find ?. Idea (a) Each noisy linear equation is an exact polynomial eqn. ? Consider? = ?,? + ? = ?=? ????+ ?. Imagine for now that the error bound ? = 1. So, ? 1,0,1 . In other words, b ?=? ? ???? 1,0,1 . So, here is a noiseless polynomial equation on ??: ? ? ? (b ?=? ???? 1) (b ?=? ????)(b ?=? ????+ 1) = 0
Attack 1: Linearization Given?,?? + ?, find ?. BUT: Solving (even degree 2) polynomial equations is NP-hard. ? ? ? (b ?=? ???? 1) (b ?=? ????)(b ?=? ????+ 1) = 0
Attack 1: Linearization ? ? ? (b ?=? ???? 1) (b ?=? ????)(b ?=? ????+ 1) = 0 Idea (b) Easy to solve given sufficiently many equations. (using a technique called linearization ) ??????????+ ???????+ ????+ ? 1 ?(? + 1) = 0 Treat each monomial , e.g. sisjskas an independent variable, e.g. tijk. Now, you have a noiseless linear equation in tijk!!!
Attack 1: Linearization ????????+ ??????+ ????+ ? 1 ?(? + 1) = 0
Attack 1: Linearization ????????+ ??????+ ????+ ? 1 ?(? + 1) = 0
Attack 1: Linearization ????????+ ??????+ ????+ ? 1 ?(? + 1) = 0
Attack 1: Linearization ????????+ ??????+ ????+ ? 1 ?(? + 1) = 0
Attack 1: Linearization ????????+ ??????+ ????+ ? 1 ?(? + 1) = 0
Attack 1: Linearization Given?,?? + ?, find ?. Can solve/break as long as ? ???+? We will set ? = ? (1), in other words polynomial in ? so as to blunt this attack.
Attack 2: Lattice Decoding a1*s1+a2*s2 a1*s1+a2*s2+e a2 a1 O The famed Lenstra-Lenstra-Lovasz algorithm decodes in polynomial time when ?/? > ??
Setting Parameters Put together, we are safe with: ? = security parameter ( 1 10K) ? = arbitrary poly in ? ? = small poly in ?,say ? ? = poly in ?, larger than ?, and could be as large as sub-exponential, say 2?0.99 even from quantum computers, AFAWK!
Decisional LWE Can you distinguish between: s and , e A A + , b A Theorem: Decisional LWE is as hard as LWE .
OWF and PRG gA(s,e) = As+e (A ?? s ?? ??? ?random small secret vector ?: random small error vector) ? ?? gA is a one-way function (assuming LWE) gA is a pseudo-random generator (decisional LWE) gA is also a trapdoor function also a homomorphic commitment
Basic (Secret-key) Encryption [Regev05] n = security parameter, q = small modulus Secret key sk = Uniformly random vector s ?? ? Encryption Encs(?): // ? {0,1} Sample uniformly random a ?? The ciphertext c =(a, b = a, s + e +? ?/2 ) ?, small noise e ? DecryptionDecsk(c): Output Roundq/2(b a, s mod q) // correctness as long as |e| < q/4
Basic (Secret-key) Encryption [Regev05] This scheme is additively homomorphic. ? =(a, b = a, s + e + ? ?/2 ) Encs(m) + Encs(m ) ? =(a , b = a , s + e + ? ?/2 ) ? + ? =(a+a , b+ b ) ? + ? =(a+a , b+ b = a +a , s + (e+e ) + (? +? ) ?/2 ) In words: ? + ? is an encryption of ? +? (mod 2)
Basic (Secret-key) Encryption [Regev05] You can also negate the encrypted bit easily. We will see how to make this scheme into a fully homomorphic scheme (in the next few lectures) For now, note that the error increases when you add two ciphertexts. That is, |???? |?1+ ?2 2?. Setting ? = ?log ? and ? = support any polynomial number of additions. ? (for example) lets us
Next Lecture: Fully Homomorphic Encryption
