No Arabic abstract
Truthful spectrum auctions have been extensively studied in recent years. Truthfulness makes bidders bid their true valuations, simplifying greatly the analysis of auctions. However, revealing ones true valuation causes severe privacy disclosure to the auctioneer and other bidders. To make things worse, previous work on secure spectrum auctions does not provide adequate security. In this paper, based on TRUST, we propose PS-TRUST, a provably secure solution for truthful double spectrum auctions. Besides maintaining the properties of truthfulness and special spectrum reuse of TRUST, PS-TRUST achieves provable security against semi-honest adversaries in the sense of cryptography. Specifically, PS-TRUST reveals nothing about the bids to anyone in the auction, except the auction result. To the best of our knowledge, PS-TRUST is the first provably secure solution for spectrum auctions. Furthermore, experimental results show that the computation and communication overhead of PS-TRUST is modest, and its practical applications are feasible.
We design a framework for truthful double multi-channel spectrum auctions where each seller (or buyer) can sell (or buy) multiple spectrum channels based on their individual needs. Open, market-based spectrum trading motivates existing spectrum owners (as sellers) to lease their selected idle spectrum channels to new spectrum users (as buyers) who need the spectrum desperately. The most significant requirement is how to make the auction economic-robust (truthful in particular) while enabling spectrum reuse to improve spectrum utilization. Additionally, in practice, both sellers and buyers would require to trade multiple channels at one time, while guaranteeing their individual profitability. Unfortunately, none of the existing designs can meet all these requirements simultaneously. We address these requirements by proposing True-MCSA, a framework for truthful double multi-channel spectrum auctions. True-MCSA takes as input any reusability-driven spectrum allocation algorithm, introduces novel virtual buyer group (VBG) splitting and bidding algorithms, and applies a winner determination and pricing mechanism to achieve truthfulness and other economic properties while improving spectrum utilization and successfully dealing with multi-channel requests from both buyers and sellers. Our results show that the auction efficiency is impacted by the economic factors with efficiency degradations within 30%, under different experimental settings. Furthermore, the experimental results indicate that we can improve the auction efficiency by choosing a proper bidding algorithm and using a base bid. True-MCSA makes an important contribution on enabling spectrum reuse to improve auction efficiency in multi-channel cases.
We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.
Micropayment channels are the most prominent solution to the limitation on transaction throughput in current blockchain systems. However, in practice channels are risky because participants have to be online constantly to avoid fraud, and inefficient because participants have to open multiple channels and lock funds in them. To address the security issue, we propose a novel mechanism that involves watchtowers incentivized to watch the channels and reveal a fraud. Our protocol does not require participants to be online constantly watching the blockchain. The protocol is secure, incentive compatible and lightweight in communication. Furthermore, we present an adaptation of our protocol implementable on the Lightning protocol. Towards efficiency, we examine specific topological structures in the blockchain transaction graph and generalize the construction of channels to enable topologies better suited to specific real-world needs. In these cases, our construction reduces the required amount of signatures for a transaction and the total amount of locked funds in the system.
JUBILEE is a securely computed mechanism for debt relief and forgiveness in a frictionless manner without involving trusted third parties, leading to more harmonious debt settlements by incentivising the parties to truthfully reveal their private information. JUBILEE improves over all previous methods: - individually rational, incentive-compatible, truthful/strategy-proof, ex-post efficient, optimal mechanism for debt relief and forgiveness with private information - by the novel introduction of secure computation techniques to debt relief, the blessing of the debtor is hereby granted for the first time: debt settlements with higher expected profits and a higher probability of success than without using secure computation A simple and practical implementation is included for The Secure Spreadsheet. Another implementation is realised using Raziel smart contracts on a blockchain with Pravuil consensus.
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $exp(Omega(varepsilon^2 cdot m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [2009] is already known to achieve a $frac{3}{4}$-approximation in $poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation requires communication $exp(Omega(varepsilon^2 cdot m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).