Efficient Certificate-Based Signature with Short Key and Signature Sizes from Lattices

Article type: Research Article

Authors: Tseng, Yuh-Min^{; *} | Tsai, Tung-Tso | Wu, Jui-Di | Huang, Sen-Shan

Affiliations: Department of Mathematics, National Changhua University of Education, Jin-De Campus, Chang-Hua City 500, Taiwan. E-mail: ymtseng@cc.ncue.edu.tw

Correspondence: [*] Corresponding author.

Abstract: Certificate-based cryptography (CB-PKC) is an attractive public key setting, which reduces the complexity of public key infrastructure in traditional public key settings and resolves the key escrow problem in ID-based public key settings. In the past, a large number of certificate-based signature and encryption schemes were proposed. Nevertheless, the security assumptions of these schemes are mainly relied on the difficulties of the discrete logarithm and factorization problems. Unfortunately, both problems will be resolved when quantum computers come true in the future. Public key cryptography from lattices is one of the important candidates for post-quantum cryptography. However, there is little work on certificate-based cryptography from lattices. In the paper, we propose a new and efficient certificate-based signature (CBS) scheme from lattices. Under the short integer solution (SIS) assumption from lattices, the proposed CBS scheme is shown to be existential unforgeability against adaptive chosen message attacks. Performance comparisons are made to demonstrate that the proposed CBS scheme from lattices is better than the previous lattice-based CBS scheme in terms of private key size and signature size.

Keywords: lattice, certificate-based signature, post-quantum cryptography, short integer solution

Journal: Informatica, vol. 30, no. 3, pp. 595-612, 2019