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?