## 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

Short URL: ia.cr/2020/374

[ Cryptology ePrint archive ]