Author:

Abstract:

Deze thesis geeft een overzicht van het gebruik van stelsels vanmultivariate kwadratische veeltermen in publieke sleutelcryptografie.Inhet eerste hoofdstuk worden enkele cryptografische begrippengeintroduceerd. In het bijzonder wordt de noodzaak van publiekesleutelcryptografie en de alternatieve oplossing ervoor, d.z.w.,systemen die noch factorisatie (zoals RSA, Rivest-Shamir-Adleman) nochhet discrete logaritme gebruiken (zoals ECC, elliptischekrommecryptografie). Dit wordt gevolgd door een korte inleiding vaneindige lichamen en een algemene bespreking over systemen van stelselsvan multivariate kwadratische veeltermen en manieren om zevoortestellen. In deze context worden ook affiene transformaties en hunvoorstelling besproken. Nadat deze hulpmiddelen zijn geintroduceerd,worden zij gebruikt om aan te tonen hoe de stelsels van multivariatekwadratische veeltermen voor handtekening- en encryptietoepassingenkunnen worden gebruikt. Bovendien wordt het probleem van uitkwadratische veeltermen bestaande stelsels van vergelijkingen inperspectief gezet en er wordt een verbinding gelegd met de theorie vanNP-Volledigheid. Het tweede hoofdstuk besluit met een discussie over detwee verwante problemen isomorfismen van veeltermen en minimale rangvan de som van matrices. Beide blijken nuttig te zijn voor decryptanalyse van systemen gebaseerd op stelsels van multivariatekwadratische veeltermen.Het belangrijkste deel van deze thesis gaat over concrete valkuilenvoor het probleem van publieke sleutelsystemen die gebaseerd zijn opstelsels van multivariate kwadratische veeltermen. We kunnen aantonendat al dergelijke systemen in een van de volgende vier klassen vallen:uit evenwicht gebrachte olie- en azijn-systemen (UOV), trapsgewijzedriehoekige systemen (STS), Matsumoto-Imai schema A (MIA), en verborgenlichaamsverglijkingen (HFE). Voorts tonen we het gebruik vanverscheidene wijzigingen aan. Om de veiligheid van deze vierbasis-valkuilen en hun wijzigingen te evalueren, herzien we sommigecryptanalytische resultaten. In het bijzonder kunnen we onze eigenbijdragen op dit gebied ontwikkelen door twee aanvallen tegen UOV aante tonen, namelijk een benaderingsaanval en een aanval dieGroebnerbasis berekeningen gebruikt. Voorts leidden we eensleutelterug-win en een inversie-aanval tegen de klasse STS af. Gebruikmakend van onze kennis over HFE, ontwikkeln we twee veiligeversiesvan het Quartz handtekeningsschema. Een ander belangrijk deel van dezethesis is de studie van de sleutelruimte van publiekesleutelcryptografie gebaseerd op stelsels van multivariate kwadratischeveeltermen.Gebruikmakend van speciale klassen van affiene transformaties, diewe``onderhouders" noemen, kunnen we aantonen dat alle vier debasisklassen wat redundantie in hun sleutelruimte hebben en dus eenkleinere sleutelruimte bevatten dan eerder verwacht. In het bijzonderblijkt deze reductie voor UOV en de STS klasse vrij dramatisch. VoorHFE en MIA vinden we slechts enkele minder belangrijke reduntanties.Voorts kunnen we aantonen dat onze resultaten voor MIA de enigemogelijke zijn, d.z.w., zijn er geen andere redundanties dan degene diewe in deze thesis beschrijven. Bovendien breiden we onze resultaten totverscheidenebelangrijke variaties van HFE en MIA uit, namelijkHFE-, HFEv, HFEv-, en MIA-. Deze zijn in de praktijk gebruikt voor debouw van handtekeningsschema's, namelijk Quartz, Flash en Sflash.Om de praktische relevantie van de bouw van systemen gebaseerd opstelsels van multivariate kwadratische veeltermen en ook van onzeclassificatie aan te tonen, geven we enkele concrete voorbeelden. Inhet bijzonder behandelen we de NESSIE inzendingen, Flash, Sflash enQuartz en bespreken we hun voor- en nadelen. Voorts beschrijven we watmeer recente ontwikkelingen, namelijk op STS-gebaseerde ``verbeterdeTTS", ``Handelbare Rationele Transformaties", en Regenboog. Vervolgensbegeven we ons naar de toepassingsgebieden van publiekesleutelcryptografie systemen gebaseerd op stelsels van multivariatekwadratische veeltermen. In het bijzonder behandelen we toepassingen ophet gebied van product-activeringssleutels, elektronische postzegels ensnelle eenrichtingsfuncties. Ten slotte stellen we enkele nieuweschema's voor. In het bijzonder geven we een generalisatie van MIA vooroneven karakteristiek, en onderzoeken we ook andere valkuilen zoals STSen UOV met vertakking- en homogenisatieaanpassers. Al met al, gelovenwe dat de uit stelsels van multivariate kwadratische veeltermenbestaande systemen een zeer praktische oplossing geven voor hetprobleem van publieke sleutelcryptografie. Momenteel is het nietmogelijk om ze voor encryptie te gebruiken. Nochtans zijn we zeker dathet mogelijk zal zijn om dit probleem te overwinnen, en om de stelselsvan multivariate kwadratische veeltermen te gebruiken voor zowelencryptie als voor het zetten van handtekeningen.