Project Topics
Get Complete Project Material File(s) Now! »
Complexity of Gröbner Basis Computation
Computing Gröbner basis is at least as hard as solving a system of polynomials. The worst case time complexity of Gröbner basis methods is known to be doubly exponential in the number of variables, even for quadratic systems [MM82]. This was achieved for a positive dimensional system where the complexity is precisely the 22n/10 , where n is the number of variables. However, in cryptography we deal with systems which are zero-dimensional. Hence we do not encounter such doubly exponential complexity of computing Gröbner basis. For instance, given a regular (see Definition 2.3.28) and square polynomial system with degrees (d1, . . . , dn) having only a finite number of roots, then computing its GRevLex Gröbner basis has a time complexity which is polynomial in Qn i di (the Bézout’s bound) [Laz83, FGHR13].Specifically for Degree reverse lexicographic ordering (GrevLex), the highest degree of the Gröbner basis elements is bounded by The Macaulay Bound: 1 + Xn i=1 (di − 1) .
Hybrid Combinatorial-Algebraic methods
In this section, we present two classical hybrid algorithms to solve the PoSSoq problem. The first method was proposed by Luk Bettale et al. [BFP09,BFP12] which mixes exhaustive search and Gröbner basis technique. The core idea is to fix a certain fraction of the variables. Thus given a system of m polynomial equation in Fq[x1, . . . , xn] over n variables, one fixes k < n variables to obtain m new polynomial equations over n − k variables. Now instead of computing one single Gröbner basis, one computes qk subsystems over n − k variables. Choosing an appropriate value of k, which gives us a gain in the complexity by computing Gröbner basis over a lesser number of variables allows us to overcome the loss of doing an exhaustive search. This is the main rationale of this approach.
Quantum Hybrid Approach
In similar lines to the combinatorial approaches, [HRSS16] derives a quantum variant of hybrid approach from [Bet11,BFP12] by explicitly using Grover’s algorithm [Gro96] to accelerate the exhaustive search over the fixed variables. However, they do not provide any asymptotic complexity of this approach. [FHK+17] goes a step further, firstly it builds a new (inspired) algorithm called QuantumBooleanSolve on top of the state-of-the-art BooleanSolve algorithm [BFSS13] and secondly, proposes an asymptotic complexity of QuantumBooleanSolve. This algorithm is different from the one proposed in [HRSS16]. In QuantumBooleanSolve, the authors instantiate a non-trivial quantum oracle which has a specific quantum circuit required for simplified Gröbner basis computation using Macaulay matrices. In this work, our main interest lies in the complexity of such algorithms and thus the algorithms themselves have been discussed. However, for more detailed working of the QuantumBooleanSolve we invite the reader to have a look at [FHK+17].
Theorem 2.4.6. [FHK+17, Theorem 1] There is a quantum algorithm which solves the MQ2 problem and requires:
• evaluation of O(20.47n) quantum gates for the deterministic variant.
• evaluation of expected O(20.462n) quantum gates for the probabilistic version.
This algorithm beats the Quantum exhaustive search (see 2.2) which is O(2n/2).
Example 2.4.7. Continuing with the same example as before, the deterministic QuantumBooleanSolve algorithm solve the system of equations requires the evaluation of at least ≈ 238 quantum gates, which is much faster than the Quantum exhaustive search which requires the evaluation of minimum 259 quantum gates.
Example 2.4.8. Let us again take the example of 90 quadratic equations over 80 variables in F2[x1, . . . , xn]. Using Grover’s approach along with hybrid Gröbner basis technique [BFP09], we can estimate that this process takes 259 arithmetic operations.
Multivariate Public-Key Cryptography
Multivariate Public-Key Cryptography (MPKC) is a subclass of asymmetric cryptography that deals with the cryptographic schemes whose hardness are based on the PoSSoq problem (see Section 2.1). MPKC is a very active area of research that culminated with the NIST Post-Quantum Cryptography standardization process [CCJ+16]. As mentioned previously in Chapter 1, it is one of the candidate areas for design of post-quantum cryptosystems. About 10% out of 69 submissions were multivariate. In the following section, we give an overview of the most prominent multivariate schemes.
Generic Modifications on MQ-schemes
In the previous sections, we presented a variety of trapdoors that have served as foundation for most of the multivariate cryptographic schemes that have been proposed in the recent past. However, most of these trapdoors suffer from some vulnerabilities. Fortunately, many modifications are available, which can be used along with these. The general goal of these modifiers is to protect the design of such trapdoors from some commonly known attacks against multivariate schemes, which we shall discuss in the following sections.
Minus Modifier: “−”
This modifier, which was first witnessed in [Sha93], removes polynomials from the public-keys. In general one fixes m′ = m−a where a ∈ N. The public-key is defined as the map P := π ◦ T ◦ F ◦ S where π : Fmq → Fm′ q denotes a projection function, S ∈ Affn(Fq), T ∈ Affm(Fq). The function π disregards the last a components of the output vector (T ◦ F ◦ S) ∈ Fmq.
The idea of introducing this modifier was a countermeasure against Patarin’s linearization attack [PGC98] on C∗. We discuss the linearization attack in Section 3.5. C∗ with the minus modifier, written as C∗−, was introduced by the name of Flash [PCG01a] in 2001. Flash along with a variant, named Sflash [PCG01a], were submitted to the European Nessie competition in 2001. The minus modifier was also seen as an answer to render the attacks [SK99,FJ03] against HFE useless. It is important to note that, for a multivariate encryption scheme, on one hand, application of minus modifier increases the security of the scheme, on the other hand, it makes the decryption process inefficient. Removing a polynomials requires guessing qa possible missing ciphertexts, where q is the size of the finite field over which the public-keys are defined. Once we have all the possible solutions, one requires pruning through this solution set. Hence for efficient decryption, a must be small.
For digital signatures, a can be much larger. However, one must have enough public-keys in order that the underlying PoSSoq for this instance is still hard. In general, the choice of a ≤ n/2 is efficient in practice. Unfortunately, even with the application of this modifier, C∗− and its variants have broken in [DFSS07, BFMR11,GM02]. Application of this modifier on HFE (HFE−) [PGC98] with some appropriate parameters renders the attacks of [SK99, FJ03] ineffective.
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
