Up to Research, Theory group at Nada, KTH.
Cryptography
Researchers
Students
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 nonstandard 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 MixNet From Any CCA2 Secure Cryptosystem
 Shahram Khazaei, Tal Moran, and Douglas Wikström.
 Submitted for publication.
 Cryptanalysis of a universally verifiable efficient reencryption 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 Sigmaprotocols for group homomorphisms revisited
 Björn Terelius and Douglas Wikström.
 Submitted for publication.
 Wombat: An implementation and field testing of dual papercryptographic election system
 Jonathan BenNun, Niko Farhi, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon TaShma, 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):116135, (2012
 On the composition of publiccoin zeroknowledge protocols
 Rafael Pass, WeiLung Dustin Tseng, and Douglas Wikström
 SIAM J. Comput., 40(6):15291553, (2011
 An efficient parallel repetition theorem
 Johan Håstad, Rafael Pass, Douglas Wikström, and Krzystof Pietrzak
 TCC 2010: 11
 Proofs of restricted shuffles
 Björn Terelius and Douglas Wikström
 AFRICACRYPT 2010: 10011
 Group message authentication
 Bartosz Przydatek and Douglas Wikström
 SCN 2010: 39941
 Practical private information aggregation in large networks
 Gunnar Kreitz, Mads Dam, and Douglas Wikström
 NORDSEC 2010: 231243, 2010.
 On the composition of publiccoin zeroknowledge protocols
 Rafael Pass, WeiLung Dustin Tseng, and Douglas Wikström
 CRYPTO 2009: 16017
 A commitmentconsistent proof of a shuffle
 Douglas Wikström
 ACISP 2009: 40742
 Simplified submission of inputs to protocols
 Douglas Wikström
 SCN 2008: 29330
 Practical Construction and Analysis of PseudoRandomness Primitives
 Johan Håstad, Mats Näslund
 J. Cryptology 21(1): 126 (2008)
 The Security of the IAPM and IACBC Modes
 Johan Håstad
 J. Cryptology 20(2): 153163 (2007)
 Offline/Online Mixing
 Ben Adida, Douglas Wikström
 ICALP 2007, pp. 484495
 Designated Confirmer Signatures Revisited
 Douglas Wikström
 TCC 2007: 342361
 How to Shuffle in Public
 Ben Adida, Douglas Wikström
 TCC 2007: 555574
 Parallel Repetition of Computationally Sound Protocols Revisited
 Krzysztof Pietrzak, Douglas Wikström
 TCC 2007: 86102
 An Adaptively Secure MixNet Without Erasures
 Douglas Wikström, Jens Groth
 ICALP (2) 2006: 276287
 A Sender Verifiable MixNet and a New Proof of a Shuffle
 Douglas Wikström
 ASIACRYPT 2005: 273292
 Hierarchical Group Signatures
 Mårten Trolin, Douglas Wikström
 ICALP 2005: 446458
 A Universally Composable Scheme for Electronic Cash
 Mårten Trolin
 INDOCRYPT 2005: 347360
 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: 494510
 The security of all RSA and discrete log bits
 Johan Håstad, Mats Näslund
 J. ACM 51(2): 187230 (2004)
 Universally Composable DKG with Linear Number of Exponentiations
 Douglas Wikström
 SCN 2004: 263277
 A Universally Composable MixNet
 Douglas Wikström
 TCC 2004: 317335
 Lattices with Many Cycles Are Dense
 Mårten Trolin
 STACS 2004: 370381
 Universally Composable Protocols with Relaxed SetUp Assumptions
 Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass
 FOCS 2004: 186195
 Boundedconcurrent secure multiparty computation with a dishonest majority
 Rafael Pass
 STOC 2004: 232241
 On the Possibility of OneMessage Weak ZeroKnowledge
 Boaz Barak, Rafael Pass
 TCC 2004: 121132
 Lattices with Many Cycles Are Dense
 Mårten Trolin
 Electronic Colloquium on Computational Complexity (ECCC)(113): (2004)
 Five Practical Attacks for 'Optimistic Mixing for ExitPolls'
 Douglas Wikström
 Selected Areas in Cryptography 2003: 160175
 Nearly OneSided Tests and the Goldreich?Levin Predicate
 Gustav Hast
 J. Cryptology 17(3): 209229 (2004)
 Nearly OneSided Tests and the GoldreichLevin Predicate
 Gustav Hast
 EUROCRYPT 2003: 195210
 On Deniability in the Common Reference String and Random Oracle Model
 Rafael Pass
 CRYPTO 2003: 316337
 Simulation in QuasiPolynomial Time, and Its Application to Protocol Composition
 Rafael Pass
 EUROCRYPT 2003: 160176
 BoundedConcurrent Secure TwoParty 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: 176184
 The Security of a MixCenter Based on a Semantically Secure Cryptosystem
 Douglas Wikström
 INDOCRYPT 2002: 368381
 Practical Construction and Analysis of PseudoRandomness Primitives
 Johan Håstad, Mats Näslund
 ASIACRYPT 2001: 442459
 The Shortest Vector Problem in Lattices with Many Cycles
 Mårten Trolin
 CaLC 2001: 194205
 On the complexity of interactive proof with bounded communication
 O. Goldreich, J. Håstad,
 Information processing letters, Vol.~67 (4), 1998, pp 205214.
 postscript

 A Pseudorandom Generator from any oneway function
 J. Håstad, R. Imagliazzo, L. Levin, and M. Luby
 SIAM Journal on Computing, Vol 28, 1999, pp 13641396.
 postscript
 The Security of Individual RSA Bits
 J. Håstad and M. Näslund
 Proceedings, FOCS '98, pp 510519, IEEE.
 A more complete version of this is contained in Mats Näslund's
thesis found below.
 Bit Extraction, HardCore Predicates, and the Bit Security of RSA
 M. Näslund
 Ph.D. Thesis, Nada, October, 1998
 PDF.
 The Complexity of Computing Hard Core Predicates
 M. Goldmann and M. Näslund
 Proceedings, CRYPT0 '97. LNCS 1294, pp 115, Springer Verlag.

 PseudoRandom Generators under Uniform Assumptions
 J. Håstad
 Proceedings, 22nd STOC, 1990, pp 395404.

 The Discrete Logarithm Modulo a Composite Hides O(n) Bits
 J. Håstad, A. W. Schrift, and A. Shamir
 JCSS 47 1993, pp. 376403

 Universal Hash Functions & Hard Core Bits
 M. Näslund
 Proceedings, EUROCRYPT '95, LNCS 921, pp 356366, Springer Verlag

 All Bits in ax+b mod p are Hard
 M. Näslund
 Proceedings, CRYPT0 '96. LNCS 1109, pp 114128, 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.
