Kleptographic Weaknesses in Benaloh-Tuinstra Protocol

During designing of cryptographic protocols, their participants are usually identified with software or hardware they use. However, these supporting tools are not verified at the protocol level. Such carelessness opens the door to kleptographic (SETUP) attacks. In this paper we design such an attack on the classical Benaloh-Tuinstra election protocol. One of the technical tools developed in the paper is a new variant of a Diffie-Hellman SETUP attack, in which Kronecker Decomposition of the group is not known to the attacker. This is especially the case of Goldwasser-Micali cryptosystem.