Reduction Principle of Ajtai
Zhiyong Zheng, Kun Tian, Fengxia Liu · Financial Mathematics and Fintech · 2022
Abstract In 1996, the famous scholar Ajtai proposed the reduction principle from the worst case to the average case at the 28th Summer Symposium of the American Computer Society (ACM), named the Ajtai reduction principle [see Ajtai (1996), Ajtai (1999) and Ajtai and Dwork (1997)]. Subsequently, Ajtai and Dwork presented the first lattice-based cryptosystem, which is called the Ajtai-Dwork cryptosystem in the academic circles. The proof of this cryptosystem resisting Shor’s quantum computing is to apply Ajtai reduction principle to transform searching for collision points of the Hash function into the SIS problem, and Ajtai reduction principle proves that the difficulty of solving the SIS problem is polynomially equivalent to the shortest vector problem on lattice. The main purpose of this chapter is to prove the Ajtai reduction principle.