Cryptosystems with a multi prime composite modulus

Multi-Prime (MP)RSA is an RSA construction in which the public modulus is a product of more than two primes, and its private key operations can be accelerated by using the Chinese Reminder Theorem (CRT). While MPRSA has been studied extensively, only limited information is found for other MP constructions, such as Paillier cryptosystem. This paper shows how to extend the security proofs for Quadratic Residue Problem (QRP), Higher Residuosity Problem (HRP) and Decisional Composite Residuosity Problem (DCRP), formulated for a two-primes modulus, to a MP setting. For the Paillier cryptosystem, we demonstrate how this technique can speed up decryption by more than 17x.

• Publication year

  2018

• Venue

  Consumer Communications and Networking Conference

• Publication date

  2018-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CCNC.2018.8319159
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Speed Records for Multi-prime RSA Using AVX2 Architectures

  2016cited by this paper
• Factoring a Multiprime Modulus N with Random Bits

  2013cited by this paper
• Number Field Sieve

  2011influential reference
• Factorization of a 768-Bit RSA Modulus

  2010cited by this paper
• Benaloh's Dense Probabilistic Encryption Revisited

  2010influential reference
• On the security of multi-prime RSA

  2008cited by this paper
• Fast Variants of RSA

  2007cited by this paper
• On Some Attacks on Multi-prime RSA

  2002cited by this paper
• Unbelievable Security. Matching AES Security Using Public Key Systems

  2001cited by this paper
• TWENTY YEARS OF ATTACKS ON THE RSA CRYPTOSYSTEM

  1999cited by this paper
• Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

  1999cited by this paper
• Dense Probabilistic Encryption

  1999influential reference
• A new public key cryptosystem based on higher residues

  1998influential reference
• Residuosity problem and its applications to cryptography

  1988cited by this paper
• Factoring integers with elliptic curves

  1987cited by this paper
• Discrete Logarithms and Factoring

  1984cited by this paper
• An application of higher reciprocity to computational number theory

  1982cited by this paper
• A modification of the RSA public-key encryption procedure (Corresp.)

  1980cited by this paper
• DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION

  1979influential reference

• Fault attacks on multi-prime RSA signatures

  2024cites this paper