The ZKProof Community

Lattice Cryptography, with zero-knowledge proofs

I would like to introduce the topic here, of zero-knowledge proofs of and/or using Lattice Cryptography, but more specifically the primitive operations which form the basis of Lattice Cryptography (like the matrix vector product) and how the similarities compared to all of the state-of-the-art zero-knowledge proof systems mean that they could be a match made in heaven… if only we didn’t have to deal with n \times m variables , and the huuuge public keys and/or transcripts usually associated with Lattice Cryptography.

Lets look at the primitive operation for lattice cryptography, the matrix-vector product, given A and x, A^{n \times m} \cdot x^m \mapsto y^n; furthermore we may want to do a transform for S^{m \times k}\cdot c^k \mapsto z^m so the result can be used by Az, where all elements are in \mathbb{Z}_q.

With a R1CS, we have n polynomials with m terms, and finding a Short Integer Solution where each of the coefficients x_i \in \mathbb{F}_2 is a ‘Hard Problem™’, especially where the Hamming weight w_h(x) \overset{\text{~}}{=} n. However, with a zkSNARK a matrix-vector product of n \times m requires only n constraints, when the coefficients from A are hard-coded into the proving key.

The problem is \|x\|_2 can’t be calculated \mod{q}, it can only be done over the integers, so we can only rely on using binary constraints to ensure x_i \in \{0,1\}, and possibly some checks for the hamming weight if you are being paranoid.

What are your thoughts?

3 Likes

Cool idea!
@HarryR I really see eye-to-eye on this one and believe that ZK based on lattices will end up becoming efficient and more secure than current constructions.

I find this latest paper quite interesting
https://eprint.iacr.org/2019/642

Where they explore fundamental techniques of constructing zk schemes that are algebraic, based on lattices.

What you claim intuitively in your approach is that since R1CS has the matrix structure, just use it over some ideal lattice to compute some LWE style problem, but then parameters may not match. I like the approach, but I doubt that this would make for an efficient scheme.

1 Like