Lattices and Zero Knowledge by Lyubashevsky
L
a
t
t
i
c
e
s
a
n
d
Z
e
r
o
-
K
n
o
w
l
e
d
g
e
Vadim Lyubashevsky
IBM Research Europe, Zurich
September 16, 2020
Goals of this Talk
Show a glimpse of the similarities / differences between the structure
of lattice and discrete log proofs
Describe situations where lattice-based proofs may already be the
best quantum-safe option
Encourage people to work of improving the fundamentals of lattice-
based zero-knowledge
Zero Knowledge
Typical Use Scenario
(One-way) function f and output f(x) = y
The Prover knows f, x, and y, while the verifier knows f and y.
The Prover presents the verifier a transcript which:
1.
makes the verifier accept an honest prover (Completeness)
2.
implies that the prover knows x (Soundness)
3.
does not reveal any additional information (Zero-Knowledge)
A Lot of Recent Constructions …
with some nice additional properties
1.
The proof transcript is shorter than |x|
2.
The verification time is (almost) independent of |x|
Bulletproofs, Sonic, SuperSonic, MARLIN, PLONK, etc.
Have outputs of just a few KB for proving very large instances
… all based on classical hardness assumptions
Quantum Computing
… and when is it coming?
Make quantum computers good
for something
Reduce errors, increase qubits
Keep improving it (a la new
Moore’s Law)
“It is difficult to make predictions, especially about the future.”
- Danish proverb
Shor’s algorithm breaks
256-bit ECC crypto
“Quantum Supremacy”
“For device physicists to worry about when to reach supremacy is like worrying about when your baby is going to be
smarter than your dog
.
Just focus on taking good care of her and it’ll happen, even though you aren’t sure when.”
-
Yaoyun Shi (2018)
In 2020, we are here
Alien technology
makes this all
irrelevant
2030: 1 million qubit Google prediction
or here…
AES-128
broken by
Grover’s
Make quantum computers good
for something
Reduce errors, increase qubits
Shor’s algorithm breaks
256-bit ECC crypto
2030: 1 million qubit Google prediction
10 – 30 years??
Why do something now?
•
Store now, decrypt later attack
•
Takes time to properly switch crypto
•
In a distributed (e.g. blockchain or even personal automobiles) scenario –
users would need to individually migrate … could take time to get them all
•
May still need to optimally design the crypto protocols. KEMs + signatures
are done, but most of the other stuff is not!
Quantum-Safe ZK Proofs
•
The PCP approach of Kilian, Micali relies just on collision-resistant
hashing, so is quantum-safe
•
Many recent improvements (e.g. Ligero, Aurora)
Downsides:
1.
Some “start up” cost (around 100KB)
2.
Not fast (at least a few hundred ms per hash function proof)
Lattices
(USA-centric) Quantum-Safe Standards
Progress
NSA 2015:
“
IAD
will initiate a transition to quantum resistant algorithms
in the not too distant future
…
For those partners and vendors that have not yet made the transition to Suite B elliptic curve
algorithms, we recommend not making a significant expenditure to do so at this point
but instead to
prepare for the upcoming quantum resistant algorithm transition
.”
NIST 2017:
Starts the Post-Quantum Cryptography Standardization Process for Encryption / KEM and
digital signatures. 69 entries received.
NIST Round 3 Finalists
(announced in July 2020)
Encryption and KEM
•
Classic McEliece
•
CRYSTALS-Kyber
•
NTRU
•
SABER
Digital Signatures
•
CRYSTALS-Dilithium
•
FALCON
•
Rainbow
Lattice schemes in blue
public key + ciphertext ≈ 2KB
faster than EC / RSA-based schemes
public key + signature ≈ 2 - 5KB
verification about the same speed as classical schemes
signing is a bit slower (still can do > 3K sigs/sec)
(USA-centric) Quantum-Safe Standards
Progress
NSA 2020:
“
NSA CSD has reviewed the security analysis and performance characteristics of the
proposals, and
we are confident in those lattice-based schemes with strong dependence on well-
studied mathematical problems
and in hash-based signatures for certain niche solutions …
Based on their history of analysis and implementation efforts,
NSA CSD expects that a NIST-
candidate lattice-based signature and a NIST-candidate lattice-based key encapsulation
mechanism will be approved for NSS
.”
NIST 2022:
Standardizes ???
NSA 2015:
“
IAD will initiate a transition to quantum resistant algorithms in the not too distant future …
For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms,
we recommend not making a significant expenditure to do so at this point but instead to prepare for the
upcoming quantum resistant algorithm transition.”
NIST 2017:
Starts the Post-Quantum Cryptography Standardization Process for Encryption / KEM and digital
signatures. 69 entries received.
Basic Lattice Zero Knowledge
Like Schnorr … but different
Discrete Log and Lattice Problems
Discrete Log Relation
Ring R: Z
q
function f mapping R
k
R’
f(
s
1
, … ,
s
k
) = g
1
s
1
∙ … ∙
g
k
s
k
mod p
f is 1-way
Ring-LWE/ Ring-SIS Relation
Ring R: Z[X]/(X
n
+1)
function mapping R
k
R’
f(
s
1
, … ,
s
k
) = a
1
s
1
+ … a
k
s
k
mod p
f is 1-way if
s
1
, … ,
s
k
have small coefficients
an algebraic bonus: R’ = Z
p
[X]/(X
n
+1)
Want this to be
small (2
12
- 2
32
)
Exponentially
large ( ≥ 2
256
)
More General Lattice Problems
(Module-LWE / SIS)
A
S
t
=
mod p
n
m
a
1,1
a
1,2
…
a
1,m
a
n,1
a
n,2
…
a
n,m
…
…
…
…
s
1
s
2
…
s
m
=
t
1
…
t
n
mod p
Schnorr Protocol for g
s
=h
y
Z
q
w:=g
y
mod p
w
c
Z
q
c
z:=
s
c+y
z
check if:
g
z
= h
c
w mod p
Correctness:
g
sc+y
= g
sc
g
y
Prover:
(g,
s
)
Verifier:
(g,h)
Schnorr Protocol
y
Z
q
w:=g
y
mod p
w
c
Z
q
c
z:=
s
c+y
z
check if:
g
z
= h
c
w mod p
Honest-Verifier Zero Knowledge
Generate random c,z
Z
q
. Set w=g
z
/ h
c
(w,c,z) has the same distribution as in the protocol
Prover:
(g,
s
)
Verifier:
(g,h)
Schnorr Protocol
w
c
Z
q
c
z
g
z
= h
c
w mod p
Proof of Knowledge:
g
z-z’
= h
c-c’
g
(z-z’)/(c-c’)
= h mod p
c’
Z
q
c’
z’
g
z’
= h
c’
w mod p
A successful prover must be able to
answer more than one distinct challenge
s
Prover:
(g,
s
)
Extractor:
(g,h)
Let’s try the same ZK Proof
R=
Z[X]/(X
n
+1)
Prover:
(A,
s
)
Verifier:
(A,t)
y
R
m
w:=Ay mod p
w
c
R
c
z:=
s
c+y
z
check if:
Az = tc + w mod p
Correctness:
A(
s
c+y) = A
s
c+Ay mod p
Let’s try the same ZK Proof
Prover:
(A,
s
)
Verifier:
(A,t)
y
R
m
w:=Ay mod p
w
c
R
c
z:=
s
c+y
z
check if:
Az = tc + w mod p
1.
Should have “small” coefficients – otherwise forging is trivial
2.
(1)
y should have small, with respect to p, coefficients
3.
Now z=
s
c+y is not uniform and leaks information about
s
•
Could make y exponentially larger than
s
c, but this is very bad for efficiency
4.
Better solution: use rejection sampling to make the distribution of z independent of s
(Simple) Rejection Sampling
1.
The distribution in the triangle is uniform
2.
Can’t tell from which “shifted square” the distribution came from
(because it’s the same distribution!)
Want to sample
uniformly in this triangle
Have access to a distribution
for sampling in a square
Use rejection sampling to get a uniform
distribution in the triangle
Important side effect: any “shifted” square
distribution results in the same triangle
distribution
Let’s try the same ZK Proof
Prover:
(A,
s
)
Verifier:
(A,t)
y
R
m
w:=Ay mod p
w
c
R
c
z:=
s
c+y
Rejection sample, and
restart if necessary
z
check that:
1.
Az = tc + w mod p
2.
||
z
||
is small
y+
s
c is a “shifted distribution”
use rejection sampling to get a non-shifted one
other more sophisticated rejection sampling is possible that
allows for “narrower” distributions reducing the norm of z
e.g. gaussian, bimodal gaussian, rounded gaussian
Let’s try the same ZK Proof
w
c
R
c
z
Az = tc+w
||
z
||
is small
Proof of Knowledge:
A(z-z’) = t(c-c’)
A(z-z’)/(c-c’) = t mod p
c’
R
c’
z’
Az’=tc’+w
||
z’
||
is small
A successful prover must be able to
answer more than one distinct challenge
s
Prover:
(A,
s
)
Extractor:
(A,t)
may not be invertible
not necessarily small
Let’s try the same ZK Proof
w
c
R
c
z
Az = tc+w mod p
||
z
||
is small
Proof of Knowledge:
A(z-z’) = t(c-c’) mod p
c’
R
c’
z’
Az’=tc’+w mod p
||
z’
||
is small
A successful prover must be able to
answer more than one distinct challenge
Prover:
(A,
s
)
Extractor:
(A,t)
small
Still a meaningful extraction
Practical Zero-Knowledge Proofs
Approximate Proofs.
Approximate Proofs.
Given:
Given:
As=t
As=t
Prove knowledge of:
Prove knowledge of:
small
small
s’
s’
,
,
c
c
such that
such that
As’=tc
As’=tc
[L ‘09]
[L ‘09]
Fiat-Shamir
Fiat-Shamir
Digital Signatures.
Digital Signatures.
(i.e. Dilithium)
(i.e. Dilithium)
Commitment Scheme to
Commitment Scheme to
vectors of messages in R
vectors of messages in R
with linear (over R)
with linear (over R)
proofs
proofs
[BDLOP]
[BDLOP]
Exact Proofs.
Exact Proofs.
Given:
Given:
A, As=t
A, As=t
Prove knowledge of:
Prove knowledge of:
s
s
such that
such that
As=t
As=t
Multiplicative
Multiplicative
Proofs for
Proofs for
[BDLOP]
[BDLOP]
“Unstructured Proofs”
“Unstructured Proofs”
(i.e. proofs over Z
(i.e. proofs over Z
q
q
) for
) for
[BDLOP]
[BDLOP]
Proofs of Integer
Proofs of Integer
Relations (e.g.
Relations (e.g.
addition,
addition,
multiplication)
multiplication)
[YAZXYW ‘19, BLS ‘19]
[YAZXYW ‘19, BLS ‘19]
[BDLOP ‘18]
[BDLOP ‘18]
[L ‘09, L ’12, DDLL
[L ‘09, L ’12, DDLL
‘13,BG ’14, … ]
‘13,BG ’14, … ]
[EZSLL ‘19]
[EZSLL ‘19]
[ALS ‘20]
[ALS ‘20]
[LNS ‘20]
[LNS ‘20]
[ENS ‘20]
[ENS ‘20]
[ENS ‘20]
[ENS ‘20]
(300KB for some instance)
(50KB)
(3KB for 128-bit security)
An Application Example
Commit-and-prove schemes:
Recall: Ligero and Aurora require a few hundred ms just to prove a commitment
but ... our commitment sizes grow linearly, whereas Ligero / Aurora are sublinear
Make quantum computers good
for something
Reduce errors, increase qubits
Keep improving it (a la new
Moore’s Law)
Shor’s algorithm breaks
256-bit ECC crypto
“Quantum Supremacy”
Goal: Prevent the “store now, decrypt later attack”
f(x) = y where f is a quantum-safe 1-way function (or e.g. f is a commitment / encryption scheme)
ZKPoK of x is:
1.
Complete
2.
Sound based on a
classical assumption
(classical soundness)
3.
Statistically-hiding (i.e. information-theoretically zero-knowledge)
Complete
Sound
Zero-Knowledge
Complete
Sound
Zero-Knowledge
Complete
X
Sound (but could be if proof is timed)
Zero-Knowledge
A Middle-Ground Between Classical and
Quantum-Safe?
Middle-Ground Example [DLS ‘19]
A
A
s
s
t
t
=
A
A
s
s
t
t
=
B
B
v
v
Ring = Z
q
[X]/(X
n
+1)
Ring = Z[X]
Pedersen commitment c=Com(s,v) using ECC
challenge
α
Use “bulletproofs” to prove the
polynomial equality of the values
in c over Z[X] evaluated at
α
implies original statement
Slow!! Takes a few dozen seconds for
“small” lattice relations.
But short: < 2KB for the proof
Conclusions and Further Resources
•
Lattice ZK research is just beginning. We’re still building the fundamentals for proving basic
relations.
•
Could be the fastest quantum-safe solution for many expressions (maybe faster than some
classical ones too?)
•
Can the “middle-ground” approach be made practical? We have not explored any of the post-
bulletproofs proofs.
•
No practical succinct proofs yet – some theoretical works with asymptotic results
Some supplementary resources:
Zero-Knowledge Applications and Standards:
https://docs.zkproof.org/pages/reference/reference.pdf
Basic Lattice Cryptography Tutorial:
www.tinyurl.com/latticesurvey
(or go to a link from my webpage)
More details on lattice-based ZK (and other practical things):
https://simons.berkeley.edu/workshops/schedule/10565
(Some) References
•
[ALS ‘20] Thomas Attema, Vadim Lyubashevsky Gregor Seiler: Practical Product Proofs for Lattice Commitments (Crypto 2020)
•
[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
•
[BLS ‘19]:
Jonathan Bootle
, Vadim Lyubashevsky,
Gregor Seiler
: Algebraic Techniques for Short(er) Exact Lattice-Based Zero-
Knowledge Proofs.
CRYPTO (1) 2019
•
[ENS ‘20]: Muhammed Esgin, Ngoc Khanh Nguyen, Gregor Seiler: Practical Exact Proofs from Lattices: New Techniques to Exploit
Fully-Splitting Rings (Asiacrypt 2020)
•
[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.
EUROCRYPT 2012
•
[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 (CCS 2020)
•
[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
"Explore the concept of lattices and zero-knowledge protocols presented by Vadim Lyubashevsky from IBM Research Europe. The discussion delves into the interplay of cryptographic systems and zero-knowledge proofs in securing data transactions and communication. Gain insights into the practical implications and theoretical foundations of this cutting-edge research in cryptography and cybersecurity."
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
Lattices and Zero Lattices and Zero- -Knowledge Knowledge Vadim Lyubashevsky IBM Research Europe, Zurich September 16, 2020
Goals of this Talk Show a glimpse of the similarities / differences between the structure of lattice and discrete log proofs Describe situations where lattice-based proofs may already be the best quantum-safe option Encourage people to work of improving the fundamentals of lattice- based zero-knowledge
Typical Use Scenario (One-way) function f and output f(x) = y The Prover knows f, x, and y, while the verifier knows f and y. The Prover presents the verifier a transcript which: 1. makes the verifier accept an honest prover (Completeness) 2. implies that the prover knows x (Soundness) 3. does not reveal any additional information (Zero-Knowledge)
A Lot of Recent Constructions with some nice additional properties 1. 2. The proof transcript is shorter than |x| The verification time is (almost) independent of |x| Bulletproofs, Sonic, SuperSonic, MARLIN, PLONK, etc. Have outputs of just a few KB for proving very large instances all based on classical hardness assumptions
Quantum Computing and when is it coming?
It is difficult to make predictions, especially about the future. - Danish proverb 2030: 1 million qubit Google prediction In 2020, we are here or here Make quantum computers good for something Keep improving it (a la new Moore s Law) Reduce errors, increase qubits AES-128 broken by Grover s Quantum Supremacy Shor s algorithm breaks 256-bit ECC crypto Alien technology makes this all irrelevant For device physicists to worry about when to reach supremacy is like worrying about when your baby is going to be smarter than your dog. Just focus on taking good care of her and it ll happen, even though you aren t sure when. - Yaoyun Shi (2018)
2030: 1 million qubit Google prediction Make quantum computers good for something Reduce errors, increase qubits 10 30 years?? Shor s algorithm breaks 256-bit ECC crypto Why do something now? Store now, decrypt later attack Takes time to properly switch crypto In a distributed (e.g. blockchain or even personal automobiles) scenario users would need to individually migrate could take time to get them all May still need to optimally design the crypto protocols. KEMs + signatures are done, but most of the other stuff is not!
Quantum-Safe ZK Proofs The PCP approach of Kilian, Micali relies just on collision-resistant hashing, so is quantum-safe Many recent improvements (e.g. Ligero, Aurora) Downsides: 1. Some start up cost (around 100KB) 2. Not fast (at least a few hundred ms per hash function proof)
(USA-centric) Quantum-Safe Standards Progress NSA 2015: IAD will initiate a transition to quantum resistant algorithms in the not too distant future For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition. NIST 2017: Starts the Post-Quantum Cryptography Standardization Process for Encryption / KEM and digital signatures. 69 entries received.
NIST Round 3 Finalists (announced in July 2020) Encryption and KEM Classic McEliece CRYSTALS-Kyber NTRU SABER Digital Signatures CRYSTALS-Dilithium FALCON Rainbow public key + ciphertext 2KB faster than EC / RSA-based schemes public key + signature 2 - 5KB verification about the same speed as classical schemes signing is a bit slower (still can do > 3K sigs/sec) Lattice schemes in blue
(USA-centric) Quantum-Safe Standards Progress NSA 2015: IAD will initiate a transition to quantum resistant algorithms in the not too distant future For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition. NIST 2017: Starts the Post-Quantum Cryptography Standardization Process for Encryption / KEM and digital signatures. 69 entries received. NSA 2020: NSA CSD has reviewed the security analysis and performance characteristics of the proposals, and we are confident in those lattice-based schemes with strong dependence on well- studied mathematical problems and in hash-based signatures for certain niche solutions Based on their history of analysis and implementation efforts, NSA CSD expects that a NIST- candidate lattice-based signature and a NIST-candidate lattice-based key encapsulation mechanism will be approved for NSS. NIST 2022: Standardizes ???
Basic Lattice Zero Knowledge Like Schnorr but different
Discrete Log and Lattice Problems Discrete Log Relation Ring-LWE/ Ring-SIS Relation Ring R: Z[X]/(Xn+1) Ring R: Zq Exponentially large ( 2256) Want this to be small (212 - 232) function f mapping Rk R function mapping Rk R s1 gk skmod p f(s1 , , sk) = g1 f(s1 , , sk) = a1s1+ aksk mod p f is 1-way f is 1-way if s1 , , sk have small coefficients an algebraic bonus: R = Zp[X]/(Xn+1)
More General Lattice Problems (Module-LWE / SIS) A = t mod p n S m a1,1 a1,2 a1,m s1 t1 tn = mod p s2 an,1 an,2 an,m sm
Schnorr Protocol for gs=h Prover: (g,s) Verifier: (g,h) y Zq w:=gy mod p w c Zq c z z:=sc+y check if: gz = hcw mod p Correctness: gsc+y = gscgy
Schnorr Protocol Prover: (g,s) Verifier: (g,h) y Zq w:=gy mod p w c Zq c z z:=sc+y check if: gz = hcw mod p Honest-Verifier Zero Knowledge Generate random c,z Zq. 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 Zq c Zq z z gz = hcw mod p gz = hc w mod p Proof of Knowledge: gz-z = hc-c g(z-z )/(c-c ) = h mod p s
Lets try the same ZK Proof R=Z[X]/(Xn+1) Prover: (A,s) Verifier: (A,t) y Rm w:=Ay mod p w c R c z z:=sc+y check if: Az = tc + w mod p Correctness: A(sc+y) = Asc+Ay mod p
Lets try the same ZK Proof Prover: (A,s) Verifier: (A,t) y Rm w:=Ay mod p w c R c z z:=sc+y check if: Az = tc + w mod p 1. Should have small coefficients otherwise forging is trivial 2. (1) y should have small, with respect to p, coefficients 3. Now z=sc+y is not uniform and leaks information about s Could make y exponentially larger than sc, but this is very bad for efficiency 4. Better solution: use rejection sampling to make the distribution of z independent of s
(Simple) Rejection Sampling Want to sample uniformly in this triangle Have access to a distribution for sampling in a square Use rejection sampling to get a uniform distribution in the triangle Important side effect: any shifted square distribution results in the same triangle distribution 1. The distribution in the triangle is uniform 2. Can t tell from which shifted square the distribution came from (because it s the same distribution!)
Lets try the same ZK Proof Prover: (A,s) Verifier: (A,t) y Rm w:=Ay mod p w c R c z:=sc+y Rejection sample, and restart if necessary z check that: 1. Az = tc + w mod p 2. ||z|| is small y+sc is a shifted distribution use rejection sampling to get a non-shifted one other more sophisticated rejection sampling is possible that allows for narrower distributions reducing the norm of z e.g. gaussian, bimodal gaussian, rounded gaussian
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 mod p 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 mod p ||z|| is small Az =tc +w mod p ||z || is small Proof of Knowledge: A(z-z ) = t(c-c ) mod p Still a meaningful extraction small
Practical Zero-Knowledge Proofs Approximate Proofs. Commitment Scheme to vectors of messages in R with linear (over R) proofs [BDLOP] [EZSLL 19] [ALS 20] Given: As=t Prove knowledge of: small s ,c such that As =tc [L 09] [BDLOP 18] Multiplicative Proofs for [BDLOP] 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. (i.e. Dilithium) Given: A, As=t Prove knowledge of: s such that As=t (50KB)
An Application Example Commit-and-prove schemes: Commit to three 32-bit integers A, B, C & Prove that A + B = C & Prove that A * B = C Proof time < 3 ms < 3 ms Proof size 11 KB 15 KB Recall: Ligero and Aurora require a few hundred ms just to prove a commitment but ... our commitment sizes grow linearly, whereas Ligero / Aurora are sublinear
A Middle-Ground Between Classical and Quantum-Safe? Make quantum computers good for something Keep improving it (a la new Moore s Law) Reduce errors, increase qubits Complete Sound Zero-Knowledge Complete X Sound (but could be if proof is timed) Zero-Knowledge Complete Sound Zero-Knowledge Quantum Supremacy Shor s algorithm breaks 256-bit ECC crypto Goal: Prevent the store now, decrypt later attack f(x) = y where f is a quantum-safe 1-way function (or e.g. f is a commitment / encryption scheme) ZKPoK of x is: 1. Complete 2. Sound based on a classical assumption (classical soundness) 3. Statistically-hiding (i.e. information-theoretically zero-knowledge)
Middle-Ground Example [DLS 19] Ring = Zq[X]/(Xn+1) Ring = Z[X] = B A t = A t s s v implies original statement Use bulletproofs to prove the polynomial equality of the values in c over Z[X] evaluated at Pedersen commitment c=Com(s,v) using ECC Slow!! Takes a few dozen seconds for small lattice relations. But short: < 2KB for the proof challenge
Conclusions and Further Resources Lattice ZK research is just beginning. We re still building the fundamentals for proving basic relations. Could be the fastest quantum-safe solution for many expressions (maybe faster than some classical ones too?) Can the middle-ground approach be made practical? We have not explored any of the post- bulletproofs proofs. No practical succinct proofs yet some theoretical works with asymptotic results Some supplementary resources: Zero-Knowledge Applications and Standards: https://docs.zkproof.org/pages/reference/reference.pdf Basic Lattice Cryptography Tutorial: www.tinyurl.com/latticesurvey (or go to a link from my webpage) More details on lattice-based ZK (and other practical things): https://simons.berkeley.edu/workshops/schedule/10565
(Some) References [ALS 20] Thomas Attema, Vadim Lyubashevsky Gregor Seiler: Practical Product Proofs for Lattice Commitments (Crypto 2020) [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 [BLS 19]: Jonathan Bootle, Vadim Lyubashevsky, Gregor Seiler: Algebraic Techniques for Short(er) Exact Lattice-Based Zero- Knowledge Proofs. CRYPTO (1) 2019 [ENS 20]: Muhammed Esgin, Ngoc Khanh Nguyen, Gregor Seiler: Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings (Asiacrypt 2020) [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. EUROCRYPT 2012 [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 (CCS 2020) [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
