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.

To better leverage the massive data obtained by Internet of Things (IoT) devices, an increasing number of IoT applications are choosing to outsource data to the cloud. However, outsourcing services may cause the issue of privacy leakage. Fuzzy keyword searchable encryption is a desirable tool to provide flexible searching functionality while maintaining the privacy of data. Such schemes consist of two essential components: the underlying match algorithm, such as the fuzzy dictionary, locality-sensitive hashing, and bloom filter, and the privacy preserving mechanism, including symmetric encryption, asymmetric encryption, etc. However, most fuzzy keyword search schemes hardly balance accuracy, efficiency, and multiuser simultaneously. We construct a verifiable multiuser fuzzy search system for cloud-assisted IoT scenarios. Our contribution is twofold. First, we propose a novel vector sum range decision (VSRD) fuzzy search technique with high accuracy, which is of independent interest. Second, to ensure privacy and efficiency, we combine VSRD and Shamir’s threshold scheme to design a verifiable multiuser fuzzy keyword search (MFKS) distributed system, which supports dynamic update. Extensive analyses and experiments demonstrate that our MFKS system resists inside keyword guessing attacks and enjoys high accuracy and efficiency.

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon (GRS) codes is proved to be co-NP-complete by Guruswami and Vardy. For the extended Reed-Solomon codes RSq(Fq, k), a conjecture was made to classify deep holes by Cheng and Murray. Since then efforts have been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for GRS codes RSp(D, k), where p is a prime, |D| > k ≥ (p - 1)/2. Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös-Heilbronn conjecture.