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

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.

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

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.

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 a^q 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.