Efficient Zero-Knowledge Argument for Bilinear Matrix Relation over the Residue Ring
摘要
In private computing applications various data relations can be represented by or reduced to some matrix relations. In addition, the residue ring \(\textrm{Z}_m\) is one of the most widely used arithmetic systems in practice. One of the main challenges in constructing zero-knowledge argument/proof protocols for relations over a ring is how to ensure sufficient number of challenges to fulfill the necessary knowledge-soundness requirements. In this paper, we establish an efficient zero-knowledge arguments for bilinear matrix relation \(\textbf{U}^{\textbf{T}} \textbf{Q V}=\textbf{Y}\) over \(\textrm{Z}_m\) with logarithmic message complexity. We take a direct, matrix-oriented (rather than vector-oriented as usual) approach to such establishments on basis of the elegant commitment scheme over the ring recently established by Attema et al. (2022). The protocol is public-coin and in c.r.s paradigm (c.r.s used only as the public-key of the commitment scheme), suitable for matrices in any size and significantly outperforms the protocols constructed in usual approach when number of columns > log(number of rows) with significantly smaller c.r.s. (e.g., decreased by a factor of \(n^2 d\) where d is the extension degree of Galois ring and n is the order of square witness), fewer rounds (decreased by a fraction \(>1 / 2\) ) and lower message complexity (e.g., number of ring elements decreased by a fraction \(>1 / 6\) ) for large-size squares. The on-line computational complexity is almost the same for both approaches.