Metraipolis › archive › dc_bf336f100ddf

Bilinear Compressive Security with Finitely Many Samples — arXiv:2610.19898

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.19898
License (as archived): CC0-1.0
Archived: 2026-10-15T14:36:19.452Z
SHA-256 of the archived text: b333f9b6f82a513f887bccb76161eedd5083978979f3376c8a779b791e637e14
Stable URL of this page: https://metraipolis.com/documento/dc_bf336f100ddf

How to cite

Bilinear Compressive Security with Finitely Many Samples — arXiv:2610.19898 — arXiv (en), https://arxiv.org/abs/2610.19898 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bf336f100ddf (Metraipolis archive dc_bf336f100ddf, sha256 b333f9b6f82a513f887bccb76161eedd5083978979f3376c8a779b791e637e14)

BibTeX

@misc{dcbf336f100ddf,
  title = {Bilinear Compressive Security with Finitely Many Samples — arXiv:2610.19898},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19898},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bf336f100ddf; sha256 b333f9b6f82a513f887bccb76161eedd5083978979f3376c8a779b791e637e14},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19898. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Cryptography and Security (cs.CR) ; Information Theory (cs.IT); Signal Processing (eess.SP).
Pagina del lavoro: https://arxiv.org/abs/2610.19898 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:57:05.406Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).