Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


38122.pdf (885.55 KB)

ETD Abstract Container

Abstract Header

The Singularity Attack on Himq-3: A High-Speed Signature Scheme Based on Multivariate Quadratic Equations

Zhang, Zheng
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623251333085284

Abstract Details

2021, PhD, University of Cincinnati, Arts and Sciences: Mathematical Sciences.
It has been known that the rapid development of large-scale quantum computers gives rise to threats to widely-deployed number theory based cryptography such as RSA, DSA, ECDH, etc. The goal of post-quantum cryptography is to develop cryptosystems that can resist quantum computer attacks. Multivariate public key cryptography is believed to be one of the choices for quantum-safe cryptography. At the end of 2017, 10 multivariate public key cryptosystems participated the round one of the National Institute of Standards and Technology (NIST) post-quantum standardization. The Himq-3 signature scheme proposed by Kyung-Ah Shim et al. is one of those NIST post-quantum standardization candidates. The Himq-3 signature scheme can be classified into the oil vinegar signature scheme family. Similar to the rainbow signature scheme, the Himq-3 signature scheme uses a multilayer structure to shorten the key size and the signature size. Moreover, the signing process is very fast due to a special system called L-invertible cycle system in its central map. The authors of the Himq-3 signature scheme claim that the scheme can resist all known attacks. The main result of this dissertation is a new attack method on the Himq-3 signature scheme. We will first discuss the urgency of post-quantum cryptography. Next multivariate public key cryptography will be introduced. We will also present some useful attacks on multivariate public key cryptography. Then the Himq-3 scheme will be described and the security against all known attacks will be analyzed. Afterward, we will show our new attack method called the singularity attack on the Himq-3 scheme and its variant Himq-3F. This new attack is based on the fact that some variables in the central map cannot be equal to zero in any valid signature. Based on this observation, we are able to filter out those linear combinations of variables that would be equal to zero for some signature, leaving the true ones we want provided that a large number of signatures are accessible. For the sake of completeness, we further illustrate step by step how variables and layers can be separated so that equivalent keys can be made. We will show that our attack achieves much lower complexity than the proposed levels of security. Furthermore, we will provide experimental results as evidence that our attack works indeed. Finally, we will discuss the advantages as well as the disadvantages of our attack in the conclusion, and we will state our future plans.
Jintai Ding, Ph.D. (Committee Chair)
Seungki Kim (Committee Member)
Benjamin Vaughan, Ph.D. (Committee Member)
123 p.
Mathematics
Post-quantum cryptography; Multivariate public key cryptography; Security analysis; Oil vinegar signature scheme

Recommended Citations

Citations

  • Zhang, Z. (2021). The Singularity Attack on Himq-3: A High-Speed Signature Scheme Based on Multivariate Quadratic Equations [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623251333085284

    APA Style (7th edition)

  • Zhang, Zheng. The Singularity Attack on Himq-3: A High-Speed Signature Scheme Based on Multivariate Quadratic Equations. 2021. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623251333085284.

    MLA Style (8th edition)

  • Zhang, Zheng. "The Singularity Attack on Himq-3: A High-Speed Signature Scheme Based on Multivariate Quadratic Equations." Doctoral dissertation, University of Cincinnati, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623251333085284

    Chicago Manual of Style (17th edition)

ucin1623251333085284
117
© 2021, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.