Elements in Z*p\Gq are Dangerous
Number of Authors: 1
2003 (English)Report (Refereed)
A subgroup G_q, of prime order q, for which the discrete logarithm problem is assumed hard is mostly a subgroup of a larger group, e.g. Z_p^* for some prime p=k*q+1. Arithmetic for G_q is not implemented directly. Instead, arithmetic for the larger group, e.g. Z_p^*, is implemented, which gives arithmetic also for G_q. Furthermore, in most protocols based on arithmetic in G_q the participants do not verify their input properly. They only verify that inputs are in Z_p^*, even when they should verify that the inputs are in G_q. This practice sometimes allows the adversary to hand inputs from Z_p^*\G_q to honest participants without detection. Surprisingly, this seems to be a novel observation. In this paper we discuss the general problem further, introduce a novel class of attacks based on the above observations, and outline an efficient generic recipe for how to counter the attacks efficiently. To illustrate both the attacks and the countermeasures we provide examples of protocols that are vulnerable to the novel attacks, and show how they may be modified to counter the attacks. In particular we present attacks on the robustness for the majority of the El Gamal based mix-nets in the literature, and an attack on the privacy for the generic mix-net based on the proof of knowledge of correct shuffle of Furukawa and Sako.
Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2003, 1. , 20 p.
SICS Technical Report, ISSN 1100-3154 ; 2003:05
cryptanalysis, mix-net, anonymous channel, electronic voting
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22038OAI: oai:DiVA.org:ri-22038DiVA: diva2:1041580