A public key cryptosystem utilizes a hard lattice with O(n log n) random bits for security. The system comprises a public-key cryptosystem whose hardness assumption is a clearly stated mathematical problem with a long history and comprises a short key, reaching a balance between the favorable properties of the hardness assumption and the key size. This balance has not been achieved by previously known public-key cryptosystems. The improved efficiency of the present system is achieved by reducing the size of the public key from O(n2 log n) to O(n log n). The improved security of the system is achieved by reducing the security to the hardness of a clearly stated computational problem, the dipohantine approximation problem of Dirichlet.