CS Paper Radar

Verification of $K$- and Infinite-Step Strong/Weak Anonymity Using Concurrent Compositions

Jiahui Zhang, Kuize Zhang, Xiaoguang Han, Zhiwu Li

cs.FL cs.CR ·submitted 2026-09-01 13:03 UTC · v1

Abstract

Anonymity is an information flow property that provides privacy protection in the sense of non-uniqueness of system information at certain moments with respect to observations. The notion of $K$-step anonymity in the context of discrete-event systems characterizes the scenario that the state estimates cannot be a singleton within at most $K$ observational steps prior to the current instant, while infinite-step anonymity is the same as $K$-step anonymity without considering the limit on $K$. In this paper, we lucubrate $K$- and infinite-step anonymity for partially-observed discrete-event systems modeled by non-deterministic finite-state automata. First, we define two strong types and two weak types of $K$- and infinite-step anonymity that are fundamentally different from the existing notions of $K$- and infinite-step anonymity due to the consideration of strong and weak anonymous projections. Then, we develop a new methodology by exploiting the concurrent-composition technique to verify these four types of anonymity. Based on the constructed concurrent compositions, verifiable necessary and sufficient conditions for the four types of anonymity are provided, along with their complexity analysis. Finally, the upper bounds on $K$ for $K$-step strong anonymity and weak anonymity are computed.

Closest papers

Nearest neighbours by meaning across the whole index.

Existential Opacity for Discrete-Event Systems with State Observations

eess.SY ·2026-09-02 ·Zhiyuan Huang, Zhao Tong, Jiakai Li, Bingzhuo Zhong
similarity 0.65
Abstract

Opacity is a fundamental system property for confidentiality in discrete-event systems (DES). Classical opacity is typically defined under event-based observations, requiring that any secret system behavior remains indistinguishable from some non-secret behavior to an external intruder. However, in many applications such as path planning or opacity-preserving tasks, the intruder observes system states rather than events. Moreover, it often suffices that the system exhibits secret behaviors that can be exploited for opacity-preserving task execution, but such a system property cannot be fully captured by existing notions of state-observation-based opacity. Motivated by this limitation, we propose a relaxed notion of existing state-observation-based opacity, called existential opacity (EO), which only requires the existence of secret behaviors (instead of all secret behaviors) that are indistinguishable from a non-secret behavior under the state observations of the intruder. We show that the notion of EO is more expressive than existing state-observation-based opacity notions. In addition, a class of EO properties together with their corresponding verification approaches are developed, enabling the analysis of existential opacity in discrete-event systems and providing a new criterion for determining the feasibility of opacity-preserving problems.

0.21

Constant-Coin Complete-Information Debates for $\mathsf{P}$ with Arbitrarily Small Strong Error

cs.CC cs.FL ·2026-09-21 ·M. Utkan Gezer
similarity 0.62
Abstract · 11 pages

We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz showed that every language in $\mathsf{P}$ has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.

0.34

Opacity of Discrete Event Systems under Sensor Attacks

eess.SY ·2026-11-09 ·Shengbao Zheng, Yu Liu, Shaolong Shu, Feng Lin
similarity 0.61
Abstract

Many information control problems in discrete event systems can be addressed using strong opacity, weak opacity, and non-opacity. These opacities depend on observations. If cyber attackers can attack sensors (or observation channels), then opacities will change. An opaque system may become not opaque, or a not opaque system may become opaque. Therefore, it is important to investigate opacities under sensor attacks. In this paper, we consider opacities under sensor attacks for two settings. The first one is the user has prior knowledge of sensor attacks in which the opacities are called as W-CA-opacities. The second one is the user has no prior knowledge of sensor attacks, and opacities are called as N-CA-opacities. For the former, we construct an augmented automaton that integrates the information of sensor attacks and then converts W-CA-opacities into classical opacities to solve the verification problem. For the latter, we construct the observers for the given system without sensor attacks and with sensor attacks, respectively. We then do the parallel operation on these two observers to obtain a method of verifying N-CA opacities. Furthermore, by adopting the detector technique, we find polynomial algorithms for verifying weak opacity and non opacity for both settings.

0.14

I Prove, Therefore I Am: Spatiotemporal Multi-Party Computation

cs.CR quant-ph ·2026-09-22 ·Ziqing Guo, Fuyuki Kitagawa, Xiao Liang
similarity 0.61
Abstract · 50 pages

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of spatiotemporal MPC, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce arguments of spatiotemporal knowledge, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove of spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to support quantum functionalities with classical spatiotemporal input.

0.31

CA-Observability of Discrete Event Systems under Cyber Attacks

eess.SY ·2026-10-06 ·Shengbao Zheng, Shaolong Shu, Feng Lin
theory similarity 0.60
Abstract

In a previous paper, we investigate the control problem of discrete event systems under cyber attacks, where CA-controllability and CA-observability are proposed. We prove that a discrete event system can be controlled to generate a specification language K if and only if K is CA-controllable and CA-observable. While CA controllability can be "converted" to (conventional) controllability, CA-observability cannot be "converted" to (conventional) observability. In this paper, we further investigate CA-observability. We develop a method and an algorithm to check CA-observability. The method involves constructing an augmented automaton whose states are pairs of the current state and state estimate of the supervised system. We prove that K is CA-observable if and only if the language generated by the augmented automaton is equal to K. An algorithm is then developed to check CA-observability. We also investigate the properties of CA-observability. We show that CA-observability is not closed under (set) in tersection. Note that (conventional) observability is closed under intersection. We further show that CA-observability is not closed under union. This is similar to observability. If K is not CA-controllable and CA-observable, we pro pose a method to calculate a CA-controllable and CA observable sublanguage. We first calculate the supremal CA-controllable sublanguage for K which can be described by a sub-automaton of the automaton for K. We then propose a state-estimate-based supervisor based on the subautomaton, which ensures the supervised system stays within K.

0.23

Provable Mixing Properties of Parallel Mixnets Revisited

cs.CR ·2026-11-17 ·Pierfrancesco Ingo, Peter Druschel, Deepak Garg
similarity 0.56
Abstract · 16 pages, 3 figures, 2 pages of appendix

A mix-network (mixnet) is a routing network that breaks source-to-destination message trackability by indistinguishably mixing the routes of concurrently transmitted messages, thus providing anonymity to senders, receivers and sender-receiver pairs. Given their potential use in high-stakes scenarios like protecting whistleblowers, one would like to prove formally that sender anonymity holds in a mixnet, even against strong adversaries that can compromise subsets of mixnet servers. However, existing work on anonymity in mixnets is either limited to linear mixnets (which do not scale horizontally), relies on special provisions such as additional noise or chaff messages, or is empirical -- typically based on entropy, which does not provide strong guarantees if the adversary has auxiliary information. In this paper, we present a new analysis of parallel mixnets which scale horizontally, showing that these networks can provide strong indistinguishability for messages even without additional noise messages. Our analysis works by bounding the statistical variance of the adversary's posterior likelihood of where a message of interest is at a given point in time. Using concentration bounds on this distribution, we show that parallel mixnets satisfy $(\varepsilon, δ)$-differential indistinguishability for messages routed through the mixnet (similar to $(\varepsilon, δ)$-differential privacy) with very small failure probabilities $δ$ and small privacy parameters $\varepsilon$ under reasonable operating conditions. Our model also enables an examination of the quantitative trade-off between anonymity, latency and per-router bandwidth in parallel mixnets.

0.35

Symmetry Breaking over Multiway Channels

cs.IT ·2026-11-06 ·Raymond Zhang, Richard Combes, Sheng Yang
similarity 0.56
Abstract · Submitted to TIT

Identical users running the same algorithm must often break their symmetry and agree on distinct roles, as in leader election, naming, and resource allocation. We study anonymous symmetry breaking over a discrete memoryless multiway channel invariant under permutations of its $J$ users: each user observes only a private output and must choose a number in $\{1,\dots,J\}$, and the symmetry is broken if the $J$ numbers are distinct. Using a Rényi change of measure, we derive a finite-blocklength converse on the error probability of every symmetric causal protocol, including adaptive and randomized ones. For achievability, block coding with random names reduces the problem to all-source multicast, for which we derive a Gallager random-coding exponent for every fixed $J$, and a cut-set bound that limits the exponent of the probability that two names coincide or are decoded wrongly. Interactive role controllers instead let the users contend for identifiers directly: we give their exact error probability, an achievable exponent given by a spectral radius when some outputs certify a role, and a floor for finite-state controllers when every output has positive probability, and we introduce generalized musical chairs. On a noisy bandit channel motivated by multiplayer multi-armed bandits, with noiseless collisions and arms of a common mean below one, interactive schemes provably exceed the limit of name decoding, and numerical estimates suggest the same with noisy collisions. For two users, noiseless collisions, one informative arm and a silent arm, the optimal error probability is determined up to a factor of two.

0.21

The Anonymity Gap: Understanding Real Privacy in Shielded UTXO-based Protocols for DeFi

cs.CR ·2026-08-24 ·Hanze Guo, Stefanos Chaliasos, Yebo Feng, Jiahua Xu
similarity 0.56
Abstract

Shielded UTXO-based protocols are becoming a core form of privacy infrastructure for DeFi. Unlike mixers that organize privacy mainly around deposits and withdrawals, these protocols allow assets, once inside the shielded pool, to continue moving and being re-spent within the hidden state, and to become public only when users withdraw or interact with public DeFi protocols. Their anonymity is therefore no longer a flat pool-size problem, but a provenance problem that propagates across the note/UTXO, proof, and transaction layers. Yet, a unified analysis framework for this setting is still missing. We propose a layered system model and an analysis pipeline that uses prior history as the temporal baseline, applies cumulative pruning and cross-proof propagation to each proof's Commitment Set, and recursively traces the survivors through historical hidden-state transitions to derive the final transaction-level Anonymity Set Size. We evaluate our methodology on the complete on-chain histories of all four Railgun production deployments and five independent Hinkal pools across six EVM chains, analyzing 186,356 unshielding spend transactions. Using only public protocol traces and constraints, our non-heuristic analysis yields mean Anonymity Set Size reductions of 40.1%-59.0% relative to each deployment's temporal baseline; 3,679 transactions retain at most 10 addresses, including 1,228 singletons. Public token constraints are the strongest and most stable source of pruning in both protocols, while the effects of tree number, proof roots, and value constraints vary with protocol design and historical state. Together with representative cases, these results reveal interpretable anonymity-loss patterns and implications for user behavior and future protocol design.

0.18