Understanding Signatures, Commitments, and Zero-Knowledge in Lattice Problems
Explore the intricacies of lattice problems such as Learning With Errors (LWE) and Short Integer Solution (SIS), and their relation to the Knapsack Problem. Delve into the hardness of these problems and their applications in building secure cryptographic schemes based on polynomial rings and lattices over rings. Uncover the significance of reductions in polynomial rings and the connection between lattice problems and knapsack problems. Learn about worst-case to average-case reduction from lattice problems to knapsacks, and the role of specific polynomial functions in this context.
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
Signatures, Commitments, and Zero-Knowledge Vadim Lyubashevsky IBM Research Europe, Zurich
Lattice Problems (LWE & SIS) The knapsack problem encompasses SIS and LWE: m mod q n A t = s Given integer (A,t), find s with small coefficients such that As=t mod q This is inhomogeneous SIS (the homogeneous SIS has t=0).
Why is this LWE? = t = + t = s2 A A B A t Id B s1 s s
Hardness of the Knapsack Problem = mod q A A t t s s Consider fA : fA(s) = As mod q Problem: Find small s s.t. fA(s ) = t Want to build a scheme based with this ||s||, but usually constraints don t allow it e.g. encryption schemes won t have correctness, signature schemes won t have soundness, etc. hardness LWE SIS injective onto ||s||
Knapsack Problem = Lattice Problem m mod q n A t = s Find a short vector in an integer lattice of dimension m and determinant qn
Polynomial Rings R=Zq[X]/(f(x)) Example Ring Z17[x]/(x4+1) Elements are z(x)=z3x3+z2x2+z1x+z0 where zi are integers mod 17 Addition is the usual coordinate-wise addition Multiplication is the usual polynomial multiplication followed by a reduction modulo x4+1 6
Polynomial Rings R=Zq[X]/(f(x)) (X3 - 2X - 1)(-3X2 + 6) = (-3X5 + 12X3 +3X2 -12X - 6) = (3X + 12X3 + 3X2 -12X - 6) = (-5X3 +3X2 +8X -6) Important: Reductions modulo X4+1 do not increase the coefficients! (For some moduli, there could be an exponential increase these are not useful for crypto). 7
Lattices over R=Zq[X]/(f(x)) m n A t = s Find a short vector in an integer lattice of dimension dm and determinant qdn f(X)=Xd + fd-1Xd-1 + + f1X + f0 , fi in Z A is in Rn x m s is in Rm with small coefficients
Polynomial Rings Asymptotically, worst-case to average-case reduction from lattice problems over the ring Z[X]/(f(X)) to knapsacks over Zq[X]/(f(x)) What should f(X) and q be according to the reductions? f(X) should be irreducible and multiplication mod f(X) should not increase the coefficients too much. Otherwise, no guidance (e.g. could some f(X) make the problem to be easier?) reductions (mostly) work for any q
So, which f(X) and q get used most often? For efficiency, some popular choices are: 1. f(X) = Xd+1 (d a power of 2), and q such that Xd+1 has low-degree (of 1 or 2) factors Least coefficient growth and fastest operations using NTT 2. f(X) = Xd+1 (d a power of 2), q a power of 2 Least coefficient growth and easy mod q representation 3. f(X) = a cyclotomic has many of the same properties of Xd+1
Choosing f(X) and q for various schemes f(X) q Comment Encryption and Fiat-Shamir Signatures (see http://tinyurl.com/LatticeSurvey) doesn t matter much doesn t matter much, but a q compatible with NTT will lead to the fastest schemes The algebraic structure of f(X) does not come into play in the constructions Hash-and-Sign Signatures (talks on Wednesday) Want a cyclotomic f(X)= m(X) where m has a few distinct small factors doesn t matter much. verification will be fastest with NTT In practice, anything other than f(X)= 2d(X)= Xd+1 (where d is a power-of-2), makes the sampling algorithm really complicated Fully-Homomorphic Encryption (talks on Thursday / Friday) want a cyclotomic f(X)= m(X) doesn t matter much. there are trade-offs for different q (Ring-)LWE Ciphertexts are modulo p << q. To have many CRT slots for arithmetic operations, choose p such that m(X) splits into linear factors mod p want CRT slots for arithmetic operations, and algebraic structure (e.g. automorphisms) is useful. May not necessarily want splitting into linear factors. Zero-Knowledge Proofs and Applications (This talk) want a cyclotomic f(X)= m(X) We ll fix f(X)=Xd+1 want a q where m(X) splits into linear (or small-degree) factors mod q
A Word of Caution Need to be very careful when claiming the shortest lattice-based proof There are generic (e.g. PCP) proofs (e.g. [BCRSVW 19]) which can prove lattice relations These generic proofs are even succinct (i.e. grow logarithmically in the number of inputs) So what can lattices offer (right now)? 1. Shorter proofs for certain relations PCP-based proofs have a fixed cost of 100KB (for somewhat acceptable speeds) 2. Speed. Lattice schemes are fast. Lattice encryption schemes can be 5X faster than the best discrete log schemes (e.g. [LS 19]). The ZK proofs use essentially the same operations. PCP schemes are fairly slow (would take seconds / minutes) to prove lattice relations. Personal view for a lattice ZK proof to be interesting, it should be less than 500KB preferably less than 100KB. Or at the very least, a comparison with PCP proofs in terms of speed / size needs to be given.
What do we Want to Prove in Zero-Knowledge? For starters, knowledge of the solution to the fundamental problem i.e. given A and t=As, with s being small, prove knowledge of s Discrete logarithm equivalent: given g, h=gs, prove knowledge of s This is the Schnorr protocol
Schnorr Protocol Prover: (g,s) Verifier: (g,h) y Zp w:=gy w c Zp c z z:=sc+y check if: gz = hcw Correctness: gsc+y = gscgy
Schnorr Protocol Prover: (g,s) Verifier: (g,h) y Zp w:=gy w c Zp c z z:=sc+y check if: gz = hcw Honest-Verifier Zero Knowledge Generate random c,z Zp. Set w=gz / hc (w,c,z) has the same distribution as in the protocol
Schnorr Protocol Prover: (g,s) Extractor: (g,h) w A successful prover must be able to answer more than one distinct challenge c c c Zp c Zp z z gz = hcw gz = hc w Proof of Knowledge: gz-z = hc-c g(z-z )/(c-c ) = h s
In the lattice world A = t mod q n S m R=Zq[X]/(Xd+1) A is in Rn x m s is in Rm with small coefficients
Lets try the same ZK Proof Prover: (A,s) Verifier: (A,t) y Rm w:=Ay w c R c z z:=sc+y check if: Az = tc + w Correctness: A(sc+y) = Asc+Ay
Lets try the same ZK Proof Prover: (A,s) Verifier: (A,t) y Rm w:=Ay w c R c z z:=sc+y check if: Az = tc + w 1. Should have small coefficients otherwise it s not hard to find such a z without knowing s 2. This means that y and c should have small coefficients and the verifier should check that z is small 3. Now z=sc+y is not uniform and leaks information about s Could make y exponentially larger than sc (a.k.a. noise drowning), but this is inefficient because the coefficients of everything grow 4. Better solution: use rejection sampling to make the distribution of z independent of s
Rejection Sampling Have access to a distribution g(x), but would like to sample from f(x) Define M= max (f(x)/g(x)) over all x in the domain of g Then, the solution is: 1. Sample x from distribution g 2. Output it with probability f(x)/Mg(x), and repeat otherwise Easy to see that at each try, Pr[x] = g(x) f(x)/Mg(x) = f(x)/M, This is the correct (scaled) distribution Another way to look at it: the output hides the original distribution g
Lets try the same ZK Proof Prover: (A,s) Verifier: (A,t) y Rm w:=Ay w c R c z:=sc+y Rejection sample, and restart if necessary z check that: 1. Az = tc + w 2. ||z|| is small distribution g depends on s want to output a distribution f that doesn t depend on s Several possible distributions: 1. Can aim for a uniform distribution in a box (i.e. each coefficient is random between [-r and r] 2. Can aim for a Gaussian distribution 3. Sometimes, can get a bimodal Gaussian distribution Can get ||z|| = O( ??) ||s|| instead of 2128 ||s||
Lets try the same ZK Proof Prover: (A,s) Extractor: (A,t) w A successful prover must be able to answer more than one distinct challenge c c c R c R z z Az = tc+w ||z|| is small Az =tc +w ||z || is small Proof of Knowledge: A(z-z ) = t(c-c ) A(z-z )/(c-c ) = t may not be invertible not necessarily small s
Lets try the same ZK Proof Prover: (A,s) Extractor: (A,t) w A successful prover must be able to answer more than one distinct challenge c c c R c R z z Az = tc+w ||z|| is small Az =tc +w ||z || is small Proof of Knowledge: A(z-z ) = t(c-c ) Still a meaningful extraction small
A Relaxed Zero-Knowledge Proof The prover knows a linear relation As=t He can only prove knowledge of a small c and a larger z such that Az=ct Useful for signatures (the previous protocol made non-interactive using the Fiat-Shamir transform). Proof intuition: If the public key is A,t=As, and an adversary can produce a solution Az=tc, then we obtain the equation Az=Asc, and so A(z-sc)=0 is a solution to SIS (If s is hidden from the adversary and not unique, then z-sc is not 0) But not useful for other applications: e.g. proof of a proper ciphertext
Practical Zero-Knowledge Proofs Approximate Proofs. Commitment Scheme to vectors of messages in R with linear (over R) proofs [BDLOP] Given: As=t Prove knowledge of: small s ,c such that As =tc [L 09] [BDLOP 18] Multiplicative Proofs for [BDLOP] [ALS 20] Proofs of Integer Relations (e.g. addition, multiplication) [L 09, L 12, DDLL 13,BG 14, ] [YAZXYW 19, BLS 19] (300KB for some instance) [LNS 20] [ENS 20] (3KB for 128-bit security) Exact Proofs. [ENS 20] Unstructured Proofs (i.e. proofs over Zq) for [BDLOP] Fiat-Shamir Digital Signatures. Given: A, As=t Prove knowledge of: s such that As=t (50KB)
Practical Zero-Knowledge Proofs This talk Approximate Proofs. Commitment Scheme to vectors of messages in R with linear (over R) proofs [BDLOP] Given: As=t Prove knowledge of: small s ,c such that As =tc [L 09] [BDLOP 18] Multiplicative Proofs for [BDLOP] [ALS 20] Proofs of Integer Relations (e.g. addition, multiplication) [L 09, L 12, DDLL 13,BG 14, ] [YAZXYW 19, BLS 19] [LNS 20] [ENS 20] Exact Proofs. [ENS 20] Unstructured Proofs (i.e. proofs over Zq) for [BDLOP] Fiat-Shamir Digital Signatures. Given: A, As=t Prove knowledge of: s such that As=t
Practical Zero-Knowledge Proofs Next (Gregor s) talk This talk Approximate Proofs. Commitment Scheme to vectors of messages in R with linear (over R) proofs [BDLOP] Given: As=t Prove knowledge of: small s ,c such that As =tc [L 09] [BDLOP 18] Multiplicative Proofs for [BDLOP] [ALS 20] Proofs of Integer Relations (e.g. addition, multiplication) [L 09, L 12, DDLL 13,BG 14, ] [YAZXYW 19, BLS 19] [LNS 20] [ENS 20] Exact Proofs. [ENS 20] Unstructured Proofs (i.e. proofs over Zq) for [BDLOP] Fiat-Shamir Digital Signatures. Given: A, As=t Prove knowledge of: s such that As=t
[BDLOP 18] Commitment Scheme A B 0 tA + = tB m r Hiding: ( , ) r A B A B indistinguishable from uniform To Open: 1. Reveal small r 2. The m is implicitly tB - Br Binding: Suppose r r are valid openings Then Ar = tA = Ar A(r-r )=0 Solution to SIS
Proof of Knowledge B ( ) r A 0 m tA tB Given Ar=tA + = Prove knowledge of small z,c satisfying Az=ctA If c is invertible in Rq, write v=z/c. So equivalent to: To Open: 1. Reveal (v,c) 2. The m is implicitly tB - Bv Given Ar=tA Prove knowledge of v and small c such that 1. Av=tA 2. vc is small Binding: Suppose (v,c) and (v ,c ) for v v are valid openings Then Av = tA= Av Acc v = cc tA = Acc v A(cvc c v c)=0 Solution to SIS small coefficients and cc v cc v
Parameter Setting ( , ) r A B A B Hiding: indistinguishable from uniform Binding: can t find y (= cvc c v c) such that Ay=0 ||vc||,||vc|| = O( ??) ||r|| ||y||= O( ??) ||r|| hiding binding O( ??) ||r|| LWE SIS hardness injective onto ||s||
Invertibility in R NB: A sufficient, but not a necessary condition if q = 2k+1 (mod 4k) is prime, then: Xd+1 = (Xd/k r1) (Xd/k rk) mod q for ri in Zq and (Xd/k ri) irreducible. Addition is coefficient-wise a = a0 + a1X + a2X2 + + ad-1Xd-1 Coefficient Representation: CRT / NTT representation: (a mod Xd/k - r1, , a mod Xd/k - rk) Addition and multiplication is coefficient-wise Polynomials of degree d/k-1 An element in R is invertible if and only if its NTT representation has no zeros.
Invertibility of the Extracted Challenge Can prove that all polynomials with small norms are invertible (e.g. [SS 11, LS 18]) if Xd+1 splits into a few (e.g. 8 or 16) irreducible factors Can prove that the probability that a random polynomial in R with -1/0/1 coefficients hits any particular NTT value is very small (e.g. for q 232, Pr [c mod X4-r1= b] 2-128). So two values in the extraction are unlikely to collide and the difference will be invertible mod every X4-r1 [CLS 16, ALS 20]
Proof of Knowledge of Linear Relations B ( ) and Lm=u (r,m) are secret r A 0 m tA tB Verifier Prover + = choose small y wA = Ay wB = LBy Doesn t need to be sent in the NIZK So proof size stays the same wA, wB c z = rc + y (Rej. Sample) z check that 1. z is small 2. Az = ctA + wA 3. LBz = c(LtB - u) + wB Rewriting v=z /c Rewinding Av=t L(tB- Bv) = u Az = c tA LBz = c (LtB - u) m = tB - Bv Note: With one extra commitment, u can be secret too Lm = u
More Powerful Proofs Given: Commitments to m1, m2, m3 Prove: m1m2 = m3 (Multiplicative Relation) Given: Commitment to m = m0+m1X+ + md-1Xd-1 , n = n0 + n1X + + nd-1Xd-1 and a public matrix L in Zq d x d m0 m1 md-1 n0 n1 nd-1 L Prove that = mod q (Unstructured Relation)
Example Applications Committing to a message with 0/1 coefficients. Let m in R in NTT form consist of 0/1 integers tA tB tA c1 = Commit(m-1) = c0 = Commit(m) = tB-1 Prove that the product of the committed messages of c0 and c1 is 0 m1 m2 mk m1-1 m2 -1 mk -1 0 0 0 = if and only if mi are 0/1
Example Applications (Range Proof) Range Proof: show that an integer is between 0 and 2j Let m in Rq in NTT form be a binary integer mk m2m1 0 tA tA tB 1 1 0 0 c0 = Commit(m) = - first j NTT positions c1 = tB last NTT positions m1-1 mj-1 mj+1 mk 0 0 0 0 m1 mj mj+1 mk = if and only if 0 m < 2j in binary
Example Applications (As = t) Proof of small s (0/1 coeffs) satisfying As=t (i.e. LWE or SIS solution) 1. Commit to s and to a message m whose NTT are the coefficients of s 2. Prove that m has 0/1 NTT coefficients (Multiplicative proof) 3. Prove that As=t (Proof of Linear Relation) 4. Prove that s= NTT(m) (Unstructured Relation Proof) NTT over R is a linear relation over Zq
Example Application (Integer Sum) Proof of integer addition: Given commitments to integers m1, m2, m3 (written in binary), prove that m1 + m2 = m3 1. Let c be the carry vector => as polynomials m3 = m1 + m2 + (X-2)c 2. Commit to n1, n2, n3, nc whose NTT coefficients are m1, m2, m3, c 3. Prove that n1, n2, n3, nc have 0/1 coefficients(Mult. Proof) 4. Prove that NTT(ni)=mi and NTT(nc)=c (Unstr. Rel. Proof) 5. Prove that m3 = m1 + m2 + (X-2)c (Lin. Rel. Proof) 0 1 1 1 0 00101 + 00111 01100 0X4+0X3+1X2+0X+1 + 0X4+0X3+1X2+1X+1 0X4+0X3+2X2+1X+2 1X-2 Does not change the evaluation at 2 (i.e. the binary representation) 1X2 -2X 1X3 -2X2 0X4+1X3+1X2+0X+0
Example Application (Integer Product) Proof of integer multiplication: Given commitments to integers m1, m2, m3 (written in binary), prove that m1m2 = m3 1. Let c be the carry vector => as polynomials m3 = m1m2 + (X-2)c 2. Commit to n1, n2, n3, nc whose NTT coefficients are m1, m2, m3, c 3. Prove that n1, n2, n3 have 0/1 coefficientsand c has small coefficients 4. Prove that NTT(ni)=mi and NTT(nc)=c 5. Prove that m3 = m1m2 + (X-2)c The carry vector for schoolbook multiplication has coefficients between 0 and 32 (if multiplying 32-bit numbers) Can be much larger when multiplying larger numbers Range proofs for larger ranges is more expensive proof grows logarithmically in the range size Observation: we just need to prove that the coefficients in c don t cause a reduction mod q
Relaxed Range Proof c Lemma [BL 18]: let c be a vector in Zk and y a vector in Zn If U is chosen at random with coefficients in 0/1, then Pr[ ||Uc+y mod q|| .5 ||c|| ] 2-n In other words, if Uc+y mod q is small, then c must be small. U y z + = Important Notes: If working over Z[X]/(Xd+1), the probability does not become 2-dn, it stays as 2-n Taking the coefficients of U from a larger range than 0/1 also does not help So it s important that the random matrix U be integer even if working over a larger ring
k Relaxed Range Proof c U y z n + = Have a commitment to c 1. Create a commitment to y and send it to the Verifier 2. Receive the challenge U from the Verifier 3. Output z=Uc+y (use rejection sampling to not leak c) 4. Use Unstructured Relation proof to show that Uc is a commitment to z-y. If ||c|| < 32, then ||z|| is approximately 32nk, so the lemma states that ||c|| < 64nk << q, so no carries
Proof and Commitment Sizes Commitment Size Proof Size Digital Signature (e.g. [DKLLSSS 18]) (public key) 1.5 KB (signature) 3KB Commit to a message in R and Prove knowledge of it 6KB 6KB Commit to a 32-bit integer and Prove that it s between 0 and 2j 6KB 7KB Commit to 32-bit integers m1, m2, m3 and Prove m1+m2=m3 Commit to 32-bit integers m1, m2, m3 and Prove m1m2=m3 7KB 15KB (Ongoing work. The numbers are approximate and could change.) 7KB 20KB
Lots of Open Problems Improve BDLOP commitment Improving ZK proofs Improve ZK proofs without improving BDLOP commitments Apply ZK proofs to more efficient blind signatures / group signatures / etc. Practical succinct proofs. There are some sublinear proofs, but the noise grows a lot. ROM vs QROM the most efficient instantiations are based on the hardness of lattice problems in the ROM. Can we prove their hardness in the QROM (see Mark s talk Tuesday) Does it matter? i.e. can we produce any natural example where a proof in the ROM ends up being insecure against a quantum attacker?
Thanks! [ALS 20] Thomas Attema, Vadim Lyubashevsky Gregor Seiler: Practical Product Proofs for Lattice Commitments (In submission) [BCRSVW 19]: Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, Nicholas P. Ward: Aurora: Transparent Succinct Arguments for R1CS. EUROCRYPT (1) 2019 [BDLOP 18]: Carsten Baum, Ivan Damg rd, Vadim Lyubashevsky, Sabine Oechsner, Chris Peikert: More Efficient Commitments from Structured Lattice Assumptions. SCN 2018 [BG 14]: Shi Bai, Steven D. Galbraith: An Improved Compression Technique for Signatures Based on Learning with Errors. CT-RSA 2014: 28-47 [BL 18]: Carsten Baum, Vadim Lyubashevsky: Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings. IACR Cryptology ePrint Archive 2017 [BLS 19]: Jonathan Bootle, Vadim Lyubashevsky, Gregor Seiler: Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs. CRYPTO (1) 2019 [CLS 16]: Hao Chen, Kristin E. Lauter, Katherine E. Stange: Security Considerations for Galois Non-dual RLWE Families. SAC 2016 [DDLL 13]: L o Ducas, Alain Durmus, Tancr de Lepoint, Vadim Lyubashevsky: Lattice Signatures and Bimodal Gaussians. CRYPTO (1) 2013: [DKLLSSS 18]: L o Ducas, Eike Kiltz , Tancr de Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, Damien Stehl :CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(1) [ENS 20]: Muhammed Esgin, Ngoc Khanh Nguyen, Gregor Seiler: Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings (In Submission) [L 09]: Vadim Lyubashevsky: Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. ASIACRYPT 2009 [L 12]: Vadim Lyubashevsky: Lattice Signatures without Trapdoors. EUROCRYPT2012 [LS 18]: Vadim Lyubashevsky, Gregor Seiler: Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs. EUROCRYPT (1) 2018 [LS 19]: Vadim Lyubashevsky, Gregor Seiler: NTTRU: Truly Fast NTRU Using NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019 [LNS 20]: Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler: Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations (In preparation) [SS 11]: Damien Stehl , Ron Steinfeld: Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. EUROCRYPT2011 [YAZXYW 19]: Rupeng Yang, Man Ho Au, Zhenfei Zhang, Qiuliang Xu, Zuoxia Yu, William Whyte: Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications. CRYPTO (1) 2019
