Paper 2026/1323

miniMEDS - Short GMW Signatures from Isometry Hints

Abstract

Hints are a concept from side-channel analysis referring to small amounts of information that enable an adversary, via a potentially very efficient procedure, to extract the secret. We take this cryptanalytic concept and give it a constructive make-over. We formalize a short $\Sigma$-protocol based on the famous Goldreich, Micali, Wigderson protocol, in which the responses are not of the full witness size, but are only small hints. The hints can be used to extract the full response. We show that under our formalization, these protocols preserve the security properties of $\Sigma$-protocols. We instantiate a practical protocol using a group action from tensor isomorphism and an efficient extracting procedure borrowed from an attack by Narayanan et al. on the MEDS signature scheme. We derive a signature scheme, called miniMEDS, which demonstrates practically the benefits of our hint-based construction, allowing for 22%-24% reduction in signature size compared to the latest updated parameters of MEDS.