A question for the hardness of the TMO problem (GCKSign)

[Seongkwang Kim]

Dear authors of GCKSign,

I am writing to you to inquire about Appendix A of your paper, specifically regarding the hardness of the TMO problem. While reviewing your work, I came across a question related to Theorem 3, where TMO is reduced to OW or CR based on the inf-norm of xc^-1.

As I understand it, you claimed that the probability of sampling an invertible c is (1-1/q)^n, which you believe to be high enough. However, I was wondering if this probability may not be high enough given your parameters. For instance, in security level 2, q is approximately 2^54 and n is 256, which means that (1-1/q)^n is approximately 1-2^-46.

If the TMO oracle in the proof outputs a uniformly random c, as you mentioned, I believe the upper bound of the advantage of TMO (in the Thm 3 statement) appears to be added by 2^-46, which is dominant for 128-bit security. (i.e., Adv^TMO <= 2 * Adv^CR + 1 - (1 - q)^n)

I would appreciate it if you could clarify this issue for me, and please let me know if there is any misunderstanding on my part.

Best regards, Seongkwang Kim.

[Joo Woo]

First of all, it is correct that the probability that c is invertible is not high enough according to the paper we submitted.

Therefore, we changed the parameter set satisfying the condition in reference [LS18].

In more detail, we can force any element in the ring with small infinite norm (maximum 2, in our case) to have an inverse in the ring according to Corollary 1.2. in [LS18]  .

Its downside is that we can not split X^n+1 completely into linear factors to follow the parameter requirement in the corollary (which means that we can't use fully splitting NTT anymore).

To maximize a computation efficiency, we would combine the partially-splitting NTT algorithm with a Karatsuba multiplication.

We will update our paper accordingly.

Thank you again for your analysis.

Respectfully,

Joo Woo

Reference: V. Lyubashevsky, and G. Seiler, "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs", Eurocrypt 2018.

2023년 2월 23일 목요일 오후 10시 7분 54초 UTC+9에 Seongkwang Kim님이 작성: