Paper 2022/1728
Efficient Zero Knowledge Arguments for Bilinear Matrix Relations over Finite Fields and KnowledgeSoundness Enhancement via Operations over Extended Field
Abstract
In dataintensive private computing applications various relations appear as or can be reduced to matrix relations. In this paper we investigate two problems related to constructing the zeroknowledge argument (ZKA) protocols for matrix relations (in commitandprove paradigm). 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 nonlinear relations, our approach is matrixspecific. The matrix equation is treated as a tensor identity and probabilisticequivalent reduction techniques (amortization) are widely applied to reduce nonlinear 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 nbyt matrix witnesses the required size of c.r.s (only used as the publickey for commitment) can be compressed by 2nt times and the number of rounds, group and field elements in messages are all decreased by ~1/2 for largesize matrix. In the second part, we enhance knowledgesoundness of ZKA for the linear matrix relation over the ground field Fp. By treating the matrix in F_p^(n×td) as a ntdimensional vector over the dth extended field over Fp and applying appropriate reductions, we decrease the knowledgeerror of the original ZKA over Fp from O(1/p) down to O(1/pd). This is comparable to the general parallel repetition approach which improves knowledgeerror to the same degree, but our approach (matrixspecific) at the same time significantly improves other performances, e.g., smallersized c.r.s., fewer rounds and shorter messages.
Note: Some typos Corrected.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 ZeroKnowledge Matrix Equations ∑Protocols Knowledgeerror Finite Field
 Contact author(s)
 tianyuan_ca @ dlut edu cn
 History
 20221221: last of 2 revisions
 20221215: received
 See all versions
 Short URL
 https://ia.cr/2022/1728
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1728, author = {Yuan Tian}, title = {Efficient Zero Knowledge Arguments for Bilinear Matrix Relations over Finite Fields and KnowledgeSoundness Enhancement via Operations over Extended Field}, howpublished = {Cryptology ePrint Archive, Paper 2022/1728}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1728}}, url = {https://eprint.iacr.org/2022/1728} }