Optimal tightness for chain-based unique signatures (Q2170062)

The determinism of unique signature schemes may entail security reduction losses. Security reduction deals with proving the robustness of a cryptologic protocol by reducing its breaking problem to find a solution to a known difficult problem. Roughly speaking, for any such reduction, if a probability \(\varepsilon\) to break the protocol turns into a probability \(\varepsilon/L\) to solve the hard problem then it is said that \(L\) is the reduction loss. Usually, this reduction is put in terms of the number of queries that an adversary poses to a prover to break the cryptologic protocol, and the reduction is tight if it is constant. BLS (for Boneh-Lynn-Shacham) signature schemes are based on bilinear maps. For cyclic groups \(G_0\), \(G_1\), \(G_2\) of prime order, any participant has a pair of public-private keys \((h,u)\) where \(h=g_1^x\) and \(G_1 = \langle g_1\rangle\). A bilinear non-degenerate map \(e:G_0\times G_1\to G_2\) is considered as well as a hashing \(H:G_1\to G_0\). Any signer with keys \((h,u)\) signs a message \(m_1\in G_1\) with the signature \(s=u\,H(m_1)\in G_0\). Anybody can verify the signature by checking whether \(e(s,g_1) = e(H(m_1),h)\). This is a scheme with a unique signature for each message. The scheme can be turned into one with several signatures by composing it with a kind of ElGamal encryption. In a series of former papers, the authors have proposed a particular chain-based unique signature scheme where each unique signature consists of \(n\) BLS signatures computed sequentially like a blockchain. In the reviewed paper, they show that their proposed chain-based unique signature scheme must have the reduction loss \(4\cdot q^{\frac{1}{n}}\) for \(q\) signature queries when each unique signature consists of \(n\)-BLS signatures in their proposed blockchain by reducing to the computational Diffie-Hellman problem. To this end, the authors introduce the notion of non-uniform simulation. For the entire collection see [Zbl 1493.94002].