Paper 2024/793

Hide-and-Seek and the Non-Resignability of the BUFF Transform

Jelle Don, Centrum Wiskunde & Informatica
Serge Fehr, Centrum Wiskunde & Informatica, Leiden University
Yu-Hsuan Huang, Centrum Wiskunde & Informatica
Jyun-Jie Liao, Cornell University
Patrick Struck, University of Konstanz
Abstract

The BUFF transform, due to Cremers et al. (S&P'21), is a generic transformation for digital signature scheme, with the purpose of obtaining additional security guarantees beyond unforgeability: exclusive ownership, message-bound signatures, and non-resignability. Non-resignability (which essentially challenges an adversary to re-sign an unknown message for which it only obtains the signature) turned out to be a delicate matter, as recently Don et al. (CRYPTO'24) showed that the initial definition is essentially unachievable; in particular, it is not achieved by the BUFF transform. This led to the introduction of new, weakened versions of non-resignability, which are (potentially) achievable. In particular, it was shown that a salted variant of the BUFF transform does achieves some weakened version of non-resignability. However, the salting requires additional randomness and leads to slightly larger signatures. Whether the original BUFF transform also achieves some meaningful notion of non-resignability remained a natural open question. In this work, we answer this question in the affirmative. We show that the BUFF transform satisfies the (almost) strongest notions of non-resignability one can hope for, facing the known impossibility results. Our results cover both the statistical and the computational case, and both the classical and the quantum setting. At the core of our analysis lies a new security game for random oracles that we call Hide-and-Seek. While seemingly innocent at first glance, it turns out to be surprisingly challenging to rigorously analyze.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
digital signaturesrandom oracle modelBUFF Transformpost-quantum cryptography
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
yhh @ cwi nl
jjliao @ cs cornell edu
patrick struck @ uni kn
History
2024-05-24: approved
2024-05-22: received
See all versions
Short URL
https://ia.cr/2024/793
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/793,
      author = {Jelle Don and Serge Fehr and Yu-Hsuan Huang and Jyun-Jie Liao and Patrick Struck},
      title = {Hide-and-Seek and the Non-Resignability of the {BUFF} Transform},
      howpublished = {Cryptology ePrint Archive, Paper 2024/793},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/793}},
      url = {https://eprint.iacr.org/2024/793}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.