1. Home
  2. Issues
  3. Volume 30, Issue 3 (2019)
  4. Efficient Certificate-Based Signature wi ...

Informatica


Efficient Certificate-Based Signature with Short Key and Signature Sizes from Lattices
Volume 30, Issue 3 (2019), pp. 595–612
Pub. online: 1 January 2019      Type: Research Article      Open accessOpen Access
Received
1 May 2018
Accepted
1 March 2019
Published
1 January 2019

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.

References

 
Ajtai, M. (1996). Generating hard instances of lattice problems. In: Proceedings of STOC’96. ACM, pp. 99–108.
 
Al-Riyami, S.S., Paterson, K.G. (2003). Certificateless public key cryptography. In: Proceedings of ASIACRYPT’03, LNCS, Vol. 2894, pp. 452–473.
 
Bernstein, D.J. (2009). Introduction to post-quantum cryptography. In: Post-Quantum Cryptography. Springer-Verlag, Berlin, Germany, pp. 1–14.
 
Boneh, D., Franklin, M. (2001). Identity-based encryption from the Weil pairing. In: Proceedings of CRYPTO’01, LNCS, Vol. 2139, pp. 213–229.
 
Ducas, L., Lyubashevsky, V., Prest, T. (2014). Efficient identity-based encryption over NTRU lattices. In: Proceedings of ASIACRYPT’14, LNCS, Vol. 8874, pp. 22–41.
 
ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4), 469–472.
 
Galindo, D., Morillo, P., Rafols, C. (2008). Improved certificate-based encryption in the standard model. Journal of Systems and Software, 81(7), 1218–1226.
 
Gao, W., Wang, G., Wang, X., Chen, K. (2015). Generic construction of certificate-based encryption from certificateless encryption revisited. The Computer Journal, 58(10), 2747–2757.
 
Gentry, C. (2003). Certificate-based encryption and the certificate revocation problem. In: Proceedings of EURORYPT’03, LNCS, Vol. 2656, pp. 272–293.
 
Gentry, C., Peikert, C., Vaikuntanathan, V. (2008). How to use a short basis: trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC’08. ACM, pp. 197–206.
 
Goldreich, O., Goldwasser, S., Halevi, S. (1997). Public-key cryptosystems from lattice reduction problems. In: Proceedings of CRYPTO’97, LNCS, Vol. 1294, pp. 112–131.
 
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J., Whyte, W. (2003). Ntrusign: digital signatures using the ntru lattice. In: Proceedings of CT-RSA’03, LNCS, Vol. 2612, pp. 122–140.
 
Hung, Y.H., Huang, S.S., Tseng, Y.M. (2016a). A short certificate-based signature scheme with provable security. Information Technology and Control, 45(3), 243–253.
 
Hung, Y.H., Tseng, Y.M., Huang, S.S. (2016b). A revocable certificateless short signature scheme and its authentication application. Informatica, 27(3), 549–572.
 
Hung, Y.H., Tseng, Y.M., Huang, S.S. (2017a). Revocable ID-based signature with short size over lattices. Security and Communication Networks. Article ID-7571201.
 
Hung, Y.H., Tseng, Y.M., Huang, S.S. (2017b). Lattice-based revocable certificateless signature. Symmetry, 9. Article ID-242.
 
Li, J., Huang, X., Mu, Y., Susilo, W., Wu, Q. (2007). Certificate-based signature: security model and efficient construction. In: Proceedings of EUROPKI’07, LNCS, Vol. 4582, pp. 110–125.
 
Li, J., Huang, X., Zhang, Y., Xu, L. (2012). An efficient short certificate-based signature scheme. Journal of Systems and Software, 85(2), 314–322.
 
Liu, Z.H., Hu, Y.P., Zhang, X.S., Li, F. (2013). Efficient and strongly unforgeable identity-based signature scheme over lattices in the standard model. Security and Communication Networks, 6(1), 69–77.
 
Lu, Y., Li, J. (2014). Efficient certificate-based encryption scheme secure against key replacement attacks in the standard model. Journal of Information Science and Engineering, 30(5), 1553–1568.
 
Lyubashevsky, V. (2009). Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Proceedings of ASIACRYPT’09, LNCS, Vol. 5912, pp. 598–616.
 
Lyubashevsky, V. (2012). Lattice signatures without trapdoors. In: Proceedings of EUROCRYPT’12, LNCS, Vol. 7237, pp. 738–755.
 
Micciancio, D., Regev, O. (2007). Worst-case to average-case reductions based on Gaussian measure. SIAM Journal on Computing, 37(1), 267–302.
 
Pointcheval, D., Stern, J. (2000). Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13, 361–396.
 
Rivest, R.L., Shamir, A., Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126.
 
Ruckert, M. (2010). Strongly unforgeable signatures and hierarchical identity-based signatures over lattices without random oracles. In: Proceedings of PQC’10, LNCS, Vol. 6061, pp. 182–200.
 
Shamir, A. (1984). Identity-based cryptosystems and signature schemes. In: Proceedings of Crypto’84, LNCS, Vol. 196, pp. 47–53.
 
Shor, P.W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509.
 
Stehle, D., Steinfeld, R. (2013). Making NTRUEnrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices. Cryptology ePrint Archive, Report 2013/4. Available source file from http://eprint.iacr.org/2013/004.
 
Tian, M., Huang, L. (2014). Efficient identity-based signature over lattices. In: Proceedings of SEC’14, IFIP, Vol. 428, pp. 321–329.
 
Tian, M., Huang, L. (2015). Certificateless and certificate-based signatures from lattices. Security and Communication Networks, 8(8), 1575–1586.
 
Tsai, T.T., Tseng, Y.M. (2015). Revocable certificateless public key encryption. IEEE Systems Journal, 9(3), 824–833.
 
Tsai, T.T., Huang, S.S., Tseng, Y.M. (2017). SIBSC: separable identity-based signcryption for resource-constrained devices. Informatica, 28(1), 193–214.
 
Tseng, Y.M., Tsai, T.T. (2012). Efficient revocable ID-based encryption with a public channel. The Computer Journal, 55(4), 475–486.
 
Tseng, Y.M., Huang, S.S., Tsai, T.T., Ke, J.H. (2016). List-free ID-based mutual authentication and key agreement protocol for multi-server architectures. IEEE Transactions on Emerging Topics in Computing, 4(1), 102–122.
 
Tseng, Y.M., Tsai, T.T., Huang, S.S., Huang, C.P. (2018). Identity-based encryption with cloud revocation authority and its applications. IEEE Transactions on Cloud Computing, 6(4), 1041–1053.
 
Wu, W., Mu, Y., Susilo, W., Huang, X. (2009). Certificate-based signatures revisited. Journal of Universal Computer Science, 15(8), 1659–1684.
 
Wu, J.D., Tseng, Y.M., Huang, S.S., Chou, W.C. (2018). Leakage-resilient certificateless key encapsulation scheme. Informatica, 29(1), 125–155.
 
Xiang, X. (2015). Adaptive secure revocable identity-based signature scheme over lattices. Computer Engineering, 41(10), 126–129.

Biographies

Tseng Yuh-Min
ymtseng@cc.ncue.edu.tw

Y.-M. Tseng is currently a professor in the Department of Mathematics, National Changhua University of Education, Taiwan. He is a member of IEEE Computer Society, IEEE Communications Society and the Chinese Cryptology and Information Security Association (CCISA). He has published over one hundred scientific journal and conference papers on various research areas of cryptography, security and computer network. His research interests include cryptography, network security, computer networks and mobile communications. He serves as an editor of several international journals.

Tsai Tung-Tso

T.-T. Tsai is currently a senior engineer in HON HAI Technology Group, Taiwan. His research interests include applied cryptography and pairing-based cryptography. He received the PhD degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2014 under the Professor Yuh-Min Tseng.

Wu Jui-Di

J.-D. Wu received the BS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2006. He received the MS degree from the Department of Mathematics, National Changhua University of Education, Taiwan, in 2008. He is currently a PhD candidate in the Department of Mathematics, National Changhua University of Education, Taiwan. His research interests include applied cryptography and pairing-based cryptography.

HUANG Sen-Shan

S.-S. Huang is currently a professor in the Department of Mathematics, National Changhua University of Education, Taiwan. His research interests include number theory, cryptography, and network security. He received his PhD from the University of Illinois at Urbana-Champaign in 1997 under the supervision of professor Bruce C. Berndt.


Full article Related articles Cited by PDF XML
Full article Related articles Cited by PDF XML

Copyright
© 2019 Vilnius University
Open access article under the CC BY license.

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

Funding
This research was partially supported by Ministry of Science and Technology, Taiwan, under contract no. MOST106-2221-E-018-007-MY2.

Metrics
since January 2020
1060

Article info
views

 714

Full article
views
608

PDF
downloads

 214

XML
downloads


Share


RSS