School of
Computer Science
and Communication
KTH / CSC / TCS / Douglas Wikström / Research

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

I supervise and work with my student Björn Terelius.

## Foundations of Interaction

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 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 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 zero-knowledge.

## 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:

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.
• Shahram Khazaei, Tal Moran, and Douglas Wikström.
A Mix-Net From Any CCA2 Secure Cryptosystem.
Submitted for publication.
• Shahram Khazaei, Björn Terelius, and Douglas Wikström.
Cryptanalysis of a universally verifiable efficient re-encryption
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 Ben-Nun, Niko Farhi, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon Ta-Shma, and Douglas Wikström.
Wombat: An implementation and field testing of dual paper-cryptographic 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 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.

## 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.
• 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.

# Verificatum -- An Implementation of a Provably Secure Mix-net

For several years I have worked on an implementation of a complete and provably secure mix-net. 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.

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

## 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. This motivated me to investigate binary residue symbol algorithms.

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