Sourav Das (University of Illinois at Urbana-Champaign), Zhuolun Xiang (Aptos), Ling Ren (University of Illinois at Urbana-Champaign)

The $q$-Strong Diffie-Hellman~($q$-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive argument of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon. The only existing method to generate these parameters securely is highly sequential, requires strong network synchrony assumptions, and has very high communication and computation cost. For example, to generate parameters for any given $q$, each party incurs a communication cost of $Omega(nq)$ and requires $Omega(n)$ rounds. Here $n$ is the number of parties in the secure multiparty computation protocol. Since $q$ is typically large, i.e., on the order of billions, the cost is highly prohibitive.

In this paper, we present a distributed protocol to generate $q$-SDH parameters in an asynchronous network. In a network of $n$ parties, our protocol tolerates up to one-third of malicious parties. Each party incurs a communication cost of $O(q + n^2log q)$ and the protocol finishes in $O(log q + log n)$ expected rounds. We provide a rigorous security analysis of our protocol. We implement our protocol and evaluate it with up to 128 geographically distributed parties. Our evaluation illustrates that our protocol is highly scalable and results in a 2-6$times$ better runtime and 4-13$times$ better per-party bandwidth usage compared to the state-of-the-art synchronous protocol for generating $q$-SDH parameters.

View More Papers

On the Feasibility of CubeSats Application Sandboxing for Space...

Gabriele Marra (CISPA Helmholtz Center for Information Security), Ulysse Planta (CISPA Helmholtz Center for Information Security and Saarbrücken Graduate School of Computer Science), Philipp Wüstenberg (Chair of Space Technology, Technische Universität Berlin), Ali Abbasi (CISPA Helmholtz Center for Information Security)

Read More

LMSanitator: Defending Prompt-Tuning Against Task-Agnostic Backdoors

Chengkun Wei (Zhejiang University), Wenlong Meng (Zhejiang University), Zhikun Zhang (CISPA Helmholtz Center for Information Security and Stanford University), Min Chen (CISPA Helmholtz Center for Information Security), Minghu Zhao (Zhejiang University), Wenjing Fang (Ant Group), Lei Wang (Ant Group), Zihui Zhang (Zhejiang University), Wenzhi Chen (Zhejiang University)

Read More

Exploiting Diagnostic Protocol Vulnerabilities on Embedded Networks in Commercial...

Carson Green, Rik Chatterjee, Jeremy Daily (Colorado State University)

Read More

SyzBridge: Bridging the Gap in Exploitability Assessment of Linux...

Xiaochen Zou (UC Riverside), Yu Hao (UC Riverside), Zheng Zhang (UC RIverside), Juefei Pu (UC RIverside), Weiteng Chen (Microsoft Research, Redmond), Zhiyun Qian (UC Riverside)

Read More