Trapdoor Sampling in Lattice-Based Cryptography
Simple Lattice Trapdoor Sampling
from a
Broad Class of Distributions
Vadim Lyubashevsky and Daniel Wichs
T
r
a
p
d
o
o
r
S
a
m
p
l
i
n
g
A
t
s
=
Given: a random matrix
A
and vector
t
Find: vector
s
with small coefficients such that
As
=
t
Without a “trapdoor” for
A
, this is a very hard problem
When sampling in a protocol, want to make sure
s
is independent of the trapdoor
mod p
T
r
a
p
d
o
o
r
S
a
m
p
l
i
n
g
First algorithm: Gentry, Peikert, Vaikuntanathan (2008)
•
Very “geometric”
•
The distribution of
s
is a discrete Gaussian
Agrawal, Boneh, Boyen (2010) + Micciancio, Peikert (2012)
•
More “algebraic” (you don’t even see the lattices)
•
Still
s
needs to be a discrete Gaussian
Are Gaussians “fundamental” to trapdoor sampling?
C
o
n
s
t
r
u
c
t
i
n
g
a
T
r
a
p
d
o
o
r
A
s
t
=
mod p
C
o
n
s
t
r
u
c
t
i
n
g
a
T
r
a
p
d
o
o
r
A
1
t
s
1
=
mod p
A
2
s
2
A
1
R
G
+
Random matrix
Random matrix with
small coefficients
Special matrix that is
easy to invert
A
1
C
o
n
s
t
r
u
c
t
i
n
g
a
T
r
a
p
d
o
o
r
A
=
A
1
R
G
+
Random matrix
Random matrix with
small coefficients
Special matrix that is
easy to invert
A
1
C
o
n
s
t
r
u
c
t
i
n
g
a
T
r
a
p
d
o
o
r
A
=
H
Invertible matrix H that is used as a “tag”
in many advanced constructions
E
a
s
i
l
y
-
I
n
v
e
r
t
i
b
l
e
M
a
t
r
i
x
Matrix
G
has the property that
for any
t
, you can find a 0/1 vector
s
2
such that
Gs
2
=
t
(a bijection between integer vectors and {0,1}*
)
1 2 4 8 … q/2
1 2 4 8 … q/2
1 2 4 8 … q/2
. . . . . .
1 2 4 8 … q/2
G
=
E
x
a
m
p
l
e
1 2 4 8
1 2 4 8
1
0
1
1
0
0
1
0
13
4
=
I
n
v
e
r
t
i
n
g
w
i
t
h
a
T
r
a
p
d
o
o
r
A
= [
A
1
|
A
2
] = [
A
1
|
A
1
R
+
G
]
Want to find a small
s
such that
As
=
t
s
= (
s
1
,
s
2
)
t
=
As
=
A
1
s
1
+(
A
1
R
+
G
)
s
2
=
A
1
(
s
1
+Rs
2
) +
Gs
2
t
=
Gs
2
s
1
= -
Rs
2
set to
0
Reveals
R
Bad
I
n
v
e
r
t
i
n
g
w
i
t
h
a
T
r
a
p
d
o
o
r
A
= [
A
1
|
A
2
] = [
A
1
|
A
1
R
+
G
]
Want to find a small
s
such that
As
=
t
s
= (
s
1
,
s
2
)
t
=
As
=
A
1
s
1
+(
A
1
R
+
G
)
s
2
=
A
1
(
s
1
+Rs
2
) +
Gs
2
t
-
A
1
y
=
Gs
2
s
1
=
y
-
Rs
2
small
y
Intuition:
y
helps to hide
R
T
h
e
D
i
s
t
r
i
b
u
t
i
o
n
w
e
H
o
p
e
t
o
G
e
t
t
=
A
1
(
s
1
+Rs
2
) +
Gs
2
t
-
A
1
y
=
Gs
2
s
1
=
y
-
Rs
2
s
2
D
2
s
1
D
1
|
A
1
s
1
+ (
A
1
R
+
G
)
s
2
=
t
Output
s
= (
s
1
,
s
2
)
small
y
(but enough entropy)
uniformly random
(leftover hash lemma)
random bit string
(because of the shape of
G
)
Depends on
R
,
s
2
, and
y
R
e
j
e
c
t
i
o
n
S
a
m
p
l
i
n
g
Make sure it’s at most 1
R
e
m
o
v
i
n
g
t
h
e
D
e
p
e
n
d
e
n
c
e
o
n
R
Assume
R
and
s
2
are fixed
s
1
=
y
-
Rs
2
If
y
D
y
then
Pr[
s
1
] = Pr[
y
=
s
1
+
Rs
2
]
We want Pr[
s
1
] to be exactly D
1
(
s
1
)
(conditioned on
As
=
t
)
So sample
y
and output
s
1
=
y
-
Rs
2
with probability D
1
(
s
1
) / (
c∙D
y
(
s
1
+
Rs
2
))
s
2
D
2
s
1
D
1
|
A
1
s
1
+ (
A
1
R
+
G
)
s
2
=
t
Output
s
= (
s
1
,
s
2
)
T
h
e
R
e
a
l
D
i
s
t
r
i
b
u
t
i
o
n
y
D
y
s
2
G
-1
(
t
-
A
1
y
)
s
1
y
-
Rs
2
Output
s
=(
s
1
,
s
2
) with probability
D
1
(
s
1
)/(c∙D
y
(
s
1
+
Rs
2
))
s
2
D
2
s
1
D
1
|
A
1
s
1
+ (
A
1
R
+
G
)
s
2
=
t
Output
s
= (
s
1
,
s
2
)
Real Distribution
Target Distribution
the shift
Rs
2
depends on
y
(what’s the distribution of
s
1
??)
E
q
u
i
v
a
l
e
n
c
e
o
f
D
i
s
t
r
i
b
u
t
i
o
n
s
y
D
y
s
2
G
-1
(
t
-
A
1
y
)
s
1
y
-
Rs
2
Output
s
=(
s
1
,
s
2
) with probability
D
1
(
s
1
)/(c∙D
y
(
s
1
+
Rs
2
))
s
2
D
2
s
1
D
1
|
A
1
s
1
+ (
A
1
R
+
G
)
s
2
=
t
Output
s
= (
s
1
,
s
2
)
Real Distribution
Target Distribution
1.
For (almost) all
s
=(
s
1
,
s
2
) in the support of TD ,
D
1
(
s
1
)/(c∙D
y
(
s
1
+
Rs
2
)) ≤ 1
2.
D
2
is uniformly random and G is a 1-1 and onto function between the support of D
2
and Z
p
n
3.
For
x
D
1
and
x
D
y
,
Δ
(
A
1
x
, U(Z
p
n
)) < 2
-(n logp+
λ
)
≈
λc∙2
-
λ
(2) and (3) break the dependency between s
2
and y and (1) allows rejection sampling
O
u
r
“
U
n
b
a
l
a
n
c
e
d
”
R
e
s
u
l
t
A
1
t
s
1
=
mod p
A
2
s
2
n
Has entropy greater than nlogp
Binary vector
I
s
t
h
e
G
a
u
s
s
i
a
n
D
i
s
t
r
i
b
u
t
i
o
n
“
F
u
n
d
a
m
e
n
t
a
l
”
t
o
L
a
t
t
i
c
e
s
My opinion
•
To lattices – YES
•
A Gaussian distribution centered at any point in space is uniform
over R
n
/ L for
any
“small-enough” lattice L
•
To lattice cryptography – NO
•
We usually work with
random
lattices of a special form
•
Can use the leftover hash lemma to argue uniformity
•
But … Gaussians are often an optimization
W
h
a
t
D
i
s
t
r
i
b
u
t
i
o
n
t
o
u
s
e
i
n
P
r
a
c
t
i
c
e
?
Gaussians are often (always?) the “optimal” distribution to use for
minimizing the parameters
But … Sampling Gaussians requires high(er) precision
so maybe too costly in low-power devices
Try to use the distribution that minimizes parameters
try to improve the efficiency later
Explore simple lattice trapdoor sampling techniques for generating vector s such that As = t, without revealing the trapdoor in a protocol. Learn about algorithms and methods for constructing trapdoors, Gaussian distributions, and easily invertible matrices in the context of cryptographic protocols.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Simple Lattice Trapdoor Sampling from a Broad Class of Distributions Vadim Lyubashevsky and Daniel Wichs
Trapdoor Sampling Trapdoor Sampling = mod p t A A s Given: a random matrix A and vector t Find: vector s with small coefficients such that As=t Without a trapdoor for A, this is a very hard problem When sampling in a protocol, want to make sure s is independent of the trapdoor
Trapdoor Sampling Trapdoor Sampling First algorithm: Gentry, Peikert, Vaikuntanathan (2008) Very geometric The distribution of s is a discrete Gaussian Agrawal, Boneh, Boyen (2010) + Micciancio, Peikert (2012) More algebraic (you don t even see the lattices) Still s needs to be a discrete Gaussian Are Gaussians fundamental to trapdoor sampling?
Constructing a Trapdoor Constructing a Trapdoor = mod p A A t s
Constructing a Trapdoor Constructing a Trapdoor = mod p A A2 2 A A1 1 t s1 s2
Constructing a Trapdoor Constructing a Trapdoor + A = A A1 1 A A1 1 G G R R Random matrix with small coefficients Random matrix Special matrix that is easy to invert
Constructing a Trapdoor Constructing a Trapdoor + A = A A1 1 A A1 1 H H G G R R Random matrix with small coefficients Special matrix that is easy to invert Random matrix Invertible matrix H that is used as a tag in many advanced constructions
Easily Easily- -Invertible Matrix Invertible Matrix Matrix G has the property that for any t, you can find a 0/1 vector s2 such that Gs2=t (a bijection between integer vectors and {0,1}*) 1 2 4 8 q/2 1 2 4 8 q/2 1 2 4 8 q/2 . . . . . . 1 2 4 8 q/2 G =
Example Example 1 0 1 1 0 0 1 0 = 1 2 4 8 1 2 4 8 13 4
Inverting with a Trapdoor Inverting with a Trapdoor A = [A1 | A2] = [A1 | A1R+G] Want to find a small s such that As=t s = (s1,s2) t = As = A1s1+(A1R+G)s2 = A1(s1+Rs2) + Gs2 t = Gs2s1 = - Rs2 set to 0 Reveals R Bad
Inverting with a Trapdoor Inverting with a Trapdoor A = [A1 | A2] = [A1 | A1R+G] Want to find a small s such that As=t s = (s1,s2) t = As = A1s1+(A1R+G)s2 = A1(s1+Rs2) + Gs2 t - A1y = Gs2s1 = y - Rs2 small y Intuition: y helps to hide R
The Distribution we Hope to Get The Distribution we Hope to Get s2 D2 s1 D1 | A1s1 + (A1R+G)s2 = t Output s = (s1,s2) t = A1(s1+Rs2) + Gs2 small y (but enough entropy) t - A1y = Gs2s1 = y - Rs2 uniformly random (leftover hash lemma) Depends on R, s2, and y random bit string (because of the shape of G)
Rejection Sampling Rejection Sampling Want to sample from distribution ?(?) Have access to distribution ?(?) Make sure it s at most 1 ?(?) ? ? ? Sample ? ~ ? ? and output it with probability ?(?) ? ? ?= ?(?) ? ? ? = ?(?) 1 ? Something is output with probability ? ? Pr[? = ? | something is output] = ? ?(?)
Removing the Dependence on R Removing the Dependence on R s2 D2 s1 D1 | A1s1 + (A1R+G)s2 = t Output s = (s1,s2) Assume R and s2 are fixed s1 = y - Rs2 If y Dy then Pr[s1] = Pr[y=s1+Rs2] We want Pr[s1] to be exactly D1(s1)(conditioned on As=t) So sample y and output s1=y - Rs2 with probability D1(s1) / (c Dy(s1+Rs2))
The Real Distribution The Real Distribution Real Distribution Target Distribution y Dy s2 G-1(t - A1y) s1 y - Rs2 Output s=(s1,s2) with probability D1(s1)/(c Dy(s1+Rs2)) s2 D2 s1 D1 | A1s1 + (A1R+G)s2 = t Output s = (s1,s2) the shift Rs2depends on y (what s the distribution of s1??)
Equivalence of Distributions Equivalence of Distributions c 2- Real Distribution Target Distribution y Dy s2 G-1(t - A1y) s1 y - Rs2 Output s=(s1,s2) with probability D1(s1)/(c Dy(s1+Rs2)) s2 D2 s1 D1 | A1s1 + (A1R+G)s2 = t Output s = (s1,s2) 1. For (almost) all s=(s1,s2) in the support of TD , D1(s1)/(c Dy(s1+Rs2)) 1 2. D2 is uniformly random and G is a 1-1 and onto function between the support of D2 and Zp 3. For x D1 and x Dy, (A1x, U(Zp (2) and (3) break the dependency between s2 and y and (1) allows rejection sampling n n)) < 2-(n logp+ )
Our Unbalanced Result Our Unbalanced Result = mod p n A A2 2 A A1 1 t s1 s2 Binary vector Has entropy greater than nlogp
Is the Gaussian Distribution Is the Gaussian Distribution Fundamental to Lattices Fundamental to Lattices My opinion To lattices YES A Gaussian distribution centered at any point in space is uniform over Rn / L for any small-enough lattice L To lattice cryptography NO We usually work with random lattices of a special form Can use the leftover hash lemma to argue uniformity But Gaussians are often an optimization
What Distribution to use in Practice? What Distribution to use in Practice? Gaussians are often (always?) the optimal distribution to use for minimizing the parameters But Sampling Gaussians requires high(er) precision so maybe too costly in low-power devices Try to use the distribution that minimizes parameters try to improve the efficiency later
