Space-Efficient Secret Sharing Based on Matrix Normal Forms

Pfluegel, Eckhard

doi:10.3390/cryptography10030029

Return

Space-Efficient Secret Sharing Based on Matrix Normal Forms

2026-04-30

PRE

Pfluegel, Eckhard *

Razi Arshad

Jones, Mark

DOI：10.3390/cryptography10030029

Original

Original request for help

Save

Abstract

En 中文

Secret sharing schemes distribute a secret among participants so that only authorised subsets can reconstruct it. In this paper, we focus on space-efficient secret sharing and show that matrix normal forms can significantly reduce share sizes while achieving computational security properties. Our scheme is implemented within an online secret sharing architecture, where authenticated public data P is maintained and shares of private data Q are issued over a secure channel. We study an existing probabilistic matrix-based approach to share size reduction and prove that the expected number of iterations of the underlying cyclic vector algorithm is small, yielding an expected polynomial runtime. We then design a novel deterministic method based on the Frobenius canonical normal form, avoiding reliance on cyclic vector techniques, and derive its runtime complexity. This yields a space-efficient secret sharing scheme that is computationally secure under a suitably defined adversary model. We have implemented our algorithm in the computer algebra system Maple as an Open Source project and provide an evaluation of its performance. Our results demonstrate that matrix normal forms can provide a suitable mathematical framework for secure and practical secret sharing.

Keywords:

space-efficient secret sharing

matrix-based secret sharing

matrix normal forms

online secret sharing