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

GTrans: Graph Transformer-Based Obfuscation-resilient Binary Code Similarity Detection

Yun Zhang (Hunan University), Yuling Liu (Hunan University), Ge Cheng (Xiangtan University), Bo Ou (Hunan University)

Read More

Pisces: Private and Compliable Cryptocurrency Exchange

Ya-Nan Li (The University of Sydney), Tian Qiu (The University of Sydney), Qiang Tang (The University of Sydney)

Read More

Security-Performance Tradeoff in DAG-based Proof-of-Work Blockchain Protocols

Shichen Wu (1. School of Cyber Science and Technology, Shandong University 2. Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education), Puwen Wei (1. School of Cyber Science and Technology, Shandong University 2. Quancheng Laboratory 3. Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education), Ren Zhang (Cryptape Co. Ltd. and…

Read More

Using Behavior Monitoring to Identify Privacy Concerns in Smarthome...

Atheer Almogbil, Momo Steele, Sofia Belikovetsky (Johns Hopkins University), Adil Inam (University of Illinois at Urbana-Champaign), Olivia Wu (Johns Hopkins University), Aviel Rubin (Johns Hopkins University), Adam Bates (University of Illinois at Urbana-Champaign)

Read More