## CryptoDB

### Douglas Wikström

#### Publications

**Year**

**Venue**

**Title**

2007

EPRINT

Offline/Online Mixing
Abstract

We introduce an offline precomputation technique for mix-nets that drastically reduces the amount of online computation needed. Our method can be based on any additively homomorphic cryptosystem and is applicable when the number of senders and the maximal bit-size of messages are relatively small.

2006

EPRINT

Designated Confirmer Signatures Revisited
Abstract

Previous definitions of designated confirmer signatures in the literature are incomplete, and the proposed security definitions fail to capture key security properties, such as unforgeability against malicious confirmers and non-transferability. We propose new definitions.
Previous schemes rely on the random oracle model or set-up assumptions, or are secure with respect to relaxed security definitions. We construct a practical scheme that is provably secure with respect to our security definition under the strong RSA-assumption, the decision composite residuosity assumption, and the decision Diffie-Hellman assumption.
To achieve our results we introduce several new relaxations of standard notions. We expect these techniques to be useful in the construction and analysis of other efficient cryptographic schemes.

2006

EPRINT

Simplified Submission of Inputs to Protocols
Abstract

Consider an electronic election scheme implemented using a mix-net; a large number of voters submit their votes and then a smaller number of servers compute the result. The mix-net accepts an encrypted vote from each voter and outputs the set of votes in sorted order without revealing the permutation used. To ensure a fair election, the votes of corrupt voters should be independent of the votes of honest voters, i.e., some type of non-malleability or plaintext awareness is needed. However, for efficiency reasons the servers typically expect inputs from some homomorphic cryptosystem, which is inherently malleable.
In this paper we consider the problem of how non-malleability can be guaranteed in the submission phase and still allow the servers to start their computation with ciphertexts of the appropriate homomorphic cryptosystem. This can clearly be achieved using general techniques, but we would like a solution which is: (1) provably secure under standard assumptions, (2) non-interactive for the submitting parties, (3) very efficient for all parties in terms of computation and communication.
We give the first solution to this problem which has all these properties. Our solution is surprisingly simple and can be based on various Cramer-Shoup cryptosystems. To capture its security properties we introduce a variation of CCA2-security.

2005

EPRINT

A Sender Verifiable Mix-Net and a New Proof of a Shuffle
Abstract

We introduce the first El Gamal based mix-net in which each mix-server
partially decrypts and permutes its input, i.e., no re-encryption is
necessary. An interesting property of the construction is that a
sender can verify non-interactively that its message is processed
correctly. We call this sender verifiability.
We prove the security of the mix-net in the UC-framework against
static adversaries corrupting any minority of the mix-servers. The
result holds under the decision Diffie-Hellman assumption, and
assuming an ideal bulletin board and an ideal zero-knowledge proof of
knowledge of a correct shuffle.
Then we construct the first proof of a decryption-permutation shuffle,
and show how this can be transformed into a zero-knowledge proof of
knowledge in the UC-framework. The protocol is sound under the strong
RSA-assumption and the discrete logarithm assumption.
Our proof of a shuffle is not a variation of existing methods. It is
based on a novel idea of independent interest, and we argue that it is
at least as efficient as previous constructions.

2005

EPRINT

How to Shuffle in Public
Abstract

We show how to public-key obfuscate two commonly used shuffles:
decryption shuffles which permute and decrypt ciphertexts, and
re-encryption shuffles which permute and re-encrypt ciphertexts. Given
a trusted party that samples and obfuscates a shuffle \emph{before}
any ciphertexts are received, this reduces the problem of constructing
a mix-net to verifiable joint decryption.
We construct a decryption shuffle from any additively homomorphic
cryptosystem and show how it can be public-key obfuscated. This
construction does not allow efficient distributed verifiable
decryption. Then we show how to public-key obfuscate: a decryption
shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem, and a
re-encryption shuffle based on the Paillier cryptosystem. Both
constructions allow \emph{efficient} distributed verifiable
decryption. In the Paillier case we identify and exploit a previously
overlooked ``homomorphic'' property of the cryptosystem.
Finally, we give a distributed protocol for sampling and obfuscating
each of the above shuffles and show how it can be used in a trivial
way to construct a universally composable mix-net. Our constructions
are practical when the number of senders $N$ is reasonably small,
e.g. $N=350$ in the BGN case and $N=2000$ in the Paillier case.

2004

EPRINT

Universally Composable DKG with Linear Number of Exponentiations
Abstract

Many problems have been solved by protocols using
discrete-logarithm based threshold cryptosystems. Such protocols
require a random joint public key for which the secret key is shared
among the parties.
A multiparty protocol that generates such a key is called a DKG
protocol. Until now no DKG protocol is known to be universally
composable.
We extend Feldman's original verifiable secret sharing scheme to
construct a DKG protocol, and prove that it is universally
composable. Our result holds in a common random string model under the
Decision Diffie-Hellman assumption. We stress that we do not need any
trapdoor for the common random string.
Our protocol is optimistic. If all parties behave honestly, each party
computes only $O(3k)$ exponentiations, where $k$ is the number of
parties. In the worst case each party computes $O(k^2)$
exponentiations. This should be contrasted with previous constructions
in which each party computes $\Omega(k^2)$ exponentiations regardless
of if they behave honestly or not. In the optimistic case the number
of bits sent in our protocol is essentially equal to the number of
bits sent in $k$ independent copies of Feldman's original protocol.

2004

EPRINT

Hierarchical Group Signatures
Abstract

We introduce the notion of \emph{hierarchical group signatures}. This
is a proper generalization of group signatures, which allows multiple
group managers organized in a tree with the signers as leaves. For a
signer that is a leaf of the subtree of a group manager, the group
manager learns which of its children that (perhaps indirectly) manages
the signer.
We provide definitions for the new notion and construct a scheme that
is provably secure given the existence of a family of trapdoor
permutations.
We also present a construction which is relatively practical, and
prove its security in the random oracle model under the strong RSA
assumption and the DDH assumption.

#### Coauthors

- Ben Adida (3)
- Johan Håstad (1)
- Rafael Pass (2)
- Krzysztof Pietrzak (2)
- Marten Trolin (1)
- Wei-Lung Dustin Tseng (1)