Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

Carmit Hazay; Gert Læssøe Mikkelsen; Tal Rabin; Tomas Toft; Angelo Agatino Nicolosi

doi:10.1007/s00145-017-9275-7

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

Carmit Hazay^*, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft, Angelo Agatino Nicolosi

^*Corresponding author for this work

Alexandra Instituttet A/S

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.

Original language	English
Journal	Journal of Cryptology
Volume	32
Issue	2
Pages (from-to)	265-323
Number of pages	59
ISSN	0933-2790
DOIs	https://doi.org/10.1007/s00145-017-9275-7
Publication status	Published - 2019

Keywords

Paillier
RSA generation
Secure two-party computation
Threshold encryption scheme

Access to Document

10.1007/s00145-017-9275-7

https://eprint.iacr.org/2011/494.pdf

Cite this

@article{110f7bf3f70848a79e346b0f96c21c3a,

title = "Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting",

abstract = "The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.",

keywords = "Paillier, RSA generation, Secure two-party computation, Threshold encryption scheme",

author = "Carmit Hazay and Mikkelsen, {Gert L{\ae}ss{\o}e} and Tal Rabin and Tomas Toft and Nicolosi, {Angelo Agatino}",

year = "2019",

doi = "10.1007/s00145-017-9275-7",

language = "English",

volume = "32",

pages = "265--323",

journal = "Journal of Cryptology",

issn = "0933-2790",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

AU - Hazay, Carmit

AU - Mikkelsen, Gert Læssøe

AU - Rabin, Tal

AU - Toft, Tomas

AU - Nicolosi, Angelo Agatino

PY - 2019

Y1 - 2019

N2 - The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.

AB - The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: (i) a distributed protocol for generation of an RSA composite and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: (i) a distributed generation of the corresponding secret key shares and (ii) a distributed decryption protocol for decrypting according to Paillier.

KW - Paillier

KW - RSA generation

KW - Secure two-party computation

KW - Threshold encryption scheme

UR - http://www.scopus.com/inward/record.url?scp=85044934853&partnerID=8YFLogxK

U2 - 10.1007/s00145-017-9275-7

DO - 10.1007/s00145-017-9275-7

M3 - Journal article

AN - SCOPUS:85044934853

SN - 0933-2790

VL - 32

SP - 265

EP - 323

JO - Journal of Cryptology

JF - Journal of Cryptology

IS - 2

ER -

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this