Tensor-Based Trapdoors for CVP and Their Application to Public Key Cryptography

Abstract

. We propose two trapdoors for the Closest-Vector-Problem in lattices (CVP) related to the lattice tensor product. Using these trapdoors we set up a lattice-based cryptosystem which resembles to the McEliece scheme. 1 Keywords. Public Key Cryptosystem, Closest Vector Problem, Lattice Reduction, Trapdoor, McEliece 1 Introduction Since the invention of public key cryptography in 1976 by Di#e and Hellman [DH76] security of most cryptosystems is based on the (assumed) hardness of factoring or computing discrete logarithms. Only a few schemes based on other problems remain unbroken. Among which there is the McEliece scheme [St95] based on the computational di#culty of decoding a random code. It is still a challenge to develop new public key cryptosystem originating from the hardness of non number-theoretic problems. In a pioneer work Ajtai [A96] constructed an e#ciently computable function which is hard to invert on the average if the underlying lattice problem is intractable in th...