Public-key cryptography from different assumptions

This paper constructs new public-key encryption schemes based on new hardness-on-average assumptions for natural combinatorial NP-hard optimization problems, and gets the first noisy-equations type public key scheme in which the noise rate is higher than one over the square root of the number of equations.