Welcome to the resource topic for 2022/1728
Title:
Efficient Zero Knowledge Arguments for Bilinear Matrix Relations over Finite Fields and Knowledge-Soundness Enhancement via Operations over Extended Field
Authors: Yuan Tian
Abstract:In data-intensive private computing applications various relations appear as or can be reduced to various matrix relations. In this paper we investigate two problems related to constructing the zero-knowledge argument (ZKA) protocols for matrix relations.
In the first part, we establish the ZKA for some bilinear matrix relations over Fp. The relations in consideration include (1) general forms of bilinear relations with two witness matrices and some most important special cases. (2) some special forms of bilinear relations with three or four witness matrices. (3) eigenvalue relation. In private computing tasks various important relations are instances or special cases of these relations, e.g., matrix multiplicative relation, inverse relation, similarity relation, some structure decomposition relation and some isomorphic relations for lattices and graphs, etc. Instead of applying the general linearization approach to dealing with these non-linear relations, our approach is matrix-specific. The matrix equation is treated as a tensor identity and probabilistic-equivalent reduction techniques (amortization) are widely applied to reduce non-linear matrix relations to vector nonlinear relations. With the author’s knowledge, currently there are no other systematic works on ZKA for nonlinear matrix relations. Our approach significantly outperforms the general linearization approach in all important performances, e.g., for n-by-t matrix witnesses the required size of c.r.s (only used as the public-key for commitment) can be compressed by 2t times; when n>>t or t>>n the number of rounds, group and field elements in messages are all decreased by ~1/2; when n~t (e.g., square witnesses) they are all decreased by ~1/3.
In the second part, we enhance knowledge-soundness of ZKA for the linear matrix relation over the ground field Fp. By treating the matrix in F_p^(n×td) as a nt-dimensional vector over the d-th extended field over Fp and applying appropriate reductions, we decrease the knowledge-error of the original ZKA over Fp from O(1/p) down to O(1/p^d). This is comparable to the general parallel repetition approach which improves knowledge-error to the same degree, but our approach (matrix-specific) at the same time significantly improves other performances, e.g., smaller-sized c.r.s., fewer rounds and shorter messages.
ePrint: https://eprint.iacr.org/2022/1728
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .