Skip to content

Back to the catalog

eprint.iacr.orgpaper

Key Recovery Against RLCE via the GIJS Distinguisher

Key Recovery Against RLCE via the GIJS Distinguisher is an attack on the RLCE code-based cryptosystem at the w=n-k parameter regime. It shortens the public key at random positions, runs the Ghoshal–Ishai–Jain–Sun distinguisher with each column held out, and finds twin column pairs. A root-finding cascade unmixes three pairs, then Sidelnikov–Shestakov on the k×(k+3) pure matrix recovers the key. The ID-0 (128-bit) parameters fall in 30.5 core-hours, about 3 hours on a laptop.

TL;DR Breaks RLCE ID-0 128-bit keys in about 3 laptop hours by combining the GIJS distinguisher with Sidelnikov–Shestakov.
Open original ↗

Technologies named here

  • RLCE

Techniques named here

  • Ghoshal–Ishai–Jain–Sun distinguisher
  • GIJS distinguisher
  • Public key shortening at random positions
  • Root-finding cascade
  • Sidelnikov–Shestakov attack

Concepts named here

  • Code-based cryptosystem
  • Ghoshal–Ishai–Jain–Sun
  • Key recovery attack
  • Twin column pairs

Related in other