International Association for Cryptologic Research

International Association
for Cryptologic Research


On Proving Equivalence Class Signatures Secure from Non-interactive Assumptions

Balthazar Bauer , UVSQ, France
Georg Fuchsbauer , TU Wien, Austria
Fabian Regen , TU Wien, Austria
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: 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.
  title={On Proving Equivalence Class Signatures Secure from Non-interactive Assumptions},
  author={Balthazar Bauer and Georg Fuchsbauer and Fabian Regen},