In citegb-issac we have introduced a new cryptosystem; it was called GB-NTRU, since initially we used Grobner bases to make the computations, but since eventually everything was made through Lagrange interpolation the name was inappropriate, and we name it now NTWO. This cryptosystem, from the public point of view, looks like NTRU, citeNTRU, (except the non secondary detail that multivariate polynomial algebra is used, instead of univariate algebra), but is different in key creation and decryption. As a consequence, while the message attacks are shared with NTRU, the key attacks are different; it is still possible to define a lattice like the Coppersmith-Shamir lattice, citeCS,NTRU, and breaking the private key via a SVP (shortest vector problem) in this lattice, but the metric on this lattice is heterogeneous: in some components the distance is Euclidean, in some other components the distance is Hamming. We study the SVP in this metric, and reduce the approximate solution of this problem to the approximate solution of the same problem in a larger lattice. The increased complexity of this heterogeneous SVP should allow shorter keys, and allow better protection of the message through bigger randomizing polynomials. The decoding of NTWO requires moreover the solution of a CVP (closest vector problem) in a private lattice; this lattice has a special form, being the sum of a constant sublattice qZn and a sublattice of very low dimension; we expect that specialized algorithms might exist for this kind of lattices, that might be better formalized as low dimension subspaces of (Z/q)n with a Lee metric; this is however work in progress, for which we can only provide the study of a few special cases.
Heterogeneous lattice metrics and the NTWO cryptosystem
CABOARA, MASSIMO;
2008-01-01
Abstract
In citegb-issac we have introduced a new cryptosystem; it was called GB-NTRU, since initially we used Grobner bases to make the computations, but since eventually everything was made through Lagrange interpolation the name was inappropriate, and we name it now NTWO. This cryptosystem, from the public point of view, looks like NTRU, citeNTRU, (except the non secondary detail that multivariate polynomial algebra is used, instead of univariate algebra), but is different in key creation and decryption. As a consequence, while the message attacks are shared with NTRU, the key attacks are different; it is still possible to define a lattice like the Coppersmith-Shamir lattice, citeCS,NTRU, and breaking the private key via a SVP (shortest vector problem) in this lattice, but the metric on this lattice is heterogeneous: in some components the distance is Euclidean, in some other components the distance is Hamming. We study the SVP in this metric, and reduce the approximate solution of this problem to the approximate solution of the same problem in a larger lattice. The increased complexity of this heterogeneous SVP should allow shorter keys, and allow better protection of the message through bigger randomizing polynomials. The decoding of NTWO requires moreover the solution of a CVP (closest vector problem) in a private lattice; this lattice has a special form, being the sum of a constant sublattice qZn and a sublattice of very low dimension; we expect that specialized algorithms might exist for this kind of lattices, that might be better formalized as low dimension subspaces of (Z/q)n with a Lee metric; this is however work in progress, for which we can only provide the study of a few special cases.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
