UOV and its variants have been submitted to NIST’s PQC Standardization Project. Security analysis against UOV families (i.e., UOV and its variants) are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Ran introduced a novel key-recovery attack against UOV families that could be seen as an XL attack using exterior algebra; nevertheless, this key-recovery attack is applicable only when the underlying field of UOV instances is of characteristic 2. In this work, we address this limitation by generalizing Ran’s approach, and our contributions are three-fold. First, we generalize the notion of exterior algebra and propose the notion of p-reduced symmetric algebra over any field, which is essentially symmetric algebra when the characteristic p of the underlying field is 0 and is exterior algebra when \(p=2\) . Moreover, ased upon the well-studied property of the reduced symmetric algebra, we generalize Ran’s attack from characteristic 2 to fields of any characteristic following essentially the same approach; As a result, our attack applies to all recommended QR-UOV instances submitted to the NIST PQC standardization project. Finally, analysis on these attacks also implies the connection between the characteristic p and the concrete hardness of UOV instances, which is helpful for choosing parameter sets for UOV families.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Security Analysis on UOV Families with Odd Characteristics: Using Symmetric Algebra

  • Yi Jin,
  • Yuansheng Pan,
  • Xiaoou He,
  • Boru Gong,
  • Jintai Ding

摘要

UOV and its variants have been submitted to NIST’s PQC Standardization Project. Security analysis against UOV families (i.e., UOV and its variants) are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Ran introduced a novel key-recovery attack against UOV families that could be seen as an XL attack using exterior algebra; nevertheless, this key-recovery attack is applicable only when the underlying field of UOV instances is of characteristic 2. In this work, we address this limitation by generalizing Ran’s approach, and our contributions are three-fold. First, we generalize the notion of exterior algebra and propose the notion of p-reduced symmetric algebra over any field, which is essentially symmetric algebra when the characteristic p of the underlying field is 0 and is exterior algebra when \(p=2\) . Moreover, ased upon the well-studied property of the reduced symmetric algebra, we generalize Ran’s attack from characteristic 2 to fields of any characteristic following essentially the same approach; As a result, our attack applies to all recommended QR-UOV instances submitted to the NIST PQC standardization project. Finally, analysis on these attacks also implies the connection between the characteristic p and the concrete hardness of UOV instances, which is helpful for choosing parameter sets for UOV families.