Change search
ReferencesLink to record
Permanent link

Direct link
On the security of mix-nets and hierarchical group signatures
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0003-4157-1371
2005 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

In this thesis we investigate two separate cryptographic notions: mix-nets and hierarchical group signatures. The former notion was introduced by Chaum (1981). The latter notion is introduced in this thesis, but it generalizes the notion of group signatures which was introduced by Chaum and Heyst (1991).

Numerous proposals for mix-nets are given in the literature, but these are presented with informal security arguments or at best partial proofs. We illustrate the need for a rigorous treatment of the security mix-nets by giving several practical attacks against a construction of Golle et al. (2002). Then we provide the first definition of security of a mix-net in the universally composable security framework (UC-framework) introduced by Canetti (2001). We construct two distinct efficient mix-nets that are provably secure under standard assumptions in the UC-framework against an adversary that corrupts any minority of the mix-servers and any set of senders. The first construction is based on the El Gamal cryptosystem (1985) and is secure against a static adversary, i.e., an adversary that decides which parties to corrupt before the execution of the protocol. This is the first efficient UC-secure mix-net in the literature and the first sender verifiable mix-net that is robust. The second construction is based on the Paillier cryptosystem (1999) and secure against an adaptive adversary, i.e., an adversary that decides which parties to corrupt during the execution of the protocol. This is the first efficient adaptively secure mix-net in any model. An important subprotocol in the above constructions is a zero-knowledge proof of knowledge of a witness that a party behaves as expected. There are two known approaches for constructing such a protocol given by Neff (2002) and Furukawa and Sako (2002) respectively. We present a third independent approach.

We introduce the notion of hierarchical group signatures. This is a generalization of group signatures. There are several group managers, and the signers and group managers are organized in a tree in which the signers are the leaves and the group managers are internal nodes. Given a signature, a group manager learns if it is an ancestor of the signer, and if so to which of its immediate subtrees the signer belongs, but it learns nothing else. Thus, the identity of the signer is revealed in a hierarchical way. We provide a definition of security of hierarchical group signatures and give two provably secure constructions. The first construction is secure under general assumptions. It is impractical and of purely theoretical interest. The second construction is provably secure under standard complexity assumptions and almost practical.

Place, publisher, year, edition, pages
Stockholm: Numerisk analys och datalogi , 2005. , xii, 273 p.
Trita-NA, ISSN 0348-2952 ; 05:38
National Category
Computer Science
URN: urn:nbn:se:kth:diva-555ISBN: 91-7178-200-1OAI: diva2:14421
Public defence
2005-12-19, Sal E3, Osquars backe 14, Stockholm, 14:00
Available from: 2005-12-14 Created: 2005-12-14 Last updated: 2012-03-22

Open Access in DiVA

fulltext(1921 kB)463 downloads
File information
File name FULLTEXT01.pdfFile size 1921 kBChecksum SHA-1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Wikström, Douglas
By organisation
Numerical Analysis and Computer Science, NADA
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 463 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: 683 hits
ReferencesLink to record
Permanent link

Direct link