Quantum-resistant multivariate quadratic systems and digital signatures

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Turkey

Approval Date: 2019

Student: Esen Altundağ

Supervisor: MURAT CENK


In the light of technological advances, scientists expect that quantum computers will be generated and substitute with classical ones, then all symmetric and asymmetric (public-key) cryptosystems will be invalid in the near future. This causes the need for quantum-resistant algorithms all araund the world. That’s why, we have focused on multivariate public-key cryptosystems as a kind of post-quantum cryptography. In order to explain the root idea behind this kind of cryptosystems, as a starting point, the Matsumoto-Imai cryptosystem has been scrutinised together with its linearization equations attack. After that, we have constructed our own specific toy example for illustrating the construction of both the single-branch MatsumotoImai cryptosystem and its linearization equations attack. As well as these, Matsumoto-Imai variants which were developed with the aim of increasing the security of original one, have been examined. Then, it has been passed on to our main aim which is the analysis of the Multivariate Quadratic Digital Signature Scheme which comes from the family of multivariate public-key cryptosystems. In this process, its structural tools, security sources, parameter sets, general description, detailed description and security analysis have been studied. As a consequence of all these, we have realized that the security of Multivariate Quadratic Digital Signature Scheme against both classical and quantum computers is based on the intractability of the multivariate quadratic problem, the hardness of the commitment schemes which are the structural tools of this algorithm, the splitting idea of the secret-key that comes from the Sakumoto-Shirai-Hiwatari 5-pass Identification Scheme is a special kind of canonical 2n+ 1-pass identification schemes, and the Fiat-Shamir transform which maintains the security in the process of obtaining a signature scheme from an identification scheme. That is, it is possible to generate more secure and effective cryptographic protocols by improving the combination of these tools and ideas with the optimized parameter sets.