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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient Zero-Knowledge Argument for Bilinear Matrix Relation over the Residue Ring

  • Yuan Tian,
  • Yongda Pang

摘要

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.