Research On Three Average-Case Hard Problems

Almost all recent lattice-based cryptosystems are directly based on two average-case problems:Smallest Integer Solution(SIS)problem and Learning With Errors(L-WE)problem.Although there are many exponential algorithms solving these two prob-lems,it is still ambiguous to estimate the hardness in practical applications,as well as to set security parameters in encryption primitives.Besides,average-case hardness theory has been studied for many years.The class distNP is the average-case analog of NP,and has complete problems.Livne has given the strongest result that all natural NP-complete problems have average-case complete versions.However,the distribution is not uniform,or even not natural.The three problems considered in this paper are algo-rithms to solve SIS problem and LWE problem,and constructing an average-case hard version of Satisfiability(SAT)problem.Our work includes the following three aspects:1.Proposing an algorithm which solves SIS problem and another algorithm which solves LWE problem,and giving experimental results with instances from Darm-stadt Lattice Challenge and Darmstadt LWE Challenge.The results demonstrate the feasibility and efficiency of these algorithms.2.Proposing a method to transform SIS problem instances and LWE problem in-stances into SAT problem instances.3.Constructing an average-case hard version of SAT problem,and giving a general form of the construction,as well as a random version of the construction.