Round 1 (Additional Signatures) OFFICIAL COMMENT: AIMer Signature Scheme

[김 성광]

Dear all,

 

This is Seongkwang Kim in the AIMer team.

We would like to announce AIM2, an update of our symmetric primitive AIM.

The paper "Mitigation on the AIM cryptanalysis" can be found in our website (https://aimer-signature.org) immediately, and will be submitted to the Cryptology ePrint Archive soon.

We briefly summarize recently known attacks on AIM, and how AIM2 mitigates them.

 

[1] F. Liu, M. Mahzoun, M. Øygarden, and W. Meier. Algebraic Attacks on RAIN and AIM Using Equivalent Representations (https://eprint.iacr.org/2023/1133)

- (Algebraic) fast exhaustive search, giving up to 13-bit security degradation.

- Mitigated by larger exponents of AIM2

[2] F. Liu. Mind Multiple Power Maps: Algebraic Cryptanalysis of Full AIM for Post-quantum Signature Scheme AIMer (In private communication)

- There was an easier system than expected, security claim error (not broken)

[3] M. O. Saarinen. Efficient brute-force key search method (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/BI2ilXblNy0)

- Efficient key search (by implementation), unknown amount of security degradation

- Mitigated by constant addition of AIM2

[4] K. Zhang, Q. Wang, Y. Yu, C. Guo, and H. Cui. Algebraic Attacks on Round-Reduced RAIN and Full AIM-III (https://eprint.iacr.org/2023/1397, to appear Asiacrypt 2023)

- Guess & determine + linearization attack giving up to 6-bit security degradation

- Mitigated by constant addition of AIM2

 

To mitigate all the analyses, AIM2 has three changes from AIM.

1. Inverse Mersenne S-box: the S-box in the first round is placed in the opposite direction. In this way, we can make it harder to build a large number of equations compared to AIM.

2. Constant addition to the inputs of S-box: distinct constants are added to the inputs of first-round S-boxes. It differentiates the inputs of S-boxes with negligible cost.

3. Increasing exponents for S-boxes: we opt for larger exponents for some Mersenne S-boxes in order to make it harder to establish a low-degree system of equations in ≈ λ Boolean variables from a single evaluation of AIM.

 

In the paper, we extensively strengthen algebraic cryptanalysis part as 3 out of 4 analyses are related to the algebraic characteristic.

As we recognized [4] very recently, our paper contains [1, 2, 3], but not [4].

Nevertheless, we found that the constant addition included in our update effectively mitigates the attack in [4].

 

This update does not affect efficiency much.

The signature size will remain same, and signing and verifying time will be slightly increased (expected ~10%).

 

We plan to incorporate AIM2 to AIMer, which will be dubbed AIMer2.

The specification document and implementation results will also be updated.

 

We truly thank all the authors above for pointing out the vulnerabilities of AIM.

Third-party analysis is always welcome!

 

Best regards,

Seongkwang Kim on behalf of the AIMer team

 

Windows용 메일에서 발송된 메일입니다.