### Optimal Tightness for Chain-Based Unique Signatures

Fuchun Guo and 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.

Available format(s)
Category
Public-key cryptography
Publication info
Keywords
Unique SignaturesOptimal Reduction
Contact author(s)
fuchun @ uow edu au
History
Short URL
https://ia.cr/2022/526

CC BY

BibTeX

@misc{cryptoeprint:2022/526,
author = {Fuchun Guo and Willy Susilo},
title = {Optimal Tightness for Chain-Based Unique Signatures},
howpublished = {Cryptology ePrint Archive, Paper 2022/526},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/526}},
url = {https://eprint.iacr.org/2022/526}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.