More Like this

1. Statement Voting

   https://doi.org/10.1007/978-3-030-32101-7_38  

   Zhang, Bingsheng; Zhou, Hong-Sheng (September 2019, Lecture notes in computer science)

   The conventional (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in a collective decision-making process. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of “the wisdom of crowds”. However, there is no known cryptographically secure e-voting implementation that supports liquid democracy. In this work, we propose a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. In the statement voting, instead of defining a concrete elec- tion candidate, each voter can define a statement in his/her ballot but leave the vote “undefined” during the voting phase. During the tally phase, the (conditional) actions expressed in the statement will be carried out to determine the final vote. We initiate the study of statement voting under the Universal Composability (UC) framework, and propose several construction frameworks together with their instantiations. As an application, we show how statement voting can be used to realize a UC-secure liquid democracy voting system. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes. 

   more » « less
2. Simple, Credible, and Approximately-Optimal Auctions

   Daskalakis, C; Fishelson, M; Lucier, B; Syrgkanis, V; Velusamy, S (January 2020, 21st ACM Conference on Economics and Computation, EC 2020)

   null (Ed.)

   We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17]. 

   more » « less
3. Riggs: Decentralized Sealed-Bid Auctions

   Tyagi, Nirvan; Arun, Arasu; Freitag, Cody; Wahby, Riad; Bonneau, Joseph; Mazières, David (November 2023, ACM Conference on Computer and Communications Security (CCS))

   Cremers, Cas; Kirda, Engin (Ed.)

   We introduce the first practical protocols for fully decentralized sealed-bid auctions using timed commitments. Timed commitments ensure that the auction is finalized fairly even if all participants drop out after posting bids or if bidders collude to try to learn the bidder’s bid value. Our protocols rely on a novel non-malleable timed commitment scheme which efficiently supports range proofs to establish that bidders have sufficient funds to cover a hidden bid value. This allows us to penalize users who abandon bids for exactly the bid value, while supporting simultaneous bidding in multiple auctions with a shared collateral pool. Our protocols are concretely efficient and we have implemented them in an Ethereum- compatible smart contract which automatically enforces payment and delivery of an auctioned digital asset. 

   more » « less
4. VoteXX: A Solution to Improper Influence in Voter-Verifiable Elections

   Chaum, David; Carback, Richard T.; Clark, Jeremy; Liu, Chao; Nejadgholi, Mahdi; Preneel, Bart; Sherman, Alan T.; Yaksetig, Mario; Zagorski, Filip; Zhang, Bingsheng (October 2022, E-VOTE-ID 2022)

   We solve a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: ``{\it improper influence},'' which typically refers to any combination of vote buying and voter coercion. Our approach allows each voter, or their trusted agents (which we call ``{\it hedgehogs}''), to {\it ``nullify''} (effectively cancel) their vote in a way that is unstoppable, irrevocable, and forever unattributable to the voter. In particular, our approach enhances security of online, remote, public-sector elections, for which there is a growing need and the threat of improper influence is most acute. We introduce the new approach, give detailed cryptographic protocols, show how it can be applied to several voting settings, and describe our implementation. The protocols compose a full voting system, which we call {\it {\votexx}}, including registration, voting, nullification, and tallying---using an anonymous communication system for registration, vote casting, and other communication in the system. We demonstrate how the technique can be applied to known systems, including where ballots can be mailed to voters and voters use codes on the ballot to cast their votes online. In comparison with previous proposals, our system makes fewer assumptions and protects against a strong adversary who learns all of the voter's keys. In {\votexx}, each voter has two public-private key pairs. Without revealing their private keys, each voter registers their public keys with the election authority. Each voter may share their keys with one or more hedgehogs. During nullification, the voter, or one or more of their hedgehogs, can interact through the anonymous communication system to nullify a vote by proving knowledge of one of the voter's private keys via a zero-knowledge proof without revealing the private key. We describe a fully decentralizable implementation of {\votexx}, including its public bulletin board, which could be implemented on a blockchain. 

   more » « less
5. Learning Within an Instance for Designing High-Revenue Combinatorial Auctions

   Balcan, M.-F.; Prasad, S.; Sandholm, T. (January 2021, IJCAI)

   We develop a new framework for designing truth- ful, high-revenue (combinatorial) auctions for limited supply. Our mechanism learns within an instance. It generalizes and improves over previously-studied random-sampling mechanisms. It first samples a participatory group of bidders, then samples several learning groups of bidders from the remaining pool of bidders, learns a high- revenue auction from the learning groups, and fi- nally runs that auction on the participatory group. Previous work on random-sampling mechanisms focused primarily on unlimited supply. Limited supply poses additional significant technical chal- lenges, since allocations of items to bidders must be feasible. We prove guarantees on the performance of our mechanism based on a market-shrinkage term and a new complexity measure we coin par- tition discrepancy. Partition discrepancy simulta- neously measures the intrinsic complexity of the mechanism class and the uniformity of the set of bidders. We then introduce new auction classes that can be parameterized in a way that does not depend on the number of bidders participating, and prove strong guarantees for these classes. We show how our mechanism can be implemented efficiently by leveraging practically-efficient routines for solv- ing winner determination. Finally, we show how to use structural revenue maximization to decide what auction class to use with our framework when there is a constraint on the number of learning groups. 

   more » « less