In this paper, we propose a new probabilistic encryption whose security is based on the /spl gamma//sup th/-residuosity assumption for very large /spl gamma/ with the form O(poly/sub 1/(k))(O(poly/sub 2/(k))). The proposed scheme is the first probabilistic encryption which has an exponential size of message space and is polynomially secure. And our scheme has the advantage of small message expansion due to free use of an odd integer /spl gamma/. The important properties of our scheme, that is the exponential size of message space and polynomial security, can be applied directly in many ways. We propose two applications; one is generalization of the bit commitment scheme, and the other is a large scale secret ballot multiway (many candidates) election scheme.