15 Search Results for "Kutylowski, Miroslaw"

Document
DOI: 10.4230/LIPIcs.DISC.2025.14
Energy-Efficient Maximal Independent Sets in Radio Networks

Authors: Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1) CD model: We present a randomized distributed MIS algorithm with energy complexity O(log n), round complexity O(log² n), and failure probability 1 / poly(n), where n is the network size. We show that our energy complexity is optimal by showing a matching Ω(log n) lower bound. 2) no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity O(log²n log log n), round complexity O(log³ n log Δ), and failure probability 1 / poly(n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O(log³ n) of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.
Cite as

Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2025.14,
  author =	{Banasik, Dominick and Dani, Varsha and Dufoulon, Fabien and Gupta, Aayush and Hayes, Thomas P. and Pandurangan, Gopal},
  title =	{{Energy-Efficient Maximal Independent Sets in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.14},
  URN =		{urn:nbn:de:0030-drops-248311},
  doi =		{10.4230/LIPIcs.DISC.2025.14},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Sleeping Model, Radio Networks, Maximal Independent Set}
}
Document
DOI: 10.4230/LIPIcs.ITP.2025.15
Certified Implementability of Global Multiparty Protocols

Authors: Elaine Li and Thomas Wies

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
Implementability is the decision problem at the heart of top-down approaches to protocol verification. In this paper, we present a mechanization of a recently proposed precise implementability characterization by Li et al. for a large class of protocols that subsumes many existing formalisms in the literature. Our protocols and implementations model asynchronous commmunication, and can exhibit infinite behavior. We improve upon their pen-and-paper results by unifying distinct formalisms, simplifying existing proof arguments, elaborating on the construction of canonical implementations, and even uncovering a subtle bug in the semantics for infinite words. As a corollary of our mechanization, we show that the original characterization of implementability applies even to protocols with infinitely many participants. We also contribute a reusable library for reasoning about generic communicating state machines. Our mechanization consists of about 15k lines of Rocq code. We believe that our mechanization can provide the foundation for deductively proving the implementability of protocols beyond the reach of prior work, extracting certified implementations for finite protocols, and investigating implementability under alternative asynchronous communication models.
Cite as

Elaine Li and Thomas Wies. Certified Implementability of Global Multiparty Protocols. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITP.2025.15,
  author =	{Li, Elaine and Wies, Thomas},
  title =	{{Certified Implementability of Global Multiparty Protocols}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.15},
  URN =		{urn:nbn:de:0030-drops-246139},
  doi =		{10.4230/LIPIcs.ITP.2025.15},
  annote =	{Keywords: Asynchronous protocols, communicating state machines, labeled transition systems, infinite semantics, realizability, multiparty session types, choreographies, deadlock freedom}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2025.21
Quantitative Language Automata

Authors: Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi, and N. Ege Saraç

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
A quantitative word automaton (QWA) defines a function from infinite words to values. For example, every infinite run of a limit-average QWA 𝒜 obtains a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained by nondeterministic runs of 𝒜 over w. We introduce quantitative language automata (QLAs) that define functions from language generators (i.e., implementations) to values, where a language generator can be nonprobabilistic, defining a set of infinite words, or probabilistic, defining a probability measure over infinite words. A QLA consists of a QWA and an aggregator function. For example, given a QWA 𝒜, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest lower bound assigned by 𝒜 to any word in L. For boolean value sets, QWAs define boolean properties of traces, and QLAs define boolean properties of sets of traces, i.e., hyperproperties. For more general value sets, QLAs serve as a specification language for a generalization of hyperproperties, called quantitative hyperproperties. A nonprobabilistic (resp. probabilistic) quantitative hyperproperty assigns a value to each set (resp. distribution) G of traces, e.g., the minimal (resp. expected) average response time exhibited by the traces in G. We give several examples of quantitative hyperproperties and investigate three paradigmatic problems for QLAs: evaluation, nonemptiness, and universality. In the evaluation problem, given a QLA 𝔸 and an implementation G, we ask for the value that 𝔸 assigns to G. In the nonemptiness (resp. universality) problem, given a QLA 𝔸 and a value k, we ask whether 𝔸 assigns at least k to some (resp. every) language. We provide a comprehensive picture of decidability for these problems for QLAs with common aggregators as well as their restrictions to ω-regular languages and trace distributions generated by finite-state Markov chains.
Cite as

Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi, and N. Ege Saraç. Quantitative Language Automata. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.CONCUR.2025.21,
  author =	{Henzinger, Thomas A. and Kebis, Pavol and Mazzocchi, Nicolas and Sara\c{c}, N. Ege},
  title =	{{Quantitative Language Automata}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.21},
  URN =		{urn:nbn:de:0030-drops-239718},
  doi =		{10.4230/LIPIcs.CONCUR.2025.21},
  annote =	{Keywords: Quantitative hyperproperties, quantitative automata, automata-based verification}
}
Document
DOI: 10.4230/OASIcs.Manzini.9
Search Schemes for Approximate Pattern Matching: An Overview

Authors: Lore Depuydt, Jan Fostier, Simon Gottlieb, Gregory Kucherov, Knut Reinert, and Luca Renders

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
We provide a brief survey of results on solving the approximate pattern matching problem using search schemes, as introduced by Kucherov et al. (2016). We demonstrate that search schemes constitute a flexible and versatile tool that enable the specification of various search strategies, including several known filtering methods. We present approaches for designing efficient search schemes and for implementing them effectively. Finally, we conclude with experimental results comparing multiple search schemes on DNA sequencing data using the Columba software by Renders et al. (2021).
Cite as

Lore Depuydt, Jan Fostier, Simon Gottlieb, Gregory Kucherov, Knut Reinert, and Luca Renders. Search Schemes for Approximate Pattern Matching: An Overview. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depuydt_et_al:OASIcs.Manzini.9,
  author =	{Depuydt, Lore and Fostier, Jan and Gottlieb, Simon and Kucherov, Gregory and Reinert, Knut and Renders, Luca},
  title =	{{Search Schemes for Approximate Pattern Matching: An Overview}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{9:1--9:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.9},
  URN =		{urn:nbn:de:0030-drops-239172},
  doi =		{10.4230/OASIcs.Manzini.9},
  annote =	{Keywords: FM-index, bidirectional index, approximate pattern matching, search scheme}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.13
Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility

Authors: Raphael Gerlach, Sören von der Gracht, Christopher Hahn, Jonas Harbig, and Peter Kling

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In the general pattern formation (GPF) problem, a swarm of simple autonomous, disoriented robots must form a given pattern. The robots' simplicity imply a strong limitation: When the initial configuration is rotationally symmetric, only patterns with a similar symmetry can be formed [Masafumi Yamashita and Ichiro Suzuki, 2010]. The only known algorithm to form large patterns with limited visibility and without memory requires the robots to start in a near-gathering (a swarm of constant diameter) [Christopher Hahn et al., 2024]. However, not only do we not know any near-gathering algorithm guaranteed to preserve symmetry but most natural gathering strategies trivially increase symmetries [Jannik Castenow et al., 2022]. Thus, we study near-gathering without changing the swarm’s rotational symmetry for disoriented, oblivious robots with limited visibility (the OBLOT-model, see [Paola Flocchini et al., 2019]). We introduce a technique based on the theory of dynamical systems to analyze how a given algorithm affects symmetry and provide sufficient conditions for symmetry preservation. Until now, it was unknown whether the considered OBLOT-model allows for any non-trivial algorithm that always preserves symmetry. Our first result shows that a variant of Go-To-The-Average always preserves symmetry but may sometimes lead to multiple, unconnected near-gathering clusters. Our second result is a symmetry-preserving near-gathering algorithm that works on swarms with a convex boundary (the outer boundary of the unit disc graph) and without "holes" (circles of diameter 1 inside the boundary without any robots).
Cite as

Raphael Gerlach, Sören von der Gracht, Christopher Hahn, Jonas Harbig, and Peter Kling. Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 13:1-13:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.OPODIS.2024.13,
  author =	{Gerlach, Raphael and von der Gracht, S\"{o}ren and Hahn, Christopher and Harbig, Jonas and Kling, Peter},
  title =	{{Symmetry Preservation in Swarms of Oblivious Robots with Limited Visibility}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{13:1--13:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.13},
  URN =		{urn:nbn:de:0030-drops-225490},
  doi =		{10.4230/LIPIcs.OPODIS.2024.13},
  annote =	{Keywords: Swarm Algorithm, Swarm Robots, Distributed Algorithm, Pattern Formation, Limited Visibility, Oblivious}
}
Document
DOI: 10.4230/DagSemProc.07311.1
07311 Abstracts Collection – Frontiers of Electronic Voting

Authors: David Chaum, Miroslaw Kutylowski, Ronald L. Rivest, and Peter Y. A. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
From July the 29th to August the 3th, 2007, the Dagstuhl Seminar 07311 ``Frontiers of Electronic Voting'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

David Chaum, Miroslaw Kutylowski, Ronald L. Rivest, and Peter Y. A. Ryan. 07311 Abstracts Collection – Frontiers of Electronic Voting. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chaum_et_al:DagSemProc.07311.1,
  author =	{Chaum, David and Kutylowski, Miroslaw and Rivest, Ronald L. and Ryan, Peter Y. A.},
  title =	{{07311 Abstracts Collection – Frontiers of Electronic Voting}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.1},
  URN =		{urn:nbn:de:0030-drops-13031},
  doi =		{10.4230/DagSemProc.07311.1},
  annote =	{Keywords: Voting machine, remote voting, verifiability, foundations of voting algorithms, attacks}
}
Document
DOI: 10.4230/DagSemProc.07311.2
07311 Executive Summary – Frontiers of Electronic Voting

Authors: David Chaum, Miroslaw Kutylowski, Ronald L. Rivest, and Peter Y. A. Ryan

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
This is a short report on Dagstuhl Seminar 07311 - Frontiers of Electronic Voting, 29.07.07 - 03.08.07, organized in The International Conference and Research Center for Computer Science (IBFI, Schloss Dagstuhl).
Cite as

David Chaum, Miroslaw Kutylowski, Ronald L. Rivest, and Peter Y. A. Ryan. 07311 Executive Summary – Frontiers of Electronic Voting. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chaum_et_al:DagSemProc.07311.2,
  author =	{Chaum, David and Kutylowski, Miroslaw and Rivest, Ronald L. and Ryan, Peter Y. A.},
  title =	{{07311 Executive Summary – Frontiers of Electronic Voting}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.2},
  URN =		{urn:nbn:de:0030-drops-12945},
  doi =		{10.4230/DagSemProc.07311.2},
  annote =	{Keywords: Voting machine, remote voting, verifiability, foundations of voting algorithms, attacks}
}
Document
DOI: 10.4230/DagSemProc.07311.3
A practical and secure coercion-resistant scheme for remote elections

Authors: Roberto Araujo, Sébastien Foulle, and Jacques Traoré

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Election schemes, coercion-resistance, security Juels, Catalano, and Jakobsson (JCJ) proposed at WPES 2005 the first scheme that considers real-world threats and that is more realistic for remote elections. Their scheme, though, has quadratic work factor and thereby is not efficient for large scale elections. Based on the work of JCJ, Smith proposed an efficient scheme that has linear work factor. In this paper we first show that the Smith’s scheme is insecure. Then we present a new coercion-resistant election scheme with linear work factor that overcomes this and other flaws of the Smith’s proposal. Our solution is based on the group signature scheme of Camenisch and Lysyanskaya (Crypto 2004).
Cite as

Roberto Araujo, Sébastien Foulle, and Jacques Traoré. A practical and secure coercion-resistant scheme for remote elections. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:DagSemProc.07311.3,
  author =	{Araujo, Roberto and Foulle, S\'{e}bastien and Traor\'{e}, Jacques},
  title =	{{A practical and secure coercion-resistant scheme for remote elections}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.3},
  URN =		{urn:nbn:de:0030-drops-12951},
  doi =		{10.4230/DagSemProc.07311.3},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.07311.4
An Information-Theoretic Model of Voting Systems

Authors: Benjamin Hosp and Poorvi Vora

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
We present an information-theoretic model of a voting system, consisting of (a) definitions of the desirable qualities of integrity, privacy and verifiability, and (b) quantitative measures of how close a system is to being perfect with respect to each of the qualities. We describe the well-known trade-off between integrity and privacy in this model, and defines a concept of weak privacy, which is traded off with system verifiability. This is an extension of a talk from WOTE 2006, and contains some new applications of the model and arguments for the model's applicability.
Cite as

Benjamin Hosp and Poorvi Vora. An Information-Theoretic Model of Voting Systems. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hosp_et_al:DagSemProc.07311.4,
  author =	{Hosp, Benjamin and Vora, Poorvi},
  title =	{{An Information-Theoretic Model of Voting Systems}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.4},
  URN =		{urn:nbn:de:0030-drops-12982},
  doi =		{10.4230/DagSemProc.07311.4},
  annote =	{Keywords: Information-Theory, Elections, Measurement, Integrity, Privacy, Verifiability}
}
Document
DOI: 10.4230/DagSemProc.07311.5
Civitas: A Secure Remote Voting System

Authors: Michael Clarkson, Stephen Chong, and Andrew Myers

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Civitas is the first implementation of a coercion-resistant, universally verifiable, remote voting scheme. This paper describes the design of Civitas, details the cryptographic protocols used in its construction, and illustrates how language-enforced information-flow security policies yield assurance in the implementation. The performance of Civitas scales well in the number of voters and offers reasonable tradeoffs between time, cost, and security. These results suggest that secure electronic voting is achievable. The name of this system as presented at Dagstuhl was CIVS. In August 2007, the name was changed to Civitas. For more information, see the Civitas website at http://www.cs.cornell.edu/projects/civitas.
Cite as

Michael Clarkson, Stephen Chong, and Andrew Myers. Civitas: A Secure Remote Voting System. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{clarkson_et_al:DagSemProc.07311.5,
  author =	{Clarkson, Michael and Chong, Stephen and Myers, Andrew},
  title =	{{Civitas: A Secure Remote Voting System}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--47},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.5},
  URN =		{urn:nbn:de:0030-drops-12960},
  doi =		{10.4230/DagSemProc.07311.5},
  annote =	{Keywords: Electronic voting, coercion resistance, voter registration, secure bulletin boards, cryptographic protocols}
}
Document
DOI: 10.4230/DagSemProc.07311.6
CodeVoting: protecting against malicious vote manipulation at the voter's PC

Authors: Rui Joaquim and Carlos Ribeiro

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Voting in uncontrolled environments, such as the Internet comes with a price, the price of having to trust in uncontrolled machines the collection of voter's vote. An uncontrolled machine, e.g. the voter's PC, may be infected with a virus or other malicious program that may try to change the voter's vote without her knowledge. Here we present CodeVoting, a technique to create a secure communication channel to a smart card that prevents vote manipulation by the voter's PC, while at the same time allows the use of any cryptographic voting protocol to cast the vote.
Cite as

Rui Joaquim and Carlos Ribeiro. CodeVoting: protecting against malicious vote manipulation at the voter's PC. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{joaquim_et_al:DagSemProc.07311.6,
  author =	{Joaquim, Rui and Ribeiro, Carlos},
  title =	{{CodeVoting: protecting against malicious vote manipulation at the voter's PC}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.6},
  URN =		{urn:nbn:de:0030-drops-12997},
  doi =		{10.4230/DagSemProc.07311.6},
  annote =	{Keywords: Internet voting, vote manipulation}
}
Document
DOI: 10.4230/DagSemProc.07311.7
Component Based Electronic Voting Systems

Authors: David Lundin

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
An electronic voting system may be said to be composed by a number of components, each of which has a number of properties. One of the most attractive effects of this way of thinking is that each component may have an attached in-depth threat analysis and verification strategy. Furthermore, the need to include the full system when making changes to a component is minimised and a model at this level can be turned into a lower-level implementation model where changes made can cascade to as few parts of the actual implementation as possible.
Cite as

David Lundin. Component Based Electronic Voting Systems. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lundin:DagSemProc.07311.7,
  author =	{Lundin, David},
  title =	{{Component Based Electronic Voting Systems}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.7},
  URN =		{urn:nbn:de:0030-drops-13004},
  doi =		{10.4230/DagSemProc.07311.7},
  annote =	{Keywords: Component based electronic voting systems}
}
Document
DOI: 10.4230/DagSemProc.07311.8
Simulation-based analysis of E2E voting systems

Authors: Olivier de Marneffe, Olivier Pereira, and Jean-Jacques Quisquater

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
End-to-end auditable voting systems are expected to guarantee very interesting, and often sophisticated security properties, including correctness, privacy, fairness, receipt-freeness, dots However, for many well-known protocols, these properties have never been analyzed in a systematic way. In this paper, we investigate the use of techniques from the simulation-based security tradition for the analysis of these protocols, through a case-study on the ThreeBallot protocol. Our analysis shows that the ThreeBallot protocol fails to emulate some natural voting functionality, reflecting the lack of election fairness guarantee from this protocol. Guided by the reasons that make our security proof fail, we propose a simple variant of the ThreeBallot protocol and show that this variant emulates our functionality.
Cite as

Olivier de Marneffe, Olivier Pereira, and Jean-Jacques Quisquater. Simulation-based analysis of E2E voting systems. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{demarneffe_et_al:DagSemProc.07311.8,
  author =	{de Marneffe, Olivier and Pereira, Olivier and Quisquater, Jean-Jacques},
  title =	{{Simulation-based analysis of E2E voting systems}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.8},
  URN =		{urn:nbn:de:0030-drops-12970},
  doi =		{10.4230/DagSemProc.07311.8},
  annote =	{Keywords: UC framework, simulatability, security proof, ThreeBallot}
}
Document
DOI: 10.4230/DagSemProc.07311.9
Weighted Voronoi Region Algorithms for Political Districting

Authors: Bruno Simeone, Federica Ricca, and Andrea Scozzari

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Automated political districting shares with electronic voting the aim of preventing electoral manipulation and pursuing an impartial electoral mechanism. Political districting can be modelled as multiobjective partitioning of a graph into connected components, where population equality and compactness must hold if a majority voting rule is adopted. This leads to the formulation of combinatorial optimization problems that are extremely hard to solve exactly. We propose a class of heuristics, based on discrete weighted Voronoi regions, for obtaining compact and balanced districts, and discuss some formal properties of these algorithms. Their performance has been tested on randomly generated rectangular grids, as well as on real-life benchmarks; for the latter instances the resulting district maps are compared with the institutional ones adopted in the Italian political elections from 1994 to 2001.
Cite as

Bruno Simeone, Federica Ricca, and Andrea Scozzari. Weighted Voronoi Region Algorithms for Political Districting. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{simeone_et_al:DagSemProc.07311.9,
  author =	{Simeone, Bruno and Ricca, Federica and Scozzari, Andrea},
  title =	{{Weighted Voronoi Region Algorithms for Political Districting}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.9},
  URN =		{urn:nbn:de:0030-drops-13024},
  doi =		{10.4230/DagSemProc.07311.9},
  annote =	{Keywords: Political districting, weighted Voronoi regions, graph partitioning, heuristics}
}
Document
DOI: 10.4230/DagSemProc.06111.7
Fault Jumping Attacks against Shrinking Generator

Authors: Marcin Gomulkiewicz, Miroslaw Kutylowski, and Pawel Wlaz

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
In this paper we outline two new cryptoanalytic attacks against hardware implementation of the shrinking generator by Coppersmith et al., a classic design in low-cost, simple-design pseudorandom bitstream generator. This is a report on work on progress, since implementation and careful adjusting the attack strategy in order to optimize the atatck is still not completed.
Cite as

Marcin Gomulkiewicz, Miroslaw Kutylowski, and Pawel Wlaz. Fault Jumping Attacks against Shrinking Generator. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gomulkiewicz_et_al:DagSemProc.06111.7,
  author =	{Gomulkiewicz, Marcin and Kutylowski, Miroslaw and Wlaz, Pawel},
  title =	{{Fault Jumping Attacks against Shrinking Generator}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.7},
  URN =		{urn:nbn:de:0030-drops-6117},
  doi =		{10.4230/DagSemProc.06111.7},
  annote =	{Keywords: Pseudorandom generator, shrinking generator, fault cryptanalysis}
}
  • Refine by Type
  • 15 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 9 2008
  • 1 2006

  • Refine by Author
  • 3 Kutylowski, Miroslaw
  • 2 Chaum, David
  • 2 Rivest, Ronald L.
  • 2 Ryan, Peter Y. A.
  • 1 Araujo, Roberto
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 OASIcs
  • 10 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Logic and verification
  • Show More...

  • Refine by Keyword
  • 2 Voting machine
  • 2 attacks
  • 2 foundations of voting algorithms
  • 2 remote voting
  • 2 verifiability
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact