Complexity of Gröbner Basis Computation

For more info about our services contact : help@bestpfe.com

Table of contents

List of Figures
List of Tables
1 Introduction
1.1 Organization and Contributions of the thesis
1.2 Publications
I Preliminaries
2 Polynomial System Solving
2.1 General Framework
2.2 Combinatorial Methods
2.2.1 Classical Setting
2.2.2 Quantum Setting
2.3 Gröbner Basis
2.3.1 Preliminary Definitions and Properties
2.3.2 Gröbner Basis Algorithms
2.3.3 Complexity of Gröbner Basis Computation
2.4 Hybrid Combinatorial-Algebraic methods
2.4.1 Classical Hybrid Algorithms
2.4.2 Quantum Hybrid Approach
2.5 Conclusion
3 Quantum-Safe Public-key Cryptography
3.1 Multivariate Public-Key Cryptography
3.1.1 General Structure
3.1.2 Historical Cryptosystems
3.1.3 Generic Modifications on MQ-schemes
3.1.4 EFC Scheme
3.2 Standard attacks on MPKCs
3.2.1 Key Recovery Attacks
3.2.2 Message Recovery Attacks
3.3 Lattice Based Cryptosystems
3.3.1 Frodo Key Exchange
II Contribution
4 Cryptanalysis of EFC Cryptosystem
4.1 Introduction
4.1.1 Main Results and Organization
4.2 Algebraic Cryptanalysis of EFC
4.2.1 A Key Recovery Attack
4.2.2 A Message Recovery Attack
4.2.3 Lower Degree of Regularity
4.2.4 Analysis of the EFCq(0) and EFCFq (0) instances
4.2.5 Extending to EFC−q (a)
4.2.6 Analysis on the case EFC− 2 (1)
4.2.7 Analysis on the case EFC− 2 (2)
4.2.8 Analysis on the case EFC− 3 (1) and EFC− 3 (2)
4.3 A Method to Find Degree Fall Equations
4.3.1 An improvement on the method
4.4 Are the Degree Fall Equations Useful?
4.5 Experimental Results and Observations
4.5.1 Attack on Challenge Parameters
4.6 Conclusion
5 Solving Polynomials with Noise
5.1 Motivation
5.2 Hardness of the PoSSoWN Problem
5.2.1 Hardness of PoSSoWN: The Linear Case
5.2.2 Hardness of PoSSoWN: The Non-Linear Case
5.3 Algorithms to Solve PoSSoWN
5.3.1 Arora-Ge Gröbner Basis Method
5.3.2 Arora-Ge Method with Linearization
5.3.3 Exhaustive Search
5.3.4 Max-PoSSo Gröbner Basis Attack
5.4 Conclusion
6 CFPKM: A Submission to NIST
6.1 Background
6.2 Passively Secure KEM
6.2.1 Parameter Space
6.2.2 Construction
6.2.3 Correctness
6.2.4 Failure Rate
6.3 Analysis of Attacks Considered in Submission
6.3.1 Arora-Ge Gröbner Basis Method
6.3.2 Exhaustive Search
6.3.3 Hybrid Attacks
6.4 Detailed Performance Analysis
6.4.1 Time
6.4.2 Space
6.4.3 How parameters affect performance
6.5 Advantages and Limitations
6.6 Why the Scheme Failed
6.7 Can This Issue be Resolved?
6.8 Conclusion
Bibliography