Bilinear compressive security’s key recovery depends on matrix sparsity
Bilinear Compressive Security with Finitely Many Samples
Cryptography and SecurityInformation Theory
Summary
This paper studies how secure a data encryption method called Bilinear Compressive Security (BCS) is when an attacker sees only a limited number of encrypted samples. The researchers found a way to attack and recover the secret keys by analyzing repeated encryptions. They show that the success of the attack depends heavily on the structure of the secret matrix used in encryption: if the matrix is dense, keys are easier to recover with fewer samples, while for sparse matrices, more data is needed. This suggests that choosing a sparse matrix can make BCS more secure against such attacks.
What this means in practice
- •For security system designers: Select measurement matrices with sparsity to improve resistance against key recovery when using BCS encryption with limited samples.
- •For signal processing engineers: Use insights on measurement matrix structure to design BCS systems balancing security and efficiency based on expected attack sample sizes.
Authors
Axel Flinth, Semira Einsele, Matilda Kylberg, Hubert Orlicki, Gerhard Wunder
Abstract
Bilinear Compressive Security (BCS) is a lightweight encryption scheme that combines compressed sensing with a fresh random convolution filter to improve resistance against key-recovery attacks under key reuse. Previous work derived information-theoretic guarantees for BCS by relating key identifiability to phase retrieval under the assumption that an adversary has access to the full ciphertext distribution induced by the random filter. In practice, however, an adversary only observes finitely many encryptions, leaving the security of BCS in the finite-sample regime largely unexplored. In this paper, we study key recovery from only finitely many observations. We first develop a covariance-based attack that estimates the linear measurements from repeated encryptions of the same plaintext and subsequently recovers the secret measurement matrix. We analyze the estimation procedure and derive finite-sample guarantees together with corresponding sample-complexity bounds. We further investigate the complete attack experimentally and compare its observed recovery behavior with the previously established information-theoretic identifiability results. Our experiments show two qualitatively different recovery regimes on the structure of the measurement matrix. For dense matrices, including Gaussian matrices, the number of measurements required for successful recovery appears to grow linearly with the signal dimension. This differs from the worst-case behavior suggested by information theory. In contrast, for matrices with sparse rows, we observe a quadratic growth consistent with the theoretical bound. These results suggest that the sparsity structure of the measurement matrix plays an important role in the security of BCS and should be taken into account when selecting parameters and designing practical instances of the scheme.