A new public key cryptosystem based on higher residues

By David Naccache, Jacques Stern. 1998

This paper describes a new public-key cryptosystem based on the hardness of computing higher residues modulo a composite RSA integer. We introduce two versions of our scheme, one deterministic and the other probabilistic. The deterministic version is practically oriented: encryption amounts to a single exponentiation w.r.t. a modulus with at least 768 bits and a 160-bit exponent. Decryption can be suitably opti- mized so as to become less demanding than a couple RSA decryptions. Although slower than RSA, the new scheme is still reasonably compet- itive and has several specific applications. The probabilistic version ex- hibits an homomorphic encryption scheme whose expansion rate is much better than previously proposed such systems. Furthermore, it has se- mantic security, relative to the hardness of computing higher residues for suitable moduli.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Review of Homomorphic Encryption Libraries for Secure Computation (2018, background): “Partially Homomorphic Encryption (PHE) schemes such as [9,10,11,12,13,14,15,16,17,18,19] allow only one type of operation any number of times - either addition or multiplication on encrypted data as compared to Somewhat Homomorphic schemes that support both.”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “Until Gentry’s breakthrough in [Gen-try 2009], all the attempts [Rivest et al. 1978b; Goldwasser and Micali 1982; ElGamal 1985; Benaloh 1994; Naccache and Stern 1998; Okamoto and Uchiyama 1998; Pail-lier 1999; Damgård and Jurik 2001; Kawachi et al. 2007; Yao 1982; Boneh et al. 2005; Sander et al.…”
Non-interactive cryptocomputing for NC/sup 1/ (1999, methodology): “The Goldwasser-Micali scheme and the Benaloh scheme [6] (see also [29]) give us via Chinese Remaindering homomorphic schemes using Abelian groups of smooth order.”
Fully homomorphic encryption using ideal lattices (2009, unknown): “Other additively homomorphic encryption schemes with proofs of semantic security are Benaloh [8], Naccache-Stern [ 42 ], Okamoto-Uchiyama [46], Paillier [47], and Damgard-Jurik [19].”
Sharing Decryption in the Context of Voting or Lotteries (2000, background): “Most homomorphic cryptosystems as Goldwasser-Micali's 11], Benaloh's 1, 4], Naccache-Stern's 12], Okamoto-Uchiyama's 13] or Paillier's 14] cryptosystems need to distribute a secret value related to the factorization of an RSA modulus.”
A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications (2003, methodology): “A more efficient variant of the Benaloh-Fischer scheme was proposed in 1998 by Naccache and Stern [18], who observed that in order to make the decryption procedure faster one can consider a value e that is not prime but instead obtained as the product of several small primes e 1 , . . . , e n such t”
Privacy-preserving SVM classification (2008, unknown): “There are several homorphic encryption systems such as the Goldwasser–Micali cryptosystem [5], the Benaloh cryptosystem [4], the Naccache–Stern cryptosystem[25], the Paillier cryptosystem [28], and the Okamoto–Uchiyama cryptosystem [26], any of which can be used in practice.”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, background): “Several e cient partially-homomorphic encryption schemes are known (Paillier, 1999; Naccache and Stern, 1998; Boneh et al., 2005).”
A Survey of Homomorphic Encryption for Nonspecialists (2007, background): “(iii) Naccache-Stern [51] is an improvement of Benaloh’s scheme.”
Cryptanalysis of a homomorphic encryption scheme from ISIT 2008 (2012, methodology): “After the introduction of privacy homomorphism, many schemes have been proposed, such as additive homomorphic encryption schemes [16], [1], [23], [30], [24], [9], [15], [18], [20], [25] and multiplicative homomorphic encryption schemes [10].”
Homomorphic Signature Schemes (2002, background): “Goldwasser-Micali encryption takes the form of a group homomorphism Z/2Z → (Z/nZ) [17], and others have proposed a number of other public-key encryption schemes that have various useful homomorphic properties [15, 8, 22, 20].”
Secure Matrix Multiplication with MapReduce (2017, unknown): “There exist several schemes that have this property [16, 17, 5, 15].”
Privacy-preserving Naïve Bayes classification (2008, methodology): “The key idea behind the protocol is to use a homomorphic encryption system such as the Goldwasser– Micali cryptosystem [4], the Benaloh cryptosystem [3], the Naccache–Stern cryptosystem [30], the Paillier cryptosystem [34], and the Okamoto–Uchiyama cryptosystem [33].”