Abstract. This paper investigates a novel computational problem, namely the Composite Residuosity Class Problem, and its applications to public-key cryptography. We propose a new trapdoor mechanism and derive from this technique three encryption schemes: a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA. Our cryptosystems, based on usual modular arithmetics, are provably secure under appropriate assumptions in the standard model. Since the discovery of public-key cryptography by Diffie and Hellman [5] , very few convincingly secure asymetric schemes have been discovered despite considerable research efforts. We refer the reader to [26] for a thorough survey of existing public-key cryptosystems. Basically, two major species of trapdoor techniques are in use today. The first points to RSA [25] and related variants such as Rabin-Williams [24, 30] , LUC, Dickson's scheme or elliptic curve versions of RSA like KMOV [10] . The technique conjugates the polynomial-time extraction of roots of polynomials over a finite field with the intractability of factoring large numbers. It is worthwhile pointing out that among cryptosystems belonging to this family, only Rabin-Williams has been proven equivalent to the factoring problem so far. Another famous technique, related to Diffie-Hellman-type schemes (El Gamal [7], DSA, McCurley [14], etc.) combines the homomorphic properties of the modular exponentiation and the intractability of extracting discrete logarithms over finite groups. Again, equivalence with the primitive computational problem remains open in general, unless particular circumstances are reached as described in [12] .
The scheme relies on the homomorphic property of the Paillier encryption REF , and the winning number is retrieved in the drawing phase using the verifiable threshold decryption.
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
EUROCRYPT
Computer Science