Introduction to Lattice-Based Cryptography and Linear Equations Solving
MIT 6.875
Lecture 18
Foundations of Cryptography
TODAY (and next few lectures):
Lattice-based Cryptography
Why Lattice-based Crypto?
Quantum-Resistant
(so far)
Exponentially Hard
(so far)
Why Lattice-based Crypto?
Quantum-Resistant
(so far)
Worst-case hardness
Exponentially Hard
Simple and Efficient
(unique feature of lattice-based crypto)
Enabler of Surprising Capabilities
(Fully Homomorphic Encryption)
(so far)
Solving Linear Equations
Solving Linear Equations
and
A
A
s
Given
:
GOAL
: Find s.
Solving Linear Equations
GOAL
: Find s.
EASY!
For example, by Gaussian Elimination
and
A
A
s
Given
:
Solving Linear Equations
GOAL
: Find s.
How to make it hard
:
and
A
A
s
Given
:
Chop the head?
Solving Linear Equations
GOAL
: Find s.
How to make it hard
:
Chop the tail?
Add a small error to each equation.
Still EASY!
Linear regression.
and
A
A
s
Given
:
+
e
Solving Linear Equations
GOAL
: Find s.
How to make it hard
:
Chop the head
and
the tail?
Turns out to be very HARD!
and
A
A
s
Given
:
+
e
Solving
Noisy
Modular Linear Equations
GOAL
: Find s.
and
A
A
s
Given
:
+
e
Learning with Errors (LWE)
Learning with Errors (LWE)
D
e
c
o
d
i
n
g
R
a
n
d
o
m
L
i
n
e
a
r
C
o
d
e
s
(
o
v
e
r
F
q
w
i
t
h
L
1
e
r
r
o
r
s
)
L
e
a
r
n
i
n
g
N
o
i
s
y
L
i
n
e
a
r
F
u
n
c
t
i
o
n
s
W
o
r
s
t
-
c
a
s
e
h
a
r
d
L
a
t
t
i
c
e
P
r
o
b
l
e
m
s
[
R
e
g
e
v
’
0
5
,
P
e
i
k
e
r
t
’
0
9
]
Attack 1:
Linearization
Idea (a)
Each noisy linear equation is an exact polynomial eqn.
Attack 1:
Linearization
BUT:
Solving (even degree 2) polynomial equations is NP-hard.
Attack 1:
Linearization
Idea (b)
Easy to solve given
sufficiently many
equations.
(using a technique called “linearization”)
Attack 1:
Linearization
Solution space
(with some eqns):
The real solution
Attack 1:
Linearization
Solution space
(with more eqns):
The real solution
Attack 1:
Linearization
Solution space
(with even more eqns):
The real solution
Attack 1:
Linearization
Solution space
(keep going):
The real solution
Attack 1:
Linearization
the only surviving solution to the linear system is the
real solution.
Attack 1:
Linearization
Can solve/break as long as
a
1
O
a2
Attack 2:
Lattice Decoding
a1*s1+a2*s2
a1*s1+a2*s2+e
The famed Lenstra-Lenstra-Lovasz algorithm decodes
Setting Parameters
Put together, we are safe with:
even from quantum computers, AFAWK!
Decisional LWE
T
h
e
o
r
e
m
:
“
D
e
c
i
s
i
o
n
a
l
L
W
E
i
s
a
s
h
a
r
d
a
s
L
W
E
”
.
Can you distinguish between
:
and
OWF and PRG
•
g
A
is a one-way function (assuming LWE)
•
g
A
is a pseudo-random generator (decisional LWE)
•
g
A
i
s also a trapdoor function…
•
also a homomorphic commitment…
Basic (Secret-key) Encryption
n = security parameter, q = “small” modulus
[Regev05]
•
D
e
c
r
y
p
t
i
o
n
D
e
c
s
k
(
c
)
:
O
u
t
p
u
t
R
o
u
n
d
q
/
2
(
b
−
a
,
s
m
o
d
q
)
// correctness as long as |e| < q/4
Basic (Secret-key) Encryption
[Regev05]
This scheme is additively homomorphic.
E
n
c
s
(
m
)
E
n
c
s
(
m
’
)
Basic (Secret-key) Encryption
[Regev05]
We will see how to make this scheme into a fully
homomorphic scheme (in the next few lectures)
You can also negate the encrypted bit easily.
Next Lecture:
Fully Homomorphic Encryption
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
