ITEM METADATA RECORD
Title: Multivariate Quadratic Polynomials in Public Key Cryptography (Stelsels van multivariate kwadratische veeltermen in publieke sleutelcryptografie)
Other Titles: Multivariate Quadratic Polynomials in Public Key Cryptography
Authors: Wolf, Christopher; M0333295
Issue Date: 4-Nov-2005
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.
Table of Contents: Ph.D. Thesis
Multivariate Quadratic Polynomials in Public Key Cryptography
Christopher Wolf (chris@Christopher-Wolf.de)
November 2005
K.U.Leuven, Belgium

1 Introduction
1.1 Cryptology
1.1.1 The Caesar Cipher
1.1.2 One-Time Pad
1.1.3 Modern Cryptology
1.2 Motivation
1.3 Related Work
1.4 Achievement
1.5 Outline

2 The General MQ-construction
2.1 Finite Fields
2.2 Multivariate Polynomial Equations
2.2.1 General Multivariate Polynomial Equations
2.2.2 Multivariate Quadratic Polynomials
2.2.3 Affine Transformations
2.2.4 Matrix Representation
2.3 MQ-trapdoor
2.3.1 Signature Verification
2.3.2 Signature Generation
2.3.3 Decryption
2.3.4 Encryption
2.4 Univariate and Multivariate Representations
2.5 N P-Completeness of MQ
2.5.1 MQ over GF(2)
2.5.2 MQ over Domains
2.5.3 Discussion
2.6 Related Problems
2.6.1 Isomorphism of Polynomials
2.6.2 MinRank

3 Constructions for MQ-trapdoors
3.1 Basic Trapdoors
3.1.1 Unbalanced Oil and Vinegar Schemes: UOV
3.1.2 Stepwise Triangular Systems: STS
3.1.3 Matsumoto-Imai Scheme A: MIA
3.1.4 Hidden Field Equations: HFE
3.1.5 Taxonomy and Discussion
3.2 Generic Modification on MQ-schemes
3.2.1 Minus method: "-"
3.2.2 Plus method: "+"
3.2.3 Subfield method: "/"
3.2.4 Branching: "_|_"
3.2.5 Fixing: "f"
3.2.6 Sparse Polynomials: "s"
3.2.7 Vinegar Variables: "v"
3.2.8 Internal Perturbation: "i"
3.2.9 Homogenising: "h"
3.2.10 Masking: "m"
3.3 Discussion

4 Cryptanalysis of MQ-schemes
4.1 Types of Attacks
4.2 Generic Linearisation Attack
4.3 Cryptanalysis of UOV
4.3.1 The Kipnis and Shamir Attack
4.3.2 Attacks using Gr"obner Basis Algorithms
4.3.3 Exploiting the Existence of Affine Subspaces
4.3.4 Discussion
4.4 Cryptanalysis of STS
4.4.1 Chain of Kernels
4.4.2 Recovering the Transformation T
4.4.3 Inversion Attack
4.4.4 Key Recovery Attack
4.4.5 Special Instances of STS
4.4.6 Discussion
4.5 Attacks against MIA
4.6 Attacks against HFE
4.6.1 Kipnis-Shamir: Recover the Private Key
4.6.2 Faug`ere: Fast Gr"obner Bases
4.6.3 Variations of HFE
4.7 Discussion

5 Equivalent Keys
5.1 Initial Considerations
5.2 Sustaining Transformations
5.2.1 Additive Sustainer
5.2.2 Big Sustainer
5.2.3 Small Sustainer
5.2.4 Permutation Sustainer
5.2.5 Gauss Sustainer
5.2.6 Frobenius Sustainer
5.2.7 Reduction Sustainer
5.3 Application to Multivariate Quadratic Schemes
5.3.1 Hidden Field Equations
5.3.2 Matsumoto-Imai Scheme A
5.3.3 Unbalanced Oil and Vinegar Schemes
5.3.4 Stepwise-Triangular Systems
5.4 Tightness for MIA and MIO
5.5 Discussion

6 Interesting Variants
6.1 NESSIE Contributions
6.1.1 Flash / Sflash
6.1.2 Quartz
6.2 Mixed Schemes
6.2.1 Enhanced TTS
6.2.2 Tractable Signature Schemes
6.2.3 Rainbow
6.2.4 Discussion
6.3 Applications
6.3.1 Electronic Stamps
6.3.2 Product Activation Keys
6.3.3 Fast One-Way functions
6.4 New Schemes and Open Questions
6.4.1 MIO
6.4.2 STS_|_h
6.4.3 UOV_|_h
6.5 Discussion

7 Conclusions
URI: 
Publication status: published
KU Leuven publication type: TH
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics

Files in This Item:
File Description Status SizeFormat
thesis.pdf Published 1053KbAdobe PDFView/Open

 


All items in Lirias are protected by copyright, with all rights reserved.