bild
School of
Electrical Engineering
and Computer Science
KTH / CSC / TCS

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).

Foundations of Interaction

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.

Electronic Election Schemes and Mix-nets

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:

  1. 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.
  2. 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.

Signature Schemes With Anonymity Properties

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.

Various

Some of my research in cryptography does not fall into one of the above areas.

Philosophy

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).

GCD algorithms and Residue Symbols

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.
Published by: Douglas Wikström <dog@kth.se>
Updated 2019-09-12