Trapdoor Hash Functions From LPN Assumption And Their Security Analysis

At CRYPTO 2019,Dottling et al.proposed a cryptographic protocol called trapdoor hash function,which has broad applications in secure computation and noninteractive zero-knowledge fields.By using number-theoretic assumptions such as Decision Diffie-Hellman,Quadratic Residuosity,or Decisional Composite Residuosity,or using the Learning with Errors assumption,they demonstrated how to construct trapdoor hash functions.However,only the Learning with Errors assumption is considered to be resistant to attacks by quantum algorithms.Therefore,to enhance the security of trapdoor hash functions in a quantum computing environment,it is necessary and meaningful to use other reliable post-quantum assumptions to construct trapdoor hash functions,such as the hard assumption in the coding field,the Learning Parity with Noise(LPN)assumption.The main research contributions of this thesis are as follows:Firstly,this thesis proposes a trapdoor hash function construction scheme based on the LPN assumption.Our work is inspired by the construction scheme of collisionresistant hash functions based on the LPN assumption.Roughly speaking,we find a way to set up a trapdoor for random linear mappings on F2q→F2n(q>n),to recover one bit of information from the input.The trapdoor hash function based on the LPN assumption leads to many secure computation protocols which are more secure and efficient directly implied by the LPN assumption,such as the oblivious transfer protocol with download rate 1,and it was not known before whether these protocols could be implied by the LPN assumption.Secondly,we also study the solving algorithms of LPN problem to comprehensively examine the hardness of the LPN problem in the real word.Prior to solving LPN,it is necessary to perform a reduction operation to transform the instance into a shorter secret length instance.This thesis proposes a new hybrid reduction algorithm,which combines the classical techniques of the drop reduction and covering code reduction.This reduction process drops LPN samples that have a distance greater than a given threshold from the closest codeword instead of approximating all the samples to the closest codeword,to achieve a trade-off between sample complexity and time complexity.From an algorithmic point of view,the drop reduction and covering code reduction can be considered as special cases of hybrid reduction.We also use the WellPooled Gauss algorithm to solve the LPN samples after hybrid reduction and provide its complete theoretical complexity.The results of numerical estimation show that hybrid reduction can further reduce the sample complexity of the Well-Pooled Gauss algorithm,but at the cost of increased time overhead.