Understanding Signature Schemes in Cryptography
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
