CTL
14 June 2011 - 14h00
Benaloh's Dense Probabilistic Encryption Revisited
by Laurent Fousse from LJK équipe CASYS
Abstract: In 1994, Josh Benaloh proposed a probabilistic homomorphic
encryption scheme, enhancing the poor expansion factor provided by
Goldwasser and Micali's scheme. Since then, numerous papers have
taken advantage of Benaloh's homomorphic encryption function,
including voting schemes, private multi-party trust computation,
non-interactive verifiable secret sharing, online poker. In this
paper we show that the original description of the scheme is
incorrect, because it can result in ambiguous decryption of
ciphertexts. Then we show on several applications that a bad choice
in the key generation phase of Benaloh's scheme has a real impact on
the behaviour of the application. For instance in an e-voting
protocol, it can inverse the result of an election. Our main
contribution is a corrected description of the scheme (we provide a
complete proof of correctness). Moreover we also compute the
probability of failure of the original scheme. Finally we show how
to formulate the security of the corrected scheme in a generic
setting suitable for several homomorphic encryptions.
Joint work with Pascal Lafourcade and Mohamed Alnuaimi.
