Analysis of REDOG

[Alex Pellegrini]

Dear all,

Marc Vorstermans and I want to share our analysis on REDOG.
We found a simple message recovery attack whose complexity is lower than the
claimed security for each parameter set. We named it "Pad Thai attack".
Our attack transforms a ciphertext and a public key into an alternative
ciphertext, which corresponds to the encryption of the same message under an
alternative public key, *without* added noise.

We start by manipulating the c2 part of a ciphertext and the F matrix of the
public key to build an error-free system of linear equations.
This system needs to be padded with extra equations in order to uniquely solve
for the message. We do that by manipulating the first part of the ciphertext
and the M matrix of the public key.
Once enough equations have been collected, we invert the system and compute the
message.

The attack works for every security level of REDOG with complexity upper-bounded
by the following values:

 sec. level | pad thai cost 
----------------------------------------|
 128           | 87.92              |
-----------------|----------------------|
 192           | 132                 |
 ----------------|----------------------|
 256           | 230.53           |

The attached document contains a detailed explanation of the attack and its
complexity analysis.

All the best,
Alex and Marc