Umeå universitets logga

This project analyses an encryption scheme based on bilinear compressive sensing. The scheme requires the intended receiver to solve a bilinear problem for each transmitted message, and involves a random filter h with a public distribution and an unknown vector Qx. Here Q serves as the secret key shared between sender and receiver, x carries the message, and y, formed by convolving h with Qx, is the resulting observation sent to the receiver. This work is devoted to studying an eavesdropper's ability to recover Q from intercepted pairs (x, y) by drawing samples of h - a setting that is deliberately favorable to the eavesdropper.

We argue the relevance of the encryption scheme by presenting four recovery algorithms available to the intended receiver. Their respective applicability depends on the dimensionality, concentration of values, and sparsity of h, Q, and x to varying degrees.

Two methods available to a potential eavesdropper are presented and analysed. They rely respectively on estimating the mean and covariance of y by drawing samples of h from its public distribution. The accuracy and performance of these methods reveal potential vulnerabilities in the scheme, and we discuss possible countermeasures to mitigate them.

Our results include parameter configurations under which our methods are not applicable, and a specific construction of the key Q for which the encryption scheme fails entirely. We analyse the behavior of our estimates and show that the error of both methods decay as 1/√r and grows with larger values of the distribution parameters of h. These analytical findings are supported by numerical experiments for two cases, whose results are consistent with our analysis.