Paper 2026/1952

Structure-Preserving Compressing Primitives, Revisited

Abstract

Structure-preserving (SP) cryptography enables the modular composition of pairing-based primitives through the definition of cryptographic algorithms whose public inputs and outputs are group elements and whose computations are generic group operations or pairings. Despite their potential usefulness, obtaining compressing primitives such as accumulators and vector commitments in the SP setting has remained a long-standing challenge, partly due to known impossibility results [Abe et al. Eurocrypt 2012]. Recently, [Krenn, Mir, and Slamanig PKC 2026] proposed the first SP vector commitments (SPVC) and accumulators (SPA) that circumvent these barriers via the adoption of structured message spaces that, albeit restricted, enable interesting applications such as constant-size pairing-based ring signatures. In this work, we revisit the security of these recent constructions with a twofold contribution. First, we identify attacks against the recently proposed SPVC, SPA, and ring signature schemes. Second, we present new constructions of SPVCs and SPAs that preserve the efficiency and structure-preserving nature of the original designs while achieving the desired standard security notions of position-binding and collision-resistance respectively. Specifically, we construct a new SPVC with constant-size proofs and verification under the power discrete logarithm assumption in the algebraic group model. Building upon it, we introduce a new notion of SPA with extended message spaces and give a construction achieving collision resistance and constant-size membership proofs under the same assumption. Finally, we apply our techniques to obtain constant-size ring signatures in bilinear groups.