Up to now, any attempt to use Gröbner bases in the design of public key cryptosystems has failed, as anticipated by a classical paper of B. Barkee et al.; we show why, and show-that the only residual hope is to use binomial ideals, i.e. lattices. We propose two lattice-based cryptosystems that will show the usefulness of multivariate polynomial algebra and Gröbner bases in the construction of public key cryptosystems. The first one tries to revive two cryptosystems Polly Cracker and GGH, that have been considered broken, through a hybrid; the second one improves a cryptosystem (NTRU) that only has heuristic and challenged evidence of security, providing evidence that the extension cannot be broken with some of the standard lattice tools that can be used to break some reduced form of NTRU. Because of the bounds on length, we only sketch the construction of these two cryptosystems, and leave many details of the construction of private and public keys, of the proofs and of the security considerations to forthcoming technical papers

Groebner basis for public key cryptograpy

CABOARA, MASSIMO;
2008-01-01

Abstract

Up to now, any attempt to use Gröbner bases in the design of public key cryptosystems has failed, as anticipated by a classical paper of B. Barkee et al.; we show why, and show-that the only residual hope is to use binomial ideals, i.e. lattices. We propose two lattice-based cryptosystems that will show the usefulness of multivariate polynomial algebra and Gröbner bases in the construction of public key cryptosystems. The first one tries to revive two cryptosystems Polly Cracker and GGH, that have been considered broken, through a hybrid; the second one improves a cryptosystem (NTRU) that only has heuristic and challenged evidence of security, providing evidence that the extension cannot be broken with some of the standard lattice tools that can be used to break some reduced form of NTRU. Because of the bounds on length, we only sketch the construction of these two cryptosystems, and leave many details of the construction of private and public keys, of the proofs and of the security considerations to forthcoming technical papers
2008
9781595939043
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/126734
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact