Change search
Refine search result
1 - 32 of 32
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Adida, Ben
    et al.
    MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA.
    Wikström, Douglas
    ETH Zürich, Department of Computer Science.
    How to shuffle in public2007In: THEORY OF CRYPTOGRAPHY, PROCEEDINGS, 2007, p. 555-574Conference paper (Refereed)
    Abstract [en]

    We show how to obfuscate a secret shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct public-key obfuscations of a decryption shuffle based on the Boneh-Coh-Nissim (BGN) cryptosystem and a re-encryption shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption. 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 small, yet large enough to handle a number of practical cases, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.

  • 2.
    Adida, Ben
    et al.
    Harvard Univ, Ctr Res Computat & Soc, Cambridge, MA 02138 USA.
    Wikström, Douglas
    Harvard Univ, Ctr Res Computat & Soc, Cambridge, MA 02138 USA.
    Offline/online mixing2007In: AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2007, p. 484-495Conference paper (Refereed)
    Abstract [en]

    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.

  • 3. Ben-Nun, J.
    et al.
    Farhi, N.
    Llewellyn, M.
    Riva, B.
    Rosen, A.
    Ta-Shma, A.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A new implementation of a dual (paper and cryptographic) voting system2012Conference paper (Refereed)
    Abstract [en]

    We report on the design and implementation of a new cryptographic voting system, designed to retain the "look and feel" of standard, paper-based voting used in our country Israel while enhancing security with end-to-end verifiability guaranteed by cryptographic voting. Our system is dual ballot and runs two voting processes in parallel: one is electronic while the other is paper-based and similar to the traditional process used in Israel. Consistency between the two processes is enforced by means of a new, specially-tailored paper ballot format. We examined the practicality and usability of our protocol through implementation and field testing in two elections: the first being a student council election with over 2000 voters, the second a political party's election for choosing their leader. We present our findings, some of which were extracted from a survey we conducted during the first election. Overall, voters trusted the system and found it comfortable to use.

  • 4.
    Håstad, Johan
    et al.
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Pass, Rafael
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Pietrzak, Krzysztof
    An Efficient Parallel Repetition Theorem2010In: THEORY OF CRYPTOGRAPHY, PROCEEDINGS / [ed] Micciancio D, 2010, Vol. 5978, p. 1-18Conference paper (Refereed)
    Abstract [en]

    We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.

  • 5.
    Khazaei, Shahram
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Moran, T.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A mix-net from any CCA2 secure cryptosystem2012In: Advances in Cryptology – ASIACRYPT 2012: 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings / [ed] Xiaoyun Wang, Kazue Sako, Springer, 2012, p. 607-625Conference paper (Refereed)
    Abstract [en]

    We construct a provably secure mix-net from any CCA2 secure cryptosystem. The mix-net is secure against active adversaries that statically corrupt less than λ out of k mix-servers, where λ is a threshold parameter, and it is robust provided that at most min(λ - 1, k - λ) mix-servers are corrupted. The main component of our construction is a mix-net that outputs the correct result if all mix-servers behaved honestly, and aborts with probability 1 - O(H-(t-1)) otherwise (without disclosing anything about the inputs), where t is an auxiliary security parameter and H is the number of honest parties. The running time of this protocol for long messages is roughly 3tc, where c is the running time of Chaum's mix-net (1981).

  • 6.
    Khazaei, Shahram
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Terelius, Björn
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Cryptanalysis of a Universally Verifiable Efficient Re-encryption Mixnet2012Manuscript (preprint) (Other academic)
    Abstract [en]

    We study the heuristically secure mix-net proposed by Puiggal´ı and Guasch (EVOTE2010). We present practical attacks on both correctness and privacy for some sets of parametersof the scheme. Although our attacks only allow us to replace a few inputs, or tobreak the privacy of a few voters, this shows that the scheme can not be proven secure.

  • 7.
    Khazaei, Shahram
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Randomized partial checking revisited2013In: Lect. Notes Comput. Sci., 2013, p. 115-128Conference paper (Refereed)
    Abstract [en]

    We study mix-nets with randomized partial checking (RPC) as proposed by Jakobsson, Juels, and Rivest (2002). RPC is a technique to verify the correctness of an execution both for Chaumian and homomorphic mix-nets. The idea is to relax the correctness and privacy requirements to achieve a more efficient mix-net. We identify serious issues in the original description of mix-nets with RPC and show how to exploit these to break both correctness and privacy, both for Chaumian and homomorphic mix-nets. Our attacks are practical and applicable to real world mix-net implementations, e.g., the Civitas and the Scantegrity voting systems.

  • 8.
    Khazaei, Shahram
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Randomized Partial Checking Revisited2012Manuscript (preprint) (Other academic)
    Abstract [en]

    We study mix-nets with randomized partial checking (RPC) as proposed by Jakobsson, Juels, and Rivest (2002). RPC is a technique to verify the correctness of an execution both for Chaumian and homomorphic mix-nets. The idea is to relax the correctness and privacy requirements to achieve a more efficient mix-net.

    We identify serious issues in the original description of mix-nets with RPC and show how to exploit these to break both correctness and privacy, both for Chaumian and homomorphic mix-nets. Our attacks are practical and applicable to real world mix-net implementations, e.g., the Civitas and the Scantegrity voting systems.

  • 9.
    Kreitz, Gunnar
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Dam, Mads
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Practical Private Information Aggregation in Large Networks2012In: Information Security Technology For Applications, Springer Berlin/Heidelberg, 2012, p. 89-103Conference paper (Refereed)
    Abstract [en]

    Emerging approaches to network monitoring involve large numbers of agents collaborating to produce performance or security related statistics on huge, partial mesh networks. The aggregation process often involves security or business-critical information which network providers are generally unwilling to share without strong privacy protection. We present efficient and scalable protocols for privately computing a large range of aggregation functions based on addition, disjunction, and max/min. For addition, we give a protocol that is information-theoretically secure against a passive adversary, and which requires only one additional round compared to non-private protocols for computing sums. For disjunctions, we present both a computationally secure, and an information-theoretically secure solution. The latter uses a general composition approach which executes the sum protocol together with a standard multi-party protocol for a complete subgraph of ``trusted servers''. This can be used, for instance, when a large network can be partitioned into a smaller number of provider domains.

  • 10. Pass, Rafael
    et al.
    Tseng, Wei-Lung Dustin
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the composition of public-coin zero-knowledge protocols2011In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 6, p. 1529-1553Article in journal (Refereed)
    Abstract [en]

    We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of "resettable soundness" if the verifier picks its random coins using a pseudorandom function.

  • 11.
    Pass, Rafael
    et al.
    Cornell Univ, Ithaca, NY 14853 USA.
    Tseng, Wei-Lung Dustin
    Cornell Univ, Ithaca, NY 14853 USA.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the Composition of Public-Coin Zero-Knowledge Protocols2009In: ADVANCES IN CRYPTOLOGY - CRYPTO 2009 / [ed] Halevi, S, 2009, Vol. 5677, p. 160-176Conference paper (Refereed)
    Abstract [en]

    We show that only languages in BPP have public-coin, black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any set-up) and in the Bare Public-Key Model (where the prover and the verifier have registered public keys). We complement this result by showing the existence of a public-coin black-box zero-knowledge proof that remains secure under any a-priori bounded number of concurrent executions.

  • 12.
    Pietrazak, Krzystof
    et al.
    Ecole Normale Super, Dept Informat, Paris, France .
    Wikström, Douglas
    ETH Zürich, Department of Computer Science.
    Parallel repetition of computationally sound protocols revisited2007In: THEORY OF CRYPTOGRAPHY, PROCEEDINGS, 2007, p. 86-102Conference paper (Refereed)
    Abstract [en]

    Parallel repetition is well known to reduce the error probability at an exponential rate for single- and multi-prover interactive proofs. Bellare, Impagliazzo and Naor (1997) show that this is also true for protocols where the soundness only holds against computationally bounded provers (e.g. interactive arguments) if the protocol has at most three rounds. On the other hand, for four rounds they give a protocol where this is no longer the case: the error probability does not; decrease below some constant even if the protocol is repeated a polynomial number of times. Unfortunately, this protocol is not very convincing as the communication complexity of each instance of the protocol grows linearly with the number of repetitions, and for such protocols the error does not even decrease for some types of interactive proofs. Noticing this, Bellare et al. construct (a quite artificial) oracle relative to which a four round protocol exists whose communication complexity does not depend on the number of parallel repetitions. This shows that there is no "black-box" error reduction theorem for four round protocols. In this paper we give the first computationally sound protocol where k-fold parallel repetition does not decrease the error probability below some constant for any polynomial k (and where the communication complexity does not depend on k). The protocol has eight rounds and uses the universal arguments of Barak and Goldreich (2001). We also give another four round protocol relative to an oracle, unlike the artificial oracle of Bellare et al., we just need a generic group. This group can then potentially be instantiated with some real group satisfying some well defined hardness assumptions (we do not know of any candidate for such a group at the moment).

  • 13. Pietrzak, Krzysztof
    et al.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Parallel Repetition of Computationally Sound Protocols Revisited2012In: Journal of Cryptology, ISSN 0933-2790, E-ISSN 1432-1378, Vol. 25, no 1, p. 116-135Article in journal (Refereed)
    Abstract [en]

    We prove a negative result concerning error reduction by parallel repetition for computationally sound protocols, e.g., interactive arguments. Our main result is a complete and computationally sound eight round interactive argument for which k-fold parallel repetition does not reduce the error below a constant for any polynomial k. The starting point for our construction is the work of Bellare, Impagliazzo and Naor (FOCS'97). For any fixed k, they construct a four round protocol for which k-fold parallel repetition does not lower the soundness error. The communication complexity of this protocol is linear in k. By using universal arguments due to Barak and Goldreich (CCC 2002), we turn this protocol into an eight-round protocol whose complexity is basically independent of k.

  • 14. Przydatek, Bartosz
    et al.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Group Message Authentication2010In: SECURITY AND CRYPTOGRAPHY FOR NETWORKS, 2010, p. 399-417Conference paper (Refereed)
    Abstract [en]

    Group signatures is a powerful primitive with many practical applications, allowing a group of parties to share a signature functionality, while protecting the anonymity of the signer. However, despite intensive research in the past years, there is still no fully satisfactory implementation of group signatures in the plain model. The schemes proposed so far are either too inefficient to be used in practice, or their security is based on rather strong, non-standard assumptions. We observe that for some applications the full power of group signatures is not necessary. For example, a group signature can be verified by any third party, while in many applications such a universal verifiability is not needed or even not desired. Motivated by tins observation, we propose a notion of group message authentication, which can be viewed as a relaxation of group signatures. Group message authentication enjoys the group-oriented features of group signatures, while dropping some of the features which are not needed in many real-life scenarios. An example application of group message authentication is an implementation of an anonymous credit card. We present a generic implementation of group message authentication, and also propose an efficient concrete implementation based on standard assumptions, namely strong RSA and DDH.

  • 15.
    Terelius, Björn
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Efficiency limitations of Σ-protocols for group homomorphisms revisited2012In: Security and Cryptography for Networks, Springer Berlin/Heidelberg, 2012, p. 461-476Conference paper (Refereed)
    Abstract [en]

    We study the problem of constructing efficient proofs of knowledge of preimages of general group homomorphisms. We simplify and extend the recent negative results of Bangerter et al. (TCC 2010) to constant round (from three-message) generic protocols over concrete (instead of generic) groups, i.e., we prove lower bounds on both the soundness error and the knowledge error of such protocols. We also give a precise characterization of what can be extracted from the prover in the direct (common) generalization of the Guillou-Quisquater and Schnorr protocols to the setting of general group homomorphisms. Then we consider some settings in which these bounds can be circumvented. For groups with no subgroups of small order we present: (1) a three-move honest verifier zero-knowledge argument under some set-up assumptions and the standard discrete logarithm assumption, and (2) a Σ-proof of both the order of the group and the preimage. The former may be viewed as an offline/online protocol, where all slow cut-andchoose protocols can be moved to an offline phase.

  • 16.
    Terelius, Björn
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Proofs of Restricted Shuffles2010In: PROGRESS IN CRYPTOLOGY - AFRICACRYPT 2010 / [ed] Bernstein DJ; Lange T, 2010, Vol. 6055, p. 100-113Conference paper (Refereed)
    Abstract [en]

    A proof of a shuffle is a zero-knowledge proof that one list of ciphertexts is a permutation and re-encryption of another list of ciphertexts. We call a shuffle restricted if the permutation is chosen from a public subset of all permutations. In this paper, we introduce a general technique for constructing proofs of shuffles which restrict the permutation to a group that is characterized by a public polynomial. This generalizes previous work by Reiter and Wang [22], and de Hoogh et al. [7]. Our approach also gives a new efficient proof of an unrestricted shuffle that we think is conceptually simpler and allow a simpler analysis than all previous proofs of shuffles.

  • 17.
    Trolin, Mårten
    et al.
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Hierarchical group signatures2005In: AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS / [ed] Caires, L; Italiano, GE; Monteiro, L; Palamidessi, C; Yung, M, 2005, Vol. 3580, p. 446-458Conference paper (Refereed)
    Abstract [en]

    We introduce the notion of 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. When opening a signature a group manager only learns to which of its subtrees, if any, the signer belongs. 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.

  • 18.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A Commitment-Consistent Proof of a Shuffle2009In: INFORMATION SECURITY AND PRIVACY, PROCEEDINGS / [ed] Boyd C, Nieto JG, Berlin: SPRINGER-VERLAG BERLIN , 2009, Vol. 5594, p. 407-421Conference paper (Refereed)
    Abstract [en]

    We introduce a pre-computation technique that drastically reduces the online computational complexity of mix-nets based on homomorphic cryptosystems. More precisely, we show that there is a permutation commitment scheme that allows a mix-server to: (1) commit to a permutation and efficiently prove knowledge of doing so correctly in the offline phase, and (2) shuffle its input and give an extremely efficient commitment-consistent proof of a shuffle in the online phase. We prove our result for a general class of shuffle maps that generalize a known types of shuffles, and even allows shuffling ciphertexts of different cryptosystems in parallel.

  • 19.
    Wikström, Douglas
    Swedish Institute of Computer Science (SICS).
    A note on the malleability of the El Gamal cryptosystem2002In: PROGRESS IN CRYPTOLOGY - INDOCRYPT 2002, PROCEEDINGS / [ed] Menezes, A; Sarkar, P, Berlin: Springer Verlag , 2002, p. 176-184Conference paper (Refereed)
    Abstract [en]

    The homomorphic property of the El Gamal cryptosystem is useful in the construction of efficient protocols. It is believed that only a small class of transformations of cryptotexts are feasible to compute. In the program of showing that these are the only computable transformations we rule out a large set of natural transformations

  • 20.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A sender verifiable mix-net and a new proof of a shuffle2005In: ADVANCES IN CRYPTOLOGY ASIACRYPT 200 / [ed] Roy, B, BERLIN: SPRINGER-VERLAG BERLIN , 2005, Vol. 3788, p. 273-292Conference paper (Refereed)
    Abstract [en]

    We introduce the first El Carnal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no reencryption 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. The mix-net is provably UC-secure 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.

  • 21.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    A universally composable mix-net2004In: THEORY OF CRYTOGRAPHY, PROCEEDINGS  Book Series: LECTURE NOTES IN COMPUTER SCIENCE / [ed] Naor, M, BERLIN: SPRINGER , 2004, Vol. 2951, p. 317-335Conference paper (Refereed)
    Abstract [en]

    A mix-net is a cryptographic protocol executed by a set of mix-servers that provides anonymity for a group of senders. The main application is electronic voting. Numerous mix-net constructions and stand-alone definitions of security are proposed in the literature, but only partial proofs of security are given for most constructions and no construction has been proved secure with regards to any kind of composition. We define an ideal mix-net in the universally composable security framework of Canetti [6]. Then we describe a mix-net based on Feldman [13] and using similar ideas as Desmedt and Kurosawa [10], and prove that it securely realizes the ideal mix-net with respect to static adversaries that corrupt a minority of the mix-servers and arbitrarily many senders. The mix-net executes in a hybrid model with access to ideal distributed key generation, but apart from that our only assumption is the existence of a group in which the Decision Diffie-Hellman Problem is hard. If there are relatively few mix-servers or a strong majority of honest mix-servers our construction is practical.

  • 22.
    Wikström, Douglas
    ETH Zürich, Department of Computer Science.
    Designated confirmer signatures revisited2007In: Theory of Cryptography, Proceedings, 2007, p. 342-361Conference paper (Refereed)
    Abstract [en]

    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.

  • 23.
    Wikström, Douglas
    Swedish Institute of Computer Science (SICS).
    Five Practical Attacks for “Optimistic Mixing for Exit-Polls”2004In: SELECTED AREAS IN CRYPTOGRAPHY, BERLIN: Springer Verlag , 2004, p. 160-174Conference paper (Refereed)
    Abstract [en]

    Golle, Zhong, Boneh, Jakobsson, and Juels [9] recently presented an efficient mix-net, which they claim to be both robust and secure. We present five practical attacks for their mix-net, and break both its privacy and robustness. The first attack breaks the privacy of any given sender without corrupting any mix-server. The second attack requires that the first mix-server is corrupted. Both attacks are adaptations of the “relation attack” introduced by Pfitzmann [24, 23]. The third attack is similar to the attack of Desmedt and Kurusawa [4] and breaks the privacy of all senders. It requires that all senders are honest and that the last mix-server is corrupted. The fourth attack may be viewed as a novel combination of the ideas of Lim and Lee [16] and Pfitzmann [24, 23]. It breaks the privacy of any given sender, and requires that the first and last mix-servers are corrupted. This attack breaks also Jakobsson [14], including the fixed version of Mitomo and Kurosawa [18]. The fifth attack breaks the robustness in a novel way. It requires corruption of some senders and the first mix-server. This attack breaks also Jakobsson and Juels [15].

  • 24.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    On the l-ary GCD-algorithm in rings of integers2005In: AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS / [ed] Caires, L; Italiano, GE; Monteiro, L; Palamidessi, C; Yung, M, 2005, Vol. 3580, p. 1189-1201Conference paper (Refereed)
    Abstract [en]

    The greatest common divisor (GCD) of two integers a and b is the largest integer d such that d divides both a and b. The problem of finding the GCD of two integers efficiently is one of the oldest problems studied in number theory. The corresponding problem can be considered for two elements alpha and beta in any factorial ring R. Then lambda is an element of R is a GCD of alpha and beta if it divides both elements, and whenever lambda is an element of R divides both alpha and beta it also holds that lambda' divides lambda. A precise understanding of the complexity of different GCD algorithms gives a better understanding of the arithmetic in the domain under consideration.

  • 25.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    On the security of mix-nets and hierarchical group signatures2005Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    In this thesis we investigate two separate cryptographic notions: mix-nets and hierarchical group signatures. The former notion was introduced by Chaum (1981). The latter notion is introduced in this thesis, but it generalizes the notion of group signatures which was introduced by Chaum and Heyst (1991).

    Numerous proposals for mix-nets are given in the literature, but these are presented with informal security arguments or at best partial proofs. We illustrate the need for a rigorous treatment of the security mix-nets by giving several practical attacks against a construction of Golle et al. (2002). Then we provide the first definition of security of a mix-net in the universally composable security framework (UC-framework) introduced by Canetti (2001). We construct two distinct efficient mix-nets that are provably secure under standard assumptions in the UC-framework against an adversary that corrupts any minority of the mix-servers and any set of senders. The first construction is based on the El Gamal cryptosystem (1985) and is secure against a static adversary, i.e., an adversary that decides which parties to corrupt before the execution of the protocol. This is the first efficient UC-secure mix-net in the literature and the first sender verifiable mix-net that is robust. The second construction is based on the Paillier cryptosystem (1999) and secure against an adaptive adversary, i.e., an adversary that decides which parties to corrupt during the execution of the protocol. This is the first efficient adaptively secure mix-net in any model. An important subprotocol in the above constructions is a zero-knowledge proof of knowledge of a witness that a party behaves as expected. There are two known approaches for constructing such a protocol given by Neff (2002) and Furukawa and Sako (2002) respectively. We present a third independent approach.

    We introduce the notion of hierarchical group signatures. This is a generalization of group signatures. There are several group managers, and the signers and group managers are organized in a tree in which the signers are the leaves and the group managers are internal nodes. Given a signature, a group manager learns if it is an ancestor of the signer, and if so to which of its immediate subtrees the signer belongs, but it learns nothing else. Thus, the identity of the signer is revealed in a hierarchical way. We provide a definition of security of hierarchical group signatures and give two provably secure constructions. The first construction is secure under general assumptions. It is impractical and of purely theoretical interest. The second construction is provably secure under standard complexity assumptions and almost practical.

  • 26.
    Wikström, Douglas
    KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
    On the security of mix-nets and related problems2004Licentiate thesis, monograph (Other scientific)
  • 27.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Simplified Submission of Inputs to Protocols2008In: Security And Cryptography For Networks, Proceedings / [ed] Ostrovsky, R; DePrisco, R; Visconti, I, 2008, Vol. 5229, p. 293-308Conference paper (Refereed)
    Abstract [en]

    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 homomorphic cryptosystem. This can clearly be achieved using general techniques, but we would like a solution which is: (i) provably secure under standard assumptions, (ii) non-interactive for submittors (iii) 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.

  • 28.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Simplified universal composability framework2016In: 13th International Conference on Theory of Cryptography, TCC 2016, Springer, 2016, p. 566-595Conference paper (Refereed)
    Abstract [en]

    We introduce a simplified universally composable (UC) security framework in our thesis (2005). In this paper we present an updated more comprehensive and illustrated version. The introduction of our simplified model is motivated by the difficulty to describe and analyze concrete protocols in the full UC framework due to its generality and complexity. The main differences between our formalization and the general UC security framework are that we consider: a fixed number of parties, static corruption, and simple ways to bound the running times of the adversary and environment. However, the model is easy to extend to adaptive adversaries. Authenticated channels become a trivial ideal functionality. We generalize the framework to allow protocols to securely realize other protocols. This allows a natural and modular description and analysis of protocols. We introduce invertible transforms of models that allow us to reduce the proof of the composition theorem to a simple special case and transform any hybrid protocol into a hybrid protocol with at most one ideal functionality. This factors out almost all of the technical details of our framework to be considered when relating our framework to any other security framework, e.g., the UC framework, and makes this easy.

  • 29.
    Wikström, Douglas
    Swedish Institute of Computer Science.
    The security of a mix-center based on a semantically secure cryptosystem2002In: PROGRESS IN CRYPTOLOGY - INDOCRYPT 2002, PROCEEDINGS / [ed] Menezes, A; Sarkar, P, Berlin: Springer Verlag , 2002, p. 368-381Conference paper (Refereed)
    Abstract [en]

    We introduce a definition of a re-encryption mix-center, and a definition of security for such a mix-center. Then we prove that any semantically secure public key system, which allows re-encryption, can be used to construct a secure mix-center.

  • 30.
    Wikström, Douglas
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Universally composable DKG with linear number of exponentiations2005In: Security in Communication Networks: 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Revised Selected Papers, Springer Berlin/Heidelberg, 2005, p. 263-277Conference paper (Refereed)
    Abstract [en]

    Until now no distributed discrete-logarithm key generation (DKG) protocol is known to be universally composable. We extend Feld- man's verifiable secret sharing scheme to construct such a protocol. Our result holds for static adversaries corrupting a minority of the parties under the Decision Diffie-Hellman assumption in a weak common random string model in which the simulator does not choose the common random string. Our protocol is optimistic. If all parties behave honestly, each party computes O(3.5k) exponentiations, and otherwise each party computes O(k2) exponentiations, where k is the number of parties. In previous constructions each party always computes Ω(k2) exponentiations.

  • 31.
    Wikström, Douglas
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Barrat, J.
    Heiberg, S.
    Krimmer, R.
    Schürmann, C.
    How could Snowden attack an election?2017In: 2nd International Joint Conference on Electronic Voting, E-Vote-ID 2017, Springer, 2017, Vol. 10615, p. 280-291Conference paper (Refereed)
    Abstract [en]

    We discuss a new type of attack on voting systems that in contrast to attacks described in the literature does not disrupt the expected behavior of the voting system itself. Instead the attack abuses the normal functionality to link the tallying of the election to disclosing sensitive information assumed to be held by the adversary. Thus the attack forces election officials to choose between two undesirable options: Not to publish the election result or to play into the adversary’s hand and to publicize sensitive information. We stress that the attack is different from extortion and not restricted to electronic voting systems.

  • 32.
    Wikström, Douglas
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Groth, Jens
    An adaptively secure mix-net without erasures2006In: AUTOMATA, LANGAGES AND PROGRAMMING, PT 2, BERLIN: SPRINGER-VERLAG BERLIN , 2006, p. 276-287Conference paper (Refereed)
    Abstract [en]

    We construct the first mix-net that is secure against adaptive adversaries corrupting any minority of the mix-servers and any set of senders. The mix-net is based on the Paillier cryptosystem and analyzed in the universal composability model without erasures under the decisional composite residuosity assumption, the strong RSA-assumption, and the discrete logarithm assumption. We assume the existence of ideal functionalities for a bulletin board, key generation, and coin-flipping.

1 - 32 of 32
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf