A Signature Scheme Based on the Syndrome Decoding Problem Using LDPC Codes
Toshiki Tsuchida, Masanori Hirotomo, Haruka Ito, Makoto Takita, Yoshiaki Shiraishi, Kenta Nomura, Masami Mohri, Youji Fukuta, Masakatu Morii · 2019
The security of widely used authentication and signature schemes is based on the difficulty of the discrete logarithm problem and the prime factorization problem. A quantum computer might solve these problems in probabilistic polynomial time. In other words, if a quantum computer is realized, these schemes are expected to eventually become vulnerable. In preparation for the development of a quantum computer, research on post-quantum cryptography is in progress. In addition, authentication and signature schemes using the post-quantum cryptography are also studied. Generally, authentication and signature schemes based on the public key cryptography have the large computational complexity. A zero-knowledge authentication scheme based on the syndrome decoding problem was proposed as a post-quantum authentication scheme. We have proposed the smaller computational complexity authentication scheme by using LDPC codes. This paper presents a post-quantum signature scheme which is constructed from the authentication scheme by Fiat-Shamir transformation.