Imagine you have a combination lock, and every time you use it, someone nearby hears a slightly garbled version of the clicks. With enough garbled recordings, a patient eavesdropper can statistically reconstruct your combination — not by cracking the lock mechanism, but by averaging away the noise. That's the core mechanism here: Bilinear Compressive Security (BCS) encrypts by multiplying your message with a secret matrix and then convolving with a fresh random filter. The random filter is the garbling. The secret matrix is the combination. This paper asks: how many garbled recordings does the eavesdropper actually need? The committed claim: for the first time, the authors derive finite-sample complexity bounds for key recovery against BCS and show that the answer depends dramatically on the structure of the secret measurement matrix. Dense (e.g., Gaussian) matrices require only O(n) ciphertext observations for recovery — linear in signal dimension. Sparse-row matrices require O(n²) — a qualitatively harder attack. This is not a theoretical curiosity; it directly dictates how many encryptions you can safely perform under key reuse before an adversary can reconstruct your key. The attack itself is elegant and classical in flavor: a covariance-based estimator. The adversary collects repeated encryptions of the same plaintext, estimates the covariance of the ciphertext ensemble, and extracts the linear measurement component. From there, standard compressed sensing recovery algorithms reconstruct the secret matrix. The authors provide rigorous finite-sample guarantees for the covariance estimation step, grounding previously information-theoretic results in operationally meaningful sample-complexity language. The ladder position is interesting. Previous work by Berk et al. established information-theoretic identifiability — the phase-retrieval connection that says key recovery is possible in principle given the full ciphertext distribution. This paper bridges the gap to practice: finite samples, concrete rates, experimentally validated. Against the information-theoretic worst case, the dense-matrix regime is actually easier to attack than theory predicted (linear vs. the theoretical upper bound), while the sparse regime matches the theoretical quadratic bound. This is a genuine advance in understanding, not just a tighter constant. Integrity is mixed. The theoretical analysis (covariance estimation bounds) is rigorous, but the complete attack pipeline — from covariance estimation through matrix recovery — is validated experimentally rather than with end-to-end theoretical guarantees. The experiments are well-designed and the two recovery regimes (linear vs. quadratic) are clearly demonstrated, but there's no independent replication, no pre-registration, and no public benchmark suite for BCS attacks. The paper is honest about the gap between theory and experiment, which earns trust. The practical upshot for anyone designing lightweight encryption for IoT, sensor networks, or compressed sensing pipelines: your key-reuse budget is not a single number. It depends on the sparsity structure of your measurement matrix. Dense matrices give attackers a much easier path. Sparse-row matrices buy you quadratic breathing room. This should inform parameter selection today, not after a follow-up paper. The obvious next experiment the authors didn't run: adversarial robustness under noisy or partially observed ciphertexts, and scaling the attack to realistic dimensions beyond the experimental regime shown. The honest read is that compute and experimental scope limited this round — the theoretical machinery is already in place for extensions, and the authors are likely saving the applied-parameter-selection paper for the next submission.
