School of
Computer Science
and Communication

^ Up to Research, Theory group at Nada, KTH.




Theoretical cryptography aims at finding mathematically elegant definitions and constructions. For many applications much more efficient and simpler constructions can be found by using concrete assumptions and non-standard definitions of subprotocols and primitives. Even if it does not give any immediate theoretical insights it is important to study these relaxed notions.

Practical computer security is to a large extent based on experience and practitioners ignore parts of the theoretical literature to find more efficient constructions. This is often not really necessary, as a more careful study allows provably secure and efficient constructions that can be implemented in the real world.

In the project we try to bridge some of this gap by: investigating practically oriented definitions and primitives, finding provably secure and practical constructions, and implementing parts of these to illustrate their use and to better understand them.

An important application of cryptographic protocols is electronic voting and much of our research targets problems in this area.

Publications of the Group

A Mix-Net From Any CCA2 Secure Cryptosystem
Shahram Khazaei, Tal Moran, and Douglas Wikström.
Submitted for publication.
Cryptanalysis of a universally verifiable efficient re-encryption mixnet
Shahram Khazaei, Björn Terelius, and Douglas Wikström.
Cryptology ePrint Archive, Report 2012/100, 2012. Submitted for publication.
Randomized partial checking revisited
Shahram Khazaei and Douglas Wikström.
Cryptology ePrint Archive, Report 2012/063, 2012. Submitted for publication.
Efficiency limitations of Sigma-protocols for group homomorphisms revisited
Björn Terelius and Douglas Wikström.
Submitted for publication.
Wombat: An implementation and field testing of dual paper-cryptographic election system
Jonathan Ben-Nun, Niko Farhi, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon Ta-Shma, and Douglas Wikström
To appear at EVOTE 2012
Parallel repetition of computationally sound protocols revisited
Krzysztof Pietrzak and Douglas Wikström
J. Cryptology, 25(1):116-135, (2012
On the composition of public-coin zero-knowledge protocols
Rafael Pass, Wei-Lung Dustin Tseng, and Douglas Wikström
SIAM J. Comput., 40(6):1529-1553, (2011
An efficient parallel repetition theorem
Johan Håstad, Rafael Pass, Douglas Wikström, and Krzystof Pietrzak
TCC 2010: 1-1
Proofs of restricted shuffles
Björn Terelius and Douglas Wikström
AFRICACRYPT 2010: 100-11
Group message authentication
Bartosz Przydatek and Douglas Wikström
SCN 2010: 399-41
Practical private information aggregation in large networks
Gunnar Kreitz, Mads Dam, and Douglas Wikström
NORDSEC 2010: 231-243, 2010.
On the composition of public-coin zero-knowledge protocols
Rafael Pass, Wei-Lung Dustin Tseng, and Douglas Wikström
CRYPTO 2009: 160-17
A commitment-consistent proof of a shuffle
Douglas Wikström
ACISP 2009: 407-42
Simplified submission of inputs to protocols
Douglas Wikström
SCN 2008: 293-30
Practical Construction and Analysis of Pseudo-Randomness Primitives
Johan Håstad, Mats Näslund
J. Cryptology 21(1): 1-26 (2008)
The Security of the IAPM and IACBC Modes
Johan Håstad
J. Cryptology 20(2): 153-163 (2007)
Offline/Online Mixing
Ben Adida, Douglas Wikström
ICALP 2007, pp. 484-495
Designated Confirmer Signatures Revisited
Douglas Wikström
TCC 2007: 342-361
How to Shuffle in Public
Ben Adida, Douglas Wikström
TCC 2007: 555-574
Parallel Repetition of Computationally Sound Protocols Revisited
Krzysztof Pietrzak, Douglas Wikström
TCC 2007: 86-102
An Adaptively Secure Mix-Net Without Erasures
Douglas Wikström, Jens Groth
ICALP (2) 2006: 276-287
A Sender Verifiable Mix-Net and a New Proof of a Shuffle
Douglas Wikström
ASIACRYPT 2005: 273-292
Hierarchical Group Signatures
Mårten Trolin, Douglas Wikström
ICALP 2005: 446-458
A Universally Composable Scheme for Electronic Cash
Mårten Trolin
INDOCRYPT 2005: 347-360
Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes
Yevgeniy Dodis, Rosario Gennaro, Johan Håstad, Hugo Krawczyk, Tal Rabin
CRYPTO 2004: 494-510
The security of all RSA and discrete log bits
Johan Håstad, Mats Näslund
J. ACM 51(2): 187-230 (2004)
Universally Composable DKG with Linear Number of Exponentiations
Douglas Wikström
SCN 2004: 263-277
A Universally Composable Mix-Net
Douglas Wikström
TCC 2004: 317-335
Lattices with Many Cycles Are Dense
Mårten Trolin
STACS 2004: 370-381
Universally Composable Protocols with Relaxed Set-Up Assumptions
Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass
FOCS 2004: 186-195
Bounded-concurrent secure multi-party computation with a dishonest majority
Rafael Pass
STOC 2004: 232-241
On the Possibility of One-Message Weak Zero-Knowledge
Boaz Barak, Rafael Pass
TCC 2004: 121-132
Lattices with Many Cycles Are Dense
Mårten Trolin
Electronic Colloquium on Computational Complexity (ECCC)(113): (2004)
Five Practical Attacks for 'Optimistic Mixing for Exit-Polls'
Douglas Wikström
Selected Areas in Cryptography 2003: 160-175
Nearly One-Sided Tests and the Goldreich?Levin Predicate
Gustav Hast
J. Cryptology 17(3): 209-229 (2004)
Nearly One-Sided Tests and the Goldreich-Levin Predicate
Gustav Hast
EUROCRYPT 2003: 195-210
On Deniability in the Common Reference String and Random Oracle Model
Rafael Pass
CRYPTO 2003: 316-337
Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition
Rafael Pass
EUROCRYPT 2003: 160-176
Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds
Rafael Pass, Alon Rosen
FOCS 2003: 404-
A Note on the Malleability of the El Gamal Cryptosystem
Douglas Wikström
INDOCRYPT 2002: 176-184
The Security of a Mix-Center Based on a Semantically Secure Cryptosystem
Douglas Wikström
INDOCRYPT 2002: 368-381
Practical Construction and Analysis of Pseudo-Randomness Primitives
Johan Håstad, Mats Näslund
ASIACRYPT 2001: 442-459
The Shortest Vector Problem in Lattices with Many Cycles
Mårten Trolin
CaLC 2001: 194-205
On the complexity of interactive proof with bounded communication
O. Goldreich, J. Håstad,
Information processing letters, Vol.~67 (4), 1998, pp 205-214.
A Pseudorandom Generator from any one-way function
J. Håstad, R. Imagliazzo, L. Levin, and M. Luby
SIAM Journal on Computing, Vol 28, 1999, pp 1364-1396.
The Security of Individual RSA Bits
J. Håstad and M. Näslund
Proceedings, FOCS '98, pp 510-519, IEEE.
A more complete version of this is contained in Mats Näslund's thesis found below.
Bit Extraction, Hard-Core Predicates, and the Bit Security of RSA
M. Näslund
Ph.D. Thesis, Nada, October, 1998
The Complexity of Computing Hard Core Predicates
M. Goldmann and M. Näslund
Proceedings, CRYPT0 '97. LNCS 1294, pp 1-15, Springer Verlag.
Pseudo-Random Generators under Uniform Assumptions
J. Håstad
Proceedings, 22nd STOC, 1990, pp 395-404.
The Discrete Logarithm Modulo a Composite Hides O(n) Bits
J. Håstad, A. W. Schrift, and A. Shamir
JCSS 47 1993, pp. 376-403
Universal Hash Functions & Hard Core Bits
M. Näslund
Proceedings, EUROCRYPT '95, LNCS 921, pp 356-366, Springer Verlag
All Bits in ax+b mod p are Hard
M. Näslund
Proceedings, CRYPT0 '96. LNCS 1109, pp 114-128, Springer Verlag.

Previous Members of the Group

  • Mats Näslund (now at Ericsson)
  • Gustav Hast (now at Exportkredit)
  • Mårten Trolin (now at Ernst and Young)
  • Rafael Pass (now at Cornell University)

^ Up to Research, Theory group at Nada, KTH.

Published by: Mats Näslund <>
Updated 2012-05-30