Welcome to the resource topic for 2022/526
Title:
Optimal Tightness for Chain-Based Unique Signatures
Authors: Fuchun Guo, Willy Susilo
Abstract:Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo {\it et al.} proposed a particular chain-based unique signature scheme where each unique signature is composed of n BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is n\cdot q_H^{1/n} for q_H hash queries and it is logarithmically tight when n=\log{q_H}. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists. We show that the proposed chain-based unique signature scheme by Guo {\it et al.} must have the reduction loss q^{1/n} for q signature queries when each unique signature consists of n BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss 4\cdot q^{1/n} for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss n\cdot q_H^{1/n} that is logarithmically tight at most. The core of our reduction idea is a {\em non-uniform} simulation that is specially invented for the chain-based unique signature construction.
ePrint: https://eprint.iacr.org/2022/526
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/35/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .