On the Computational Complexity of the Secure State-Reconstruction Problem
In this paper, we discuss the computational complexity of reconstructing the state of a linear system from sensor measurements that have been corrupted by an adversary. The first result establishes that the problem is, in general, NP-hard. We then introduce the notion of eigenvalue observability and show that the state can be reconstructed in polynomial time when each eigenvalue is observable by at least $2s+1$ sensors and at most $s$ sensors are corrupted by an adversary. However, there is a gap between eigenvalue observability and the possibility of reconstructing the state despite attacks - this gap has been characterized in the literature by the notion of sparse observability. To better understand this, we show that when the $\mathbf{A}$ matrix of the linear system has unitary geometric multiplicity, the gap disappears, i.e., eigenvalue observability coincides with sparse observability, and there exists a polynomial time algorithm to reconstruct the state provided the state can be reconstructed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Secure Data Reconstruction: A Direct Data-Driven Approach
This paper addresses the problem of secure data reconstruction for unknown systems, where data collected from the system are susceptible to malicious manipulation. We aim to recover the real trajectory without prior know…
State Space ModelsTrajectory RecoveryLightSecAgg: a Lightweight and Versatile Design for Secure Aggregation in Federated Learning
Secure model aggregation is a key component of federated learning (FL) that aims at protecting the privacy of each user's individual model while allowing for their global aggregation. It can be applied to any aggregation…
Federated LearningAstronomical image reconstruction with convolutional neural networks
State of the art methods in astronomical image reconstruction rely on the resolution of a regularized or constrained optimization problem. Solving this problem can be computationally intensive and usually leads to a quad…
AstronomyImage ReconstructionTransmit Antenna Selection and Beamformer Design for Secure Spatial Modulation with rough CSI of Eve
The security of spatial modulation (SM) aided networks can always be improved by reducing the desired link's power at the cost of degrading its bit error ratio performance and assuming the power consumed to artificial no…
Exploring the Security Boundary of Data Reconstruction via Neuron Exclusivity Analysis
Among existing privacy attacks on the gradient of neural networks, \emph{data reconstruction attack}, which reverse engineers the training batch from the gradient, poses a severe threat on the private training data. Desp…
Face RecognitionReconstruction Attack