Glitter: A Fully Adaptive and Tightly Secure Threshold Signature

Threshold signatures (TS) have been widely used in digital wallets and blockchain ecosystems. In a (t, n) threshold signature scheme, at least t+1 signers are required to produce a valid signature. The state-of-the-art TS schemes compromise either the security model or incur at least linear-size reduction loss. Designing a fully adaptive and tightly secure TS scheme without algebraic group model (AGM) is still challenging. In this work, we propose a new security model, EUF-CMA-FC, making an enhancement in randomness guarantee and capturing fully adaptive security. We also propose Glitter, a fully adaptive and tightly secure five-round threshold signature scheme without pairing. Glitter has a comparable signature size and verification time with the state-of-the-art works. We prove the tight security of Glitter in the EUF-CMA-FC model in the random oracle model via security reduction. Without AGM, the security of Glitter can be reduced to t-algebraic translation resistance of tagged linear function (which implies DDH) with reduction loss L=2.