Dense Probabilistic Encryption

This paper describes a method of dense probabilistic encryption. Previous probabilistic encryption methods require large numbers of random bits and product large amounts of ciphertext for the encryption of each bit of plaintext. This paper develops a method of probabilistic encryption in which the ratio of ciphertext text size to plaintext size and theproportion of random bits to plaintext can both be made arbitrarily close to one. The methods described here have applications which are not in any apparent way possible with previous methods. These applications include simple and efficient protocols for noninteractive verifiable secret sharing and a method for conducting practical and verifiable secret-ballot elections.