Optimal Tightness for Chain-Based Unique Signatures

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 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 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 non-uniform simulation that is specially invented for the chain-based unique signature construction.