Research

Cryptography
I do research in cryptography and in particular in cryptographic
protocols. My main research interests are: electronic elections
and mixnets, signature schemes with anonymity properties, and
foundations of interaction. Below these are described in more
detail (click on a header to expand it).
I supervise and work with my
student Björn
Terelius.
On of the main theme of research in modern cryptography (and
complexity theory) is to understand the nature of
interaction. The most important notion of study in cryptography
is zeroknowledge proof. A zeroknowledge proof paradoxically
allows a prover to convince a verifier with high probability
that some statement is true, without disclosing anything else.
My Research
I have worked on the understanding of what happens when a basic
protocol is repeated in parallel to reduce the probability that
a prover convinces the verifier of a false statement. This idea
is quite natural, indeed the probability of success in repeated
experiments reduces exponentially with the number
experiments. What is less obvious is that there exists protocols
for which repetition does not reduce this probability. I
strengthened the counter example showing this. Then I tried to
capture the class of protocols for which it
works. Interestingly, the same techniques can be used to prove
lower bounds for protocols that are zeroknowledge.
 Björn Terelius and Douglas Wikström.
Efficiency limitations of Sigmaprotocols for group homomorphisms revisited.
Submitted for publication.
 Krzysztof Pietrzak and Douglas Wikström.
Parallel repetition of computationally sound protocols revisited.
J. Cryptology, 25(1):116135, 2012.
 Rafael Pass, WeiLung Dustin Tseng, and Douglas Wikström.
On the composition of publiccoin zeroknowledge protocols.
SIAM J. Comput., 40(6):15291553, 2011.
 Johan Håstad, Rafael Pass, Douglas Wikström, and Krzystof Pietrzak.
An efficient parallel repetition theorem.
In Theory of Cryptography Conference (TCC) 2010, volume 5978 of
Lecture Notes in Computer Science, pages 118. Springer Verlag, 2010.
 Rafael Pass, WeiLung Dustin Tseng, and Douglas Wikström.
On the composition of publiccoin zeroknowledge protocols.
In Advances in Cryptology  Crypto 2009, volume 5677 of Lecture Notes in Computer Science, pages 160176. Springer Verlag, 2009.
 Krzystof Pietrzak and Douglas Wikström.
Parallel repetition of computationally sound protocols revisited.
In 4th Theory of Cryptography Conference (TCC), volume 4392 of
Lecture Notes in Computer Science, pages 86102. Springer Verlag,
2007.
Electronic election schemes could potentially replace existing
paper based election schemes in the future. It seems likely that
at least parts of the schemes employed in most countries today
for "lesser" elections will be replaced.
There are several types of physical election schemes, e.g., in
some countries the candidate with the largest number of votes is
elected, whereas in other countries several rounds, or
preferential voting is used. These schemes are also governed by
national laws and constitutions in different ways. This imposes
corresponding demands on the electronic scheme, or indeed on the
legislative authorities should an electronic scheme in conflict
with existing laws be employed.
Thus, electronic election schemes come in many forms and are the
topic of active research to cater for specific
requirements. However, after the voter has submitted an
encrypted vote, two main techniques are used for tabulation:
 Homomorphic tabulation. Here the cryptosystem used
has the property that the product of two ciphertexts is a
ciphertext containing the sum of the plaintexts of the
original ciphertexts. In a twocandidate election, the idea
is to simply encode a vote for the first candidate as a one
and then let the tabulators compute the product of all
encrypted votes and decrypt the result. For more candidates
similar ideas can be used.
 Mixnets. A mixnet is the electronic equivalent of
"hat elections", i.e., voters encrypt their votes and the
mixservers (tabulators) jointly computes the set of
plaintexts, but in randomly permuted order.
In both cases, zeroknowledge proofs (of knowledge) are used to
turn protocols secure against passive adversaries into protocols
that are secure against malicious (byzantine adversaries). In
the mixnet setting one of the main protocols of this type is
called a proof of a shuffle, i.e., a proof that a
mixserver behaved according to the protocol.
Although I have not done any research on how to construct
ciphertexts in an acceptable way, this is an important research
topic that contains interdisciplinary questions such as
usability, bias of candidates due to the scheme, etc.
My Research
My research in this area spans all aspects of mixnets. I
defined the security of mixnets in the UC framework and gave
the first proof of security of a mixnet as a whole for any
definition of security. Masayuki Abe had previously provided a
different type of definition of security of mixnets, but no
satisfying implementation. I have also provided two alternative
proofs of shuffles, of which the latter seems simpler than all
previously known, e.g., the proofs of shuffles of Neff, and
Furukawa and Sako. In early work I attacked existing
"heuristically secure" constructions, that typically turn out to
be insecure. The rest of my work on mixnets focuses on
improving the efficiency of constructions in general or in
special settings and/or outsourcing computation.
 Shahram Khazaei, Tal Moran, and Douglas Wikström.
A MixNet From Any CCA2 Secure Cryptosystem.
Submitted for publication.
 Shahram Khazaei, Björn Terelius, and Douglas Wikström.
Cryptanalysis of a universally verifiable efficient reencryption
mixnet.
Cryptology ePrint Archive, Report 2012/100, 2012. Submitted for publication.
 Shahram Khazaei and Douglas Wikström.
Randomized partial checking revisited.
Cryptology ePrint Archive, Report 2012/063, 2012. Submitted for publication.
 Jonathan BenNun, Niko Farhi, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon TaShma, and Douglas Wikström.
Wombat: An implementation and field testing of dual
papercryptographic election system.
To appear at EVOTE 2012.
 Björn Terelius and Douglas Wikström.
Proofs of restricted shuffles.
In Africacrypt 2010, volume 6055 of Lecture Notes in Computer Science, pages 100113, 2010.
 Douglas Wikström.
A commitmentconsistent proof of a shuffle.
In Australasian Conference on Information Security and Privacy
 ACISP 2009, volume 5594 of Lecture Notes in Computer Science, pages
407421. Springer Verlag, 2009.
 Douglas Wikström.
Simplified submission of inputs to protocols.
In Security in Communication Networks 2008, volume 5229 of Lecture Notes in Computer Science, pages 293308, 2008.
 Ben Adida and Douglas Wikström.
Offline/online mixing.
In 34th International Colloquium on Automata, Languages and
Programming (ICALP), volume 4596 of Lecture Notes in Computer Science,
pages 484495. Springer Verlag, 2007.
 Ben Adida and Douglas Wikström.
How to shuffle in public.
In 4th Theory of Cryptography Conference (TCC), volume 4392 of
Lecture Notes in Computer Science, pages 555574. Springer Verlag,
2007.
 Douglas Wikström and Jens Groth.
An adaptively secure mixnet without erasures.
In 33rd International Colloquium on Automata, Languages and
Programming (ICALP), volume 4052 of Lecture Notes in Computer Science,
pages 276287. Springer Verlag, 2006.
 Douglas Wikström.
A sender verifiable mixnet and a new proof of a shuffle.
In Advances in Cryptology  Asiacrypt 2005, volume 3788 of
Lecture Notes in Computer Science, pages 273292. Springer Verlag,
2005.
 Douglas Wikström.
A universally composable mixnet.
In 1st Theory of Cryptography Conference (TCC), volume 2951 of
Lecture Notes in Computer Science, pages 315335. Springer Verlag,
2004.
 Douglas Wikström.
Five practical attacks for ``optimistic mixing for exitpolls''.
In Selected Areas in Cryptography  SAC 2003, volume 3006 of
Lecture Notes in Computer Science, pages 160174. Springer Verlag,
2003.
 Douglas Wikström.
The security of a mixcenter based on a semantically secure
cryptosystem.
In Indocrypt 2002, volume 2551 of Lecture Notes in Computer Science, pages 368381. Springer Verlag, 2002.
An electronic signature scheme allows a signer Alice to generate
two keys: a public key, and a private key. The
public key is published in an authenticated way, i.e., others
who fetch the public key are convinced that the key belongs to
Alice and not to somebody else. Alice uses its private key
to sign a file, i.e., she invokes a signature algorithm
on the private key and the file to produce a signature file of
small size. Alice can then publish the file (without
authentication), along with the signature. Anybody who holds the
authenticated public key of Alice can then verify the
signature of the file, i.e., that Alice and nobody else produced
the signature file.
A signature scheme is said to be secure if it is infeasible to
produce a signature of any file without holding the private key,
i.e., producing a signature file deemed to be a valid signature
of any file relative the public key of Alice is infeasible.
An application of electronic signatures is to improve the
security of credit cards. Modern credit cards have chips that
allow a chip to sign transactions. The credit card would sign,
say 10:31:03, January 1, 2010: Alice owes Seven Eleven 12 SEK,
and the shop would check the validity of this signature using
the public key of Alice. This improves the security
significantly, since it is no longer possible to make use of the
card without physical access to it. A drawback of this solution
is that a purchase cannot be made without disclosing the
identity of the buyer.
To solve this and similar problem, David Chaum proposed the
notion of group signatures. Here a group manager
generates a public key, a private key, and a signing key for
each member of the group. A group member can sign a file as
before, but now the signatures of all group members can be
verified using the public key of the group manager. It is
infeasible to distinguish the signature of the group members,
i.e., the producer of a signature can not be
identified. However, the group manager can use its private key
to open a group signature and determine the signer. Note
that this solves the anonymity problem in the credit card
application.
There are numerous other variations of signatures in addition to
group signatures. Most research in this area attempts to add
features, develop new notions, and improve the efficiency of
constructions.
My Research
I have generalized the notion of group signatures to so called
hierarchical group signatures. I have also improved the
definitions of security of designated confirmer signatures, and
given a fairly efficient implementation of such signatures under
standard assumptions in the plain model (without random
oracles). My most recent work in this area is to formalize a
relaxation of group signatures, group message authentication,
and implement this efficiently in the plain model under standard
assumptions.
 Bartosz Przydatek and Douglas Wikström.
Group message authentication.
In Security in Communication Networks 2010, volume 6280 of Lecture Notes in Computer Science, pages 399417, 2010.
 Douglas Wikström.
Designated confirmer signatures revisited.
In 4th Theory of Cryptography Conference (TCC), volume 4392 of
Lecture Notes in Computer Science, pages 342361. Springer Verlag,
2007.
 Mårten Trolin and Douglas Wikström.
Hierarchical group signatures.
In 32nd International Colloquium on Automata, Languages and
Programming (ICALP), volume 3580 of Lecture Notes in Computer Science,
pages 446458. Springer Verlag, 2005.
Some of my research in cryptography does not fall into one of
the above areas.
 Gunnar Kreitz, Mads Dam, and Douglas Wikström.
Practical private information aggregation in large networks.
In 15th Nordic Conference in Secure IT Systems (NORDSEC 2010),
volume 7127 of Lecture Notes in Computer Science, pages 231243, 2010.
 Douglas Wikström.
Universally composable DKG with linear number of exponentiations.
In Security in Communication Networks 2004, volume 3352 of Lecture Notes in Computer Science, pages 263277. Springer Verlag, 2004.
 Douglas Wikström.
A note on the malleability of the El Gamal cryptosystem.
In Indocrypt 2002, volume 2551 of Lecture Notes in Computer Science, pages 176184. Springer Verlag, 2002.

Verificatum  An Implementation of a Provably Secure Mixnet
For several years I have worked on an implementation of a
complete and provably secure mixnet. I wish to believe that my
implementation is far more faithful to theory than all previous
implementations, yet very efficient even for very large security
parameters and huge numbers of ciphertexts.
This project is now named Verificatum. Please visit
the project homepage
for more information.

General Computer Science
I have a general interest in algorithms, complexity theory, and
mathematics (in particular algebra) and I have made some
research in the intersection (click on a header to expand it).
The best known residue symbol is probably the Legendre symbol
(or Jacobi symbol), which indicates if an element a is a
quadratic residue modulo a prime p, i.e., if there is a
solution to a=x·x mod p. This concept can be
generalized to arbitrary power residues in suitably chosen
integer rings, e.g., the cubic residues arise naturally in
Eistenstein integers and quartic (biquadratic) residues arise
naturally in Gaussian integers.
My Research
In my research I discovered "binary" algorithms for such residue
symbols, including slight variations of the already known cubic
and quartic algorithms.
(Weak) Cryptographic Motivation. In cryptography, large
subgroups G of order q of the multiplicative group
modulo p=kq+1 are used. When k=2 the
prime p is said to be safe and checking membership
in G of an element a in the multiplicative group
corresponds to compute its quadratic residue symbol, which is
quadratic in the bitsize.
Membership can of course be checked by verifying that
a^{q} mod p=1, but this is computationally
expensive, and in a mixnet application where thousands of
element must be checked it is worthwhile to find more efficient
alternatives. This motivated me to investigate binary residue
symbol algorithms.
 Douglas Wikström.
On the lary GCDalgorithm in rings of integers.
In 32nd International Colloquium on Automata, Languages and
Programming (ICALP), volume 3580 of Lecture Notes in Computer Science,
pages 11891201. Springer Verlag, 2005.
 Douglas Wikström: On the lAry GCDAlgorithm and Computing Residue Symbols, Technical Report, TRITANA0439, Nada KTH, 2004.

