TU/e report on KpqC Round 2

[Tanja Lange]

Dear all,
It is our pleasure to announce our report on the evaluation of the round-2
candidates for KpqC. Please see attached. We have also submitted this to eprint
but that typically takes a few days until posting.

All the best
Tanja

[Seongkwang Kim]

Dear TU/e team and all,

I have one point to make a correction on the latest TU/e report.

In Section 8.3.1, there is a new exhaustive search attack on AIM2.
The main approach of the attack is,
1. Construct sparse quadratic equations;
2. Guess common lambda variables to make linear equations;
3. Solve the linear equation and check the correctness.

We want to correct three points on the complexity claim of the attack.
We remark that small constants may be crucial in the complexity of exhaustive attacks.

1. The correct complexity should be 2^lambda * (m-1) * (lambda^w + 2 * lambda^2)
 - This includes the substitution process. In Step 2, an attacker can build a linear equation by substituting guessed variables. Unless specified, this process cannot be a zero cost.
 
2. w=2.37 is not an appropriate choice for lambda = 128, 192, 256.
 - Fast matrix multiplication algorithms such as Strassen's algorithm, or Coppersmith-Winograd algorithm are not faster than Gaussian elimination at small dimension such as lambda <= 256.
 - The hidden choice for Boolean matrix would be Method of 4 Russians, but this has rather large asymptotic complexity O(n^3 / log n).
 - If applying Method of 4 Russians to the attack, the theoretic complexities are smaller than our claim, but by less than 1 bit. These values are still few bits larger than the exhaustive search of AES.

3. Table 8.7 is unfair and not realistic.
 - Cryptanalysis using slow implementation is not realistic. Our keygen (even containing some SHAKE evaluation) ran in Apple M2 Pro is 16x faster than the SageMath implementation in the report.
 - For a fair comparison, we compare the benchmark of inverting a square matrix in M4RI and AIM2 (which is keygen without SHAKE evaluation) in C, and in the same environment (Intel Haswell).
 (cc)   128    192    256
 M4RI  167K   297K   470K
 AIM2   53K    66K    83K

 Best,
 Seongkwang on behalf of the AIMer team

2024년 12월 26일 목요일 오후 2시 13분 36초 UTC+9에 Tanja Lange님이 작성:

[Jonghyun Kim]

Dear TU/e Team and All,

We have reviewed the report on the evaluation of round-2 

and identified flaws in the proof of Lemma 4.3 , as mentioned in the report. 

Instead of relying on the injectiveness (collision resistance) of NTRU,

we are currently updating the security proof (in the ROM and QROM) that leverages

the properties related to the worst-case correctness of CPA-NTRU+

and the uniqueness of randomness in GenNTRU when the public key, ciphertext and message are fixed.

We will update our specification as soon as the revised proof is completed.

Best regards,

NTRU TEAM

2024년 12월 26일 목요일 오후 2시 13분 36초 UTC+9에 Tanja Lange님이 작성:

Dear all,