Elimination-based certificates for triangular equivalence and rank profiles
Elimination-based certificates for triangular equivalence and rank profiles
复制标题
DOI：
10.1016/j.jsc.2019.07.013
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
J. Dumas;E. Kaltofen;David Lucas;Clément Pernet
中科院分区：
文献类型：
--
作者：
J. Dumas;E. Kaltofen;David Lucas;Clément Pernet
在本文中，我们给出了三角形等价和等级分布的新颖证书。这些证书使某人能够比重新计算它们更快地验证行或列等级配置文件或整个等级配置文件矩阵，并且总体开销可以忽略不计。我们首先提供二次时间和空间非交互式证书，保存了先前已知证书的对数因子。然后，我们针对相同问题提出交互式证书，其蒙特卡罗验证复杂性需要少量恒定数量的矩阵向量乘法、线性空间和线性数量的额外字段操作，以及线性数量的交互。作为一个应用程序，我们还提供了一个交互式协议，证明密集矩阵的行列式或签名，对于证明者来说比之前已知的协议更快。最后，我们给出行或列等级分布的线性空间和常量轮证书。
In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable somebody to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead. We first provide quadratic time and space non-interactive certificates saving the logarithmic factors of previously known ones. Then we propose interactive certificates for the same problems whose Monte Carlo verification complexity requires a small constant number of matrix-vector multiplications, a linear space, and a linear number of extra field operations, with a linear number of interactions. As an application we also give an interactive protocol, certifying the determinant or the signature of dense matrices, faster for the Prover than the best previously known one. Finally we give linear space and constant round certificates for the row or column rank profiles.