Cryptology ePrint Archive: Report 2020/374

Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority

Megan Chen and Carmit Hazay and Yuval Ishai and Yuriy Kashnikov and Daniele Micciancio and Tarik Riviere and abhi shelat and Muthu Venkitasubramaniam and Ruihan Wang

Abstract: In this work, we design and implement the first protocol for RSA modulus construction that can support thousands of parties and offers security against an arbitrary number of corrupted parties.

In a nutshell, we design the ``best'' protocol for this scale that is secure against passive corruption, then amplify it to obtain active security using efficient non-interactive zero-knowledge arguments. Our protocol satisfies a stronger security guarantee where a deviating party can be identified when the protocol aborts (referred to as security with identifiable-abort) and allows for ``public verifiability''.

Our passively secure protocol extends the recent work of Chen et al. that, in turn, is based on the blueprint introduced in the original work of Boneh-Franklin protocol (CRYPTO 1997, J. ACM, 2001). Specifically, we reduce the task of sampling a modulus to secure distributed multiplication, which we implement via an efficient threshold additively homomorphic encryption (AHE) scheme based on the Ring-LWE assumption. This results in a protocol where the amortized per-party communication cost grows logarithmically in the number of parties. In order to keep the parties lightweight, we employ an ``untrusted'' coordinator that is connected to all parties and performs all public and broadcast operations.

We amplify this protocol to obtain active security (with identifiable-abort) by attaching zero-knowledge proofs. We instantiate our ZK proof system by composing two different types of ZK proof systems: (1) the Ligero sub-linear zero-knowledge proof system (Ames et al., CCS 2017), and (2) Sigma-protocol for proving the knowledge of a discrete logarithm in unknown order groups (Shoup, Eurocrypt 2000).

We implemented both the passive and the active variants of our protocol and ran experiments using 2 to 4,000 parties. This is the first such implementation of any MPC protocol that can scale to more than 1,000 parties. For generating a 2048-bit modulus among 1,000 parties, our passive protocol executed in under 4 minutes and the active variant ran in 22 minutes.

Category / Keywords: implementation / distributed sampling, RSA modulus, large-scale secure computation, active security

Date: received 31 Mar 2020, last revised 20 Apr 2020

Contact author: muthu at ligero-inc com,carmit@ligero-inc com,gmdami@gmail com,hiabhi@gmail com,contact meganchen@gmail com,yuvali@cs technion ac il,tarik@ligero-inc com,ruihan@ligero-inc com,yuriy@ligero-inc com

Available format(s): PDF | BibTeX Citation

Version: 20200420:155754 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]