ABSTRACT
This chapter describes the Paillier encryption scheme, a public-key encryption scheme whose security is based on an assumption related to the hardness of factoring. The Paillier encryption scheme is useful in a number of settings because it is homomorphic. Roughly, a homomorphic encryption scheme enables computations to be performed on encrypted data, yielding a ciphertext containing the encrypted result. The chapter focuses on both , encryption and signature schemes, because they can involve multiple parties exchanging several rounds of messages, as well as because they are intended to realize more-complex security requirements. It describes a VSS scheme due to Feldman that relies on an algorithm G relative to which the discrete-logarithm problem is hard. The chapter explores the easier case of quadratic residues modulo a prime p, and looks at the slightly more complicated case of quadratic residues modulo a composite N.
