More Like this

1. Information Design in Spatial Resource Competition

   Yang, Pu; Iyer, Krishnamurthy; Frazier, Peter I. (December 2019, Lecture notes in computer science)

   We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N co-located agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfare-maximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient two-step approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient sampling procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks. 

   more » « less
2. UDM: Private User Discovery with Minimal Information Disclosure

   Chaum, David; Yaksetig, Mario; Sherman, Alan T.; de Ruiter, Joeri (July 2021, Cryptologia)

   We present and analyze UDM, a new protocol for user discovery in anonymous communication systems that minimizes the information disclosed to the system and users. Unlike existing systems, including those based on private set intersection, UDM learns nothing about the contact lists and social graphs of the users, is not vulnerable to off-line dictionary attacks that expose contact lists, does not reveal platform identifiers to users without the owner’s explicit permission, and enjoys low computation and communication complexity. UDM solves the following user-discovery problem. User Alice wishes to communicate with Bob over an anonymous communication system, such as cMix or Tor. Initially, each party knows each other’s public contact identifier (e.g., email address or phone number), but neither knows the other’s private platform identifier in the communication system. If both parties wish to communicate with each other, UDM enables them to establish a shared key and learn each other’s private platform identifier. UDM uses an untrusted user-discovery system, which processes and stores only public information, hashed values, or values encrypted with keys it does not know. Therefore, UDM cannot learn any information about the social graphs of its users. Using the anonymous communication system, each pair of users who wish to communicate with each other uploads to the user-discovery system their private platform identifier, encrypted with their shared key. Indexing their request by a truncated cryptographic hash of their shared key, each user can then download each other’s encrypted private platform identifier. 

   more » « less
3. Privacy-Preserving and Post-Quantum Counter Denial of Service Framework for Wireless Networks

   https://doi.org/10.1109/MILCOM61039.2024.10773665  

   Darzi, Saleh; Yavuz, Attila Altay (October 2024, IEEE)

   As network services progress and mobile and IoT environments expand, numerous security concerns have surfaced for spectrum access systems (SASs). The omnipresent risk of Denial-of-Service (DoS) attacks and raising concerns about user privacy (e.g., location privacy, anonymity) are among such cyber threats. These security and privacy risks increase due to the threat of quantum computers that can compromise longterm security by circumventing conventional cryptosystems and increasing the cost of countermeasures. While some defense mechanisms exist against these threats in isolation, there is a significant gap in the state of the art on a holistic solution against DoS attacks with privacy and anonymity for spectrum management systems, especially when post-quantum (PQ) security is in mind. In this paper, we propose a new cybersecurity framework, PACDoSQ, which is the first to offer location privacy and anonymity for spectrum management with counter DoS and PQ security simultaneously. Our solution introduces the private spectrum bastion concept to exploit existing architectural features of SASs and then synergizes them with multi-server private information retrieval and PQ-secure Tor to guarantee a location-private and anonymous acquisition of spectrum information, together with hash-based client-server puzzles for counter DoS. We prove that PACDoSQ achieves its security objectives and show its feasibility via a comprehensive performance evaluation. 

   more » « less
4. Ultra Lightweight Multiple-time Digital Signature for the Internet of Things Devices

   https://doi.org/10.1109/TSC.2019.2928303  

   Yavuz, Attila Altay; Ozmen, Muslum Ozgur (July 2019, IEEE Transactions on Services Computing)

   Digital signatures are basic cryptographic tools to provide authentication and integrity in the emerging ubiquitous systems in which resource-constrained devices are expected to operate securely and efficiently. However, existing digital signatures might not be fully practical for such resource-constrained devices (e.g., medical implants) that have energy limitations. Some other computationally efficient alternatives (e.g., one-time/multiple-time signatures) may introduce high memory and/or communication overhead due to large private key and signature sizes. In this paper, our contributions are two-fold: First, we develop a new lightweight multiple-time digital signature scheme called Signer Efficient Multiple-time Elliptic Curve Signature (SEMECS), which is suitable for resource-constrained embedded devices. SEMECS achieves optimal signature and private key sizes for an EC-based signature without requiring any EC operation (e.g., EC scalar multiplication or addition) at the signer. We prove SEMECS is secure (in the random oracle model) with a tight security reduction. Second, we fully implemented SEMECS on an 8-bit AVR microprocessor with a comprehensive energy consumption analysis and comparison. Our experiments confirm up to 19× less battery-consumption for SEMECS as compared to its fastest (full-time) counterpart, SchnorrQ, while offering significant performance advantages over its multiple-time counterparts in various fronts. We open-source our implementation for public testing and adoption. 

   more » « less
5. Truthful and Optimal Data Preservation in Base Station-less Sensor Networks: An Integrated Game Theory and Network Flow Approach

   https://doi.org/10.1145/3606263  

   Yu, Yuning; Hsu, Shanglin; Chen, Andre; Chen, Yutian; Tang, Bin (October 2023, ACM Transactions on Sensor Networks)

   We aim to preserve a large amount of data generated insidebase station-less sensor networks(BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:datapreservationproblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit. In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN. 

   more » « less