Nuit Blanche: A small Q&A with Valerio Cambareri

Tuesday, July 16, 2013

A small Q&A with Valerio Cambareri

While reading the previous paper, I was bothered by something and asked Valerio Cambareri, one of the author and long time reader of the blog, the following question:

Hello Valerio,

First of all, I am far from being a specialist... Here is something I don't understand. Given a certain number of measurements.information is preserved through the matrix multiplication A. In other words, irrespective of matrix A, given enough measurement y, one can build a manifold that corresponds to the initial manifold of the initial data. Wouldn't be enough to do a good job for cracking future correspondences by Eve ? Not being a specialist I wonder if the passage of time like in the ECG example, you are not likely to improve the code breaking over time ?

Could you enlighten me on this ?

Valerio kindly responded with:

Dear Igor,

(1) the code can definitely be broken if the matrix A remains the same. As an example, let y = Ax with x collecting n instances (i.e., messages, plaintexts) of an n dimensional vector and y collecting the resulting n projections (i.e. cryptograms, ciphertexts) where A_j a single row of a random sign matrix (i.e. a symmetric Bernoulli random vector), then breaking the code just takes a matrix inversion (with A_j the unknown) which succeeds providing there is no noise on y.

The point is A is never the same twice for any pair of message x and ciphertext y since it is generated by a cryptographically secure pseudorandom number generator with a very long period (Mersenne Twister itself has an astronomical period of 2^(19937) symbols, and while not cryptographically robust it can be secured, see CryptMT).

In a cryptographic sense (but pointing out that "multiclass" CS has no ambition of being cryptographically robust, it is just meant to provide basic, zero-cost data hiding in CS), considering the measurement matrix A deterministic or recurrent is equivalent to considering that the encryption key is not random, a hypothesis which might disturb even true cryptosystems.

(2) ECG signals definitely show some periodicity, but this is broken by the fact that A is never the same twice provided that the PRNG is reliable (as you can see much of the system security is moved to the PRNG, which has a pretty long literature and is a basic building block for any cryptographic scheme). Attacks upgrading existing solutions with more priors (e.g. on the statistical properties of the signal) might exist, but they will probably be more complex or less accurate than "buying" the first-class user key.

Thank you for your questions!