Harry W. H. Wong (The Chinese University of Hong Kong), Jack P. K. Ma (The Chinese University of Hong Kong), Sherman S. M. Chow (The Chinese University of Hong Kong)

Threshold signatures, notably ECDSA, are fundamental for securing decentralized applications. Their non-linear structure poses challenges in distributed signing, often tackled by pairwise multiplicative-to-additive share conversion, leading to O(n) communication and O(n2) verification costs for each of n signers. Moreover, most schemes lack robustness, necessitating a complete restart upon fault. A pioneering work by Wong et al. (NDSS '23) still requires rolling back to the preceding round to resume signing after another round to convince all other signers.

We revisit secure multiparty computation from threshold linearly homomorphic encryption (LHE). Realizing its public verifiability and fault recovery, we encompass two technical contributions to Castagnos–Laguillaumie LHE (CT-RSA '15): a 2-round robust distributed key generation (DKG) protocol in the dishonest majority setting and an accompanying zero-knowledge proof allowing extraction in an unknown-order group. We extend the DKG with dual-code-based verification (ACNS '17), upgrading its O(tn2)-cost private verifiability to an O(n2) public one.

Built on our DKG, we present the first threshold ECDSA protocol with O(1) communication and O(n) verification per-party costs while matching the lowest round complexity of nonrobust schemes (CCS '20). Empirically, we halve the computation and communication costs of the signing phase compared to state-of-the-art robust threshold ECDSA (NDSS '23). We also illustrate the versatility of our techniques with an improved threshold extension (IEEE S&P '23) of BBS+ signatures (IEEE Syst. J. '13).

View More Papers

Programmer's Perception of Sensitive Information in Code

Xinyao Ma, Ambarish Aniruddha Gurjar, Anesu Christopher Chaora, Tatiana R Ringenberg, L. Jean Camp (Luddy School of Informatics, Computing, and Engineering, Indiana University Bloomington)

Read More

Towards Integrating Human-Centered Cybersecurity Research Into Practice: A Practitioner...

Julie Haney, Clyburn Cunningham, Susanne Furman (National Institute of Standards and Technology)

Read More

MOCK: Optimizing Kernel Fuzzing Mutation with Context-aware Dependency

Jiacheng Xu (Zhejiang University), Xuhong Zhang (Zhejiang University), Shouling Ji (Zhejiang University), Yuan Tian (UCLA), Binbin Zhao (Georgia Institute of Technology), Qinying Wang (Zhejiang University), Peng Cheng (Zhejiang University), Jiming Chen (Zhejiang University)

Read More

ReqsMiner: Automated Discovery of CDN Forwarding Request Inconsistencies and...

Linkai Zheng (Tsinghua University), Xiang Li (Tsinghua University), Chuhan Wang (Tsinghua University), Run Guo (Tsinghua University), Haixin Duan (Tsinghua University; Quancheng Laboratory), Jianjun Chen (Tsinghua University; Zhongguancun Laboratory), Chao Zhang (Tsinghua University; Zhongguancun Laboratory), Kaiwen Shen (Tsinghua University)

Read More