## CryptoDB

### Douglas Wikström

#### Publications

Year
Venue
Title
2010
TCC
2009
CRYPTO
2007
TCC
2007
TCC
2007
TCC
2007
EPRINT
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
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
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
ASIACRYPT
2005
EPRINT
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
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
TCC
2004
EPRINT
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
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.