Search papers, labs, and topics across Lattice.
This paper explores $K$- and infinite-step anonymity in partially-observed discrete-event systems using non-deterministic finite-state automata, introducing novel definitions for strong and weak anonymity types. The authors leverage a concurrent-composition technique to establish verifiable conditions for these anonymity types, providing a comprehensive complexity analysis. Key findings include the derivation of upper bounds on $K$ for both strong and weak anonymity, enhancing the understanding of privacy guarantees in dynamic systems.
New definitions of strong and weak anonymity reveal critical insights into privacy guarantees in discrete-event systems, challenging existing notions.
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.
