Signature Schemes in Cryptography
Lattice Signature Schemes
Vadim Lyubashevsky
INRIA / ENS Paris
DIGITAL SIGNATURE SCHEMES
Digital Signatures
(sk,pk)
KeyGen
Sign(sk,m
i
) = s
i
Verify(pk,m
i
,s
i
) = YES / NO
Correctness: Verify(pk, m
i
, Sign(sk,m
i
)) = YES
Security: Unforgeability
1.
Adversary gets pk
2.
Adversary asks for signatures of m
1
, m
2
, …
3.
Adversary outputs (m,s) where m ≠ m
i
and wins
if Verify(pk,m,s) = YES
Signature Schemes
•
Hash-and-Sign
–
Requires a trap-door function
•
Fiat-Shamir transformation
–
Conversion from an identification scheme
–
No trap-door function needed
FIAT-SHAMIR SIGNATURE SCHEMES
Signature Scheme (Main Idea)
Secret Key:
S
Public Key:
A
,
T
=
A
S
mod q
Sign
(
μ
)
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
)
Verify
(
z
,
c
)
Check that
z
is “small”
and
c
= H(
A
z
–
T
c
mod q,
μ
)
Main Security Intuition
Secret Key:
S
Public Key:
A
,
T
=
A
S
mod q
Sign
(
μ
)
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
)
Verify
(
z
,
c
)
Check that
z
is “small”
and
c
= H(
A
z
–
T
c
mod q,
μ
)
Signature is independent of the secret key
Signature Scheme
Secret Key:
S
Public Key:
A
,
T
=
A
S
mod q
Sign
(
μ
)
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
)
make
y
uniformly random mod q?
then
z
is too big and forging is easy
Signature Scheme
Secret Key:
S
Public Key:
A
,
T
=
A
S
mod q
Sign
(
μ
)
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
)
make
y
small?
then
z
will not be independent of
S
Rejection Sampling
Secret Key:
S
Public Key:
A
,
T
=
A
S
mod q
Sign
(
μ
)
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
)
if
z
meets certain criteria, else repeat
make
y
small
Rejection Sampling
g(x)
f(x)
Have access to samples from
g(x)
Want
f(x)
Rejection Sampling
g(x)
f(x)/M
Have access to samples from
g(x)
Want
f(x)
Sample from
g(x)
, accept x with probability
f(x)
/M
g(x)
≤ 1
Pr[x] =
g(x)
∙(
f(x)
/M
g(x)
) =
f(x)
/M
Something is output with probability 1/M
Rejection Sampling
h(x)
Have access to samples from
g(x)
Want
f(x)
Sample from
g(x)
, accept x with probability
f(x)
/M
g(x)
≤ 1
or … Sample from
h(x)
, accept x with probability
f(x)
/M
h(x)
≤ 1
Pr[x] =
g(x)
∙(
f(x)
/M
g(x)
) =
f(x)
/M =
h(x)
∙(
f(x)
/M
h(x)
)
Something is output with probability 1/M
g(x)
f(x)/M
Impossible to tell whether
g(x)
or
h(x)
was the original distribution
Rejection Sampling
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
) w.p. …
f(y)
f(y+Sc)
Normal Distribution
1-dimensional Normal distribution:
ρ
σ
(x) =
1/(
√2
πσ
)
e
-x
2
/2
σ
2
It is:
Centered at 0
Standard deviation:
σ
Examples
Shifted Normal Distribution
1-dimensional shifted Normal distribution:
ρ
σ
,v
(x) =
1/(
√2
πσ
)
e
-(x-v)
2
/2
σ
2
It is:
Centered at v
Standard deviation:
σ
n-Dimensional Normal Distribution
n-dimensional shifted Normal distribution:
ρ
σ
,
v
(
x
) =
1/(
√2
πσ
)
n
e
-
||
x
-
v
||
2
/2
σ
2
It is:
Centered at
v
Standard deviation:
σ
2-Dimensional Example
n-Dimensional Normal Distribution
n-dimensional shifted Normal distribution:
ρ
σ
,
v
(
x
) =
1/(
√2
πσ
)
n
e
-
||
x
-
v
||
2
/2
σ
2
It is:
Centered at
v
Standard deviation:
σ
Discrete Normal: for
x
in
Z
n
,
D
σ
,v
(
x
)=
ρ
σ
,
v
(
x
)
/
ρ
σ
,
v
(
Z
n
)
Rejection Sampling
-v
v
v=max
||
Sc
||
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
) w.p. D
σ
,0
(
z
) / (MD
σ
,
Sc
(
z
))
for
σ
= 12v,
D
σ
,0
(
z
) / (MD
σ
,
Sc
(
z
)) ≈ e/M
Security Reduction
A
Adversary
Simulator
Pick random
S
A,A
S
μ
i
(
z
i
,
c
i
)
(
z
i
,
c
i
)=Sign(
μ
i
)
μ
, (
z
,
c
)
…
μ
, (
z’
,
c’
)
A(
z
-
z’
)+T(
c’
-
c
)=0
If this is not 0, then
SIS
is solved.
Important for adversary to not know
S
.
A(
z
-
z’
+
Sc’
-
Sc
)=0
INTERLUDE: THE SIS PROBLEM
The SIS Problem
A
s
= 0 (mod q)
n
m
Given a random
A
in
Z
q
n x m
,
Find a “small”
s
such that
As
=
0
mod q
The LWE Problem
A
s
e
b
+
=
m
n
||
e
||
is small
f
i
n
d
s
mod q
Decision LWE
A
s
e
b
+
=
A
b
Valid LWE Distribution
Uniformly Random
Solve SIS to Solve LWE
A
v
=
0
mod q
Solve SIS to Solve LWE
b
v
Solve SIS to Solve LWE
v
A
s
e
+
Solve SIS to Solve LWE
b
v
Compute
v∙b
mod q. If
b
=
As
+
e
, then
v∙b
=
v∙e
is small.
If
b
is uniform, then
v∙b
mod q is uniform.
BACK TO SIGNATURES…
Improving the Rejection Sampling
Rejection Sampling from [Lyu12]
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
z
=
Sc
+
y
Output(
z
,
c
) w.p. D
σ
,0
(
z
) / (MD
σ
,
Sc
(
z
))
Bimodal Gaussians [DDLL ‘13]
Pick a random
y
Compute
c
=H(
A
y
mod q,
μ
)
Pick a random b in {-1,1}z
=b
Sc
+
y
Output(
z
,
c
) w.p. D
σ
,0
(
z
) / M(½D
σ
,
Sc
(
z
) + ½D
σ
,
-Sc
(
z
))
Verify
(
z
,
c
)
Check that
z
is “small”
and
c
= H(
A
z
–
T
c
mod q,
μ
)
A
z
–
T
c
=
A
(b
Sc
+
y
) -
T
c
=
b
T
c
-
T
c
+
A
y
Want:
T
c
= - T
c
for
σ
= max
||
Sc
||
/ √2
D
σ
,0
(
z
) / M(½D
σ
,
Sc
(
z
) + ½D
σ
,
-Sc
(
z
)) ≈ e / M
Optimizations
•
Base problem on the hardness of the NTRU
problem
•
Compress the signature
not all of z needs
to be output
if H only acts on the high order
bits
•
A few other small tricks
Performance of the
Bimodal LattIce Signature Scheme
HASH-AND-SIGN SIGNATURE SCHEMES
Constructing the Trapdoor
A’
R
G
+
Random matrix
Random matrix with
small coefficients
Special matrix that is
easy to invert
A’
Easily-Invertible Matrix
Want: Matrix
G
such that:
For any
b
in
Z
q
n
, you can find a 0/1 vector
s
such
that
Gs
=
b
mod q
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
=
Inverting with a Trapdoor
A
= [
A’
|
A’R
+
G
]
Want to find a small
s
such that
As
=
b
s
= (
s
1
,
s
2
)
b
=
As
=
A’s
1
+(
A’R
+
G
)
s
2
=
A’
(
s
1
+Rs
2
) +
Gs
2
b
=
Gs
2
s
1
=
- Rs
2
set to 0
Revealing
R
!
(probably bad…)
Inverting with a Trapdoor
A
= [
A’
|
A’R
+
G
]
Want to find a small
s
such that
As
=
b
s
= (
s
1
,s
2
)
b
=
As
=
A’s
1
+(
A’R
+
G
)
s
2
=
A’
(
s
1
+
Rs
2
) +
Gs
2
b
-
A’y
=
Gs
2
s
1
=
y
-
Rs
2
small
y
Maybe
y
hides
R
?
Signature Scheme
Secret (Signing) Key:
R
Public (Verification) Key:
A
= [
A’
|
A’R
+
G
]
Random Oracle H: {0,1}*
Z
q
n
Sign(m):
Find short
s
such that
As
= H(m
,
u)
Verify (
s
,u,m)
Check that
s
is short, and
As
=H(m,u)
Security Proof Sketch
A
pick from D
=
= H(m
i
,u
i
)
program the random oracle
sign m
i
Security Proof Sketch
A
pick from D
=
= H(m
i
,u
j
)
program the random oracle
give me H(m
i
,u
j
)
Security Proof Sketch
I will forge the
signature of m
To forge on m, the Adversary needs H(m,u)
So m is one of the m
j
he asked for H(m
i
,u
j
)
Thus we know an s
j
such that As
j
=H(m
i
,u
j
)
A
=
A
=
Security Proof Sketch
A
-
=
0
short and hopefully non-zero
if it’s non-zero, then we have a solution to SIS
Properties Needed
A
b
s
=
1.
Can sample the distribution D of
s
without knowing the
trapdoor.
2.
The following produce the same distribution of (
s
,
b
)
(a) Choose
s
~ D. Set
b
=
As
(b) Choose random
b
. Use the trapdoor to find an
s
such
that
As
=
b
.
3. For a random
b
, there is more than one likely possible
output
s
such that
b
=
As
.
Inverting with a Trapdoor
A
= [
A’
|
A’R
+
G
]
Want to find a small s such that As=b
s = (
s
1
,
s
2
)
H(m,u) =
As
=
A’s
1
+(
A’R+G
)
s
2
=
A’
(
s
1
+Rs
2
) +
Gs
2
H(m,u) -
A’y
=
Gs
2
s
1
=
y
-
Rs
2
small
y
Maybe
y
hides
R
?
Rejection Sampling
H(m,u) -
A’y
=
Gs
2
s
1
=
y
-
Rs
2
Choose
y
to be a Gaussian.
If
y
has a lot of entropy, the distribution of
s
2
is
uniform and does not depend on the exact value of
y.
s
1
=
y
-
Rs
2
is now a shifted Gaussian. Use rejection
sampling as before (this requires a proof).
Another Approach for Sampling
Suppose we have a matrix
A
and a trapdoor
R
such
that
AR=G
.
Here is another way to generate an
s
such that
As
=
b
Sample some vector
p
Sample a
z
such that
Gz
=
b
-
Ap
Output
s
=
p
+
Rz
( so
As
=
Ap
+
Gz
=
b
)
Correcting the Distribution
Sample some vector
p
Sample a
z
such that
Gz
=
b
-
Ap
Output
s
=
p
+
Rz
( so
As
=
Ap
+
Gz
=
b
)
How to make the distribution of
s
independent of
R
?
Tailor the distribution of
p
to
R
Rz
p
s
+
=
IDENTITY-BASED ENCRYPTION
“Dual” Cryptosystem
A
s
t
=
t
r
+
u
v
=
0
m
+
A
Secret Key
(short)
Public Key
“Dual” Cryptosystem
v
-
=
A
s
t
=
t
r
+
u
v
=
0
m
+
+
m
represent 0 by m=0
represent 1 by m=(q-1)/2
A
u
s
“Dual” Cryptosystem Security
A
s
t
=
t
r
+
u
v
=
0
m
+
A
Random
Pseudorandom
Identity-Based Encryption
Secret Key = s
Public Key = Bob
Key Authority
Master Public Key
Master Secret Key
Identity-Based Encryption
Key Authority
Master Public Key
Master Secret Key
Secret Key = s
Chris
Public Key = Chris
Secret Key = s
Bob
Public Key = Bob
Secret Key = s
Dave
Public Key = Dave
Encrypt(Chris,msg)
Security for IBE
Key Authority
Master Public Key
Master Secret Key
Secret Key = s
Chris
Public Key = Chris
Secret Key = s
Bob
Public Key = Bob
Secret Key = s
Dave
Public Key = Dave
Encrypt(Chris,msg)
CPA-Security: For all m
i
Encrypt(Chris,m
i
) are
computationally indistinguishable
from each other
IBE Based on LWE
A
b
s
=
Master Public Key:
A
Master Secret Key:
R
Identity = “Bob”
b
= H(Bob)
Use the sampling algorithm to find
a short
s
such that
As
=
b
mod q
Use “Dual” LWE encryption to
Encrypt to Bob
Security Proof Sketch
Show that breaking IBE implies breaking the “Dual” cryptosystem
A
t
u
v
public key
ciphertext
A
master public key
Bob
pick from D
=
= H(Bob)
program the random oracle
Security Proof Sketch
Show that breaking IBE implies breaking the “Dual” cryptosystem
A
t
u
v
public key
ciphertext
A
master public key
Bob
=
= H(Bob)
program the random oracle
Security Proof Sketch
Show that breaking IBE implies breaking the “Dual” cryptosystem
A
t
u
v
public key
ciphertext
A
master public key
I will break an encryption to Dave
= H(Dave)
t
u
v
Decryption
SIGNATURES WITHOUT RANDOM ORACLES
Signatures without Random Oracles
Public Key: [
A
|
AR
],
b
Messages will be square invertible matrices
M
To sign
M
, find a short s such that [
A
|
AR
+
MG
]
s
=
b
A
(
s
1
+
Rs
2
)+
MGs
2
=
b
Gs
2
=
M
-1
(
b
-
A
(
s
1
+
Rs
2
))
s
1
=
s
1
+
Rs
2
-
Rs
2
Proof of “Selective” Security
In a selectively secure scheme, the adversary
declares the message he will forge on
before
seeing the public key.
Proof of “Selective” Security
Given
A
,
b
, want to find a short
r
such that
Ar
=
b
.
Adversary gives message
M’
on which he will forge
We want to construct a public key [
A
|
B
] so that a signature
of
M’
will be an
s
that [
A
|
B + M’G
]
s
=
b
will let us find the
short
r
Pick a trap-door
R
and let
B
=
AR
-
M’G
Then if the adversary can forge, we will get [
A
|
AR
]
s
=
b
So
A
(
s
1
+
Rs
2
)=
b
, and so
s
1
+
Rs
2
is the
r
we need.
Proof of “Selective” Security
Adversary designed to work on public key
[
A
|
AR
]
We give it public key [
A
|
AR
-
M’G
]
Will it still succeed in forging?
Yes, if [
A
|
AR
] is uniformly random, then
[
A
|
AR
] has the same distribution as [
A
|
AR
-
M’G
]
Adversary may ask us to sign other messages
M
.
How do we do it?
Proof of “Selective” Security
To sign
M
, we need to find an
s
such that
[
A
|
AR
-
M’G
+
MG
]
s
=
b
A
(
s
1
+
Rs
2
) + (
M
-
M’
)
Gs
2
=
b
Gs
2
= (
M
-
M’
)
-1
(
b
-
A
(
s
1
+
Rs
2
))
s
1
=
s
1
+
Rs
2
-
Rs
2
Need
M
-
M’
to always be invertible.
Such a set of size q
n
is easy to construct.
Hint: consider a field F of order q
n
. Every difference of
polynomials in the field is invertible.
How do you map this to matrices?
This content delves into various aspects of signature schemes, focusing on lattice signature schemes, digital signature schemes, Fiat-Shamir signature schemes, and the main idea behind signature schemes. It explores the concepts of correctness and security in digital signatures, the relevance of trap-door functions, and the importance of randomness in ensuring signature scheme security.
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
Lattice Signature Schemes Vadim Lyubashevsky INRIA / ENS Paris
Digital Signatures (sk,pk) KeyGen Sign(sk,mi) = si Verify(pk,mi,si) = YES / NO Correctness: Verify(pk, mi, Sign(sk,mi)) = YES Security: Unforgeability 1. Adversary gets pk 2. Adversary asks for signatures of m1, m2, 3. Adversary outputs (m,s) where m miand wins if Verify(pk,m,s) = YES
Signature Schemes Hash-and-Sign Requires a trap-door function Fiat-Shamir transformation Conversion from an identification scheme No trap-door function needed
Signature Scheme (Main Idea) Secret Key: S Public Key: A, T=AS mod q Verify(z,c) Check that zis small and c = H(Az Tc mod q, ) Sign( ) Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c)
Main Security Intuition Secret Key: S Public Key: A, T=AS mod q Verify(z,c) Check that zis small and c = H(Az Tc mod q, ) Sign( ) Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) Signature is independent of the secret key
Signature Scheme Secret Key: S Public Key: A, T=AS mod q Sign( ) Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) then z is too big and forging is easy make y uniformly random mod q?
Signature Scheme Secret Key: S Public Key: A, T=AS mod q Sign( ) Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) then z will not be independent of S make y small?
Rejection Sampling Secret Key: S Public Key: A, T=AS mod q Sign( ) Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) if z meets certain criteria, else repeat make y small
Rejection Sampling g(x) Have access to samples from g(x) f(x) Want f(x)
Rejection Sampling g(x) Have access to samples from g(x) f(x)/M Want f(x) Sample from g(x), accept x with probability f(x)/Mg(x) 1 Pr[x] = g(x) (f(x)/Mg(x)) = f(x)/M Something is output with probability 1/M
Rejection Sampling Impossible to tell whether g(x) or h(x) was the original distribution g(x) Have access to samples from g(x) f(x)/M Want f(x) h(x) Sample from g(x), accept x with probability f(x)/Mg(x) 1 or Sample from h(x), accept x with probability f(x)/Mh(x) 1 Pr[x] = g(x) (f(x)/Mg(x)) = f(x)/M = h(x) (f(x)/Mh(x)) Something is output with probability 1/M
Rejection Sampling Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) w.p. f(y+Sc) f(y)
Normal Distribution 1-dimensional Normal distribution: (x) = 1/( 2 )e-x2/2 2 It is: Centered at 0 Standard deviation:
Shifted Normal Distribution 1-dimensional shifted Normal distribution: ,v(x) = 1/( 2 )e-(x-v)2/2 2 It is: Centered at v Standard deviation:
n-Dimensional Normal Distribution n-dimensional shifted Normal distribution: ,v(x) = 1/( 2 )ne-||x-v||2/2 2 It is: Centered at v Standard deviation:
n-Dimensional Normal Distribution n-dimensional shifted Normal distribution: ,v(x) = 1/( 2 )ne-||x-v||2/2 2 It is: Centered at v Standard deviation: Discrete Normal: for x in Zn, D ,v(x)= ,v(x)/ ,v(Zn)
Rejection Sampling Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) w.p. D ,0(z) / (MD ,Sc(z)) v -v v=max ||Sc|| for = 12v, D ,0(z) / (MD ,Sc(z)) e/M
Security Reduction Simulator Adversary A A,AS Pick random S i (zi,ci)=Sign( i) (zi,ci) A(z-z )+T(c -c)=0 , (z,c) A(z-z +Sc -Sc)=0 , (z ,c ) If this is not 0, then SIS is solved. Important for adversary to not know S.
The SIS Problem n x m, Given a random A in Zq Find a small s such that As = 0 mod q A = 0 (mod q) n s m
The LWE Problem s mod q A b e m + = n ||e|| is small find s
Decision LWE Valid LWE Distribution Uniformly Random s A b e A + = b
Solve SIS to Solve LWE v = 0 mod q A
Solve SIS to Solve LWE v s A e +
Solve SIS to Solve LWE Compute v bmod q. If b=As+e, then v b=v eis small. If b is uniform, then v b mod q is uniform. v b
Improving the Rejection Sampling Pick a random y Compute c=H(Ay mod q, ) z=Sc+y Output(z,c) w.p. D ,0(z) / (MD ,Sc(z)) Rejection Sampling from [Lyu12]
Bimodal Gaussians [DDLL 13] Pick a random y Compute c=H(Ay mod q, ) Pick a random b in {-1,1} z=bSc+y Output(z,c) w.p. D ,0(z) / M( D ,Sc(z) + D ,-Sc(z)) for = max ||Sc||/ 2 D ,0(z) / M( D ,Sc(z) + D ,-Sc(z)) e / M Verify(z,c) Check that zis small and c = H(Az Tc mod q, ) Az Tc = A(bSc+y) - Tc = bTc - Tc + Ay Want: Tc = - Tc
Optimizations Base problem on the hardness of the NTRU problem Compress the signature not all of z needs to be output if H only acts on the high order bits A few other small tricks
Performance of the Bimodal LattIce Signature Scheme
Constructing the Trapdoor + A A G R Random matrix with small coefficients Random matrix Special matrix that is easy to invert
Easily-Invertible Matrix Want: Matrix G such that: For any b in Zq that Gs=b mod q n , you can find a 0/1 vector s such 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 =
Inverting with a Trapdoor A = [A | A R+G] Want to find a small s such that As=b s = (s1,s2) b = As = A s1+(A R+G)s2 = A (s1+Rs2) + Gs2 b = Gs2 set to 0 Revealing R! (probably bad ) s1 = - Rs2
Inverting with a Trapdoor A = [A | A R+G] Want to find a small s such that As=b s = (s1,s2) b = As = A s1+(A R+G)s2 = A (s1+Rs2) + Gs2 Maybe y hides R? b - A y = Gs2s1 = y - Rs2 small y
Signature Scheme Secret (Signing) Key: R Public (Verification) Key: A = [A | A R+G] Random Oracle H: {0,1}* Zq n Sign(m): Find short s such that As = H(m,u) Verify (s,u,m) Check that s is short, and As=H(m,u)
Security Proof Sketch A = = H(mi,ui ) pick from D program the random oracle sign mi
Security Proof Sketch A = = H(mi,uj ) pick from D program the random oracle give me H(mi,uj)
Security Proof Sketch A A = = I will forge the signature of m To forge on m, the Adversary needs H(m,u) So m is one of the mj he asked for H(mi,uj) Thus we know an sj such that Asj=H(mi,uj)
Security Proof Sketch A =0 - short and hopefully non-zero if it s non-zero, then we have a solution to SIS
Properties Needed = b A s 1. Can sample the distribution D of s without knowing the trapdoor. 2. The following produce the same distribution of (s,b) (a) Choose s ~ D. Set b=As (b) Choose random b. Use the trapdoor to find an s such that As=b. 3. For a random b, there is more than one likely possible output s such that b=As.
Inverting with a Trapdoor A = [A | A R+G] Want to find a small s such that As=b s = (s1,s2) H(m,u) = As = A s1+(A R+G)s2 = A (s1+Rs2) + Gs2 Maybe y hides R? H(m,u) - A y = Gs2s1 = y - Rs2 small y
Rejection Sampling H(m,u) - A y = Gs2 s1 = y - Rs2 Choose y to be a Gaussian. If y has a lot of entropy, the distribution of s2is uniform and does not depend on the exact value of y. s1 = y-Rs2 is now a shifted Gaussian. Use rejection sampling as before (this requires a proof).
Another Approach for Sampling Suppose we have a matrix A and a trapdoor R such that AR=G. Here is another way to generate an s such that As=b Sample some vector p Sample a z such that Gz = b - Ap Output s = p + Rz ( so As=Ap+Gz=b)
Correcting the Distribution Sample some vector p Sample a z such that Gz = b - Ap Output s = p + Rz ( so As=Ap+Gz=b) How to make the distribution of s independent of R? Tailor the distribution of p to R
