Tighter bound for generalized multiple discrete logarithm problem via MDS matrix method

Discrete logarithm problem (DLP) is one of the fundamental hard problems used in cryptography. For 1 ≤ k ≤ n , solving the k -out-of- n DLP instances is an important problem emerging in certain scenarios in public-key cryptography. Ying and Kunihiro (ACNS 2017) pioneered in studying k -out-of- n instance solutions of DLP, which is a generalized version of multiple DLP. By reducing the multiple DLP to the generalized version, they established lower bounds on the computational complexity of k -out-of- n DLP for different parameter values of k . In this paper, we further reduce the reduction complexity presented in Ying and Kunihiro's work and increase the range of k and n for the tight lower bound of k -out-of- n DLP in the generic group model, which has applications in related cryptographic schemes. To achieve the goal, the key technique is to utilize a variant of fast multipoint evaluation. We divide the discussion into two cases. In the special case when n divides p − 1 , by leveraging Number Theory Transform (NTT) technique, we expand k and n to a larger range. In the general case, by using a variant of fast multipoint evaluation, we increase k and n to a moderately larger range. • The complexity of reducing the k-MDL problem to the (k, n)-GMDL problem has been effectively lowered. • The range of parameters when (k, n)-GMDL problem achieves the tight complexity bound is expanded. • The main techniques are a variant of Number Theory Transform and a variant of fast multipoint evaluation.