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

LoRDMA: A New Low-Rate DoS Attack in RDMA Networks

Shicheng Wang (Tsinghua University), Menghao Zhang (Beihang University & Infrawaves), Yuying Du (Information Engineering University), Ziteng Chen (Southeast University), Zhiliang Wang (Tsinghua University & Zhongguancun Laboratory), Mingwei Xu (Tsinghua University & Zhongguancun Laboratory), Renjie Xie (Tsinghua University), Jiahai Yang (Tsinghua University & Zhongguancun Laboratory)

Read More

Beyond the Surface: Uncovering the Unprotected Components of Android...

Hao Zhou (The Hong Kong Polytechnic University), Shuohan Wu (The Hong Kong Polytechnic University), Chenxiong Qian (University of Hong Kong), Xiapu Luo (The Hong Kong Polytechnic University), Haipeng Cai (Washington State University), Chao Zhang (Tsinghua University)

Read More

Understanding the Implementation and Security Implications of Protective DNS...

Mingxuan Liu (Zhongguancun Laboratory; Tsinghua University), Yiming Zhang (Tsinghua University), Xiang Li (Tsinghua University), Chaoyi Lu (Tsinghua University), Baojun Liu (Tsinghua University), Haixin Duan (Tsinghua University; Zhongguancun Laboratory), Xiaofeng Zheng (Institute for Network Sciences and Cyberspace, Tsinghua University; QiAnXin Technology Research Institute & Legendsec Information Technology (Beijing) Inc.)

Read More

Acoustic Keystroke Leakage on Smart Televisions

Tejas Kannan (University of Chicago), Synthia Qia Wang (University of Chicago), Max Sunog (University of Chicago), Abraham Bueno de Mesquita (University of Chicago Laboratory Schools), Nick Feamster (University of Chicago), Henry Hoffmann (University of Chicago)

Read More