Design And Security Provement Of Public Key Cryptosystems Based On Hard Problems In Lattice

The speeds of traditional public-key cryptosystems based on large integer factor-ization and discrete logarithm problems are relatively low, which hampers their furtherapplications. With the development of quantum computation, the design of cryptosystembased on new hard problems but not traditional number theoretic ones is more importantthan ever. Public key cryptosystems based on hard problems in lattice are importantdirection. We research on that and obtain the following main results.(1) We make a rule to choose parameters for NTRU: n,p,q should satisfy that thecyclotomic polynomials is irreducible over GF(p) and GF(q). Then anypolynomial in the ring R = Z[x]/(x~n-1) satisfying f(1) = 0has an inverse in a sense of modular p or q. This rule could ensure the speed of keygeneration and avoid weak keys.(2) If the degree of the greatest common divisor of NTRU public key h and (x~n - 1)is greater than zero, we can design an algorithm to break NTRU by the decod-ing technique of cyclic code and lattice reduction algorithm. When the order ofgcd is k > 0, the attacker could recover the plaintext by solve the SVPproblem of lattice with dimension no more than (n - k).(3) When the attacker could obtain the random string of OAEP 3-Round, it would notbe indistinguishable against adaptive chosen ciphertext attacks any more. Examplesare given to support this argument. We improve OAEP 3-Round padding schemeto be plaintext awareness and prove that the revised version is semantic securityagainst adaptive chosen ciphertext attacks in the random oracle model even in thecase that attacker could get the random string of the padding scheme.(4) We design an encryption padding, called EPN, for NTRU. Under the full domain onewayness assumption of NTRU, EPN can been proved to be indistinguishable fromadaptive chosen ciphertext attack by using the Game-Hopping technology in therandom oracle model. Compared with NAEP, EPN is simpler and more convenientfor implementation.(5) A revised version of the NTRU cryptosystem, R-NTRU, is presented. Comparedwith NTRU, for which all vectors short enough in the CS lattice could be used todecrypt, R-NTRU possesses more attractive character that only the prime privatekey can decrypt ciphertexts. In other words, lattice reduction algorithms, whichperform good in search short vectors of a lattice, could not threaten the security of SLH directly at the cost of large key size and slow speed. We propose a paddingscheme for R-NTRU and prove that it is indistinguishable against adaptive chosenciphertext attack under the full domain one wayness assumption of encrypt functionin the random oracle model.