New hybrid attack on RYDE round 2

[Hugo Sauerbier Couvée]

Dear all,

We wanted to inform you that we seem to have a new technique to attack the rank syndrome decoding problem, that is used in the RYDE signature scheme.

We are using a hybrid attack with the MaxMinors modeling [1]  in combinations with a new guessing step to reduce the parameters and reach the overdetermined case where MaxMinors can be applied. 

The guessing step consists in choosing a random subspace R in F_q^n  of dimension a’ and appending a basis for R as rows to the parity-check matrix H. Additionally, we append a’ zeros below the syndrome. This new technique has a similar success probability to the guessing of a zeros in e: it succeeds as soon as the row support of e is contained in the dual of R.

However, compared to the hybrid technique in [1] where the length n and dimension k are reduced to (n-a) and (k-a) respectively, in our new technique we only reduce k to (k-a').  Although this gives us a larger reduced instance than with the technique from [1],  in general we need much fewer guesses  a'  to reach the overdetermined condition. In total this turns out to be beneficial as we replace the exponential factor  q^{a r} with the much smaller q^{a' r}, with on average a‘ = a/2 for RYDE parameters.

This leads to a security reduction for all the RYDE round 2 parameters.

For RYDE-1 the attack requires 104 bits, for RYDE-3 we require 153 bits and for RYDE-5 we need 210 bits.

We also noted that the security reduction is less severe for the RYDE round 1 parameters.

You can find our paper on eprint here: https://eprint.iacr.org/2025/1303  and we have informed the RYDE team.

Best,

Hugo, Antonia, Violetta

[1] Bardet, M. et al. (2020). Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. In: Moriai, S., Wang, H. (eds) Advances in Cryptology – ASIACRYPT 2020. ASIACRYPT 2020. Lecture Notes in Computer Science(), vol 12491. Springer, Cham. 

[Hugo Sauerbier Couvée]

Dear all,

We have been in contact with the RYDE team regarding a heuristic on the rank of the algebraic system that our new hybrid attack relied on.

We came to the conclusion that this heuristic needs to be updated and a new non-negligible success probability needs to be introduced.

We are still working out what this success probability is, and thus we cannot currently provide sufficient evidence for our previously claimed attack costs. 

With the current understanding on attacks on RYDE and the rank syndrome decoding problem, the parameters of RYDE round 2 are still secure.

Best,

Hugo, Violetta, Antonia

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Hugo Sauerbier Couvée <hugo.sauer...@tum.de>
Sent: 19 July 2025 10:24:52
To: pqc-...@list.nist.gov
Cc: Antonia Wachter-Zeh; Violetta Weger
Subject: [pqc-forum] New hybrid attack on RYDE round 2

 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/c541ed525fc24e7dabe8bca32c47821d%40tum.de.