@inproceedings{e3f62eb5174448f2851a4ff72424a5c5,
title = "Algebraic cryptanalysis of yasuda, takagi and sakurai{\textquoteright}s signature scheme",
abstract = "Recently Yasuda, Takagi and Sakurai proposed a new and interesting signature scheme from the classification of quadratic forms over finite fields of odd characteristic published in PQCrypto 2013. In this paper we propose two algebraic attacks to their scheme using only linear algebra. Both attacks are motivated by Kipnis and Shamir{\textquoteright}s attack to the oil-vinegar signature scheme. Namely we first turn the original problem to a geometric problem and then apply the theory of invariant subspace intensively. We show that Yasuda, Takagi and Sakurai{\textquoteright}s scheme can be broken by our attacks with complexity O\{formal presented\} where m is the number of variables and q is the size of the base field. Here d is expected generally to be 1 and is confirmed in our tests. We also compare our attacks with Y. Hashimoto{\textquoteright}s attack which is just published in PQCrypto 2014.",
keywords = "Multivariate public key cryptosystem, Post-quantum cryptography, Quadratic form",
author = "Wenbin Zhang and Tan, \{Chik How\}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 17th International Conference on Information Security and Cryptology, ICISC 2014 ; Conference date: 03-12-2014 Through 05-12-2014",
year = "2014",
doi = "10.1007/978-3-319-15943-0\_4",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "53--66",
editor = "Jongsung Kim and Jooyoung Lee",
booktitle = "Information Security and Cryptology - ICISC 2014 - 17th International Conference, Revised Selected Papers",
}