Trustless digital signatures in blockchain

Abstract

Trustless in cryptography is an important property which means that there exists no trusted authority in a cryptosystem. Schnorr and ECDSA are two popular trustless signatures since they work in a trapdoorless cyclic group. On the contrary, RSA style signatures, like RSA signature and GQ signature, rely on system parameter containing trapdoor, which cannot be initialized by non-trusted system developer, and hence hinders their application in trustless environment like public blockchain. This thesis considers the weakness of Schnorr and ECDSA in public blockchain and eXpressive Internet Architecture (XIA) and thus proposes an alternative trustless signature; optimizes threshold ECDSA which is also a trustless signature with multiple participants; explores the possibility to reuse GQ signature in a trustless environment.

Blockchain and XIA-like systems have proposed using the hash of a public key as an address, with signatures validated against these addresses. In this context, we aim to define the concept of address-based signatures to scrutinize the security aspects of these address-based systems. We put forth a robust model that takes into account the security of multiple addresses, even in scenarios where attackers even know the randomness employed by system developers. We introduce an effective and secure method for creating address-based signatures that surmount the existing issues of address-based ECDSA (low efficiency, malleability) and Schnorr (lack of BIP-32 compatibility). Additionally, we offer two generic constructions for address-based signatures and deduce that our proposed method always outperforms the implementations of these constructions in Schnorr, ECDSA, BLS/BB signatures, either in efficiency or security.

Next, we move forward to trustless multiparty threshold ECDSA signatures, typically employed for digital wallets or cryptocurrency asset custody. For most threshold ECDSA signatures that utilize additively homomorphic encryption, the zero-knowledge proofs often become the limiting factor in terms of bandwidth and computational power. As a solution, we introduce a compact zero-knowledge (ZK) proof related to the Castagnos-Laguillaumie (CL) encryption. This new method is 32\% more concise in size and 29\% quicker in computation than prior work in PKC 2021. Moreover, we present new ZK proofs that relate to homomorphic operations over the CL ciphertext. These new ZK proofs are instrumental in constructing a bandwidth-efficient UC-secure threshold ECDSA that doesn't sacrifice proactive security or non-interactivity.

Lastly, we delve into the Guillou-Quisquater (GQ) signature, a renowned and computationally efficient successor of the Fiat-Shamir follow-ons along with Schnorr. However, the GQ's storage-heavy group element representation and an RSA trapdoor limit its broader application in both industry and academia. We start by formalizing the definition and security proof of the class group-based GQ signature (CL-GQ). This new approach redefines GQ as a trustless signature by eliminating the RSA trapdoor and by enhancing the bandwidth efficiency compared to the original GQ signature. Subsequently, we extend it to a trustless GQ multi-signature scheme, by leveraging non-malleable equivocable commitments and our uniquely designed compact non-interactive zero-knowledge proofs (NIZK). Our scheme demonstrates competitive performance when compared with existing multiparty GQ, Schnorr, and ECDSA.