Paper 2022/1689
Efficient Zero-Knowledge Arguments for Some Matrix Relations over Ring and Non-malleable Enhancement
Abstract
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 commit-and-proof zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UTQV = 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 finite 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 significantly outperform the protocols constructed in usual approach with smaller-sized c.r.s.(e.g., decreased by a factor of d for linear and by n2d for bilinear relation where d is the extension degree of Galois ring and n is the order of square witness), fewer rounds (decreased by a fraction >logd/2logn for linear and >1/2 for bilinear relation) and lower message complexity (e.g., number of ring elements decreased by a fraction > logd/logn for linear and >1/6 for bilinear relation) for large-size squares. The on-line computational complexities are almost the same in 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.
Note: A small example and Appendix D added.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Zero-KnowledgeLinear Matrix EquationBilinear Matrix Equation∑- ProtocolConcurrent Nom-malleabilityGalois Ring
- Contact author(s)
- tianyuan_ca @ dlut edu cn
- History
- 2023-04-08: last of 4 revisions
- 2022-12-05: received
- See all versions
- Short URL
- https://ia.cr/2022/1689
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1689,
author = {Yuan Tian},
title = {Efficient Zero-Knowledge Arguments for Some Matrix Relations over Ring and Non-malleable Enhancement},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1689},
year = {2022},
url = {https://eprint.iacr.org/2022/1689}
}
