International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 05 December 2022

Yuan Tian
ePrint Report ePrint Report
Various matrix relations widely appeared in data-intensive computations, as a result their zero-knowledge proofs/arguments (ZKP/ZKA) are naturally required in large-scale private computing applications. In the first part of this paper, we concretely establish efficient zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UQV = Y over the residue ring Zm with logarithmic message complexity. We take a direct, matrix-oriented (rather than vector-oriented in usual) approach to such establishments on basis of the elegant commitment scheme over the ring recently established by Attema et al[16]. The constructed protocols are public coin and in c.r.s paradigm (c.r.s used only as the public-key of the commitment scheme), suitable for any size matrices and outperform the protocols constructed in usual approach when number of columns > log(number of rows) with significantly smaller c.r.s., fewer rounds and lower message complexity, particularly for large-size squares. The on-line computational complexity is almost the same for both approaches. In the second part, on basis of the simulation-sound tag-based trapdoor commitment schemes we establish a general compiler to transform any public coin proof/argument protocol into the one which is concurrently non-malleable with unchanged number of rounds, properly increased message and computational complexity. Such enhanced protocols, e.g., the versions compiled from those constructed in the first part of this work, can run in parallel environment while keeping all their security properties, particularly resisting man-in-the-middle attacks.
Expand

Additional news items may be found on the IACR news page.