Anonymous Stochastic Routing

DOI10.1287/STSY.2021.0074zbMATH Open1489.90203arXiv1911.08875OpenAlexW3212016815MaRDI QIDQ5084500FDOQ5084500

Authors: Mine Su Erturk, Kuang Xu 

Publication date: 24 June 2022

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: We propose and analyze a recipient-anonymous stochastic routing model to study a fundamental trade-off between anonymity and routing delay. An agent wants to quickly reach a goal vertex in a network through a sequence of routing actions, while an overseeing adversary observes the agent's entire trajectory and tries to identify her goal among those vertices traversed. We are interested in understanding the probability that the adversary can correctly identify the agent's goal (anonymity), as a function of the time it takes the agent to reach it (delay). A key feature of our model is the presence of intrinsic uncertainty in the environment, so that each of the agent's intended steps is subject to random perturbation and thus may not materialize as planned. Using large-network asymptotics, our main results provide near-optimal characterization of the anonymity-delay trade-off under a number of network topologies. Our main technical contributions are centered around a new class of "noise-harnessing" routing strategies that adaptively combine intrinsic uncertainty from the environment with additional artificial randomization to achieve provably efficient obfuscation.

Full work available at URL: https://arxiv.org/abs/1911.08875

Recommendations

• Finding routes in anonymous sensor networks
• Anti-localization anonymous routing for delay tolerant network
• Stochastic selfish routing
• Efficient bidirectional anonymous routing protocol for wireless ad hoc networks
• Stochastic Routing in Ad-Hoc Networks
• An anonymous routing scheme with forward secrecy for mobile ad hoc networks

zbMATH Keywords

predictionrandom walknetworksanonymitystochastic routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Database theory (68P15) Signaling and communication in game theory (91A28)

Cites Work

• Differential Privacy: A Survey of Results
• An Analysis of Stochastic Shortest Path Problems
• The algorithmic foundations of differential privacy
• Routing optimization under uncertainty
• Robust adaptive routing under uncertainty
• A note on the stochastic shortest-route problem
• To reveal or not to reveal: privacy preferences and economic frictions
• Infection Spreading and Source Identification: A Hide and Seek Game
• Perception games and privacy
• The empirical implications of privacy-aware choice
• Delay-predictability trade-offs in reaching a secret goal
• Privacy-Preserving Public Information for Sequential Games

Cited In (7)

• Anonymous Networking Amidst Eavesdroppers
• Anti-localization anonymous routing for delay tolerant network
• Title not available (Why is that?)
• Delay-predictability trade-offs in reaching a secret goal
• A Model of Onion Routing with Provable Anonymity
• Non-interactive anonymous router
• The anonymous subgraph problem

This page was built for publication: Anonymous Stochastic Routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084500)