Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


43016.pdf (784.31 KB)

ETD Abstract Container

Abstract Header

A Cryptanalysis of Lifted Underdetermined Multivariate Cryptosystems

Deaton, Joshua
http://orcid.org/0000-0002-2967-7547
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1659531924342305

Abstract Details

2022, PhD, University of Cincinnati, Arts and Sciences: Mathematical Sciences.
In this digital age, well tested public-key cryptography is vital for the continuing function of society. An example of one of the uses of cryptography is signature schemes which allow us to digitally sign a document. However, quantum computers utilizing Shor’s algorithm threaten the security of all the cryptosystem currently in use. What is needed is post-quantum cryptography: classical cryptographic algorithms able to resist quantum attacks. In 2016, NIST put out a call for proposals for post-quantum cryptosystems for standardization. We are currently in the third round of the “competition,” with many different types of schemes being proposed. In 2017, Ward Beullens et al. submitted the Lifted Unbalanced Oil and Vinegar signature scheme to the NIST competition, which is a modification to the Unbalanced Oil and Vinegar Scheme by Patarin. The main modification is called lifting, which is to take a polynomial over a small finite field and view it as a map over some extension field. LUOV made it into the second round of the competition, but two attacks by Ding et al. showed a flaw in the modifications of LUOV. The first attack was the Subfield Differential Attack (SDA) which prompted a change of parameters by the authors of LUOV. The second was the Nested Subset Differential Attack (NSDA), which broke half of the parameters put forward by the authors of LUOV again. Due to the strengths of these attacks and the possibility stronger ones of a similar nature exist, LUOV did not go into the third round. This dissertation shows that such a stronger attack, which will be called NSDA+, is possible. All three of the attacks SDA, NSDA, and NSDA+ are straightforward but powerful in application against the lifting modification. First in chapter 1, we will discuss what is a public key cryptosystem by looking at the original definition of Diffie and Hellman. Then we will talk of the NIST Post-Quantum Standardization Process. Following that, in chapter 2 the basics of Multivariate cryptography will be explained including the most common method which we will use to solve multivariate equations, the XL algorithm. In chapter 3, we will look at our first example of a Multivariate cryptosystem which is also one of the most important historically: the Matsumoto-Imai cryptosystem. After describing the Linearization attack, which is both what defeated Matsumoto-Imai and was the inspiration to Unbalanced Oil and Vinegar, we will have a quick discussion of the cryptosystem HFEv- as it can be thought of as a generalization of the Matsumoto-imai cryptosystem which resists said Linearization attack. In chapter 4 we will discuss the Unbalanced Oil and Vinegar cryptosystem, which again is what LUOV is a modification of. We will look at the Kipnis-Shamir Invariant Subspace attack, the Reconciliation attack, and the Intersection attack. We then will briefly define LUOV itself as well as the cryptosystem Rainbow as it was the last Multivariate cryptosystem left in the NIST competition in round 3 though it did not make it into round 4. Then in chapter 5 we will look at SDA, NSDA, and NSDA+ in turn.
Jintai Ding, Ph.D. (Committee Member)
Seungki Kim, Ph.D. (Committee Member)
Robert Buckingham, Ph.D. (Committee Member)
110 p.
Mathematics
Cryptanalysis; Multivariate; Cryptography; Post-Quantum; Solving System of Polynomial Equations; Mathematics

Recommended Citations

Citations

  • Deaton, J. (2022). A Cryptanalysis of Lifted Underdetermined Multivariate Cryptosystems [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1659531924342305

    APA Style (7th edition)

  • Deaton, Joshua. A Cryptanalysis of Lifted Underdetermined Multivariate Cryptosystems. 2022. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1659531924342305.

    MLA Style (8th edition)

  • Deaton, Joshua. "A Cryptanalysis of Lifted Underdetermined Multivariate Cryptosystems." Doctoral dissertation, University of Cincinnati, 2022. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1659531924342305

    Chicago Manual of Style (17th edition)

ucin1659531924342305
189
© 2022, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.