Analyzing Improved Cryptanalysis of UOV and Rainbow Signature Algorithms

In this detailed study, the cryptanalysis of UOV and Rainbow signature algorithms by Ward Beullens is explored, focusing on key recovery attacks and the trapdoor structures of Oil & Vinegar and Rainbow schemes. The research highlights the complexities involved in deciphering these multivariate quadratic map-based signatures and introduces new attack methods such as the Intersection Attack.

• Cryptanalysis
• Multivariate Signatures
• Trapdoor Structures
• UOV
• Rainbow

bstev Follow

Uploaded on Oct 09, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Improved cryptanalysis of UOV and Rainbow Ward Beullens imec-COSIC, KU Leuven, Belgium

2. Two multivariate signature algorithms: Rainbow Oil & Vinegar 1997, Patarin Cryptanalysis in 1998/1999, no real improvements since then. (until now) E.g., 89 byte signatures, 60 KB public keys. 2005, Ding and Schmidt Based on Oil and vinegar, multiple layers of OV stacked together. More complicated cryptanalysis. E.g., 71 byte signatures, 60 KB public key. NIST PQC finalist Two Contributions: Simplified exposition of Oil & Vinegar and Rainbow New key recovery attacks.

3. Oil and Vinegar & Rainbow Trapdoor-based signatures using multivariate quadratic maps: ? ?? ?looks random. Public key: ? ? :?? Secret key: some information that allows to compute preimages for ?. Signature: ? such that ? ? = ?(?), where ? ? ?? ?is hash digest. How to trapdoor ? ?

4. Rainbow structure?

5. The Oil and Vinegar Trapdoor ?of dimension ? such that ? ? ? ? = 0 Trapdoor is a linear subspace ? ?? ? ?? ? ?? ? ? . 0

6. The Oil and Vinegar Trapdoor ?of dimension ? such that ? ? ? ? = 0 Trapdoor is a linear subspace ? ?? How to use the trapdoor to solve for ? such that ? ? = ?? 1) Pick ? ?? 2) Solve for ? ?, such that ? ? + ? = ?. This is easy, because ?at random. ? ? + ? = ? ? + ? ? + ? ?,? = ? is a system of ? linear equations in ? variables. If no solution goto 1) 3) Output ? = ? + ?.

7. The Rainbow Trapdoor ?and subspaces ?? ?? ?, ? ?? ? ? ?? ?, ? ? ??:? ?,? ??+1 ?of dimension ? such that Trapdoor is a chain of subspaces ?? ?? ? ?? ? ?? ? ?1 ?1 ?? . 0

8. The Rainbow Trapdoor ?and subspaces ?? ?? ?, ? ?? ? ? ?? ?, ? ? ??:? ?,? ?? 1 ?of dimension ? such that Trapdoor is a chain of subspaces ?? ?? ? ?? ? ?? ? ? ?? ? (?, ) ?1 ?1 ?? . 0

9. Intersection Attack New attack against UOV and Rainbow Rectangular MinRank Attack Attack against Rainbow (See video/paper)

10. Application to NIST parameters More efficient attacks for all the parameter sets submitted to NIST PQC. Security of NIST submission reduced by: 20 bits for SL I 40 bits for SL III 55 bits for SL V

11. Conclusion 1) New exposition of Oil and Vinegar and Rainbow 2) Two new attacks Intersection attack on O&V and Rainbow (See video or paper) New Minrank attack on Rainbow Reduces security of NIST parameters by 20 bits (SL 1), 40 bits (SL 3) and 55 bits (SL 5) Questions?