Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC’14, J. Crypto’19), sign vectors of elements from a bilinear group. Their main feature is “adaptivity”: given a signature on a vector, anyone can transform it to a (uniformly random) signature on any multiple of the vector. A signature thus authenticates equivalence classes and unforgeability is defined accordingly. EQS have been used to improve the efficiency of many cryptographic applications, notably (delegatable) anonymous credentials, (round-optimal) blind signatures, group signatures and anonymous tokens. EQS security implies strong anonymity (or blindness) guarantees for these schemes which holds against malicious signers without trust assumptions. Unforgeability of the original EQS construction is proven directly in the generic group model. While there are constructions from standard assumptions, these either achieve prohibitively weak security notions (PKC’18) or they require a common reference string (AC’19, PKC’22), which reintroduces trust assumptions avoided by EQS. In this work we ask whether EQS schemes that satisfy the original security model can be proved secure under standard (or even non-interactive) assumptions with standard techniques. Our answer is negative: assuming a reduction that, after running once an adversary breaking unforgeability, breaks a non-interactive computational assumption, we construct efficient meta-reductions that either break the assumption or break class-hiding, another security requirement for EQS.

Equivalence class signatures (EQS) are digital signatures which provide the additional functionality that lets users adapt a given signature to a related message without knowledge of the secret key. They have been used to instantiate numerous cryptographic primitives and increased their efficiency.Unforgeability of the original EQS construction is proven in the generic group model, a theoretical model that treats the underlying group as "ideal". There exist constructions from standard assumptions but those only achieve weak security notions.In this work we strive to answer the question whether EQS schemes which satisfy the original model can be proved secure under standard assumptions with standard techniques. We answer in the negative. There cannot be an efficient security reduction which runs an adversary breaking unforgeability to then break a non-interactive computational assumption. This will be shown by construction of efficient meta-reductions that either break the security of the scheme or said computational problem directly.