Change search
ReferencesLink to record
Permanent link

Direct link
Elements in Z*p\Gq are Dangerous
Number of Authors: 1
2003 (English)Report (Refereed)
Abstract [en]

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
Keyword [en]
cryptanalysis, mix-net, anonymous channel, electronic voting
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-22038OAI: diva2:1041580
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(295 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 295 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1 hits
ReferencesLink to record
Permanent link

Direct link