Paper 2026/514

Secure Matrix Invertibility Testing over Fields of Small Order or Characteristics

Jooyoung Lee, Korea Advanced Institute of Science and Technology

Seungmin Park, Korea Advanced Institute of Science and Technology

Mincheol Son, Korea Advanced Institute of Science and Technology

Abstract

Multi-party matrix invertibility testing over finite fields of small order or characteristic is a pivotal operation for thresholdizing multivariate quadratic (MQ) signature schemes. However, achieving perfect privacy in a constant number of rounds remains a challenge: existing solutions either suffer from information leakage, failing to provide perfect privacy, or require high computational and communication overhead, in particular, when $p\leq n$, where $p$ and $n$ denote the characteristic of the underlying field and the matrix size, respectively. To address this limitation, we propose two protocols for multi-party testing of matrix invertibility. The first protocol extends the Cramer-Damgård protocol to fields of small order by employing the field lifting technique. The second protocol is based on multi-party computation of the Samuelson-Berkowitz algorithm, specifically designed for fields of small characteristic. Both protocols are formalized in the arithmetic black-box (ABB) model with Shamir's secret sharing scheme. We show that both protocols achieve perfect privacy while allowing for a tradeoff between input-independent offline rounds and input-dependent online rounds, where the input corresponds to the shared matrices. Specifically, the first protocol runs in $7$ offline rounds with communication complexity $O(Nn^4)$ and in $3$ online rounds with communication complexity $O(n^4)$, and the second protocol runs in $3$ offline rounds with communication complexity $O(n^4)$ and in $9$ online rounds with communication complexity $O(n^4)$, where $n$ is the matrix size and $N$ is the number of parties.

@misc{cryptoeprint:2026/514,
      author = {Seungwoo Han and Jooyoung Lee and Seungmin Park and Mincheol Son},
      title = {Secure Matrix Invertibility Testing over Fields of Small Order or Characteristics},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/514},
      year = {2026},
      url = {https://eprint.iacr.org/2026/514}
}