Crittosistemi Polly Cracker

Lo scopo della trattazione è lo studio di una famiglia di crittosistemi a chiave pubblica, i crittosistemi Polly Cracker, il cui funzionamento è basato sulla teoria delle basi di Groebner. Il dibattito sui crittosistemi Polly Cracker ha inizio nel 1994 con la pubblicazione di due articoli (Barkee e altri; Fellows e Koblitz) in cui viene discussa la possibilità di utilizzare il calcolo di una base di Groebner di un ideale come problema "difficile" su cui basare la sicurezza di un crittosistema a chiave pubblica. Fin da subito appare chiaro che i crittosistemi Polly Cracker risultano vulnerabili a svariati attacchi, molti dei quali mirano a ricostruire la fase di codifica sfruttando l'interdipendenza tra chiave pubblica e messaggio cifrato che caratterizza tali crittosistemi. Nonostante ciò, sono state proposte numerose varianti, alcune delle quali particolarmente interessanti, per rendere sicuro uno schema del tipo Polly Cracker. Attualmente, tuttavia, quasi tutti i crittosistemi Polly Cracker sono stati forzati. Un'importante eccezione è rappresentata dal crittosistema Lattice Polly Cracker, che sfrutta le proprietà degli ideali binomiali e dei reticoli interi ad essi associati. E' però possibile dimostrare che la sicurezza del Lattice Polly Cracker, a differenza degli altri crittosistemi che illustriamo nella presente trattazione, non è collegata alla difficoltà del calcolo di una base di Groebner.