Cryptography
I do research in cryptography and in particular in
cryptographic protocols. My main research interests are:
electronic elections and mix-nets, signature schemes with
anonymity properties, and foundations of interaction. Below
these are described in more detail (click on a header to
expand it).
One of the main themes of research in modern cryptography
(and complexity theory) is to model and understand the
nature of interaction. Perhaps the most important notion of study in
cryptography is zero-knowledge proof. A zero-knowledge 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 observation that the
probability of success in repeated experiments reduces
exponentially with the number experiments is commonly used in statistics.
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 zero-knowledge. I have also refined a
framework for modelling the security of protocols.
-
Douglas Wikström.
Special Soundness Revisited.
IACR Cryptology ePrint Archive 2018: 1157 (2018).
Submitted.
-
Douglas Wikström.
Simplified Universal
Composability Framework.
TCC (A1) 2016: 566-595
-
Björn Terelius, Douglas Wikström.
Efficiency
Limitations of Σ-Protocols for Group Homomorphisms
Revisited. SCN 2012: 461-476.
-
Krzysztof Pietrzak and Douglas Wikström.
Parallel repetition
of computationally sound protocols revisited.
J. Cryptology, 25(1):116--135, 2012.
-
Rafael Pass, Wei-Lung Dustin Tseng, and Douglas
Wikström.
On the composition
of public-coin zero-knowledge protocols.
SIAM J. Comput., 40(6):1529--1553, 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
1--18. Springer Verlag, 2010.
-
Rafael Pass, Wei-Lung Dustin Tseng, and Douglas
Wikström.
On the composition
of public-coin zero-knowledge protocols.
In Advances in Cryptology -- Crypto 2009, volume
5677 of Lecture Notes in Computer Science, pages
160--176. Springer Verlag, 2009.
-
Douglas Wikström.
An Efficient
Concurrent Repetition Theorem. IACR Cryptology
ePrint Archive 2009: 347 (2009).
The proof in this technical report remains of independent
interest despite that the result is essentially subsumed by
our joint published work above.
-
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
86--102. 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 are:
-
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 two-candidate 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.
-
Mix-nets. A mix-net is the electronic equivalent of
"hat elections", i.e., voters encrypt their votes and the
mix-servers (tabulators) jointly computes the set of
plaintexts, but in randomly permuted order.
In both cases, zero-knowledge proofs (of knowledge) are used
to turn protocols secure against passive adversaries into
protocols that are secure against malicious (byzantine
adversaries). In the mix-net setting one of the main
protocols of this type is called a proof of a
shuffle, i.e., a proof that a mix-server 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 mix-nets. I
defined the security of mix-nets in the UC framework and
gave the first proof of security of a mix-net as a whole for
any definition of security. Masayuki Abe had previously
provided a different type of definition of security of
mix-nets, 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 mix-nets focuses on improving the
efficiency of constructions in general or in special
settings and/or outsourcing computation.
-
Douglas Wikström.
Blackbox Constructions from
Mix-Nets
IACR Cryptology ePrint Archive 2019: 995 (2019).
Submitted.
-
Shahram Khazaei, Douglas Wikström.
Return Code
Schemes for Electronic Voting Systems.
E-VOTE-ID 2017: 198-209.
-
Douglas Wikström, Jordi Barrat, Sven Heiberg, Robert
Krimmer, Carsten Schürmann.
How Could Snowden
Attack an Election?
E-VOTE-ID 2017: 280-291.
-
Shahram Khazaei, Douglas Wikström.
Randomized Partial Checking
Revisited.
CT-RSA 2013: 115-128.
-
Shahram Khazaei, Tal Moran, Douglas Wikström.
A Mix-Net from Any
CCA2 Secure Cryptosystem.
ASIACRYPT 2012: 607-625.
-
Shahram Khazaei, Björn Terelius, Douglas Wikström.
Cryptanalysis of a
Universally Verifiable Efficient Re-encryption
Mixnet.
EVT/WOTE 2012.
-
Jonathan Ben-Nun, Niko Fahri, Morgan Llewellyn, Ben Riva,
Alon Rosen, Amnon Ta-Shma, Douglas Wikström.
A New
Implementation of a Dual (Paper and Cryptographic) Voting
System.
Electronic Voting 2012: 315-329.
-
Björn Terelius and Douglas Wikström.
Proofs of restricted
shuffles. In Africacrypt 2010, volume 6055
of Lecture Notes in Computer Science, pages
100--113, 2010.
-
Douglas Wikström.
A
commitment-consistent proof of a shuffle.
In Australasian Conference on Information Security and
Privacy -- ACISP 2009, volume 5594 of Lecture Notes
in Computer Science, pages 407--421. 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 293--308,
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
484--495. 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
555--574. Springer Verlag, 2007.
-
Douglas Wikström and Jens Groth.
An adaptively secure
mix-net without erasures. In 33rd International
Colloquium on Automata, Languages and Programming
(ICALP), volume 4052 of Lecture Notes in Computer
Science, pages 276--287. Springer Verlag, 2006.
-
Douglas Wikström.
A sender verifiable
mix-net and a new proof of a shuffle.
In Advances in Cryptology -- Asiacrypt 2005, volume
3788 of
Lecture Notes in Computer Science, pages
273--292. Springer Verlag, 2005.
-
Douglas Wikström.
A universally
composable mix-net. In 1st Theory of Cryptography
Conference (TCC), volume 2951 of
Lecture Notes in Computer Science, pages
315--335. Springer Verlag, 2004.
-
Douglas Wikström.
Five practical
attacks for ``optimistic mixing for exit-polls''.
In Selected Areas in Cryptography -- SAC 2003, volume
3006 of
Lecture Notes in Computer Science, pages
160--174. Springer Verlag, 2003.
-
Douglas Wikström.
The security of a
mix-center based on a semantically secure
cryptosystem. In Indocrypt 2002, volume
2551 of Lecture Notes in Computer Science, pages
368--381. 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 399--417, 2010.
-
Douglas Wikström.
Designated confirmer
signatures revisited. In 4th Theory of
Cryptography Conference (TCC), volume 4392 of
Lecture Notes in Computer Science, pages
342--361. Springer Verlag, 2007.
This paper contains an error. Please
consult https://eprint.iacr.org/2006/123 to understand
which part of the construction is affected.
-
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
446--458. 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 231--243, 2010.
-
Douglas Wikström.
On the Security
of Mix-Nets and Hierarchical Group Signatures
Technical Report. TRITA NA 05-38, Nada KTH, 2004.
-
Douglas Wikström.
On the Security
of Mix-Nets and Related Problems.
Technical Report. TRITA NA 04-06, Nada KTH, 2004.
-
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 263--277. 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 176--184. Springer Verlag,
2002.
Philosophy is an academic discipline in its own right, but
most of the philosophy is in fact carried out informally
within various branches of science and mathematics. Our
contribution is a critical look at how assumptions are
handled within our field and theoretical and practical
implications.
|
Open Verificatum Project
From 2006 onwards I have worked on an implementation of the
first complete and provably secure mix-net, the Verificatum
Mix-Net (VMN). My implementation is faithful to theory yet
very flexible and efficient even for very large security
parameters and huge numbers of ciphertexts. Zero
vulnerabilities or attacks have been reported since the
software was released as free and open source in 2010.
There is also a pure JavaScript library for bigint arithmetic
as well as abstractions used for typical voting
clients. Knowledgeable readers may note that it is 35-40 times
faster at modular exponentiation than the commonly used
library of Tom Wu for relevant security parameters.
This project is now named Open Verificatum and uses the
MIT License for maximum freedom of use in other
projects. Please visit
the project homepage for much more
information.
|
General Computer Science
I have a general interest in algorithms, complexity theory,
and mathematics (in particular algebra) and I have done 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 bit-size.
Membership can of course be checked by verifying that
aq mod p=1, but this is computationally
expensive, and in a mix-net application where thousands of
element must be checked it is worthwhile to find more
efficient alternatives.
-
Douglas Wikström.
On the l-ary
GCD-algorithm in rings of integers. In 32nd
International Colloquium on Automata, Languages and
Programming (ICALP), volume 3580 of Lecture Notes
in Computer Science, pages 1189--1201. Springer
Verlag, 2005.
-
Douglas Wikström
On the l-Ary
GCD-Algorithm and Computing Residue
Symbols. Technical Report. TRITA-NA-04-39, Nada
KTH, 2004.
Remark:This studies mainly octic residue symbols
in Z[α] for an eighth root of unity α
and is more concrete, but less general, than the published
work above. It shows that the norm and height of elements
may diverge, which is the crux of the problem.
|
|